[30]. Mostre como pode ocorrer violação da condição de exclusão mútua se as operações down(s) e up(s) sobre semáforos não forem implementadas de forma atômica.
Passo 1
O enunciado pede para mostrar como a condição de exclusão mútua pode ser violada se as operações
e
sobre semáforos não forem implementadas de forma atômica.
Informações relevantes dadas ou implicitamente necessárias:
Informações relevantes dadas ou implicitamente necessárias:
- Existe um semáforo
usado para proteger uma seção crítica. - As operações esperadas são
(também chamada ou wait) e (também chamada ou signal). - Suporemos o caso clássico de exclusão mútua onde o semáforo é inicializado em
, (semáforo binário / mutex). - A hipótese que vamos quebrar: as implementações de
e são compostas por várias instruções e não são atômicas (ou seja, podem ser interrompidas por escalonamento entre essas instruções).
Passo 2
Breve explicação didática do que cada coisa significa (pra ficar tranquilo):
- O objetivo da exclusão mútua é garantir que, em qualquer tempo, no máximo um processo esteja dentro da seção crítica.
- Um semáforo com
funciona assim, idealmente, com operações atômicas: -
: bloqueia o processo se ; senão decrementa e permite entrar. Em semântica atômica, se o processo decrementa para e entra, e nenhum outro processo lê o valor antigo. -
: incrementa (ou acorda um processo bloqueado).
-
- Atomicidade significa que uma operação aparece aos outros processos como ocorrendo de uma só vez, sem que outros processos vejam estados intermediários.
Passo 3
Mostrando a implementação não atômica típica (modelo simplificado):
Considere que é implementada, de forma não atômica, por duas ações visíveis:
Considere que
- Ler o valor atual:
. - Se
então bloquear; senão escrever e prosseguir para a seção crítica.
Esquematicamente (pseudo-código não atômico):
Aqui há uma lacuna entre a leitura
e a escrita
em que outro processo pode executar. Essa lacuna é a origem da violação.
Passo 4
Construindo um exemplo com dois processos concorrentes
e
, e
inicializado em
. Vou descrever um intercalamento (interleaving) realista que causa a violação. Cada linha é uma ação atômica do processador (leitura, escrita, etc.).
Estado inicial:
.
Sequência de passos:
-
executa a leitura: . Agora . - (Queda de contexto) o escalonador interrompe
antes de decrementar . -
executa a leitura: . Agora (porque ainda é ). -
retoma e executa a escrita: . Assim passa a . entra na seção crítica. -
agora prossegue e executa a escrita: . Como , essa escrita faz — na prática passa a ou a um valor inválido no modelo simples, mas o importante é que NÃO foi bloqueado e também entra na seção crítica.
Resultado: tanto
quanto
entraram na seção crítica simultaneamente — a exclusão mútua foi violada.
Passo 5
Comentando mais devagar sobre por que isso é grave e como ver isso na prova:
- O problema essencial é que ambos os processos leram uma cópia antiga
antes que o primeiro tivesse a chance de atualizar o semáforo; como a decisão de entrar foi tomada com base numa leitura que ficou obsoleta, o segundo não foi impedido. - Em palavras simples: a checagem e a atualização do semáforo precisam ser indivisíveis; se outra tarefa pode se intrometer entre checar e atualizar, a garantia some.
- Este é um exemplo clássico de condição de corrida: o comportamento final depende da ordem das operações entre processos.
Passo 6
Variante mostrando problema também com
não atômico (perda de wakeup, que prejudica corretude):
- Mesmo que o problema de exclusão mútua apareça principalmente quando
não é atômico, não atômico pode causar outros malefícios (por exemplo, acordar ninguém quando devia ou incrementar duas vezes, dependendo do design). - Ex.: se
faz primeiro consultar uma fila de bloqueados e depois acordar, outra thread pode alterar a fila entre essas ações, levando a “lost wakeup” ou duplicação de acordos. Embora isso não seja exatamente violação de exclusão mútua, é outro exemplo de comportamento errado por falta de atomicidade.
Passo 7
Como evitar o problema (resumo prático que cai na prova):
- A solução é garantir que as operações
e sejam executadas de forma atômica. Em sistemas reais isso se faz usando: - instruções atômicas de hardware (por exemplo, test-and-set, swap, compare-and-swap) para implementar uma primitiva de bloqueio que protege a atualização de
; ou - primitivas do kernel que realizam a espera/sinalização de forma atômica (por exemplo, bloqueio/desbloqueio com fila gerida pelo SO); ou
- desabilitar interrupções em ambientes monoprocessador enquanto se atualiza o semáforo (técnica pedagógica, não escalável).
- instruções atômicas de hardware (por exemplo, test-and-set, swap, compare-and-swap) para implementar uma primitiva de bloqueio que protege a atualização de
- Em provas, basta argumentar que a leitura e a atualização têm que ser indivisíveis; se não forem, dar o interleaving como no Passo 4 prova claramente a violação.
Passo 8
Recapitulando com uma frase de incentivo (breve):
Você já tem a estrutura para argumentar em prova: explique a implementação não atômica, mostre o interleaving com e dois processos lendo
antes do decremento, e conclua que ambos entram na seção crítica — exclusão mútua violada. Isso é exatamente o raciocínio que o examinador espera.
Você já tem a estrutura para argumentar em prova: explique a implementação não atômica, mostre o interleaving com
Resposta
Com
e
não atômicos dois processos podem ler
simultaneamente e ambos decrementar / prosseguir (por interleaving), fazendo com que ambos entrem na seção crítica; assim a condição de exclusão mútua é violada.