Jantar dos Filósofos utilizando threads

O problema dos filósofos consiste em 5 filósofos sentados em uma mesa circular, realizando duas tarefas: pensar ou comer. Enquanto comem, os filósofos não pensam e enquanto pensam, os filósofos não comem.
Na mesa circular, existe um prato de spaghetti para cada filósofo e existe 1 garfo entre cada dois pratos, exemplificado na imagem abaixo. Para comer, o filósofo necessita dos dois garfos (da sua esquerda e da sua direita).


Este problema também pode gerar um deadlock. Isto ocorre na seguinte situação: suponha que todos os filósofos desejem comer ao mesmo tempo. Assim, todos pegam o seu garfo da esquerda simultaneamente. Ao tentarem pegar o garfo da direita, todos os filósofos esperarão eternamente, pois cada filósofo está segurando um garfo.

Na seguinte solução, utilizaremos threads e semáforos. Uma thread para cada um dos filósofos e semáforos para garantir que situações de deadlock não ocorrerão.
Na solução, mantemos constante a quantidade de tempo que o filósofo permanece comendo e a quantidade de tempo que ele permanece pensando. Cada filósofo permanece em 3 estados: HUNGRY, EATING ou THINKING, explicados no código. Caso se deseje maior aleatoriedade na simulação, é possível alterar estes valores para randômicos, utilizando a função rand().

Utilizaremos as instruções sem_wait e sem_post para controlar o acesso às regiões críticas. Documentação do uso pode ser encontrada em:
http://www.opengroup.org/onlinepubs/007908775/xsh/sem_wait.html
http://www.opengroup.org/onlinepubs/007908799/xsh/sem_post.html

Para criar estes semáforos, vamos utilizar os seguintes comandos sem_t e sem_init:
http://www.opengroup.org/onlinepubs/007908775/xsh/sem_init.html

Além disso, devemos criar as threads. Isto pode ser feito utilizando os seguintes comandos:
declaração: pthread_t
criação: pthread_create() - http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_create.html

Aqui, é interessante notar que ao criarmos a thread, ela inicia sua execução. Contudo, a thread principal não pára sua execução! Assim, é necessário utilizarmos o comando pthread_join para evitar que a thread principal termine o programa, e com isso, mate todas as outras threads.
pthread_join() - http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_join.html

Para aprender mais sobre este problema, visite: http://en.wikipedia.org/wiki/Dining_philosophers_problem

O código obtido utilizado foi o seguinte:

//Bibliotecas utilizadas...
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>

#include <semaphore.h>


#define N 5  /* qtdade de filosofos */
#define LEFT (i+N-1)%N/* calculo do vizinho a esquerda de i */
#define RIGHT (i+1)%N   /* calculo do vizinho a direita de i */
#define THINKING 0 /* filosofo pensando */
#define HUNGRY 1 /* filosofo tentando pegar garfos */
#define EATING 2 /* filosofo comendo */
#define TRUE 1

sem_t s[N];                 //um semaforo por filosofo
sem_t mutex;                //exclusao mutua para regioes cri­ticas

int   state[N];        
//array para controlar o estado dos filosofos
pthread_t thread1, thread2, thread3, thread4, thread5;
//uma thread para cada filósofo


// prototipos...

void take_forks(int i);
void put_forks(int i);

void test(int i);
void think(int i);

void eat(int i);

/* i: numero do filosofo, de 0 a N-1 */

void philosopher(int i) {

while (TRUE) {  /* repete eternamente */
 think(i);  /* o filosofo esta pensando */

 take_forks(i); /* pega dois garfos ou bloqueia */
 eat(i);  /* come espaguete */
 put_forks(i); /* coloca os dois garfos de volta na mesa */

}
}

void take_forks(int i) {

sem_wait(&mutex);//down(&mutex); /* entra na regiao cri­tica */

    state[i] = HUNGRY; /* registra que o filosofo i esta com fome */
printf("philosopher %d HUNGRY\n",i);
test(i);  /* tenta pegar 2 garfos */

sem_post (&mutex);//up(&mutex);  /* sai da regiao cri­tica */
    sem_wait(&s[i]);//down(&s[i]); /* bloqueia se os garfos nao foram pegos */

}

