O que você vai aprender
Enunciar as quatro condições necessárias para deadlock.
Distinguir prevenção, evitação, detecção e recuperação.
Aplicar a ideia do algoritmo do banqueiro e do estado seguro.
Quando o sistema simplesmente trava
Você já viu um programa "pendurar" sem dar erro, sem usar CPU, apenas parado para sempre? Às vezes a causa é um deadlock: processos que se esperam mutuamente e nunca mais avançam.
O deadlock é um dos problemas mais sutis da concorrência: não há erro de sintaxe, não há exceção, a CPU pode até estar livre — e ainda assim nada acontece. Entender por que ele surge e como tratá-lo é essencial para construir sistemas confiáveis.
O caminho desta aula
Vamos percorrer o tema em quatro frentes conectadas:
condições→Grafo de
alocação→Estratégias
(prevenir/evitar)→Banqueiro +
detecção
- Primeiro entendemos quando um deadlock pode ocorrer (condições de Coffman).
- Depois aprendemos a representá-lo em um grafo.
- Em seguida, as quatro estratégias de tratamento.
- Por fim, o algoritmo do banqueiro e a detecção, com o simulador.
O que é deadlock
O ponto-chave: a espera é circular e permanente. Sem intervenção externa, o conjunto travado nunca se desfaz sozinho.
As quatro condições de Coffman
Um deadlock só ocorre se as quatro condições valerem simultaneamente:
| Condição | Significado |
|---|---|
| Exclusão mútua | O recurso é usado por um processo de cada vez |
| Posse e espera | Um processo segura recursos e pede mais, esperando |
| Não preempção | Um recurso não pode ser tomado à força do dono |
| Espera circular | Existe um ciclo de processos esperando recursos uns dos outros |
Dois locks, dois processos
Considere dois processos que precisam de dois locks (A e B), mas os adquirem em ordens diferentes:
Se P1 pega A e, ao mesmo tempo, P2 pega B, então P1 espera B (que P2 tem) e P2 espera A (que P1 tem): impasse. As quatro condições estão presentes.
Stepper: como o impasse se forma
Grafo de alocação de recursos
É a ferramenta visual para detectar a espera circular.
Quando o ciclo indica deadlock
Com uma instância por recurso, um ciclo no grafo significa deadlock garantido. Com várias instâncias por recurso, o ciclo é condição necessária mas não suficiente — pode haver ciclo sem impasse.
O cruzamento engarrafado
Quatro formas de tratar deadlock
| Estratégia | Ideia | Custo |
|---|---|---|
| Prevenção | Negar uma das quatro condições por projeto | Pode reduzir uso de recursos |
| Evitação | Conceder só se o estado seguir seguro (banqueiro) | Exige conhecer a demanda máxima |
| Detecção e recuperação | Deixar ocorrer, detectar o ciclo, recuperar | Custo de detecção + aborto/rollback |
| Ignorar (avestruz) | Fingir que não acontece | Barato; aceita o risco |
Como o SO decide
O caminho de decisão típico ao receber um pedido de recurso:
recurso→Estratégia
ativa?→Conceder /
esperar→Verificar
segurança
Na prevenção, o pedido já vem com regras que evitam o impasse. Na evitação, o SO testa cada concessão. Na detecção, ele concede livremente e periodicamente procura ciclos.
Prevenção: quebrando cada condição
- Exclusão mútua: tornar recursos compartilháveis quando possível (ex.: arquivos só de leitura). Nem sempre dá.
- Posse e espera: exigir que o processo peça tudo de uma vez no início, ou que só peça quando não tem nada. Reduz a utilização.
- Não preempção: se um processo é negado, ele libera o que já tem e tenta de novo depois.
- Espera circular: impor uma ordem total nos recursos e exigir pedidos em ordem crescente. É a técnica mais usada na prática.
Check: identifique a condição
Impor que todo processo adquira os recursos sempre em ordem numérica crescente quebra qual condição de Coffman?
O jantar dos filósofos
Cinco filósofos compartilham cinco garfos; cada um precisa dos dois garfos vizinhos para comer. Se todos pegam o garfo da esquerda ao mesmo tempo, cada um espera o da direita: deadlock clássico.
Soluções conhecidas: limitar a quatro filósofos comendo de cada vez; numerar os garfos e pegar sempre o de menor número primeiro (ordenação); ou permitir que um filósofo pegue os dois garfos apenas se ambos estiverem livres (atômico).
Confusões frequentes
- Confundir deadlock (bloqueio mútuo permanente) com inanição (espera indefinida, mas o processo poderia rodar) ou livelock (processos ativos que mudam de estado sem progredir).
- Achar que um ciclo no grafo sempre indica deadlock — só vale para recursos de instância única.
- Esquecer que as quatro condições devem valer simultaneamente.
- Supor que o algoritmo do banqueiro detecta deadlock — ele evita, recusando concessões inseguras.
Boas práticas contra impasses
- Adote uma ordem global de aquisição de locks e siga-a em todo o código.
- Use timeouts ao adquirir recursos: se demorar demais, libere e tente novamente.
- Prefira locks de granularidade adequada — locks grandes demais aumentam a contenção.
- Em bancos de dados, conheça o detector de deadlock do SGBD: ele costuma abortar a transação mais barata.
Reveal: detecção e recuperação
Detectado um deadlock, quais são as opções de recuperação?
Revisão relâmpago
Como se liga ao resto do curso
- Sincronização (aula 7): semáforos e locks mal ordenados são a fonte mais comum de deadlocks.
- Escalonamento (aula 5): a inanição combatida com aging é "prima" do deadlock, mas não é a mesma coisa.
- Memória e E/S: recursos como quadros de memória e dispositivos também podem entrar em impasse.
- Banco de dados: transações que travam linhas em ordens diferentes reproduzem o mesmo problema.
O essencial sobre deadlocks
Mãos ao banqueiro
Hora de praticar com o simulador do banqueiro abaixo.
Informe as matrizes Alocação, Máximo e Disponível, faça pedidos de recursos e observe se o estado resultante permanece seguro. Tente descobrir a sequência segura de término que o algoritmo encontra — e provoque um pedido que leve a um estado inseguro para ver o sistema recusá-lo.
Atividade em grupo · O banqueiro na prática
Em grupos, analisem se um estado é seguro e simulem um pedido.
Roteiro
- Recebam um cenário com matrizes Alocação, Máximo e Disponível.
- Calculem a matriz Necessidade = Máximo − Alocação.
- Procurem uma sequência segura de término dos processos.
- Confiram no simulador e testem o que acontece ao conceder um pedido específico.
Mini-quiz · Aula 8
20 questões sobre esta aula. Escolha e veja a explicação na hora.
📌 Resumo — leve isto para a prova
- Deadlock exige as quatro condições de Coffman simultâneas: exclusão mútua, posse e espera, não preempção e espera circular.
- Estratégias: prevenir (quebrar uma condição), evitar (banqueiro), detectar/recuperar ou ignorar (avestruz).
- O banqueiro concede recursos só se o estado continuar seguro; precisa da demanda máxima.
- Um estado seguro tem uma sequência de término viável para todos; Necessidade = Máximo − Alocação.
- Deadlock (bloqueio permanente) difere de inanição e de livelock.