O problema dos filósofos e deadlock

Deadlock = espera circular por recursos

Deadlock acontece quando um grupo de processos/threads fica bloqueado para sempre, cada um esperando por um recurso que outro do grupo segura. Ninguém libera, ninguém avança.

As quatro condições necessárias (Coffman, 1971): exclusão mútua (recurso só pode ser usado por um de cada vez), hold and wait (segura um recurso enquanto espera outro), sem preempção (recurso não pode ser tomado à força) e espera circular (ciclo de dependências).

Cinco filósofos à mesa

Veja o cenário sem deadlock (filósofos revezam) e o cenário de deadlock (todos pegam o garfo esquerdo simultaneamente).

As 4 condições de Coffman e como quebrá-las

# As 4 condições de Coffman (1971) — todas necessárias para deadlock:

# 1. Exclusão mútua: recursos não podem ser compartilhados
#    (garfo só pode estar nas mãos de 1 filósofo por vez)

# 2. Hold and wait: processo segura recursos e espera por mais
#    (filósofo segura garfo esquerdo e espera pelo direito)

# 3. Sem preempção: recurso não pode ser tomado à força
#    (garfo só é devolvido voluntariamente)

# 4. Espera circular: A espera por B, B espera por C, ... N espera por A
#    (P0 espera garfo do P1, P1 espera garfo do P2, ..., P4 espera garfo do P0)

# Prevenção: quebrar QUALQUER condição elimina o deadlock
# Estratégia 1: ordenação de recursos (quebra espera circular)
def comer_ordenado(eu, esq, dir_):
    primeiro  = min(esq, dir_)   # sempre pega o de menor ID primeiro
    segundo   = max(esq, dir_)
    with forks[primeiro]:       # P4 pegará fork0 antes de fork4
        with forks[segundo]:    # quebra a espera circular!
            eat(eu)

Solução: ordenação de recursos

# Solução completa: filósofos com ordenação de recursos
import threading

N = 5
forks = [threading.Lock() for _ in range(N)]

def philosopher(i):
    left  = i
    right = (i + 1) % N
    # Garante ordem global: pega o garfo de menor índice primeiro
    first, second = (left, right) if left < right else (right, left)

    while True:
        print(f"P{i} pensando")
        with forks[first]:      # menor índice primeiro — sem deadlock!
            with forks[second]:
                print(f"P{i} comendo")

threads = [threading.Thread(target=philosopher, args=(i,)) for i in range(N)]
for t in threads: t.start()

# Outras soluções:
# - Árbitro: 1 semáforo global, só N-1 filósofos podem tentar ao mesmo tempo
# - Chandy-Misra: filósofos pedem garfos com mensagens, sem locks compartilhados

Implementando os filósofos

Mini projeto: implemente os 5 filósofos em Python com threading.Lock. Primeiro sem proteção (deadlock provável). Depois adicione a solução de ordenação de recursos e confirme que nunca trava. Adicione logs com timestamps para visualizar a sequência de execução.

Projeto principal: implemente o algoritmo do Banqueiro de Dijkstra. Dado: N processos, M tipos de recurso, vetor de instâncias disponíveis, matriz de alocação e matriz de necessidade máxima. Implemente is_safe(state) que determina se o estado atual é seguro, e request(process, resource) que só aloca se o estado resultante for seguro.

Desafio extra: use a ferramenta de detecção de deadlock do Java (JConsole ou ThreadMXBean.findDeadlockedThreads()) para detectar automaticamente um deadlock que você criou. Depois implemente o mesmo em Python usando threading._active e análise do grafo de espera. Explique por que deadlocks em Python são mais raros que em Java (dica: GIL).

Teste sua intuição

Onde você encontra isso