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):