/****************************************************************************** * Grupo: * * Gustavo Sverzut Barbieri * * Ivens Prates Telles Alves * * Tiago Moreira de Melo * ****************************************************************************** * * * Solução para o problema dos filósofos famintos * * * * Idéia: * * Quando um filósofo for comer, ele vê se isto é possível olhando para * * os filósofos vizinhos. Se for possível ele pega os garfos e come. Se não* * for, ele fica esperando ser chamado pelos que devolveram os garfos. * * O processo de devolução dos garfos é o seguinte: o filósofo ao * * devolver o garfo, verifica se o filósofo vizinho quer comer ( e portanto* * está esperando o garfo), se estiver ele o avisa. * * Porém, nesta solução um filósofo muito azarado pode morrer de fome! * * * ****************************************************************************** * * * This code is documented using the Doxygen tags, so you can run: * * doxygen Doxyfile * * If "Doxyfile" doesn't exist you may create one using doxywizard * * You can get Doxygen at: http://www.doxygen.org * * * ****************************************************************************** * * * Libraries used: * * - pthread * * Compilation Example: * * gcc -g 03_mutex-cond-death.c -o 03_mutex-cond-death -lpthread * * * ****************************************************************************** * (C) GPL - General Public License * * http://www.fsf.org * ****************************************************************************** */ #include "03_mutex-cond-death.h" void *pthread_philosopher( void *p ) { int i = *(int *)p; philosopher(i); return NULL; } void philosopher( int i ) { /* * This sleep (together with others below, see think() and * eat()) will simulate a situation where the philosopher#4 will * never eat! */ if ( ( i == 4 ) || ( i == 3 ) ) sleep( 2 ); while ( meals < MAX_MEALS ) { think( i ); take_forks( i ); eat( i ); put_forks( i ); } /* if printing, wait. If not, continue, blocking the printing */ pthread_mutex_lock( &printing ); printf( "Philosopher %d has left the table!\n", i ); /* signal others can print */ pthread_mutex_unlock( &printing ); } void think(int i) { /* think */ /* * These sleeps (together with others above and below, see eat() and * philosophers()) will simulate a situation where the philosopher#4 will * never eat! */ if ( ( i == 0 ) || ( i == 3 ) ) sleep( 1 ); if ( ( i == 1 ) || ( i == 2 ) ) sleep( 2 ); } void eat(int i) { if ( meals < MAX_MEALS ) { meals++; /* note: here we are not using a MUTEX because if we have some meals more doesn't matter at all. */ philosophers_meals[ i ]++; /* eat */ /* * These sleeps (together with others above, see think() and * philosophers()) will simulate a situation where the philosopher#4 will * never eat! */ if ( ( i == 0 ) || ( i == 3 ) ) sleep( 3 ); if ( ( i == 1 ) || ( i == 2 ) ) sleep( 1 ); } } void take_forks( int i ) { /* lock, so only us can update the state */ pthread_mutex_lock( &mutex ); /* * Say he is HUNGRY */ /* if printing, wait. If not, continue, blocking the printing */ pthread_mutex_lock( &printing ); /* Say he is hungry */ state[ i ] = HUNGRY ; /* Print the table */ print_table(); /* signal others can print */ pthread_mutex_unlock( &printing ); /* * he can eat? If yes, eat, if not wait * * Note: the following and the test_other() are need to replace the * algorithm based on semaphores by one based on pthread_cond and * pthread_mutex. */ if ( ( state[ i ] == HUNGRY ) && ( state[ LEFT ] != EATING ) && ( state[ RIGHT ] != EATING ) && ( meals < MAX_MEALS ) ) { /* * yes, so eat. */ /* if printing, wait. If not, continue, blocking the printing */ pthread_mutex_lock( &printing ); forks_position[ i ] = '>'; forks_position[ ( i + 1 ) % N ] = '<'; /* Say he is eating */ state[ i ] = EATING ; /* Print the table */ print_table(); /* signal others can print */ pthread_mutex_unlock( &printing ); pthread_cond_signal( &philosophers[ i ] ); /* unlock, so others can update the state */ pthread_mutex_unlock( &mutex ); } else { /* * No, wait. (but first release the mutex!) */ /* unlock, so others can update the state */ pthread_mutex_unlock( &mutex ); if ( meals < MAX_MEALS ) { /* * wait for others to signal us when they finish */ /* lock the philosopher's mutex */ pthread_mutex_lock( &philosophers_mutex[ i ] ); /* wait on philospher's condition variable */ pthread_cond_wait( &philosophers[ i ], &philosophers_mutex[ i ] ); /* unlock the philosopher's mutex */ pthread_mutex_unlock( &philosophers_mutex[ i ] ); } } } void put_forks( int i ) { /* lock, so only us can update the state */ pthread_mutex_lock( &mutex ); /* * change state to thinking, since we're not eating anymore */ /* if printing, wait. If not, continue, blocking the printing */ pthread_mutex_lock( &printing ); forks_position[ i ] = '|'; forks_position[ ( i + 1 ) % N ] = '|'; /* Say he is thinking */ state[ i ] = THINKING ; /* Print the table */ print_table(); /* signal others can print */ pthread_mutex_unlock( &printing ); /* * test and eventually signal neighbors to eat (if they're able to) */ test_other( LEFT ); test_other( RIGHT ); /* unlock, so others can update the state */ pthread_mutex_unlock( &mutex ); } void test_other( int i ) { /* he's hungry and he can eat? */ if ( ( state[ i ] == HUNGRY ) && ( state[ LEFT ] != EATING ) && ( state[ RIGHT ] != EATING ) ) { if ( meals < MAX_MEALS ) { /* if printing, wait. If not, continue, blocking the printing */ pthread_mutex_lock( &printing ); forks_position[ i ] = '>'; forks_position[ ( i + 1 ) % N ] = '<'; /* Say he is eating */ state[ i ] = EATING ; /* Print the table */ print_table(); /* signal others can print */ pthread_mutex_unlock( &printing ); } pthread_cond_signal( &philosophers[ i ] ); } } void print_table() { int i; /* print the philosophers states */ for ( i = 0; i < N; i++ ) { switch ( forks_position[ i ] ) { case '|': printf( " | " ); break; case '>': printf( " >" ); break; case '<': if ( i == 0 ) printf( " " ); else printf( "< " ); break; default: break; } #ifndef COLOR printf( "%c", state_letters[ state[ i ] ] ); #else switch (state[ i ]) { case HUNGRY: printf( "\033[0;31m" ); break; case THINKING: printf( "\033[1;33m" ); break; case EATING: printf( "\033[0;32m" ); break; default: break; } printf( "%c\033[0m", state_letters[ state[ i ] ] ); #endif if ( ( i == N - 1 ) && ( forks_position[ ( i + 1 ) % N ] == '<' ) ) printf( "<"); } printf( "\n" ); } /** * The main program */ int main() { int i; /* general counter */ pthread_t threads[ N ]; /* philosopher/thread */ int id[ N ]; /* philosopher/thread id */ /* * Init */ for ( i = 0; i < N; i++ ) { /* philosophers condition variables */ pthread_cond_init( &philosophers[ i ], NULL ); /* philosophers mutexes */ pthread_mutex_init( &philosophers_mutex[ i ], NULL ); /* forks position */ forks_position[ i ] = '|'; /* philosophers had made any meal */ philosophers_meals[ i ] = 0; } /* printing mutex */ pthread_mutex_init( &printing, NULL ); /* critical regions mutex */ pthread_mutex_init( &mutex, NULL ); /* states */ for ( i = 0; i < N; i++ ) state[i] = THINKING ; /* print the table */ print_table(); /* * Lauch threads */ for ( i = 0; i < N; i++ ) { id[ i ] = i ; pthread_create( &threads[ i ], NULL, pthread_philosopher , &id[ i ] ); } /* * Wait for threads */ for ( i = 0; i < N; i++ ) { pthread_join( threads[ i ], NULL ); } printf( ".-------------.-------.\n" "| Philosopher | Meals |\n" "}-------------+-------{\n" ); for ( i = 0; i < N; i++ ) { printf( "| % 11d | % 5d |", i, philosophers_meals[ i ] ); if ( philosophers_meals[ i ] == 0 ) { #ifdef COLOR printf("\033[1;31m"); #endif printf("DEAD!"); #ifdef COLOR printf("\033[0m"); #endif } printf( "\n" ); } printf( "`-------------'-------'\n" ); return 0; } /* author: Gustavo Sverzut Barbieri (http://www.gustavobarbieri.com.br) */