void put_forks(i) {
sem_wait(&mutex); //down(&mutex); /* entra na regiao critica */

    state[i] = THINKING;/* o filosofo acabou de comer */
printf("philosopher %d THINKING\n",i);

test(LEFT);  /* verifica se o vizinho da esquerda pode comer agora */
test(RIGHT); /* verifica se o vizinho da direita pode comer agora */
sem_post(&mutex);//up(&mutex);  /* sai da regiao cri­tica */

}

void test(i) {  //testa se os filosofos vizinhos podem comer
     if (state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING){

   state[i] = EATING;
   printf("philosopher %d EATING\n",i);
   sem_post(&s[i]);//up(&s[i]);

     }
}

void think(int i) {
/*Filosofo esta pensando...*/
sleep(1);

return;
}

void eat(int i) {
/*Filosofo esta comendo...*/

sleep(1);
return;
}

//////////////MAIN FUNCTION////////////////////////
main()
{

int  iret1, iret2, iret3, iret4, iret5;

int i;
int p[N] ;

//inicialização dos semáforos...
int sem_init(sem_t *sem, int pshared, unsigned int value);
     for(i= 0; i < N ;i++ )
{

sem_init(&s[i], 0, 1);
 p[i] = i;
}

sem_init(&mutex, 0, 1);

// criação de threads independentes que executarao a funcao...

iret1 = pthread_create( &thread1, NULL,(void *) philosopher,
(int*)p[1]);

iret2 = pthread_create( &thread2, NULL,(void *) philosopher,
(int*)p[2]);

iret3 = pthread_create( &thread3, NULL,(void *) philosopher,
(int*)p[3]);

iret4 = pthread_create( &thread4, NULL,(void *) philosopher,
(int*)p[4]);

iret5 = pthread_create( &thread5, NULL,(void *) philosopher,
(int*)p[0]);

pthread_join( thread1, NULL);

pthread_join( thread2, NULL);
pthread_join( thread3, NULL);
pthread_join( thread4, NULL);

pthread_join( thread5, NULL);

exit(0);
}

Utilizamos o comando
gcc [[nome_programa.c]] -o [[nome_programa]] -lpthread
para compilar e criar o executável.
Para executar o programa, utilizamos o comando:
./[[nome_programa]]

Assim, obtivemos o seguinte resultado para o programa:

andersonaiziro@Aaiziro:~/Documents$ ./filosofos
philosopher 1 HUNGRY
philosopher 1 EATING
philosopher 2 HUNGRY
philosopher 3 HUNGRY
philosopher 3 EATING
philosopher 4 HUNGRY
philosopher 0 HUNGRY
philosopher 1 THINKING
philosopher 0 EATING
philosopher 2 THINKING
philosopher 3 THINKING
philosopher 4 THINKING
philosopher 0 THINKING
philosopher 1 HUNGRY
philosopher 1 EATING
philosopher 2 HUNGRY
philosopher 3 HUNGRY
philosopher 3 EATING
philosopher 4 HUNGRY
philosopher 0 HUNGRY
philosopher 1 THINKING
philosopher 0 EATING
philosopher 3 THINKING
philosopher 2 EATING
philosopher 0 THINKING
philosopher 4 EATING
philosopher 1 HUNGRY
philosopher 3 HUNGRY
philosopher 0 HUNGRY
philosopher 2 THINKING
philosopher 1 EATING
philosopher 4 THINKING
philosopher 3 EATING
philosopher 1 THINKING
philosopher 0 EATING
philosopher 3 THINKING
philosopher 0 THINKING
philosopher 2 HUNGRY
philosopher 2 EATING
philosopher 4 HUNGRY
philosopher 4 EATING

Para verificar o bom comportamento do sistema, basta perceber que não temos filósofos vizinhos comendo ao mesmo tempo.