Lesson of 4 March 2011 (part a)

The philosophes problem

A NOT working example using pthread_cond_wait

File thread-filosofi.cc

  1/*
  2   NOT Working version of 5 Philosopher
  3
  4   to compile: g++ thread-filosofi.cc 
  5*/
  6
  7#include <pthread.h>
  8#include <iostream>
  9#include <unistd.h> // for sleep
 10
 11using namespace std ;
 12
 13#define N_PHILOSOPHES 5
 14
 15pthread_mutex_t mutex_var ;
 16pthread_cond_t  cond_var ;
 17
 18#define LEFT_FORK(N) (N)
 19#define RIGHT_FORK(N) (((N)+1) % N_PHILOSOPHES )
 20
 21typedef enum { THINK, EAT, SLEEP } Philosopher_STATE ;
 22typedef enum { FREE,  INUSE      } Fork_STATE ;
 23
 24static Philosopher_STATE philosopher_state[N_PHILOSOPHES] ;
 25static Fork_STATE        fork_state[N_PHILOSOPHES] ;
 26
 27void
 28get_right_fork( int const n ) {
 29  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 30  int right_fork = RIGHT_FORK(n) ;
 31  if ( fork_state[right_fork] == INUSE ) {
 32    cout << "Philosopher " << n << " waiting for the right fork!\n" ;
 33    while ( fork_state[right_fork] == INUSE ) ; // stupid loop waiting resource
 34  }
 35  fork_state[right_fork] = INUSE ; /* si accaparra la forchetta */
 36  cout << "Philosopher " << n << " acquired the right fork!\n" ;
 37  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 38}
 39
 40void
 41get_left_fork( int const n) {
 42  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 43  int left_fork = LEFT_FORK(n) ;
 44  if ( fork_state[left_fork] == INUSE ) {
 45    cout << "Philosopher " << n << " waiting for the left fork!\n" ;
 46    while ( fork_state[left_fork] == INUSE ) ; // stupid loop waiting resource
 47  }
 48  fork_state[left_fork] = INUSE ; /* si accaparra la forchetta */
 49  cout << "Philosopher " << n << " acquired the left fork!\n" ;
 50  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 51}
 52
 53void
 54drop_right_fork( int const n ) {
 55  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 56  int right_fork = RIGHT_FORK(n) ;
 57  fork_state[right_fork] = FREE ;
 58  cout << "Philosopher " << n << " drop the right fork!\n" ;
 59  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 60}
 61
 62void
 63drop_left_fork( int const n) {
 64  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 65  int left_fork = LEFT_FORK(n) ;
 66  fork_state[left_fork] = FREE ;
 67  cout << "Philosopher " << n << " drop the left fork!\n" ;
 68  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 69}
 70
 71void *
 72philosopher( void *arg ) {
 73
 74  long n = (long) arg ;
 75  
 76  // put a barrier for wait a go signal
 77  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 78  cout << "Philosopher " << n << " is waiting to start\n" ;
 79  pthread_cond_wait(&cond_var,&mutex_var);
 80  cout << "Philosopher " << n << " is started\n" ;
 81  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 82
 83  while ( true ) { // infinity loop
 84    // thinking
 85    philosopher_state[n] = THINK ;
 86    cout << "Philosopher " << n << " is THINKING\n" ;
 87    get_right_fork( n ) ;
 88    get_left_fork( n ) ;
 89    
 90    // eating
 91    philosopher_state[n] = EAT ;
 92    cout << "Philosopher " << n << " is EATING\n" ;
 93    drop_right_fork( n ) ;
 94    drop_left_fork( n ) ;
 95    
 96    // sleeping
 97    philosopher_state[n] = SLEEP ;
 98    cout << "Philosopher " << n << " is SLEEPING\n" ;
 99    //sleep(1) ;
100  }
101  pthread_exit(NULL) ;
102}
103
104void *
105monitor(void *arg) {
106  while ( true ) { /* ciclo infinito */
107    sleep(1) ; /* aspetta un secondo */
108    cout << "\nPhilosophes:  " ;
109    for ( int i = 0 ; i < N_PHILOSOPHES ; ++i ) {
110      switch ( philosopher_state[i] ) {
111        case THINK:  printf(" T") ; break ;
112        case EAT:    printf(" E") ; break ;
113        case SLEEP:  printf(" S") ; break ;
114      }
115    }
116    cout << "\nForks:        " ;
117    for ( int i = 0 ; i < N_PHILOSOPHES ; ++i ) {
118      switch ( fork_state[i] ) {
119        case FREE:  cout << " F" ; break ;
120        case INUSE: cout << " U" ; break ;
121      }
122    }
123    cout << endl ;
124  }
125  pthread_exit(NULL) ;
126}
127
128int
129main(int argc, char *argv) { 
130  pthread_t philosopher_thread[N_PHILOSOPHES], monitor_thread ;
131
132  if ( pthread_mutex_init(&mutex_var, NULL) ) { // allocate resorce for mutex mutex_var
133    cerr << "Error while creating mutex\n" ; 
134    exit(1);  
135  }
136
137  if ( pthread_cond_init(&cond_var, NULL) ) { // allocate resorce for condition variable
138    cerr << "Error while creating condition\n" ; 
139    exit(1);  
140  }
141
142  // initialize the status of the philosophes
143  for ( int i = 0 ; i < N_PHILOSOPHES ; ++i ) {
144    philosopher_state[i] = SLEEP ;
145    fork_state[i]        = FREE ;
146  }
147
148  // create threads for philosophes
149  for ( long i = 0 ; i < N_PHILOSOPHES ; ++i ) {
150    cout << "Creo il filosofo " << i << "\n" ;
151    if ( pthread_create(&philosopher_thread[i], NULL, philosopher, (void *) i) ) { 
152      cerr << "Error while creating thread\n" ; 
153      exit(1);
154    }
155    sleep(1) ;
156  }
157
158  // create threads for monitor
159  if ( pthread_create(&monitor_thread, NULL, monitor, NULL) ) { 
160    cerr << "Error while creating thread\n" ; 
161    exit(1);
162  }
163
164  // start philosopher  
165  if ( pthread_cond_signal( &cond_var ) ) {
166    cerr << "Error while signaling a condition to a thread\n" ; 
167    exit(1);  
168  }
169  sleep(5) ;
170  if ( pthread_cond_broadcast( &cond_var ) ) {
171    cerr << "Error while signaling a condition to a thread\n" ; 
172    exit(1);  
173  }
174
175  // wait for thread termination
176  pthread_exit(NULL) ;
177  return 0 ;
178}

