O Problema do Jantar dos Filósofos (com threads)

Em ciência da computação, o problema do jantar dos filósofos é um exemplo ilustrativo de um problema comum de programação concorrente. É mais um problema clássico de sincronização multi-processo.

O problema pode ser resumido como cinco filósofos sentados ao redor de uma mesa redonda, cada qual fazendo exclusivamente uma das duas coisas: comendo ou pensando. Enquanto está comendo, um filósofo não pode pensar, e vice-versa.

Cada filósofo possui um prato cheio de spaghetti à sua frente. Além disso, um garfo é posicionado entre cada par adjacente de filósofos (portanto, cada filósofo tem exatamente um garfo à sua esquerda e exatamente um garfo à sua direita).


Como spaghetti é uma comida díficil para se servir e comer com um único garfo, assume-se que um filósofo necessita de dois garfos para poder comer. E, além disso, um filósofo só pode utilizar um garfo que esteja imediatamente à sua esquerda ou imediatamente à sua direita.

A falta de disponibilidade de garfos é uma analogia à falta de recursos compartilhados em programação de computadores (situação conhecida como concorrência). Travar (lock) um recurso é um técnica comumemente utilizada para assegurar que o recurso está sendo acessado somente por um programa ou trecho de código, por vez. Quando um programa está interessado em um recurso que já foi travado por outro, o programa espera até que ele seja destravado. Quando existem vários programas envolvidos no travamento de recursos, um deadlock pode acontecer, dependendo das circunstâncias.

Para exemplificar, podemos citar um programa que necessita processar dois arquivos. Quando duas instâncias desse programa travam um arquivo cada, ambos os programas esperam o outro destravar o arquivo que falta, o que nunca irá ocorrerá.

Em geral, o problema do jantar dos filósofos é um problema genérico e abstrato que é utilizado para explicar diversas situações indesejáveis que podem ocorrer em problemas que tem como principal idéia a exclusão mútua.
Por exemplo, assim como no caso acima, deadlock/livelock é um conceito que pode ser bem explicado através do problema dos filósofos.

Abaixo encontra-se uma possível solução para o problema.
A solução apresentada é livre de deadlocks e permite o máximo de paralelismo a um número arbitrário de filósofos. Ela usa um arranjo, state, para controlar se um filósofo está comendo, pensando ou faminto (tentando pegar garfos). Um filósofo só pode mudar para o estado 'comendo' se nenhum dos vizinhos estiver comendo. Os vizinhos do filósofo i são definidos pelas macros LEFT e RIGHT. Em outras palavras, se i for 2, LEFT será 1 e RIGHT será 3.
O programa usa um arranjo de semáforos, um por filósofo; assim, filósofos famintos podem ser bloqueados se os garfos necessários estiverem ocupados. Observe que cada thread executa o procedimento philosopher como seu código principal, mas os outros procedimentos - take_forks, put_forks e test - são procedimentos ordinários, e não processos separados.

Figura1: Saída do Programa
(clique na figura para melhor visualização)

Código:

#include "stdio.h"
#include "stdlib.h"
#include "unistd.h"
#include "fcntl.h"
#include "sys/types.h"
#include "pthread.h"
#include "semaphore.h"

#define N           5           /* número de filósofos*/
#define LEFT        (i+N-1)%N   /* número do vizinho à esquerda de i*/
#define RIGHT       (i+1)%N     /* número do vizinho à direito de i*/
#define THINKING    0           /* o filósofo está pensando*/
#define HUNGRY      1           /* o filósofo está tentando pegar garfos*/
#define EATING      2           /* o filósofo está comendo*/
#define TRUE        1  
<
int state[N];                   /* arranjo para controlar o estado de cada um*/
sem_t mutex;                    /* exclusão mútua para as regiões críticas*/
sem_t s[N];                     /* um semáforo por filósofo*/

/* protótipos */
void* philosopher(void* arg);
void take_forks(int i);
void put_forks(int i);
void test(int i);
void eat(int i);
void think(int i);

int main() {
 int i;

 sem_init(&mutex, TRUE, 1);

 for(i = 0; i < N; i++) {
     sem_init(&s[i], TRUE, 1);
 }

 pthread_t tphil[5];

   /* criando os 5 filósofo - 1 thread para cada*/
   for(i = 0; i < N; i++) {
     pthread_create(&tphil[i], NULL, (void *) philosopher, (void *) &i);
 }

 for(i = 0; i < N; i++) {
     pthread_join(tphil[i], NULL);
 }

 return 0;
}

void* philosopher(void * arg) { /*i: o número do filósofo, de 0 a N-1*/
 int i = *((int *) arg);

 while(TRUE) {               /* repete para sempre*/
     think(i);               /* o filósofo está pensando*/
     take_forks(i);          /* pega dois garfos ou bloqueia*/
     eat(i);                 /* o filósofo está comendo*/
     put_forks(i);           /* devolve os dois garfos à mesa*/
 }

 pthread_exit(NULL);
}

void take_forks(int i) {        /*i: o número do filósofo, de 0 a N-1*/
 sem_wait(&mutex);           /* entra na região crítica*/
 state[i] = HUNGRY;          /* registra que o filósofo está faminto*/
 test(i);                    /* tenta pegar dois garfos*/
 sem_post(&mutex);           /* sai da região crítica*/
 sem_wait(&s[i]);            /* bloqueia se os garfos não foram pegos*/
}

void put_forks(int i) {         /*i: o número do filósofo, de 0 a N-1*/
 sem_wait(&mutex);           /* entra na região crítica*/
 state[i] = THINKING;        /* o filósofo acabou de comer*/
 test(LEFT);                 /* vê se o vizinho da esquerda pode comer agora*/
 test(RIGHT);                /* vê se o vizinho da direito pode comer agora*/
 sem_post(&mutex);           /* sai da região crítica*/
}

void test(int i) {
 if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
     state[i] = EATING;
     sem_post(&s[i]);
 }
}

void eat(int i) {               /*i: o número do filósofo, de 0 a N-1*/
 printf("Filosofo %d estah comendo!\n", i);
 sleep( rand()%5 );
}

void think(int i) {             /*i: o número do filósofo, de 0 a N-1*/
 printf("Filosofo %d estah pensando!\n", i);
 sleep( rand()%10 );
}

Fontes:

http://en.wikipedia.org/wiki/Dining_philosophers_problem
Sistemas Operacionais Modernos, 2a ed - A.S.Tanenbaum