# Impasses e inanição

Condições de impasse, grafos de espera, prevenção e estados seguros.

Página: https://resumos.rgo.pt/cadeiras/so/impasses/

A tarefa A obteve o lock X e espera por Y. B obteve Y e espera por X. Cada uma conserva o primeiro lock até conseguir o segundo, por isso nenhuma consegue avançar. Este **impasse**, ou _deadlock_, depende da posse e dos pedidos atuais, não apenas de ambas usarem os mesmos recursos.

## Quatro condições

No modelo de recursos reutilizáveis, um impasse exige quatro condições em simultâneo. No exemplo dos locks:

| Condição | Onde aparece |
| --- | --- |
| Exclusão mútua | X e Y só podem ter um dono de cada vez |
| Retenção com espera | A conserva X ao pedir Y; B conserva Y ao pedir X |
| Ausência de preempção | O protocolo não retira locks à força |
| Espera circular | A espera por B e B espera por A |

A exclusão mútua protege os dados, mas não decide uma ordem de obtenção. É essa ordem que vamos mudar.

Quebrar uma destas condições evita o impasse nesse modelo. Uma ordem global dos locks quebra a espera circular: todos obtêm X antes de Y. Se B já tem Y, não pode tentar obter X segundo esse protocolo.

Pedir todos os recursos de uma vez quebra retenção com espera, mas pode reduzir utilização e prolongar espera. Libertar o que se tem se a próxima obtenção falhar exige recomeçar com cuidado. Repetir sem nenhuma thread avançar pode dar **livelock**, em que há atividade mas não progresso útil.

## Grafos de recursos e de espera

Num grafo de atribuição, uma aresta processo→recurso é um pedido; recurso→processo é uma atribuição. Com uma única instância de cada recurso, um ciclo prova impasse. Com múltiplas instâncias, um ciclo pode não chegar.

Suponhamos X com uma instância e Y com duas: A tem X e pede Y; B tem uma instância de Y e pede X. O ciclo X→A→Y→B→X existe, mas a segunda instância de Y está livre. Se A só precisa de uma, pode obtê-la, concluir e libertar X para B. Por isso um ciclo só prova impasse no modelo de instância única.

