Problema do Jantar dos Filósofos

O Problema do Jantar dos Filósofos é um dos problemas clássicos de CIP. Consiste basicamente em uma mesa redonda com N pratos e um garfo entre cada dois pratos. Cada filósofo se posiciona em frente de cada prato e sua vida alterna entre dois estados, comer e pensar. Para comer é necessário a utilização de dos dois garfos ao lado do prato do filósofo. Quando está com fome, o filósofo tenta pegar o garfo de um lado e, se conseguir, pega o outro garfo e come. Após um tempo, ele colocar os garfos de volta a mesa e volta à pensar. A solução para o problema consiste em fazer com que nenhum filósofo fique esperando eternamente para pegar os garfos.
A solução apresentada aqui utiliza uma atribuição de um dos três estados aos filósofos: comendo, pensando e com fome. O filósofo só passa para o estado comendo caso os dois vizinhos não estajam comendo.

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

#define N 5 //numeor de filosofos
#define ESQUERDO (i+N+(-1))%(N) //indice do vizinho esquerdo
#define DIREITO (i+1)%N //indice do vizinho direto
#define PENSANDO 0 //estado pensando
#define FOME 1 //estado com fome
#define COMENDO 2 //estado comendo

int estado[N]; //vetor que guarda estado dos filosfos
sem_t mutex; //mutex para regiões críticas
sem_t s[N]; //semáforo para cada filósofo

pthread_t t[N]; //vetor de threads para filósofos

void pegar_garfos(int i);
void devolver_garfos(int i) ;

void testar(int i);
void pensar(int i);

void comer(int i);
void *filosofo (void *arg);

void imprime_estados();


int main(int argc, char *argv){


//variáveis para criação e validação das threadas
int res;
int j;
void *resultado_thread[N];


//criação de mutex
res = sem_init(&mutex, 0, 1);

if (res!= 0 ){
perror("\nFalha no semaforo");

exit(EXIT_FAILURE);
}
else printf("\n Mutex criado");

//criação do vetor de semáforos
for(j = 0; j<5; j++){

res = sem_init(&s[j], 0, 0);
if (res!= 0 ){

perror("\nFalha no semaforo");
exit(EXIT_FAILURE);
}
else printf("\nSemaforo %d criado", j);
}
//criação das threadas dos filósofos

int aux[5];
for(j = 0; j<5; j++){

aux[j] = j;
estado[j] = PENSANDO;
res = pthread_create(&t[j], NULL, filosofo, (void *)&aux[j]);
if (res!= 0 ){

perror("\nFalha na criacao da thread");
exit(EXIT_FAILURE);
}
else printf("\n Thread do filósofo %d criado", j);
}

//join nas threads dos filósofos

for(j = 0; j<5; j++){

res = pthread_join(t[j], &resultado_thread[j] );
if (res!= 0 ){

perror("\nFalha no thread join");
exit(EXIT_FAILURE);

}
}
return 0;
}

void *filosofo (void *arg)
{
int i = *(int *)arg;

while (1) { //loop infinito
pensar(i); //filósofo pensando
pegar_garfos(i); //faz tentativa de pegar garfos até conseguir

comer(i); //come
devolver_garfos(i); //devolve garfos a mesa
}

pthread_exit("exit from thread");
}

void pegar_garfos(int i) //i é o identificador do filósofo

{
sem_wait(&mutex); //entra na região crítica
estado[i] = FOME; //muda estado para fome

testar(i); //vê se é possível pegar garfos
sem_post(&mutex); //sai da região crítica
sem_wait(&s[i]); //fica bloqueado caso não tenha pego os garfos

}

void devolver_garfos(int i)
{
sem_wait(&mutex); //entra na região crítica

estado[i] = PENSANDO; //muda estado para pensando
testar(ESQUERDO); //ve se o vizinho esquerdo pode comer

testar(DIREITO); //ve se o vizinho direto pode comer
sem_post(&mutex); //sai da região critica
}

void testar(int i) /* i: filosofo number, from 0 to N−1 */
{
if (estado[i] == FOME && estado[ESQUERDO] != COMENDO && estado[DIREITO] != COMENDO) {

estado[i] = COMENDO;//come se estiver com fome e nenhum vizinho está comendo
imprime_estados(); //imprime estado dos filósofos para validar
sem_post(&s[i]);
}
}


void pensar(int i)
{
sleep(rand()%5);//pensa durante um tempo de 0 a 5 s

}

void comer(int i)
{
sleep(rand()%5);//come durante um tempo de 0 a 5s

}
void imprime_estados(){

printf("\nFilosofos: 0 1 2 3 4");
printf("\n ");

int j;
char e;
for(j = 0; j<N; j++){

if (estado[j] == PENSANDO) e = 'P';

else if (estado[j] == COMENDO) e = 'C';

else e = 'F';
printf("%c ",e);
}
}


Abaixo segue o resultado do teste realizado. São exibidos o estado de cada filósofo representado pelos caracteres:
'C' - o filósofo está comendo;
'F' - o filósofo está com fome;
'P' - o filósofo está pensando;


Mutex criado
Semaforo 0 criado
Semaforo 1 criado
Semaforo 2 criado
Semaforo 3 criado
Semaforo 4 criado
Thread do filósofo 0 criado
Thread do filósofo 1 criado
Thread do filósofo 2 criado
Filosofos: 0 1 2 3 4
P P P C P
Thread do filósofo 3 criado
Thread do filósofo 4 criado
Filosofos: 0 1 2 3 4
P C P C F
Filosofos: 0 1 2 3 4
C P F C F
Filosofos: 0 1 2 3 4
C P C P F
Filosofos: 0 1 2 3 4
C F P C F
Filosofos: 0 1 2 3 4
C F C P F
Filosofos: 0 1 2 3 4
P F C P C
Filosofos: 0 1 2 3 4
C F C P P
Filosofos: 0 1 2 3 4
P C P F P
Filosofos: 0 1 2 3 4
P C P C P
Filosofos: 0 1 2 3 4
C P P C F
Filosofos: 0 1 2 3 4
C P C P F
Filosofos: 0 1 2 3 4
P F P P C
Filosofos: 0 1 2 3 4
P C P P C
Filosofos: 0 1 2 3 4
P P C P C
Filosofos: 0 1 2 3 4
C P C F P


O teste mostra que em nenhum momento existem filósofos adjacentes comendo, sempre o vizinho de um filósofo comento está pensando ou com fome.