The following listing shows the fixed version of the dining philosophers program that uses the token system. This solution incorporates four tokens, one less than the number of diners, so no more than four philosophers can attempt to eat at the same time. This version of the program is called din_philo_fix1.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 8 #define PHILOS 5 9 #define DELAY 5000 10 #define FOOD 50 11 12 void *philosopher (void *id); 13 void grab_chopstick (int, 14 int, 15 char *); 16 void down_chopsticks (int, 17 int); 18 int food_on_table (); 19 int get_token (); 20 void return_token (); 21 22 pthread_mutex_t chopstick[PHILOS]; 23 pthread_t philo[PHILOS]; 24 pthread_mutex_t food_lock; 25 pthread_mutex_t num_can_eat_lock; 26 int sleep_seconds = 0; 27 uint32_t num_can_eat = PHILOS - 1; 28 29 30 int 31 main (int argn, 32 char **argv) 33 { 34 int i; 35 36 pthread_mutex_init (&food_lock, NULL); 37 pthread_mutex_init (&num_can_eat_lock, NULL); 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 int successful = 0; 116 117 while (!successful) { 118 pthread_mutex_lock (&num_can_eat_lock); 119 if (num_can_eat > 0) { 120 num_can_eat--; 121 successful = 1; 122 } 123 else { 124 successful = 0; 125 } 126 pthread_mutex_unlock (&num_can_eat_lock); 127 } 128 } 129 130 void 131 return_token () 132 { 133 pthread_mutex_lock (&num_can_eat_lock); 134 num_can_eat++; 135 pthread_mutex_unlock (&num_can_eat_lock); 136 }
Try compiling and running this fixed version of the dining philosophers program and running it several times. The system of tokens limits the number of diners attempting to use the chopsticks and thus avoids actual and potential deadlocks.
In spite of using the system of tokens, the Thread Analyzer reports a potential deadlock for this implementation even though none exists. This is a false positive. Consider the following screen-shot which details the potential deadlock:
Select the first thread in the chain (Thread #2) and then click on the
Dual Source tab to see the source code location in which Thread #2 held the
lock at address 0x215a8
, and where in the source
code it requested the lock at address 0x215c0
. The
following screen-shot shows the Dual Source tab for Thread #2.
The get_token() function in din_philo_fix1.c uses
a while loop to synchronize the threads. A thread will
not leave the while
loop until it successfully gets
a token (this occurs when num_can_eat
is greater
than zero). The while
loop limits the number of simultaneous
diners to four. However, the synchronization implemented by the while
loop is not recognized by the Thread Analyzer. It assumes that
all five philosophers attempt to grab the chopsticks and eat concurrently,
so it reports a potential deadlock. The following section details how to
limit the number of simultaneous diners by using synchronizations which the
Thread Analyzer recognizes.