1. Introdução: O jantar dos filósofos e as quatro condições de Coffman (1971)

Em 1965, o cientista da computação holandês Edsger W. Dijkstra formulou o célebre problema do jantar dos filósofos (Dining Philosophers Problem): cinco filósofos $P_0 \dots P_4$ sentam-se ao redor de uma mesa circular; entre cada prato de espaguete há um único garfo ($F_0 \dots F_4$). Para comer, cada filósofo precisa segurar simultaneamente seu garfo esquerdo $F_i$ e seu garfo direito $F_{(i+1)\bmod 5}$. Se todos os cinco filósofos sentirem fome no mesmo microssegundo e pegarem seu garfo esquerdo $F_i$, cada um esperará eternamente que seu vizinho da direita solte o segundo garfo: todo o sistema congela para sempre. Isso é um impasse ou bloqueio mútuo (Deadlock).

Formalmente, um subconjunto não vazio de processos $D \subseteq \mathcal{P}$ está em deadlock se e somente se cada processo $P_i \in D$ está bloqueado aguardando um evento (como a liberação de uma trava) que só pode ser disparado por outro processo $P_j \in D$ pertencente ao mesmo conjunto de espera.

Em 1971, Edward G. Coffman Jr., M. J. Elphick e Arie Shoshani provaram que um deadlock de recursos só pode ocorrer se quatro condições necessárias forem satisfeitas simultaneamente:

1. Exclusão mútua (Mutual Exclusion): Pelo menos um recurso é mantido em modo exclusivo (não compartilhável).
2. Retenção e espera (Hold and Wait): Um processo já retém pelo menos um recurso enquanto aguarda bloqueado para adquirir recursos adicionais retidos por outros processos.
3. Não preempção (No Preemption): Recursos alocados não podem ser tomados à força; só são liberados voluntariamente pelo detentor.
4. Espera circular (Circular Wait): Existe uma cadeia fechada de processos $\{P_0, P_1, \dots, P_{k-1}\}$ tal que cada $P_i$ aguarda um recurso retido por $P_{(i+1)\bmod k}$.

Como todas as quatro condições são individualmente necessárias, negar logicamente apenas uma delas torna o deadlock matematicamente impossível ($0\,\%$).

2. Grafo de Alocação de Recursos (RAG) e teoremas de ciclos (Holt, 1972)

Em 1972, Richard C. Holt modelou o estado dos recursos como um grafo direcionado bipartido chamado Grafo de Alocação de Recursos (RAG) $G = (V, E)$, com vértices $V = \mathcal{P} \cup \mathcal{R}$ (processos $P_i$ e tipos de recursos $R_j$ com $W_j \ge 1$ instâncias idênticas), arestas de requisição $P_i \to R_j$ e arestas de alocação $R_j \to P_i$.

Três teoremas fundamentais relacionam os ciclos direcionados de $G$ ao deadlock:

• Teorema 1 (Aciclicidade $\implies$ Ausência de deadlock): Se $G$ não contém ciclos direcionados (é um DAG), nenhum processo está em deadlock.
• Teorema 2 (Condição necessária e suficiente em instância única): Se cada tipo de recurso possui uma única instância ($\forall j, W_j = 1$), então ciclo direcionado em $G \iff$ deadlock.
• Teorema 3 (Não suficiência em múltiplas instâncias): Se algum recurso possui múltiplas instâncias ($\exists j, W_j > 1$), a presença de um ciclo direcionado é condição necessária, mas NÃO suficiente para o deadlock!

  flowchart TD
    subgraph RAG_Single["Caso A: RAG de instância única (Ciclo <==> Deadlock garantido)"]
        PA1(("P1 (Bloqueado)")) -->|"Requisita"| RA1["R1 (1 instância: ●)"]
        RA1 -->|"Alocado a"| PA2(("P2 (Bloqueado)"))
        PA2 -->|"Requisita"| RA2["R2 (1 instância: ●)"]
        RA2 -->|"Alocado a"| PA1
    end

    subgraph RAG_Multi["Caso B: RAG multi-instância (Existe ciclo P1->R1->P3->R2->P1, mas ZERO deadlock!)"]
        PB1(("P1 (Bloqueado)")) -->|"Requisita"| RB1["R1 (2 instâncias: ●●)"]
        RB1 -->|"Instância #1"| PB3(("P3 (Bloqueado)"))
        PB3 -->|"Requisita"| RB2["R2 (2 instâncias: ●●)"]
        RB2 -->|"Instância #1"| PB1
        RB1 -->|"Instância #2"| PB2(("P2 (RODANDO: Sem requisições!)"))
        RB2 -->|"Instância #2"| PB4(("P4 (RODANDO: Sem requisições!)"))
    end

No Caso B existe o ciclo $P_1 \to R_1 \to P_3 \to R_2 \to P_1$, mas $P_2$ e $P_4$ têm grau de saída $0$ (sorvedouros ativos): assim que terminarem e liberarem suas instâncias de $R_1$ e $R_2$, o ciclo será desfeito naturalmente.