A NOT working example with syncronized start of philosophes

File thread-filosofi-2.cc

  1/*
  2   NOT Working version of 5 Philosopher
  3   
  4   to compile: g++ thread-filosofi-2.cc 
  5
  6*/
  7
  8#include <pthread.h>
  9#include <iostream>
 10#include <iomanip>  // for setw
 11#include <unistd.h> // for sleep
 12
 13using namespace std ;
 14
 15#define N_PHILOSOPHES 5
 16
 17#define LEFT_FORK(N) (N)
 18#define RIGHT_FORK(N) (((N)+1) % N_PHILOSOPHES )
 19
 20pthread_mutex_t mutex_var ;
 21pthread_cond_t  cond_var, cond_fork[N_PHILOSOPHES] ;
 22
 23typedef enum { THINK, EAT, SLEEP } Philosopher_STATE ;
 24
 25static Philosopher_STATE philosopher_state[N_PHILOSOPHES] ;
 26static int               fork_state[N_PHILOSOPHES] ; 
 27static int const FORK_FREE = -1 ; // -1 is free otherwise the philosopher using the fork
 28
 29bool
 30get_right_fork( int const n ) {
 31  int right_fork = RIGHT_FORK(n) ;
 32
 33  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 34  if ( fork_state[right_fork] != FORK_FREE ) {
 35    cout << "Philosopher " << n << " waiting for the right fork!\n" ;
 36    while ( fork_state[right_fork] != FORK_FREE )
 37      pthread_cond_wait(&cond_fork[right_fork],&mutex_var) ; // intelligent loop waiting resource
 38  }
 39  fork_state[right_fork] = n ; // philosopher n acquire the fork
 40  cout << "Philosopher " << n << " acquired the right fork!\n" ;
 41  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 42}
 43
 44bool
 45get_left_fork( int const n) {
 46  int left_fork = LEFT_FORK(n) ;
 47
 48  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 49  if ( fork_state[left_fork] != FORK_FREE ) {
 50    cout << "Philosopher " << n << " waiting for the left fork!\n" ;
 51    while ( fork_state[left_fork] != FORK_FREE )
 52      pthread_cond_wait(&cond_fork[left_fork],&mutex_var) ; // intelligent loop waiting resource
 53  }
 54  fork_state[left_fork] = n ; // philosopher n acquire the fork
 55  cout << "Philosopher " << n << " acquired the left fork!\n" ;
 56  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 57}
 58
 59void
 60drop_right_fork( int const n ) {
 61  int right_fork = RIGHT_FORK(n) ;
 62  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 63  fork_state[right_fork] = FORK_FREE ;
 64  cout << "Philosopher " << n << " drop the right fork!\n" ;
 65  pthread_cond_signal( &cond_fork[right_fork] ) ; // signal that fork is fred
 66  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 67}
 68
 69void
 70drop_left_fork( int const n) {
 71  int left_fork = LEFT_FORK(n) ;
 72  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 73  fork_state[left_fork] = FORK_FREE ;
 74  cout << "Philosopher " << n << " drop the left fork!\n" ;
 75  pthread_cond_signal( &cond_fork[left_fork] ) ; // signal that fork is fred
 76  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 77}
 78
 79void *
 80philosopher( void *arg ) {
 81
 82  long n = (long) arg ;
 83  
 84  // put a barrier for wait a go signal
 85  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 86  cout << "Philosopher " << n << " is waiting to start\n" ;
 87  pthread_cond_wait(&cond_var,&mutex_var);
 88  cout << "Philosopher " << n << " is started\n" ;
 89  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 90
 91  while ( true ) { // infinity loop
 92    // thinking
 93    philosopher_state[n] = THINK ;
 94    cout << "Philosopher " << n << " is THINKING\n" ;
 95    get_right_fork( n ) ;
 96    get_left_fork( n ) ;
 97    
 98    // eating
 99    philosopher_state[n] = EAT ;
100    cout << "Philosopher " << n << " is EATING\n" ;
101    drop_right_fork( n ) ;
102    drop_left_fork( n ) ;
103    
104    // sleeping
105    philosopher_state[n] = SLEEP ;
106    cout << "Philosopher " << n << " is SLEEPING\n" ;
107    //sleep(1) ;
108  }
109  pthread_exit(NULL) ;
110}
111
112void *
113monitor(void *arg) {
114  while ( true ) { /* ciclo infinito */
115    sleep(1) ; /* aspetta un secondo */
116    cout << "\nPhilosophes:  " ;
117    for ( int i = 0 ; i < N_PHILOSOPHES ; ++i ) {
118      switch ( philosopher_state[i] ) {
119        case THINK:  printf(" T") ; break ;
120        case EAT:    printf(" E") ; break ;
121        case SLEEP:  printf(" S") ; break ;
122      }
123    }
124    cout << "\nForks:        " ;
125    for ( int i = 0 ; i < N_PHILOSOPHES ; ++i ) {
126      if ( fork_state[i] == FORK_FREE ) cout << " F" ;
127      else                              cout << setw(2) << fork_state[i] ;
128    }
129    cout << endl ;
130  }
131  pthread_exit(NULL) ;
132}
133
134int
135main(int argc, char *argv) { 
136  pthread_t philosopher_thread[N_PHILOSOPHES], monitor_thread ;
137
138  if ( pthread_mutex_init(&mutex_var, NULL) ) { // allocate resorce for mutex mutex_var
139    cerr << "Error while creating mutex\n" ; 
140    exit(1);  
141  }
142
143  if ( pthread_cond_init(&cond_var, NULL) ) { // allocate resorce for condition variable
144    cerr << "Error while creating condition\n" ; 
145    exit(1);  
146  }
147
148  // initialize the status of the philosophes
149  for ( int i = 0 ; i < N_PHILOSOPHES ; ++i ) {
150    philosopher_state[i] = SLEEP ;
151    fork_state[i]        = FORK_FREE ;
152  }
153
154  // create threads for philosophes
155  for ( long i = 0 ; i < N_PHILOSOPHES ; ++i ) {
156    cout << "Creo il filosofo " << i << "\n" ;
157    if ( pthread_create(&philosopher_thread[i], NULL, philosopher, (void *) i) ) { 
158      cerr << "Error while creating thread\n" ; 
159      exit(1);
160    }
161    sleep(1) ;
162  }
163
164  // create threads for monitor
165  if ( pthread_create(&monitor_thread, NULL, monitor, NULL) ) { 
166    cerr << "Error while creating thread\n" ; 
167    exit(1);
168  }
169
170  // start philosopher  
171  if ( pthread_cond_signal( &cond_var ) ) {
172    cerr << "Error while signaling a condition to a thread\n" ; 
173    exit(1);  
174  }
175  sleep(1) ;
176  if ( pthread_cond_broadcast( &cond_var ) ) {
177    cerr << "Error while signaling a condition to a thread\n" ; 
178    exit(1);  
179  }
180
181  // wait for thread termination
182  pthread_exit(NULL) ;
183  return 0 ;
184}

