Jantar dos Filósofos

O jantar dos filósofos, o mais famoso dos problemas clássicos de programação concorrente, apresenta, mais uma vez, a competição por um conjunto de recursos - neste caso os garfos. Na verdade, os filósofos não podem comer todos ao mesmo tempo já que não há "garfos" que cheguem para todos. Além disso é preciso garantir que os filósofos não se impeçam uns aos outros de comer entrando num deadlock.

Este problema consiste em cinco filósofos estão sentados em círculo, tentando comer espaguete com a ajuda de garfos. Cada filósofo possui uma bacia de massa mas há apenas cinco garfos, colocados um a direita e outro a esquerda de cada filósofo, para serem compartilhados entre eles. Isto cria um problema, pois ambos os garfos (direita e esquerda) são necessários para cada um dos filósofos poder comer. As alternativas dos filósofos compreendem duas fases: Pensar e Comer. No modo pensar, um filósofo não segura um garfo. Porém, quando está com fome(depois de ficar por um tempo finito no modo Pensar) o filósofo tenta pegar os dois garfos na direita e esquerda.

Cada filósofo recebe um número identificador. Para evitar situções de deadlock, todos os filósofos com número par tentam agarrar primeiro no garfo à sua esquerda e os ímpares tentam agarrar primeiro no garfo à direita.

(Bibliografia: http://www.jr.eti.br)

A seguir, um código em C para resolver esse clássico problema:

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

#include<math.h>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define N  5
#define LEFT  (i+N-1)%N
#define RIGHT  (i+1)%N
#define THINKING 0
#define HUNGRY  1
#define EATING  2

#define TRUE 1
#define FALSE 0

int state[N];

sem_t mutex;
sem_t s[N];

void test(int i){

if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {

state[i] = EATING;
sem_post(&s[i]);
}
}

void think(int i){
printf("Philosopher #%d says: I think, therefore I am.\n",i);
}

void eat(int i){
printf("Philosopher #%d enjoys his meal.\n",i);
}

void take_forks(int i) {
sem_wait(&mutex);
state[i] = HUNGRY;

test(i);
sem_post(&mutex);
sem_wait(&s[i]);
}

void put_forks(int i) {
sem_wait(&mutex);
state[i] = THINKING;

test(LEFT);
test(RIGHT);
sem_post(&mutex);
}

void philosopher(int i) {
while(TRUE) {
think(i);

// sleep(drand48()/10000);
  sleep(1);
take_forks(i);
eat(i);

// sleep(drand48()/10000);
  put_forks(i);
}
}

void* call_philosopher(void* arg){

/*int i = arg;*/
philosopher( (int) arg);
}

int main(){

int i;
pthread_t threads[N];

time_t t1;
time(&t1);

srand48((long) t1);

sem_init(&mutex, 0, 1);

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

for (i=0; i<N; i++) {
pthread_create(threads, NULL, call_philosopher, (void*) i);
}

for (i=0; i<N; i++) pthread_join(threads[i], NULL);


return 0;
}

A seguir, um screenshot para comprovar o bom funcionamento: