"Jantar dos Filósofos" - Uma Solução utilizando Threads e Semáforos

Proposto em 1965 por Esdger Dijkstra, o clássico "Jantar dos Filósofos" ilustra o problema de concorrência em computação, apresentando-se como uma explicação teórica do deadlock.

A situação proposta é a de um mesa de jantar ao redor da qual estão sentados 5 (cinco) filósofos, cada um capaz de realizar apenas duas atividades, mutuamente exclusivas: pensar ou comer.
Na frente de cada filósofo existe um delicioso prato de spaghetti pronto para ser devorado. Um garfo é posicionado entre cada par de filósofos e, considerando a dificuldade para comer tal saboroso macarrão, cada filósofo precisa de dois garfos para fazer sua refeição. Além disso, podem apenas usar o garfo imediatamente à sua direita ou esquerda.

A questão proposta por Dijkstra é então: como programar os filósofos de modo evitar a situação de deadlock, onde todos esperam eternamente para o outro garfo tornar-se disponível?

A seguir, apresentamos o código que implementa uma solução para tal problema, utilizando threads e semáforos. Finalmente, testes são apresentados para comprovar o bom funcionamento da solução.


CÓDIGO-FONTE

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

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

int state[N];       // vetor de estados. um estado para cada filósofo
pthread_mutex_t mutex;     // mutex para região crítica
sem_t *sem[N];       // vetor de semáforos. um sem para cada filósofo.
char *friends[5] = {"Abraham", "Bill", "Carl", "David", "Ellen"};  // pretty-printing para N=5

int dummy[N];

void *philosopher (void *arg);  
void take_forks(int i);    
void put_forks(int i);
void test(int i);
void think(int i);
void eat(int i);
void sem_close_n_unlink(sem_t *semId, char *semName); 
void error_exit(const char*);
char *rand_str(char *mystr, int size);


int main() {

 srand(time(NULL));   // fornecendo seed para uma nova série números pseudo-random
 int res;
 pthread_t philo_thread[N];  // vetor contém uma thread para cada filósofo
 void *thread_result;  // thread resultado para ser usada em pthread_join
 int index;
 
 //init dummy array
 for (index = 0; index < N; index++){
  dummy[index]=index;
 }
 
 // iniciar mutex
 res = pthread_mutex_init(&mutex, NULL);
 if(res != 0){
  perror("Inicializacao de mutex falhou");
  exit(EXIT_FAILURE);
 }

 // iniciar semaforos
 // atencao: em sistemas darwin, utilizamos sem_open ao inves de sem_init
 // no Mac OS X, apenas *semaforos nomeados* estao implementados.
 char *philosem_names[N];
 for (index = 0; index < N; index ++){
  sem[index] = sem_open(rand_str(philosem_names[N],8),O_CREAT,0,0);
 }

 for (index = 0; index < N; index++){
  state[index]=THINKING; //estado inicial dos filosofos
 }
 
 //criar filosofos
 for (index = 0; index < N; index++){
  res = pthread_create(&philo_thread[index], NULL, philosopher, (void *)&dummy[index] );
  if (res != 0){
   perror("Thread creation failed");
   exit(EXIT_FAILURE);
  }
 }

 res = pthread_join(philo_thread[0], &thread_result);
 if (res != 0){
  perror("Thread join failed");
  exit(EXIT_FAILURE);
 }
 printf("Thread joined, it returned this %s\n", (char*)thread_result);

 pthread_mutex_destroy(&mutex);
 // closing and unlink semaphores
 for (index = 0; index < N; index++) {
  sem_close_n_unlink(sem[index], philosem_names[index]);
 }
 return 1;
}

//what does a philopher do?
void *philosopher(void *arg){
 int id = *(int *) arg;
 while(1){
  think(id);
  take_forks(id);
  eat(id);
  put_forks(id);
 }
}

void take_forks(int i) {
 pthread_mutex_lock(&mutex);
 printf("Filosófo %s está com fome\n", friends[i]);
 state[i] = HUNGRY;
 test(i);
 pthread_mutex_unlock(&mutex);
 sem_wait(sem[i]);
}

void put_forks(int i) {
 pthread_mutex_lock(&mutex);
 printf("Filosófo %s está pensando\n", friends[i]);
 state[i] = THINKING;
 test(LEFT);
 test(RIGHT);
 pthread_mutex_unlock(&mutex);
}

void test(int i){
 if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
  printf("Filosófo %s está comendo.  %s está %d. %s está %d.\n",
      friends[i], friends[LEFT],state[LEFT], friends[RIGHT], state[RIGHT]);
  
  state[i] = EATING;
  sem_post(sem[i]);
 }else{
  printf("Filosófo %s está %d.  %s está %d. %s está %d.\n",
      friends[i], state[i], friends[LEFT], state[LEFT], friends[RIGHT], state[RIGHT]);
 }
}

void think(int i){
 sleep(rand() % MAX_THINK_TIME);
}

void eat(int i){
 sleep(rand() % MAX_EAT_TIME);
}

void error_exit(const char *msg) {
 perror(msg);
 exit(EXIT_FAILURE);
}

char *rand_str(char *mystr, int size) {
 if ((mystr = calloc(size + 1, sizeof(char))) == NULL) {
  printf("callor error.\n");
  return NULL;
 }
 
 int aux;
 for (aux = 0; aux < size ; aux++) {
  mystr[aux] = (char)((rand() % 23) + 'a');
 }
 mystr[aux] = '\0';
 
 return mystr;
}

void sem_close_n_unlink(sem_t *semId, char *semName) {

    if (sem_close (semId) == -1) { 
  printf ("sem_close failed\n"); 
  return; 
 } 
 
    if (sem_unlink (semName) == -1) { 
  printf ("sem_unlink failed\n"); 
        return; 
 }  
    printf ("closed and unlinked semaphore\n"); 
}

TESTES
A seguir apresentamos a saída do programa em execução. Esta foi desenvolvida de modo a tornar evidente o bom funcionamento do programa.
Considere o mapeamento: THINKING --> 0, HUNGRY --> 1, EATING --> 2.
A fim de facilitar a compreensão da saída, considere:
"Filósofo Carl está comendo. Bill está 0. David está 0." significa que enquanto o filósofo Carl está comendo, os dois ao seu lado estão pensando, significando que as restrições do problema estão satisfeitas.

Filosófo Carl está com fome
Filosófo Carl está comendo.  Bill está 0. David está 0.
Filosófo Abraham está com fome
Filosófo Abraham está comendo.  Ellen está 0. Bill está 0.
Filosófo Bill está com fome
Filosófo Bill está 1.  Abraham está 2. Carl está 2.
Filosófo Abraham está pensando
Filosófo Ellen está 0.  David está 0. Abraham está 0.
Filosófo Bill está 1.  Abraham está 0. Carl está 2.
Filosófo Carl está pensando
Filosófo Bill está comendo.  Abraham está 0. Carl está 0.
Filosófo David está 0.  Carl está 0. Ellen está 0.
Filosófo David está com fome
Filosófo David está comendo.  Carl está 0. Ellen está 0.
Filosófo Ellen está com fome
Filosófo Ellen está 1.  David está 2. Abraham está 0.
Filosófo Abraham está com fome
Filosófo Abraham está 1.  Ellen está 1. Bill está 2.
Filosófo Bill está pensando
Filosófo Abraham está comendo.  Ellen está 1. Bill está 0.
Filosófo Carl está 0.  Bill está 0. David está 2.
Filosófo David está pensando
Filosófo Carl está 0.  Bill está 0. David está 0.
Filosófo Ellen está 1.  David está 0. Abraham está 2.
Filosófo Ellen está pensando
Filosófo David está 0.  Carl está 0. Ellen está 0.
Filosófo Abraham está 2.  Ellen está 0. Bill está 0.
Filosófo Ellen está com fome
Filosófo Ellen está 1.  David está 0. Abraham está 2.
Filosófo David está com fome
Filosófo David está comendo.  Carl está 0. Ellen está 1.
Filosófo Carl está com fome
Filosófo Carl está 1.  Bill está 0. David está 2.
Filosófo Abraham está pensando
Filosófo Ellen está 1.  David está 2. Abraham está 0.
Filosófo Bill está 0.  Abraham está 0. Carl está 1.
Filosófo Ellen está pensando
Filosófo David está 2.  Carl está 1. Ellen está 0.
Filosófo Abraham está 0.  Ellen está 0. Bill está 0.
Filosófo Abraham está com fome
Filosófo Abraham está comendo.  Ellen está 0. Bill está 0.
Filosófo David está pensando
Filosófo Carl está comendo.  Bill está 0. David está 0.
Filosófo Ellen está 0.  David está 0. Abraham está 2.
Filosófo David está com fome
Filosófo David está 1.  Carl está 2. Ellen está 0.
Filosófo David está pensando
Filosófo Carl está 2.  Bill está 0. David está 0.
Filosófo Ellen está 0.  David está 0. Abraham está 2.
Filosófo Bill está com fome
Filosófo Bill está 1.  Abraham está 2. Carl está 2.