Impasses e inanição
Condições de impasse, grafos de espera, prevenção e estados seguros.
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.
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
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.
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
Mais uma pista
(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
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
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.