The following listing shows an alternative implementation of the system of tokens. This implementation still uses four tokens, so no more than four diners attempt to eat at the same time. However, this implementation uses the sem_wait() and sem_post() semaphore routines to limit the number of eating philosophers. This version of the source file is called din_philo_fix2.c.
You must compiler din_philo_fix2.c with -lrt to link with the appropriate semaphore routines.
The following listing details din_philo_fix2.c:
1 #include <pthread.h> 2 #include <stdio.h> 3 #include <unistd.h> 4 #include <stdlib.h> 5 #include <errno.h> 6 #include <assert.h> 7 #include <semaphore.h> 8 9 #define PHILOS 5 10 #define DELAY 5000 11 #define FOOD 50 12 13 void *philosopher (void *id); 14 void grab_chopstick (int, 15 int, 16 char *); 17 void down_chopsticks (int, 18 int); 19 int food_on_table (); 20 int get_token (); 21 void return_token (); 22 23 pthread_mutex_t chopstick[PHILOS]; 24 pthread_t philo[PHILOS]; 25 pthread_mutex_t food_lock; 26 int sleep_seconds = 0; 27 sem_t num_can_eat_sem; 28 29 30 int 31 main (int argn, 32 char **argv) 33 { 34 int i; 35 36 pthread_mutex_init (&food_lock, NULL); 37 sem_init(&num_can_eat_sem, 0, PHILOS - 1); 38 for (i = 0; i < PHILOS; i++) 39 pthread_mutex_init (&chopstick[i], NULL); 40 for (i = 0; i < PHILOS; i++) 41 pthread_create (&philo[i], NULL, philosopher, (void *)i); 42 for (i = 0; i < PHILOS; i++) 43 pthread_join (philo[i], NULL); 44 return 0; 45 } 46 47 void * 48 philosopher (void *num) 49 { 50 int id; 51 int i, left_chopstick, right_chopstick, f; 52 53 id = (int)num; 54 printf ("Philosopher %d is done thinking and now ready to eat.\n", id); 55 right_chopstick = id; 56 left_chopstick = id + 1; 57 58 /* Wrap around the chopsticks. */ 59 if (left_chopstick == PHILOS) 60 left_chopstick = 0; 61 62 while (f = food_on_table ()) { 63 get_token (); 64 65 grab_chopstick (id, right_chopstick, "right "); 66 grab_chopstick (id, left_chopstick, "left"); 67 68 printf ("Philosopher %d: eating.\n", id); 69 usleep (DELAY * (FOOD - f + 1)); 70 down_chopsticks (left_chopstick, right_chopstick); 71 72 return_token (); 73 } 74 75 printf ("Philosopher %d is done eating.\n", id); 76 return (NULL); 77 } 78 79 int 80 food_on_table () 81 { 82 static int food = FOOD; 83 int myfood; 84 85 pthread_mutex_lock (&food_lock); 86 if (food > 0) { 87 food--; 88 } 89 myfood = food; 90 pthread_mutex_unlock (&food_lock); 91 return myfood; 92 } 93 94 void 95 grab_chopstick (int phil, 96 int c, 97 char *hand) 98 { 99 pthread_mutex_lock (&chopstick[c]); 100 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c); 101 } 102 103 void 104 down_chopsticks (int c1, 105 int c2) 106 { 107 pthread_mutex_unlock (&chopstick[c1]); 108 pthread_mutex_unlock (&chopstick[c2]); 109 } 110 111 112 int 113 get_token () 114 { 115 sem_wait(&num_can_eat_sem); 116 } 117 118 void 119 return_token () 120 { 121 sem_post(&num_can_eat_sem); 122 }
This new implementation uses the semaphore num_can_eat_sem
to
limit the number of philosophers who can eat at the same time. The semaphore num_can_eat_sem
is initialized to four, one less than the number
of philosophers. Before attempting to eat, a philosopher calls get_token() which in turn calls sem_wait(&num_can_eat_sem)
.
The call to sem_wait() causes the calling philosopher to
wait until the semaphore's value is positive, then changes the semaphore's
value by subtracting one from the value. When a philosopher is done eating,
he calls return_token() which in turn calls sem_post(&num_can_eat_sem)
. The call to sem_post() changes the semaphore's
value by adding one. The Thread Analyzer recognizes the calls to sem_wait() and sem_post(), and determines that not all
philosophers attempt to eat concurrently.
If you run this new implementation of the program several times, you will find that it terminates normally each time and does not hang. You will also find that the Thread Analyzer does not report any actual or potential deadlocks, as the following screen-shot shows:
See Appendix A, Thread Analyzer User API for a listing of the threading and memory allocation APIs that the Thread Analyzer recognizes.