[28]. Considere uma variável inteira, denominada ocupado, compartilhada entre dois processos A e B (inicialmente, ocupado =0 ). Sendo que ambos os processos executam o trecho de programa abaixo, explique em que situação A e B poderiam entrar simultaneamente nas suas respectivas regiões críticas.
while (true) {
    regiao_nao_critica();
    while (ocupado) {};
    ocupado = 1;
    regiao_critica();
    ocupado = 0;
}

Passo 1

O que o enunciado dá e o que pede:
  • Dado: uma variável inteira compartilhada ocupado, com valor inicial ocupado=0.
  • Ambos os processos A e B executam o trecho:
    • entrar em região não crítica;
    • aguardar o laço de espera while(ocupado) (ou seja, enquanto ocupado for diferente de zero);
    • executar a atribuição ocupado = 1;
    • executar a região crítica;
    • executar ocupado = 0.
  • Pedido: explicar em que situação A e B poderiam entrar simultaneamente nas suas regiões críticas.

Passo 2

Entendendo o ponto fraco do código (conceito-chave: atomicidade).
  • A operação lógica necessária para garantir exclusão mútua é: “testar se ocupado é zero e, se for, marcar como ocupado” — isto deveria ser atômico (feito em uma única operação indivisível).
  • No código dado, o teste (o laço while(ocupado)) e a escrita ( ocupado = 1) são duas operações separadas. Entre essas duas operações existe uma janela de tempo em que outro processo pode executar.
  • Definição simples: uma operação atômica é aquela que não pode ser interrompida no meio; se o par “ler e escrever” não for atômico, pode ocorrer um intercalamento (interleaving) de instruções entre processos causando condição de corrida.

Passo 3

Construindo um cenário passo a passo (interleaving) em que ambos entram — o núcleo da explicação:
  • Estado inicial: ocupado = 0.
  • Sequência de eventos possível:
    1. Processo A termina o laço while(ocupado) porque lê ocupado = 0 (ou seja, a verificação vê 0 e o laço termina).
    2. Logo após essa leitura, antes de A executar a instrução ocupado = 1, A é pré‑emptado (interrompido) pelo escalonador.
    3. Processo B executa; ele também entra no laço, lê ocupado = 0 e sai do laço.
    4. B executa ocupado = 1.
    5. B entra na sua região crítica.
    6. Mais tarde A volta a ser agendado; ainda sem saber que B já marcou ocupado, A executa sua instrução ocupado = 1 (sobrescreve o valor já 1).
    7. A entra na sua região crítica também.
  • Conclusão do cenário: tanto A quanto B estão dentro da região crítica ao mesmo tempo.

Passo 4

Por que esse interleaving acontece (explicação didática e passo a passo das leituras/escritas):
  • Quando A faz a verificação no laço ela apenas lê o valor atual de ocupado. Ler não protege contra mudanças feitas logo depois por outro processo.
  • O fato de A ter “visto” 0 não garante que o valor continuará 0 até A escrever. Entre o momento em que A lê e o momento em que A escreve há uma lacuna onde B pode agir.
  • Assim, a sequência “ler zero” → (pausa) → “outro processo também lê zero e escreve 1” → “original escreve 1” produz entrada simultânea. É um clássico exemplo de condição de corrida (race condition).

Passo 5

Formalizando o problema com termos simples:
  • Problema: o teste e o ajuste do indicador ( ocupado) não é atômico.
  • Efeito: dois processos podem ambos observar a condição de entrada (ver ocupado=0) e ambos prosseguir para setar ocupado=1, entrando simultaneamente.
  • Nome do problema: falta de exclusão mútua — o protocolo não satisfaz a propriedade de exclusão mútua.

Passo 6

Um diagrama de valores (para fixar a ideia)
  • Inicialmente: ocupado = 0.
  • Depois do passo 4 do cenário: ocupado = 1 (quando B escreve).
  • Depois do passo 6 do cenário: ocupado = 1 (quando A escreve, sobrescrevendo).
  • Em nenhum momento esse protocolo impediu que ambos entrassem, porque a verificação e a escrita foram separadas.

Passo 7

Como evitar isso — ideias práticas (o que se usa em prova / no sistema real)
  • Fazer o teste-e-alteração de forma atômica. Exemplos:
    • Instrução atômica de hardware como test-and-set ou atomic exchange: usar algo como \text{while}(\text{test\_and\_set}(&ocupado))\\ {} (conceito: test_and_set retorna o valor antigo e faz a escrita em uma única operação atômica).
    • Usar primitivas do SO: mutex, semáforos ou spinlocks implementados com operações atômicas.
  • Para duas threads em exercícios teóricos, pode-se usar o algoritmo de Peterson (usa duas flags e uma variável turn) que garante exclusão mútua sem instruções atômicas especiais. Ideia central do Peterson: cada processo anuncia intenção e favorece o outro antes de entrar, garantindo que não ambos entrem ao mesmo tempo.
  • Alternativa de baixa abstração: desabilitar interrupções em sistemas monoprocessador durante a região crítica (não aplicável em multiprocessadores e não recomendada em geral).

Passo 8

Resumo final do “quando” pedido pelo enunciado (em linguagem direta e prática)
  • A e B entram simultaneamente se ambos verificarem ocupado=0 e saírem do laço antes de qualquer um executar ocupado = 1. Ou seja: se ambos “lerem zero” antes que qualquer um escreva 1, cada um seguirá e executará ocupado = 1 e depois entrará na região crítica — causando entrada simultânea.

Resposta

A e B podem entrar simultaneamente se ambos lerem ocupado=0 (saírem do laço de espera) antes que qualquer um dos dois execute a atribuição ocupado = 1; por exemplo: A 0 e é pré‑emptado, B 0, B faz ocupado=1 e entra, depois A volta, executa ocupado=1 e também entra — portanto ambos na região crítica ao mesmo tempo.

Exercícios relacionados