3. Estratégia 1 (Prevenção): Prova por contradição da ordenação total de travas

Em núcleos de SO (como o validador lockdep do Linux) e sistemas multithread, a condição 4 (espera circular) é eliminada impondo uma ordenação total de travas (Total Lock Ordering): atribui-se a cada mutex $L \in \mathcal{L}$ um posto global único $\phi(L) \in \mathbb{N}$, exigindo que qualquer thread que retenha o conjunto $\mathcal{H}$ só possa requisitar uma nova trava $L_{\text{new}}$ se seu posto for estritamente maior:

【Prova por contradição】: Suponha que se forme um ciclo de espera $\{P_0, P_1, \dots, P_{k-1}\}$ ($k \ge 2$), onde $P_i$ retém $L_i$ e aguarda $L_{(i+1)\bmod k}$. Como todos obedecem à regra de ordem estrita, encadeando as desigualdades ao longo do ciclo obtemos:

Como nenhum número natural pode ser estritamente menor que si mesmo, chegamos a uma contradição ($\bot$)! Seja em transferências bancárias (travar sempre a conta de menor ID primeiro) ou no jantar dos filósofos (fazer $P_4$ pegar primeiro o garfo direito $F_0$ antes do esquerdo $F_4$, pois $0 < 4$), a espera circular torna-se impossível. $\blacksquare$

4. Estratégia 2 (Evitação): Algoritmo do banqueiro de Dijkstra (Rastreamento 5×3)

Quando a ordem de alocação é dinâmica, o algoritmo do banqueiro de Dijkstra (1965 / Habermann, 1969) exige a declaração prévia da demanda máxima $\mathbf{Max}$ e verifica em tempo $O(m \cdot n^2)$ antes de cada concessão se o estado resultante permanece um estado seguro (Safe State) com pelo menos uma sequência segura (Safe Sequence) ($\text{Deadlock} \subsetneq \text{Estado inseguro}$).

Para $n=5$ processos $\{P_0 \dots P_4\}$ e $m=3$ recursos com $\mathbf{Total} = (A=10, B=5, C=7)$ e soma alocada $(7,2,5)$, o vetor disponível inicial é $\mathbf{Available} = (10,5,7) - (7,2,5) = \mathbf{(3, 3, 2)}$:

A sequência segura $\langle P_1, P_3, P_4, P_0, P_2 \rangle$ prova que $t_0$ é seguro. Se $P_1$ requisitar $(1,0,2)$, a alocação tentativa deixa $\mathbf{Available}=(2,3,0) \ge \mathbf{Need}_1=(0,2,0)$ (concedida imediatamente). Mas se logo a seguir $P_0$ requisitar $(0,2,0)$, o disponível cai para $(2,1,0)$, que não atende ao $\mathbf{Need}$ de nenhum processo (estado inseguro): o banqueiro rejeita o pedido e bloqueia $P_0$!

5. Estratégias 3 e 4 (Detecção WFG, Wait-Die/Wound-Wait, Avestruz) e Livelock vs. Inanição

SGBDs relacionais (PostgreSQL, MySQL InnoDB) constroem um grafo de espera (Wait-For Graph, WFG) e buscam ciclos via DFS em $O(|V|+|E|)$, abortando (rollback) a transação vítima com menor log Undo (detecção imediata no MySQL; após deadlock_timeout = 1s no PostgreSQL). Bancos distribuídos (Google Spanner) usam os protocolos baseados em carimbo de tempo $\text{TS}(T_i)$ de Rosenkrantz et al. (1978): Wait-Die (não preemptivo) e Wound-Wait (preemptivo, com menos reinícios), mantendo sempre o carimbo de tempo original $\text{TS}(T_i)$ ao reiniciar para evitar inanição. Para raros esgotamentos de tabelas em SOs de uso geral, UNIX e Windows aplicam o algoritmo do avestruz (Ostrich Algorithm) ignorando o problema para não impor sobrecarga diária.

  flowchart TD
    Req["Transação distribuída Ti requisita trava mantida por Tj"] --> Cmp{"Comparar carimbos de tempo: TS(Ti) < TS(Tj) ?<br/>(A requisitante Ti é MAIS VELHA que a detentora Tj?)"}
    Cmp -->|"Sim: Ti é MAIS VELHA (Older)"| WD1["[Wait-Die (não preemptivo)]: A mais velha Ti ESPERA pela jovem Tj (Velho -> Jovem)<br/>[Wound-Wait (preemptivo)]: A mais velha Ti FERE (aborta) Tj e toma a trava!"]
    Cmp -->|"Não: Ti é MAIS JOVEM (Younger)"| WD2["[Wait-Die (não preemptivo)]: A jovem Ti MORRE (aborta e tenta com mesmo TS)<br/>[Wound-Wait (preemptivo)]: A jovem Ti ESPERA pacientemente pela velha Tj (Jovem -> Velho)"]

Por fim, comparemos as três falhas de vivacidade (Liveness):