O Jantar dos Filósofos

A versão ingênua — e o deadlock

Cada garfo é um object protegido por lock, como o saldo da aula de Concorrência. O filósofo pega o garfo da esquerda e, sem soltá-lo, pega o da direita (um lock dentro do outro).

using System.Diagnostics;

const int N = 5;
object[] garfos = new object[N];
for (int i = 0; i < N; i++)
    garfos[i] = new object();

void Filosofo(int id)
{
    int esquerdo = id;
    int direito = (id + 1) % N;

    for (int refeicao = 1; refeicao <= 3; refeicao++)
    {
        Thread.Sleep(100);                       // pensando

        lock (garfos[esquerdo])
        {
            Console.WriteLine($"Filósofo {id} pegou o garfo {esquerdo}");
            Thread.Sleep(50);                    // facilita o deadlock aparecer

            lock (garfos[direito])
            {
                Console.WriteLine($"Filósofo {id} comendo ({refeicao}ª refeição)");
                Thread.Sleep(100);               // comendo
            }
        }
    }
    Console.WriteLine($"Filósofo {id} terminou o jantar");
}

// ---------- daqui para baixo, não muda nas soluções ----------
Stopwatch relogio = Stopwatch.StartNew();
List<Thread> filosofos = new List<Thread>();

for (int i = 0; i < N; i++)
{
    int id = i;                                  // cópia para a lambda
    Thread t = new Thread(() => Filosofo(id));
    t.IsBackground = true;
    filosofos.Add(t);
    t.Start();
}

bool todosJantaram = filosofos.All(t => t.Join(5000));

if (todosJantaram)
    Console.WriteLine($"Todos jantaram em {relogio.Elapsed.TotalSeconds:F1}s");
else
    Console.WriteLine("DEADLOCK: depois de 5s, ainda há filósofos travados esperando um garfo.");

dotnet run

Ao rodar, todos pegam o garfo da esquerda e o programa trava. Repare que o código não tem nenhum erro de sintaxe ou de lógica se olharmos um filósofo isolado — o problema só existe na combinação das threads. Por isso deadlocks são tão difíceis de achar em sistemas reais: às vezes acontecem uma vez a cada mil execuções.

Teste: remova o Thread.Sleep(50) entre os dois lock e rode várias vezes. O deadlock continua acontecendo sempre?

Solução 1 — Um único lock para a mesa toda

A ideia mais simples: em vez de disputar garfos, os filósofos disputam a mesa. Quem consegue o lock da mesa pega os dois garfos, come e libera. Substitua apenas a função Filosofo (e declare a mesa logo acima dela):

object mesa = new object();

void Filosofo(int id)
{
    for (int refeicao = 1; refeicao <= 3; refeicao++)
    {
        Thread.Sleep(100);                       // pensando

        lock (mesa)
        {
            Console.WriteLine($"Filósofo {id} comendo ({refeicao}ª refeição)");
            Thread.Sleep(100);                   // comendo
        }
    }
    Console.WriteLine($"Filósofo {id} terminou o jantar");
}

• Quebra: posse e espera — ninguém fica segurando um garfo enquanto espera o outro.
• Vantagem: impossível ter deadlock; código trivial.
• Problema: só um filósofo come por vez, mesmo quando F0 e F2 (que não compartilham garfo nenhum) poderiam comer juntos. Compare o tempo total com as próximas soluções.

Solução 2 — Ordem global dos garfos (hierarquia de recursos)

Numeramos os garfos e combinamos uma regra: todo filósofo pega primeiro o garfo de menor número. Para F0 a F3 nada muda (esquerdo < direito). Mas F4 usa os garfos 4 e 0, então ele pega o garfo 0 primeiro — ou seja, F4 é o único que começa pela direita.

void Filosofo(int id)
{
    int esquerdo = id;
    int direito = (id + 1) % N;
    int primeiro = Math.Min(esquerdo, direito);
    int segundo = Math.Max(esquerdo, direito);

    for (int refeicao = 1; refeicao <= 3; refeicao++)
    {
        Thread.Sleep(100);                       // pensando

        lock (garfos[primeiro])
        {
            Thread.Sleep(50);
            lock (garfos[segundo])
            {
                Console.WriteLine($"Filósofo {id} comendo ({refeicao}ª refeição)");
                Thread.Sleep(100);               // comendo
            }
        }
    }
    Console.WriteLine($"Filósofo {id} terminou o jantar");
}

