Deadlock

Processo A                    Processo B
──────────                    ──────────
lock(mutex_1)  ← obtém        lock(mutex_2)  ← obtém
lock(mutex_2)  ← BLOQUEIA     lock(mutex_1)  ← BLOQUEIA
               (B tem mutex_2)                (A tem mutex_1)

  A espera B liberar mutex_2
  B espera A liberar mutex_1
  Nenhum pode liberar → DEADLOCK

Analogia do mundo real:
  Dois carros em um cruzamento estreito,
  cada um bloqueando a passagem do outro.
  Nenhum pode recuar (recurso não-preemptível).

1. EXCLUSÃO MÚTUA
   Pelo menos um recurso é não-compartilhável.
   Exemplo: um mutex só pode ser detido por um processo.

2. POSSE E ESPERA (Hold and Wait)
   Um processo detém pelo menos um recurso e está
   esperando para adquirir recursos adicionais detidos
   por outros processos.

3. NÃO-PREEMPÇÃO (No Preemption)
   Recursos não podem ser tomados à força de um processo;
   eles só são liberados voluntariamente pelo detentor.

4. ESPERA CIRCULAR (Circular Wait)
   Existe um conjunto {P0, P1, ..., Pn} de processos onde:
   P0 espera recurso de P1,
   P1 espera recurso de P2,
   ...
   Pn espera recurso de P0.

TODAS as 4 devem ser verdadeiras simultaneamente.
Eliminar QUALQUER uma impede deadlock.

Legenda:
  ○ = Processo    □ = Recurso (com instâncias como pontos)
  ──→ = requisição (processo → recurso): "preciso disto"
  ←── = alocação (recurso → processo): "estou com este"

Exemplo SEM deadlock:
  P1 ──→ R1 ←── P2     P1 quer R1, P2 tem R1
  P2 ──→ R2             P2 quer R2 (R2 está livre)
  → P2 obtém R2, libera R1, P1 obtém R1. Resolvido.

Exemplo COM deadlock:
  P1 ──→ R1 ←── P2
  P2 ──→ R2 ←── P1

  Grafo:
       ┌──→ R1 ←──┐
       │           │
      P1          P2
       │           │
       └──← R2 ──→┘

  Ciclo: P1 → R1 → P2 → R2 → P1
  Com instância única por recurso: ciclo = deadlock

Recurso com múltiplas instâncias:
  R1 tem 2 instâncias (ex: 2 impressoras)
  Ciclo no grafo NÃO garante deadlock
  (outra instância pode ser liberada)
  Precisa de algoritmo mais sofisticado para detectar

1. Eliminar EXCLUSÃO MÚTUA
   → Tornar recursos compartilháveis.
   → Impraticável para muitos recursos (mutex é necessário).
   → Possível: spooling de impressora (processo escreve no spool,
     daemon imprime; processos nunca acessam a impressora diretamente).

2. Eliminar POSSE E ESPERA
   → Exigir que processo peça TODOS os recursos de uma vez,
     antes de começar a executar.
   → Problemas: baixa utilização (recursos alocados mas não usados),
     starvation (processo que precisa de muitos recursos nunca os
     consegue todos simultaneamente).

3. Eliminar NÃO-PREEMPÇÃO
   → Se um processo que detém recursos pede um recurso indisponível,
     todos os seus recursos são liberados (preemptados).
   → Funciona para recursos cujo estado pode ser salvo e restaurado
     (CPU, memória). Não funciona para impressora ou mutex.

4. Eliminar ESPERA CIRCULAR
   → Impor uma ORDEM TOTAL nos recursos.
   → Todo processo deve requisitar recursos em ordem crescente.
   → Mais usada na prática!

// Atribuir um número a cada mutex:
// mutex_contas = 1, mutex_log = 2, mutex_rede = 3

// Regra: sempre adquirir em ordem crescente

// CORRETO:
lock(mutex_contas);   // #1
lock(mutex_log);      // #2 (2 > 1 ✓)
lock(mutex_rede);     // #3 (3 > 2 ✓)
// trabalhar...
unlock(mutex_rede);
unlock(mutex_log);
unlock(mutex_contas);

// INCORRETO (viola a ordem):
lock(mutex_rede);     // #3
lock(mutex_contas);   // #1 (1 < 3 ✗) → pode causar deadlock

// No kernel Linux, lockdep verifica essa ordem em runtime
// e avisa antes do deadlock acontecer.

Estado SEGURO:
  Existe pelo menos uma sequência de execução onde todos
  os processos podem terminar sem deadlock.

Estado INSEGURO:
  NÃO existe garantia de que todos podem terminar.
  (Não significa que deadlock vai ocorrer, mas PODE.)

  Estado seguro → nunca deadlock
  Estado inseguro → deadlock pode ocorrer
  Deadlock → estado inseguro (subconjunto)