![Ciclo de impasse: X está atribuído a A, A pede Y, Y está atribuído a B e B pede X.](https://resumos.rgo.pt/cadeiras/so/impasses/figura-1.svg)

As caixas são os locks X e Y, cada um com uma única instância; os círculos são as tarefas A e B. As setas contínuas mostram atribuições e as tracejadas mostram pedidos bloqueados. Segue o ciclo X→A→Y→B→X: cada tarefa espera pelo lock da outra e nenhuma o liberta enquanto espera.

Num grafo de espera para locks de uma instância, A→B significa que A espera por um lock que B detém. A→B→A mostra o ciclo. Desenhar apenas que ambos usam dois locks não prova impasse: é preciso identificar quem já tem cada um e quem está bloqueado à espera de quê.

## Seguro não significa livre de espera

Um estado é **seguro** se há uma ordem de conclusão que permite satisfazer as necessidades máximas declaradas de todos. É uma garantia sobre pedidos futuros dentro desses limites, não uma afirmação de que ninguém espera agora.

Com três unidades de um recurso, A tem 1 e pode precisar no máximo de 2; B tem 1 e pode precisar no máximo de 2. Há uma livre. Dá-a a A; A conclui e devolve 2, depois B pode concluir. A ordem A, B prova segurança.

Agora A e B têm 1 cada e ambos podem precisar no máximo de 3. Só há uma livre e cada um ainda pode pedir 2. Não conseguimos garantir uma primeira conclusão pelos máximos declarados, por isso o estado é inseguro. Ainda não prova impasse: podem usar menos do que o máximo ou devolver recursos sem pedir mais.

Para verificar segurança com vários tipos, começa num vetor `Work = Available`. Calcula `Need = Max - Allocation` para cada processo. Procura um processo cujo `Need` caiba componente a componente em Work, simula a sua conclusão somando a sua Allocation a Work e regista a tabela após cada passo. Se conseguires incluir todos, obtiveste uma sequência segura. O algoritmo do banqueiro só admite um pedido se respeita os máximos, a disponibilidade e deixa um estado seguro. Este aprofundamento do banqueiro é um complemento: usa-o quando o enunciado pedir análise de segurança com máximos declarados.

## Deteção e recuperação

Prevenção impõe regras que quebram uma condição. Evitação examina pedidos para manter segurança. Deteção permite alguns pedidos e depois procura impasses. Recuperação pode terminar processos ou retirar recursos recuperáveis, preservando a consistência dos dados. Retirar arbitrariamente um mutex não é uma recuperação correta.

Timeouts permitem abandonar uma espera, mas não corrigem por si a ordem dos locks nem desfazem operações parciais. O código precisa de saber o que libertar e que trabalho reverter.

## Distinguir os problemas

*   Num impasse, um conjunto de tarefas depende circularmente de recursos que as próprias tarefas não libertam.
*   Na inanição, uma tarefa pode ficar sem serviço enquanto outras continuam a avançar, por exemplo devido a prioridade.
*   No livelock, as tarefas mudam de estado ou repetem tentativas, mas não concluem o trabalho.

Não precisas de consumo alto de CPU para ter impasse. Threads bloqueadas podem consumir quase nada. Uma espera longa também não prova impasse, se o evento esperado ainda puder acontecer.

## Exercícios

Quebrar o ciclo

A obtém X e depois pede Y. B obtém Y e depois pede X. Corrige o protocolo sem eliminar exclusão mútua.

Pista

As duas tarefas usam os mesmos recursos em ordens opostas.

Mais uma pista

Escolhe uma ordem global, X antes de Y.

Solução

Ambas devem obter X antes de Y e libertar depois do trabalho. Uma tarefa que já tem Y não pode esperar por X segundo a regra, por isso o ciclo de espera nesses locks não se forma.

Confere a tua resposta:

*   Identifiquei retenção com espera e ciclo.
*   Impus a mesma ordem em todos os caminhos.
*   Expliquei por que a ordem impede o ciclo.

Erros frequentes

Mudar só um percurso e esquecer outro, ou libertar à força um mutex detido por outra thread.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/so/impasses/#quatro-condi%C3%A7%C3%B5es)

Uma disponibilidade que não basta

Existem três unidades de X e três de Y. A disponibilidade atual é `(1,1)`. As linhas seguintes indicam os recursos já atribuídos e o máximo total de cada processo.

| Processo | Allocation (X,Y) | Max (X,Y) |
| --- | --- | --- |
| P0 | (1,0) | (2,1) |
| P1 | (1,1) | (1,3) |
| P2 | (0,1) | (2,2) |

Mostra uma sequência segura. Depois P2 pede `(1,0)`: o pedido respeita a sua necessidade e a disponibilidade. O banqueiro deve concedê-lo?

Pista

Não compares apenas a soma dos recursos: cada tipo precisa de unidades próprias.

Mais uma pista

Antes do pedido, P0 precisa de `(1,1)`. Se concederes a unidade de X a P2, Work começa em `(0,1)`.

Solução

As necessidades iniciais são P0 `(1,1)`, P1 `(0,2)` e P2 `(2,1)`. Começamos com Work `(1,1)`. P0 conclui e devolve Allocation `(1,0)`, deixando Work `(2,1)`. P2 pode concluir e devolver `(0,1)`, deixando `(2,2)`. P1 conclui e devolve `(1,1)`, deixando `(3,3)`.

Se concedermos o pedido, Work fica `(0,1)` e Need de P2 fica `(1,1)`. Nenhuma necessidade cabe em Work: P0 e P2 precisam de X e P1 precisa de duas unidades de Y. O estado seria inseguro, por isso o banqueiro adia o pedido. Isto não prova que os três já estejam em impasse.

Confere a tua resposta:

*   Calculei Need como Max menos Allocation em cada componente.
*   Encontrei a sequência segura P0, P2, P1 no estado inicial.
*   Rejeitei o pedido de P2 por deixar todos sem conclusão garantida.

Erros frequentes

Somar Max a Work quando um processo conclui, ou admitir um pedido apenas porque cabe na disponibilidade atual.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/so/impasses/#seguro-n%C3%A3o-significa-livre-de-espera)

Ciclo com recurso de duas instâncias

X tem uma instância e Y tem duas, equivalentes. A detém X e pede uma unidade de Y. B detém uma unidade de Y e pede X. A segunda unidade de Y está livre. Cada tarefa conclui e liberta tudo quando obtém o que pede.

Desenha o ciclo no grafo de recursos e mostra uma ordem que permita às duas concluir. Que conclusão mudaria se Y só tivesse a unidade atribuída a B?

Pista

Marca separadamente cada instância atribuída ou livre.

Solução

As atribuições são X→A e Y→B; os pedidos são A→Y e B→X. Existe o ciclo X→A→Y→B→X, mas a segunda unidade de Y pode satisfazer A. A conclui e liberta X e Y; B obtém X e conclui. Logo não há impasse neste estado.

Se Y só tivesse uma unidade, A esperaria pelo recurso de B e B pelo de A, sem recurso livre que satisfizesse um pedido. Nas hipóteses dadas, o ciclo provaria impasse.

Confere a tua resposta:

*   Desenhei atribuições e pedidos sem os confundir.
*   Usei a instância livre de Y para permitir A concluir.
*   Distingui o mesmo grafo com Y de instância única.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/so/impasses/#grafos-de-recursos-e-de-espera)