A WORKING example of the the philosophes problem

File thread-filosofi-3.cc

  1/*
  2  Working version of 5 Philosopher
  3  
  4  to compile: g++ thread-filosofi-3.cc 
  5
  6*/
  7
  8#include <pthread.h>
  9#include <iostream>
 10#include <iomanip>  // for setw
 11#include <unistd.h> // for sleep
 12#include <sys/time.h> // for timeval
 13
 14using namespace std ;
 15
 16#define N_PHILOSOPHES 5
 17
 18#define LEFT_FORK(N) (N)
 19#define RIGHT_FORK(N) (((N)+1) % N_PHILOSOPHES )
 20
 21pthread_mutex_t mutex_var ;
 22pthread_cond_t  cond_var, cond_fork[N_PHILOSOPHES] ;
 23
 24typedef enum { THINK, EAT, SLEEP } Philosopher_STATE ;
 25
 26static Philosopher_STATE philosopher_state[N_PHILOSOPHES] ;
 27static int               fork_state[N_PHILOSOPHES] ; 
 28static int const FORK_FREE = -1 ; // -1 is free otherwise the philosopher using the fork
 29
 30static char const * left_right[] = { "left", "right" } ;
 31
 32static int eat[N_PHILOSOPHES] ; // count number of eating!
 33
 34void
 35drop_fork( int const np, /* the philosopher */
 36           int const lr  /* 0 = left fork, 1 == right fork */  ) {
 37  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 38  int nf = (np+lr) % N_PHILOSOPHES ;
 39
 40  if ( fork_state[nf] == FORK_FREE ) {
 41    cerr << "Fatal error try to free fork " << nf << " already free!!!\n" ;
 42    exit(1) ;
 43  }
 44  fork_state[nf] = FORK_FREE ;
 45  cout << "Philosopher " << np << " drop the " << left_right[lr] << " fork!\n" ;
 46  pthread_cond_signal( &cond_fork[nf] ) ; // signal that fork is fred
 47  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 48}
 49
 50void
 51get_fork( int const np, /* the philosopher */
 52          int const lr  /* 0 = left fork, 1 == right fork */ ) {
 53  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 54  int nf = (np+lr) % N_PHILOSOPHES ;
 55  while ( fork_state[nf] != FORK_FREE ) // fork not free, wait
 56    pthread_cond_wait(&cond_fork[nf],&mutex_var) ; // intelligent loop waiting resource
 57  // fork now is free, use it
 58  fork_state[nf] = np ;
 59  cout << "Philosopher " << np << " acquired " << left_right[lr] << " fork!\n" ;
 60  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 61}
 62
 63bool
 64get_fork_with_timeout( int const np, /* the philosopher */
 65                       int const lr  /* 0 = left fork, 1 == right fork */ ) {
 66
 67  // setup for the TIMEOUT
 68  struct timeval  now ;
 69  struct timespec tout ;
 70
 71  if ( gettimeofday(&now, NULL) != 0 ) {
 72    cerr << "failed gettimeofday\n" ;
 73    exit(1) ;
 74  }
 75  tout . tv_sec  = now . tv_sec + 5 ;
 76  tout . tv_nsec = 0 ; // now . tv_usec * 1000 ;
 77
 78  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
 79
 80  int nf = (np+lr) % N_PHILOSOPHES ;
 81  int ok = 0 ;
 82  if ( fork_state[nf] != FORK_FREE )
 83    ok = pthread_cond_timedwait(&cond_fork[nf],&mutex_var,&tout) ;
 84
 85  if ( fork_state[nf] == FORK_FREE ) { // fork aquired!
 86    fork_state[nf] = np ;
 87    cout << "Philosopher " << np << " acquired " << left_right[lr] << " fork!\n" ;
 88    pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 89    return true ;
 90  } else { // fork not acquired
 91    cout << "Philosopher " << np << " failed to acquire " << left_right[lr] << " fork!\n" ;
 92    pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
 93    return false ;  
 94  }
 95}
 96
 97bool
 98get_right_fork( int const n ) {
 99  return get_fork_with_timeout( n, 1 ) ;
100  //return get_fork( n, 1 ) ;
101}
102
103bool
104get_left_fork( int const n) {
105  return get_fork_with_timeout( n, 0 ) ;
106  //return get_fork( n, 0 ) ;
107}
108
109void
110drop_right_fork( int const n ) {
111  drop_fork( n, 1 ) ;
112}
113
114void
115drop_left_fork( int const n) {
116  drop_fork( n, 0 ) ;
117}
118
119void *
120philosopher( void *arg ) {
121
122  long n = (long) arg ;
123  
124  // put a barrier for wait a go signal
125  pthread_mutex_lock(&mutex_var) ; // enter in the critical section
126  cout << "Philosopher " << n << " is waiting to start\n" ;
127  pthread_cond_wait(&cond_var,&mutex_var);
128  cout << "Philosopher " << n << " is started\n" ;
129  pthread_mutex_unlock(&mutex_var) ; // exit from the critical section
130
131  while ( true ) { // infinity loop
132    // thinking
133    philosopher_state[n] = THINK ;
134    cout << "Philosopher " << n << " is THINKING\n" ;
135    
136    // try to change state
137    bool ok = false ;
138    while ( !ok ) {
139      ok = get_right_fork( n ) && get_left_fork( n ) ;
140      if ( !ok ) { // fork not FULLY acquired, drop it 
141        if ( fork_state[LEFT_FORK(n)]  == n ) drop_left_fork( n ) ;
142        if ( fork_state[RIGHT_FORK(n)] == n ) drop_right_fork( n ) ;
143        sleep(1) ;
144      }
145    }
146
147    // eating
148    ++eat[n] ;
149    philosopher_state[n] = EAT ;
150    cout << "Philosopher " << n << " is EATING\n" ;
151    sleep(2) ;
152    drop_right_fork( n ) ;
153    drop_left_fork( n ) ;
154
155    // sleeping
156    philosopher_state[n] = SLEEP ;
157    cout << "Philosopher " << n << " is SLEEPING\n" ;
158    sleep(1) ;
159  }
160  pthread_exit(NULL) ;
161}
162
163void *
164monitor(void *arg) {
165  while ( true ) { /* ciclo infinito */
166    sleep(1) ; /* aspetta un secondo */
167    cout << "\nPhilosophes:  " ;
168    for ( int i = 0 ; i < N_PHILOSOPHES ; ++i ) {
169      switch ( philosopher_state[i] ) {
170        case THINK:  printf("   T") ; break ;
171        case EAT:    printf("   E") ; break ;
172        case SLEEP:  printf("   S") ; break ;
173      }
174    }
175    cout << "\nForks:        " ;
176    for ( int i = 0 ; i < N_PHILOSOPHES ; ++i ) {
177      if ( fork_state[i] == FORK_FREE ) cout << "   F" ;
178      else                              cout << setw(4) << fork_state[i] ;
179    }
180    cout << "\nEat Number:   " ;
181    for ( int i = 0 ; i < N_PHILOSOPHES ; ++i ) cout << setw(3) << " " << eat[i] ;
182    cout << endl ;
183  }
184  pthread_exit(NULL) ;
185}
186
187int
188main(int argc, char *argv) { 
189  pthread_t philosopher_thread[N_PHILOSOPHES], monitor_thread ;
190
191  if ( pthread_mutex_init(&mutex_var, NULL) ) { // allocate resorce for mutex mutex_var
192    cerr << "Error while creating mutex\n" ; 
193    exit(1);  
194  }
195
196  if ( pthread_cond_init(&cond_var, NULL) ) { // allocate resorce for condition variable
197    cerr << "Error while creating condition\n" ; 
198    exit(1);  
199  }
200
201  // initialize the status of the philosophes
202  for ( int i = 0 ; i < N_PHILOSOPHES ; ++i ) {
203    philosopher_state[i] = SLEEP ;
204    fork_state[i]        = FORK_FREE ;
205    eat[i]               = 0 ;
206    if ( pthread_cond_init(&cond_fork[i], NULL) ) { // allocate resorce for condition variable
207      cerr << "Error while creating condition\n" ; 
208      exit(1);  
209    }
210  }
211
212  // create threads for philosophes
213  for ( long i = 0 ; i < N_PHILOSOPHES ; ++i ) {
214    cout << "Creo il filosofo " << i << "\n" ;
215    if ( pthread_create(&philosopher_thread[i], NULL, philosopher, (void *) i) ) { 
216      cerr << "Error while creating thread\n" ; 
217      exit(1);
218    }
219    sleep(1) ;
220  }
221
222  // create threads for monitor
223  if ( pthread_create(&monitor_thread, NULL, monitor, NULL) ) { 
224    cerr << "Error while creating thread\n" ; 
225    exit(1);
226  }
227
228  // start philosopher  
229  if ( pthread_cond_signal( &cond_var ) ) {
230    cerr << "Error while signaling a condition to a thread\n" ; 
231    exit(1);  
232  }
233  sleep(1) ;
234  if ( pthread_cond_broadcast( &cond_var ) ) {
235    cerr << "Error while signaling a condition to a thread\n" ; 
236    exit(1);  
237  }
238
239  // wait for thread termination
240  pthread_exit(NULL) ;
241  return 0 ;
242}