Dining Philosophers

Cinco filósofos sentam numa mesa redonda. Entre cada par de vizinhos há um garfo, cinco garfos no total, e no centro há um prato de espaguete que exige dois garfos pra comer. Cada filósofo alterna entre pensar e comer. Pra comer, ele pega o garfo da esquerda, depois o da direita, come, e devolve os dois. O problema, formulado por Dijkstra, é achar um jeito de todos comerem sem que ninguém fique preso.

A solução ingênua é escrever exatamente o enunciado: pega o garfo da esquerda, pega o da direita, come. Cada garfo é um mutex, porque um garfo só serve a um filósofo por vez.

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

#define N 5
pthread_mutex_t garfo[N];

void *filosofo(void *arg) {
    int id = *(int *)arg;
    int esq = id, dir = (id + 1) % N;
    for (;;) {
        pthread_mutex_lock(&garfo[esq]);      // pega o garfo da esquerda
        printf("filosofo %d pegou garfo esquerdo\n", id);
        usleep(100000);                        // hesita um instante
        pthread_mutex_lock(&garfo[dir]);      // quer o da direita
        printf("filosofo %d comeu\n", id);
        pthread_mutex_unlock(&garfo[dir]);
        pthread_mutex_unlock(&garfo[esq]);
    }
    return NULL;
}

int main(void) {
    setbuf(stdout, NULL);                      // mostra a saída antes do travamento
    pthread_t t[N]; int id[N];
    for (int i = 0; i < N; i++) pthread_mutex_init(&garfo[i], NULL);
    for (int i = 0; i < N; i++) { id[i]=i; pthread_create(&t[i],NULL,filosofo,&id[i]); }
    for (int i = 0; i < N; i++) pthread_join(t[i],NULL);
    return 0;
}

O usleep entre pegar um garfo e o outro cumpre o mesmo papel de sempre: dá tempo pra todos pegarem o primeiro garfo antes de qualquer um tentar o segundo. Rodando:

$ cc main.c -o main -pthread
$ ./main
filosofo 0 pegou garfo esquerdo
filosofo 1 pegou garfo esquerdo
filosofo 2 pegou garfo esquerdo
filosofo 4 pegou garfo esquerdo
filosofo 3 pegou garfo esquerdo
^C
$

Nenhum “comeu” aparece. Os cinco pegaram o garfo da esquerda, e agora cada um quer o garfo da direita, que é o garfo esquerdo do vizinho, que o vizinho está segurando e não vai soltar porque ele também está esperando o dele. É um deadlock, e das quatro condições que o produzem, a que salta aos olhos aqui é a espera circular: o filósofo 0 espera o 1, que espera o 2, e assim por diante até fechar o anel.

Duas saídas

A primeira saída já conhecemos do deadlock: quebrar a espera circular impondo uma ordem global na aquisição. Se, em vez de “cada um pega o seu garfo esquerdo primeiro”, a regra for “todos pegam primeiro o garfo de menor número”, o anel não se fecha. O filósofo 4, que pegaria o garfo 4 e depois o 0, passa a pegar o 0 e depois o 4, e essa única inversão basta pra romper o ciclo.

A segunda saída é mais interessante porque usa a ferramenta deste capítulo e ataca o problema por outro ângulo: em vez de mudar a ordem, limitar quantos tentam comer ao mesmo tempo. O deadlock só é possível porque os cinco tentam sentar pra comer de uma vez. Se no máximo quatro tentarem, sempre sobra um garfo pra alguém completar o par, comer, e liberar os seus. Basta um porteiro que admita no máximo quatro filósofos à mesa, e um porteiro que conta é um semáforo:

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>

#define N 5
pthread_mutex_t garfo[N];
sem_t garcom;                          // admite no máximo N-1 à mesa
int refeicoes[N] = {0};

void *filosofo(void *arg) {
    int id = *(int *)arg;
    int esq = id, dir = (id + 1) % N;
    for (int r = 0; r < 3; r++) {      // cada um come três vezes
        sem_wait(&garcom);             // pede lugar ao garçom
        pthread_mutex_lock(&garfo[esq]);
        pthread_mutex_lock(&garfo[dir]);
        refeicoes[id]++;
        printf("filosofo %d comeu (%d)\n", id, refeicoes[id]);
        pthread_mutex_unlock(&garfo[dir]);
        pthread_mutex_unlock(&garfo[esq]);
        sem_post(&garcom);             // levanta da mesa
    }
    return NULL;
}

int main(void) {
    setbuf(stdout, NULL);
    sem_init(&garcom, 0, N - 1);       // no máximo 4 sentados de uma vez
    pthread_t t[N]; int id[N];
    for (int i = 0; i < N; i++) pthread_mutex_init(&garfo[i], NULL);
    for (int i = 0; i < N; i++) { id[i]=i; pthread_create(&t[i],NULL,filosofo,&id[i]); }
    for (int i = 0; i < N; i++) pthread_join(t[i],NULL);
    printf("todos comeram\n");
    return 0;
}

$ cc main.c -o main -pthread
$ ./main
filosofo 0 comeu (1)
filosofo 0 comeu (2)
filosofo 0 comeu (3)
filosofo 1 comeu (1)
filosofo 1 comeu (2)
...
todos comeram

Cada filósofo come as três vezes e o programa termina. Nesta execução o filósofo 0 pegou os dois garfos e emendou as três refeições antes de soltar, porque o loop é rápido e ele estava com os garfos quentes na mão; noutra execução a ordem sai diferente. O que não muda é o essencial: o garçom nunca deixa os cinco disputarem ao mesmo tempo, então nunca se forma o anel de espera. Comparado com a ordem global, o garçom tem a vantagem de ser local: você não precisa reescrever a regra de aquisição de cada filósofo, só interpor uma permissão na entrada. É a mesma ideia do estacionamento com vagas, aplicada a uma disputa que sem o limite viraria deadlock.