Sistema com 3 tipos de recurso: A=10, B=5, C=7

         Alocação    Max    Necessidade (Max-Aloc)
         A  B  C    A B C    A  B  C
  P0     0  1  0    7 5 3    7  4  3
  P1     2  0  0    3 2 2    1  2  2
  P2     3  0  2    9 0 2    6  0  0
  P3     2  1  1    2 2 2    0  1  1
  P4     0  0  2    4 3 3    4  3  1

  Disponível: A=3, B=3, C=2
  (Total - soma das alocações = [10-7, 5-2, 7-5])

  Sequência segura? Simulamos:
  1. P1 pode executar (precisa 1,2,2 ≤ disp 3,3,2)
     → P1 termina, libera 2,0,0. Disp = 5,3,2
  2. P3 pode (precisa 0,1,1 ≤ 5,3,2)
     → P3 termina, libera 2,1,1. Disp = 7,4,3
  3. P4 pode (precisa 4,3,1 ≤ 7,4,3)
     → P4 termina, libera 0,0,2. Disp = 7,4,5
  4. P2 pode (precisa 6,0,0 ≤ 7,4,5)
     → P2 termina, libera 3,0,2. Disp = 10,4,7
  5. P0 pode (precisa 7,4,3 ≤ 10,4,7) ✓

  Sequência segura: <P1, P3, P4, P2, P0>
  Estado é SEGURO.

DETECÇÃO:

  Para recursos de instância única:
    Construir grafo de espera (wait-for graph).
    Deadlock existe ⟺ ciclo no grafo.
    Complexidade: O(n²) com n = número de processos.

  Para recursos de múltiplas instâncias:
    Algoritmo similar ao do banqueiro, mas sem usar Max.
    Verifica se o estado ATUAL pode ser resolvido.

  Frequência de detecção:
    A cada requisição? → custo alto (O(n²) por requisição)
    Periodicamente? → deadlock pode persistir entre checagens
    Quando CPU idle? → heurística prática

RECUPERAÇÃO:

  1. Abortar processos:
     a) Abortar TODOS os processos do deadlock (drástico)
     b) Abortar UM por vez até resolver (qual escolher?)
        Critérios: prioridade, tempo de CPU gasto,
        recursos detidos, quanto falta para terminar

  2. Preempção de recursos:
     a) Selecionar vítima (qual processo perde recurso)
     b) Rollback (reverter vítima a estado seguro)
     c) Starvation: garantir que mesma vítima não é
        escolhida sempre (usar contador)

  Linux na prática:
    Kernel usa lock ordering (prevenção)
    lockdep subsystem detecta violações em desenvolvimento
    Postgres detecta deadlocks via timeout + grafo de espera

#define MAX_PROC 100

bool espera[MAX_PROC][MAX_PROC];  // espera[i][j] = Pi espera Pj
bool visitado[MAX_PROC];
bool no_stack[MAX_PROC];          // na pilha de recursão

// DFS para detectar ciclo
bool tem_ciclo(int proc, int n) {
    visitado[proc] = true;
    no_stack[proc] = true;

    for (int j = 0; j < n; j++) {
        if (espera[proc][j]) {
            if (!visitado[j]) {
                if (tem_ciclo(j, n))
                    return true;
            } else if (no_stack[j]) {
                return true;  // ciclo encontrado!
            }
        }
    }

    no_stack[proc] = false;
    return false;
}

bool detectar_deadlock(int n) {
    memset(visitado, false, sizeof(visitado));
    memset(no_stack, false, sizeof(no_stack));

    for (int i = 0; i < n; i++) {
        if (!visitado[i] && tem_ciclo(i, n))
            return true;
    }
    return false;
}

Cenário: dois agentes atualizam dados cruzados

  Agente A:                         Agente B:
  BEGIN;                            BEGIN;
  UPDATE sessions SET ...           UPDATE decisions SET ...
    WHERE id = 1;  ← trava row 1     WHERE id = 5;  ← trava row 5
  UPDATE decisions SET ...          UPDATE sessions SET ...
    WHERE id = 5;  ← ESPERA row 5    WHERE id = 1;  ← ESPERA row 1
                     (B tem)                            (A tem)

Postgres detecta em ~1 segundo:
  ERROR: deadlock detected
  DETAIL: Process 1234 waits for ShareLock on transaction 5678;
          blocked by process 5678.
          Process 5678 waits for ShareLock on transaction 1234;
          blocked by process 1234.
  HINT: See server log for query details.

Postgres resolve: aborta uma das transações (a vítima).
A outra prossegue normalmente.
A aplicação deve fazer retry da transação abortada.

Configuração:
  deadlock_timeout = 1s  (tempo antes de checar deadlock)
  lock_timeout = 30s     (timeout geral para locks)

Prevenção no harness.os:
  - Agentes fazem operações atômicas simples (INSERT, não UPDATE cruzado)
  - log_decision() e log_learning() são INSERTs → nunca deadlock
  - Sessões isoladas minimizam contention