[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 \text{down}(s) e \text{up}(s) sobre semáforos não forem implementadas de forma atômica.
Informações relevantes dadas ou implicitamente necessárias:
  • Existe um semáforo s usado para proteger uma seção crítica.
  • As operações esperadas são \text{down}(s) (também chamada P(s) ou wait) e \text{up}(s) (também chamada V(s) ou signal).
  • Suporemos o caso clássico de exclusão mútua onde o semáforo é inicializado em \,s=1 , (semáforo binário / mutex).
  • A hipótese que vamos quebrar: as implementações de \text{down}(s) e \text{up}(s) 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 s=1 funciona assim, idealmente, com operações atômicas:
    • \text{down}(s): bloqueia o processo se s=0; senão decrementa s e permite entrar. Em semântica atômica, se s=1 o processo decrementa para 0 e entra, e nenhum outro processo lê o valor antigo.
    • \text{up}(s): incrementa s (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 \text{down}(s) é implementada, de forma não atômica, por duas ações visíveis:
  1. Ler o valor atual: t := s.
  2. Se t = 0 então bloquear; senão escrever s := t - 1 e prosseguir para a seção crítica.
    Esquematicamente (pseudo-código não atômico):
\text{down}(s):\quad t := s;\quad \text{if } t = 0 \text{ then block else } s := t-1;\\ \text{enter CS}
Aqui há uma lacuna entre a leitura t := s e a escrita s := t-1 em que outro processo pode executar. Essa lacuna é a origem da violação.

Passo 4

Construindo um exemplo com dois processos concorrentes P_1 e P_2, e s inicializado em \,s=1. 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: s=1.
Sequência de passos:
  1. P_1 executa a leitura: t_1 := s. Agora t_1 = 1.
  2. (Queda de contexto) o escalonador interrompe P_1 antes de decrementar s.
  3. P_2 executa a leitura: t_2 := s. Agora t_2 = 1 (porque s ainda é 1).
  4. P_1 retoma e executa a escrita: s := t_1 - 1. Assim s passa a 0. P_1 entra na seção crítica.
  5. P_2 agora prossegue e executa a escrita: s := t_2 - 1. Como t_2 = 1, essa escrita faz s := 0\!-\!? — na prática s passa a -1 ou a um valor inválido no modelo simples, mas o importante é que P_2 NÃO foi bloqueado e também entra na seção crítica.
Resultado: tanto P_1 quanto P_2 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 t=1 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 \text{up}(s) não atômico (perda de wakeup, que prejudica corretude):
  • Mesmo que o problema de exclusão mútua apareça principalmente quando \text{down} não é atômico, \text{up} 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 \text{up} 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 \text{down}(s) e \text{up}(s) 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 s; 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).
  • 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 s=1 e dois processos lendo 1 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.

Resposta

Com \text{down}(s) e \text{up}(s) não atômicos dois processos podem ler s=1 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.

Exercícios relacionados