• Quebra: espera circular. F0 e F4 disputam primeiro o garfo 0; um deles nem chega a pegar garfo nenhum, então o "círculo" de esperas nunca se fecha.
• Vantagem: simples, sem estruturas extras, e até dois filósofos comem juntos. É a técnica mais usada na prática: em uma transferência entre duas contas, bloqueie sempre primeiro a conta de menor id.
• Problema: exige que todo o código do sistema respeite a mesma ordem. Basta um trecho esquecido pegando na ordem inversa para o deadlock voltar.

Uma variação equivalente é a solução assimétrica: filósofos de número par pegam primeiro o garfo da esquerda, e os ímpares, o da direita.

Solução 3 — O garçom (limitar quem senta à mesa)

Se no máximo 4 dos 5 filósofos tentarem comer ao mesmo tempo, sobram 5 garfos para 4 pessoas: pelo menos uma delas certamente consegue os dois garfos, come e libera para as outras. Quem controla isso é um "garçom": um SemaphoreSlim com N − 1 permissões — exatamente a ferramenta de capacidade da aula de Concorrência.

SemaphoreSlim garcom = new SemaphoreSlim(N - 1);   // no máximo 4 à mesa

void Filosofo(int id)
{
    int esquerdo = id;
    int direito = (id + 1) % N;

    for (int refeicao = 1; refeicao <= 3; refeicao++)
    {
        Thread.Sleep(100);                       // pensando

        garcom.Wait();                           // pede licença ao garçom
        try
        {
            lock (garfos[esquerdo])
            {
                Thread.Sleep(50);
                lock (garfos[direito])
                {
                    Console.WriteLine($"Filósofo {id} comendo ({refeicao}ª refeição)");
                    Thread.Sleep(100);           // comendo
                }
            }
        }
        finally
        {
            garcom.Release();                    // sai da mesa
        }
    }
    Console.WriteLine($"Filósofo {id} terminou o jantar");
}

• Quebra: espera circular — para o círculo fechar, os 5 precisariam estar segurando um garfo, e o garçom nunca deixa os 5 entrarem.
• Vantagem: os filósofos continuam pegando "esquerda e depois direita", sem regra de ordem.
• Problema: o garçom é um ponto central que todos precisam consultar. Teste mudar para new SemaphoreSlim(N): o deadlock volta.

Solução 4 — Tentar e desistir (Monitor.TryEnter)

O filósofo pega o garfo da esquerda e tenta pegar o da direita por um tempo limitado. Se não conseguir, devolve o da esquerda, espera um pouco e tenta de novo. Monitor.TryEnter(objeto, 50) é a versão "com tempo limite" do lock: retorna true se conseguiu em até 50 ms, ou false se desistiu.

void Filosofo(int id)
{
    int esquerdo = id;
    int direito = (id + 1) % N;

    for (int refeicao = 1; refeicao <= 3; refeicao++)
    {
        Thread.Sleep(100);                       // pensando

        bool comeu = false;
        while (!comeu)
        {
            lock (garfos[esquerdo])
            {
                Thread.Sleep(50);
                if (Monitor.TryEnter(garfos[direito], 50))
                {
                    try
                    {
                        Console.WriteLine($"Filósofo {id} comendo ({refeicao}ª refeição)");
                        Thread.Sleep(100);       // comendo
                        comeu = true;
                    }
                    finally
                    {
                        Monitor.Exit(garfos[direito]);
                    }
                }
            }

            if (!comeu)
            {
                Console.WriteLine($"Filósofo {id} desistiu e devolveu o garfo {esquerdo}");
                Thread.Sleep(Random.Shared.Next(10, 200));   // espera ALEATÓRIA
            }
        }
    }
    Console.WriteLine($"Filósofo {id} terminou o jantar");
}

• Quebra: posse e espera — ninguém espera para sempre segurando um garfo.
• Vantagem: não depende de ordem nem de coordenador central.
• Problema: risco de livelock e de starvation. A espera aleatória é o que "desencontra" os filósofos. Troque Random.Shared.Next(10, 200) por um valor fixo, como 100, e observe quantas vezes eles desistem.