Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 10, Coordenação entre Tarefas - Coggle Diagram
Capítulo 10
Gabriel Bérti - 2127938
Luis Felipe Moro Coelho - 2128020
Coordenação entre Tarefas
O problema da Concorrência:
Quando duas ou mais tarefas acessam simultaneamente um recurso compartilhado, podem ocorrer problemas de consistência dos dados ou do estado do recurso acessado.
Aplicação Concorrente:
Caso dois clientes em terminais diferentes tentem depositar valores na mesma conta ao mesmo tempo, existirão duas tarefas
t1
e
t2
acessando os dados da conta de forma concorrente.
Condições de disputa:
Os erros e inconsistências gerados por acessos concorrentes a dados compartilhados são denominados
condições de disputa
, ou condições de corrida (do inglês
race conditions
)
Em sistemas monoprocessados, a sobreposição pode acontecer caso ocorram trocas de contexto durante a execução da função
depositar
. Em sistemas multiprocessados a situação é mais complexa, pois cada tarefa poderá estar executando em um processador distinto.
É importante observar que condições de disputa são erros
dinâmicos
, ou seja, erros que não aparecem no código fonte e que só se manifestam durante a execução. Assim, são dificilmente detectáveis através da simples análise do código fonte. Além disso, erros dessa natureza não se manifestam a cada execução, mas apenas quando certos entrelaçamentos ocorrerem.
Assim, uma condição de disputa poderá permanecer latente no código durante anos, ou mesmo nunca se manifestar.
Condições de Bernstein:
Condições de disputa entre tarefas paralelas podem ser formalizadas através das chamadas
condições de Bernstein
.
Dadas duas tarefas
t1
e
t2
, sendo
R(ti)
o conjunto de variáveis lidas por
ti
e
W(ti)
o conjunto de variáveis escritas por
ti
, essas tarefas podem executar em paralelo sem risco de condição de disputa
(t1 || t2)
se e somente se as seguintes condições forem atendidas:
Olhar imagem Capítulo 10 - Pg. 115 no livro e Pg. 04 no PDF
Outro ponto importante evidenciado pelas condições de Bernstein é que as condições de disputa somente ocorrem se pelo menos uma das operações envolvidas for de escrita.
Seções Críticas:
Os trechos de código que acessam dados compartilhados em cada tarefa são denominados
seções críticas
.
De modo geral, seções críticas são todos os trechos de código que manipulam dados compartilhados onde podem ocorrer condições de disputa. Um programa pode ter várias seções críticas, relacionadas entre si ou não (caso manipulem dados compartilhados distintos).
Exclusão Mútua:
Dado um conjunto de regiões críticas relacionadas, apenas uma tarefa pode estar em sua seção crítica a cada instante, excluindo o acesso das demais às suas respectivas regiões críticas. Essa propriedade é conhecida como
exclusão mútua.
Diversos mecanismos podem ser definidos para garantir a exclusão mútua impedindo o entrelaçamento de seções críticas. Todos eles exigem que o programador defina os limites (início e o final) de cada seção crítica.
Dada uma seção crítica
csi
podem ser definidas as primitivas
enter(csi)
, para que uma tarefa indique sua intenção de entrar na seção crítica
csi
, e
leave(csi)
, para que uma tarefa que está na seção crítica
csi
informe que está saindo da mesma.
A primitiva
enter(csi)
é bloqueante: caso uma tarefa já esteja
ocupando a seção crítica
csi,
as demais tarefas que tentarem entrar deverão aguardar até que a primeira libere
csi
através da primitiva
leave(csi).
As soluções propostas devem atender a alguns critérios básicos enumerados a seguir:
Exclusão mútua:
Somente uma tarefa pode estar dentro da seção crítica em cada instante.
Espera limitada:
Uma tarefa que aguarda acesso a uma seção crítica deve ter esse acesso garantido em um tempo finito, ou seja, não pode haver inanição.
Independência de outras tarefas:
A decisão sobre o uso de uma seção crítica deve depender somente das tarefas que estão tentando entrar na mesma. Outras tarefas, que no momento não estejam interessadas em entrar na região crítica, não podem influenciar sobre essa decisão.
Independência de fatores físicos:
A solução deve ser puramente lógica e não depender da velocidade de execução das tarefas, de temporizações, do número de processadores no sistema ou de outros fatores físicos.
Inibição de Interrupções:
Uma solução simples para a implementação da exclusão mútua consiste em impedir as trocas de contexto dentro da seção crítica. Ao entrar em uma seção crítica, a tarefa desativa as interrupções que possam provocar trocas de contexto, e as reativa ao sair da seção crítica.
Apesar de simples, essa solução raramente é usada para a construção de aplicações devido a
vários problemas
:
Ao desligar as interrupções, a preempção por tempo ou por recursos deixa de funcionar;
Enquanto as interrupções estão desativadas, os dispositivos de entrada/saída deixam de ser atendidos pelo núcleo, o que pode causar perdas de dados ou outros problemas;
A tarefa que está na seção crítica não pode realizar operações de entrada/saída, pois os dispositivos não irão responder.
Esta solução só funciona em sistemas monoprocessados.
Somente utilizada em algumas seções críticas dentro do núcleo do sistema operacional.
Solução Trivial
: Uma solução trivial para o problema da seção crítica consiste em usar uma variável
busy
para indicar se a seção crítica está livre ou ocupada.
Infelizmente,
essa solução simples não funciona!
Seu grande defeito é que o teste da variável
busy
e sua atribuição são feitos em momentos distintos.
Em outras palavras, a implementação forma uma seção crítica que também deve ser protegida.
Alternância de Uso:
Outra solução simples para a implementação da exclusão mútua consiste em definir uma variável
turno
, que indica de quem é a vez de entrar na seção crítica.
Essa variável deve ser ajustada cada vez que uma tarefa sai da seção crítica, para indicar a próxima tarefa a usá-la.
Essa abordagem garante a exclusão mútua entre as tarefas e independe de fatores externos, mas não atende os demais critérios:
Caso uma tarefa
ti
não deseje usar a seção crítica, todas as tarefas
tj
com
j > i
ficarão impedidas de fazê-lo, pois a variável
turno
não irá evoluir.
Algoritmo de Peterson:
Os algoritmos de Dekker e de Peterson foram desenvolvidos para garantir a exclusão mútua entre
duas tarefas
, garantindo também o critério de espera limitada.
Operações Atômicas:
Para resolver esse problema (variável
busy
), projetistas de hardware criaram instruções em código de máquina que permitem testar e atribuir um valor a uma variável de
forma atômica
(indivisível, sem possibilidade de troca de contexto entre essas duas operações). A execução atômica das operações de teste e atribuição impede a ocorrência de condições de disputa sobre a variável
busy.
Processadores modernos oferecem diversas operações atômicas com o mesmo objetivo da TSL, conhecidas coletivamente como
instruções RMW
(de
Read-Modify-Write
), como CAS (
Compare-And-Swap
) e XCHG (
Exchange
).
Os mecanismos de exclusão mútua usando instruções atômicas são amplamente usados no interior do sistema operacional, para controlar o acesso a seções críticas dentro do núcleo, como descritores de tarefas,
buffers
de arquivos ou de conexões de rede, etc.
Nesse contexto, eles são muitas vezes denominados
spinlocks
. Todavia, mecanismos de espera ocupada são
inadequados para a construção de aplicações de usuário
.
Problemas:
O acesso concorrente de diversas tarefas aos mesmos recursos pode provocar problemas de consistência, as chamadas
condições de disputa.
Contudo, apesar dessas soluções garantirem a exclusão mútua elas sofrem de problemas que
impedem seu uso em larga escala nas aplicações de usuário
:
Ineficiência:
As tarefas que aguardam o acesso a uma seção crítica ficam testando continuamente uma condição, consumindo tempo de processador sem necessidade.
Injustiça:
A não ser na solução de alternância, não há garantia de ordem no acesso à seção crítica; dependendo da duração de
quantum
e da política de escalonamento, uma tarefa pode entrar e sair da seção crítica várias vezes, antes que outras tarefas consigam acessá-la.
Por estas razões, as soluções com espera ocupada são pouco usadas na construção de aplicações.
Seu maior uso se encontra na programação de estruturas de controle de concorrência dentro do núcleo
do sistema operacional e na construção de sistemas de computação dedicados, como controladores embarcados mais simples.
Dependência:
Na solução por alternância, tarefas desejando acessar a seção crítica podem ser impedidas de fazê-lo por tarefas que não têm interessa na seção crítica naquele momento.