Deadlock: condições de Coffman, estado seguro e banqueiro

Deadlock (impasse ou bloqueio mútuo) é a situação em que dois ou mais processos ficam esperando para sempre por recursos que estão nas mãos uns dos outros. É um tema recorrente de sistemas operacionais, cobrado em duas frentes: as condições que o causam e as estratégias para tratá-lo. Este guia traz as condições, as estratégias e um teste de estado seguro, com os cálculos conferidos por simulação.

O problema em um exemplo

O processo A segura o recurso 1 e pede o recurso 2. O processo B segura o recurso 2 e pede o recurso 1. Nenhum libera o que tem antes de obter o que falta, e nenhum avança. Os dois ficam bloqueados.

No grafo de alocação de recursos, desenham-se arestas do processo ao recurso que ele pede e do recurso ao processo que o detém. Em um grafo de espera (processo espera por processo), o impasse aparece como um ciclo: A espera B, B espera A. Num teste, o grafo A para B, B para C e C para A foi identificado como ciclo (A, B, C, A), enquanto A para B e B para C, sem retorno, não tem ciclo. Atenção: em recursos de instância única, ciclo significa deadlock; com várias instâncias do mesmo recurso, ciclo é condição necessária, mas não suficiente.

As quatro condições (Coffman)

O deadlock só pode ocorrer se as quatro condições valerem ao mesmo tempo:

Condição	Significado
Exclusão mútua	o recurso só pode ser usado por um processo por vez
Posse e espera	o processo mantém recursos já obtidos enquanto espera por outros
Não preempção	o recurso não pode ser tomado à força; só o dono o libera
Espera circular	existe um ciclo de processos, cada um esperando um recurso do próximo

As três primeiras são características do ambiente; a quarta é o resultado delas. Eliminar qualquer uma das quatro impede o impasse.

Quatro estratégias

Prevenção: garante que pelo menos uma condição nunca ocorra.
- Contra posse e espera: exigir que o processo peça todos os recursos de uma vez, no início.
- Contra não preempção: permitir que o sistema retire recursos de quem espera.
- Contra espera circular: numerar os recursos e obrigar os pedidos em ordem crescente. É a técnica mais usada na prática.
- Contra exclusão mútua: raramente possível, pois alguns recursos são intrinsecamente exclusivos; spooling de impressão é um caso de contorno.
Evitação: o sistema analisa cada pedido e só o atende se o estado resultante for seguro. O exemplo clássico é o algoritmo do banqueiro. Exige conhecer o máximo de cada processo.
Detecção e recuperação: deixa o impasse acontecer, procura ciclos periodicamente e então se recupera: encerra processos, retira recursos ou volta a estados anteriores.
Ignorar (algoritmo do avestruz): comum em sistemas de uso geral, em que o impasse é raro e o custo da prevenção é alto; deixa-se o usuário reiniciar o que travar.

Estado seguro e algoritmo do banqueiro

Um estado é seguro se existe uma sequência em que todos os processos podem terminar, cada um recebendo o que falta para o seu máximo. Estado inseguro não é deadlock, mas é um estado em que o deadlock pode vir a ocorrer. O nome vem da analogia do banqueiro que só concede crédito se puder atender todos os clientes ao final.

Exemplo numérico com um tipo de recurso

Há 10 unidades de um recurso. Três processos:

Processo	Possui	Máximo	Ainda precisa
A	3	9	6
B	2	4	2
C	2	7	5

Livres: 10 - (3 + 2 + 2) = 3.

Teste de segurança. Procure um processo cuja necessidade caiba no que está livre:

Livres = 3. B precisa de 2: cabe. Recebe as 2 unidades, termina e devolve as 4 que passa a ter. Livres = 3 - 2 + 4 = 5.
C precisa de 5: cabe. Recebe 5, termina e devolve 7. Livres = 5 - 5 + 7 = 7.
A precisa de 6: cabe. Recebe 6, termina e devolve 9. Livres = 7 - 6 + 9 = 10.

Existe a sequência B, C, A: estado seguro.

Pedido de A por mais 1 unidade. Se concedido, A passa a ter 4, e livres = 2. Teste: B precisa de 2 e cabe; ao terminar, livres = 2 - 2 + 4 = 4. Agora C precisa de 5 e A precisa de 5; nenhum cabe em 4. Estado inseguro: o banqueiro nega o pedido de A, mesmo havendo unidades livres.

Pedido de B por mais 1 unidade. Livres = 2, B com 3. B precisa de 1 e cabe, e a sequência B, C, A continua possível. Estado seguro: o pedido pode ser concedido.

Conclusão importante para a prova: o banqueiro nega pedidos que levam a estado inseguro, mesmo que o recurso esteja disponível naquele momento. Ele é conservador e exige conhecer, de antemão, o máximo de cada processo, o que limita o uso real.

Relações com outros temas

Inanição (starvation) não é deadlock: ali um processo espera indefinidamente porque outros sempre passam na frente, mas o sistema continua progredindo. No deadlock, os processos envolvidos param de avançar.
Livelock: os processos continuam mudando de estado, reagindo uns aos outros, sem progresso útil.
Condição de corrida: resultado depende da ordem de execução de acessos concorrentes; é resolvida com sincronização (semáforos, monitores, travas), e o uso incorreto das travas é uma fonte clássica de deadlock.
Em bancos de dados, a mesma ideia aparece em transações que travam linhas em ordem oposta; os sistemas detectam o ciclo e abortam uma das transações. Veja o contexto de transações em SQL: DDL, DML, DCL e TCL.

Erros comuns

Dizer que basta uma das quatro condições para haver deadlock; é preciso que todas ocorram.
Confundir estado inseguro com deadlock já instalado.
Achar que ciclo no grafo sempre significa deadlock, ignorando recursos com várias instâncias.
Confundir inanição com deadlock.
Esquecer que a evitação precisa do máximo declarado de cada processo.

Fontes e atualização

Não há norma oficial brasileira sobre sistemas operacionais; o conteúdo segue a literatura clássica, e as sequências do exemplo numérico foram conferidas por simulação. Nomes (impasse, bloqueio mútuo, travamento) variam entre autores: confira o edital.

Próximos passos

Veja o escalonamento em FCFS, SJF e Round Robin com cálculos.
Estude a memória em substituição de páginas FIFO, LRU e ótimo.
Retome o conceito em sistema operacional: funções, arquivos, pastas e atalhos.