[28]. Considere uma variável inteira, denominada ocupado, compartilhada entre dois processos A e B (inicialmente, ocupado
). 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;
}
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
, com valor inicial . - Ambos os processos
e executam o trecho: - entrar em região não crítica;
- aguardar o laço de espera
(ou seja, enquanto for diferente de zero); - executar a atribuição
; - executar a região crítica;
- executar
.
- Pedido: explicar em que situação
e 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
é 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
) e a escrita ( ) 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:
. - Sequência de eventos possível:
- Processo
termina o laço porque lê (ou seja, a verificação vê 0 e o laço termina). - Logo após essa leitura, antes de
executar a instrução , é pré‑emptado (interrompido) pelo escalonador. - Processo
executa; ele também entra no laço, lê e sai do laço. -
executa . -
entra na sua região crítica. - Mais tarde
volta a ser agendado; ainda sem saber que já marcou , executa sua instrução (sobrescreve o valor já 1). -
entra na sua região crítica também.
- Processo
- Conclusão do cenário: tanto
quanto 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
faz a verificação no laço ela apenas lê o valor atual de . Ler não protege contra mudanças feitas logo depois por outro processo. - O fato de
ter “visto” não garante que o valor continuará até escrever. Entre o momento em que lê e o momento em que escreve há uma lacuna onde 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 (
) não é atômico. - Efeito: dois processos podem ambos observar a condição de entrada (ver
) e ambos prosseguir para setar , 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:
. - Depois do passo 4 do cenário:
(quando escreve). - Depois do passo 6 do cenário:
(quando 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 (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
e saírem do laço antes de qualquer um executar . Ou seja: se ambos “lerem zero” antes que qualquer um escreva , cada um seguirá e executará e depois entrará na região crítica — causando entrada simultânea.
Resposta
A e B podem entrar simultaneamente se ambos lerem
(saírem do laço de espera) antes que qualquer um dos dois execute a atribuição
; por exemplo:
lê
e é pré‑emptado,
lê
,
faz
e entra, depois
volta, executa
e também entra — portanto ambos na região crítica ao mesmo tempo.