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.
The following listing details din_philo_fix2.c:
1 /* 2 * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All Rights Reserved. 3 * @(#)din_philo_fix2.c 1.3 (Oracle) 10/03/26 4 */ 5 6 #include <pthread.h> 7 #include <stdio.h> 8 #include <unistd.h> 9 #include <stdlib.h> 10 #include <errno.h> 11 #include <assert.h> 12 #include <semaphore.h> 13 14 #define PHILOS 5 15 #define DELAY 5000 16 #define FOOD 100 17 18 void *philosopher (void *id); 19 void grab_chopstick (int, 20 int, 21 char *); 22 void down_chopsticks (int, 23 int); 24 int food_on_table (); 25 void get_token (); 26 void return_token (); 27 28 pthread_mutex_t chopstick[PHILOS]; 29 pthread_t philo[PHILOS]; 30 pthread_mutex_t food_lock; 31 int sleep_seconds = 0; 32 sem_t num_can_eat_sem; 33 34 35 int 36 main (int argn, 37 char **argv) 38 { 39 int i; 40 41 pthread_mutex_init (&food_lock, NULL); 42 sem_init(&num_can_eat_sem, 0, PHILOS - 1); 43 for (i = 0; i < PHILOS; i++) 44 pthread_mutex_init (&chopstick[i], NULL); 45 for (i = 0; i < PHILOS; i++) 46 pthread_create (&philo[i], NULL, philosopher, (void *)i); 47 for (i = 0; i < PHILOS; i++) 48 pthread_join (philo[i], NULL); 49 return 0; 50 } 51 52 void * 53 philosopher (void *num) 54 { 55 int id; 56 int i, left_chopstick, right_chopstick, f; 57 58 id = (int)num; 59 printf ("Philosopher %d is done thinking and now ready to eat.\n", id); 60 right_chopstick = id; 61 left_chopstick = id + 1; 62 63 /* Wrap around the chopsticks. */ 64 if (left_chopstick == PHILOS) 65 left_chopstick = 0; 66 67 while (f = food_on_table ()) { 68 get_token (); 69 70 grab_chopstick (id, right_chopstick, "right "); 71 grab_chopstick (id, left_chopstick, "left"); 72 73 printf ("Philosopher %d: eating.\n", id); 74 usleep (DELAY * (FOOD - f + 1)); 75 down_chopsticks (left_chopstick, right_chopstick); 76 77 return_token (); 78 } 79 80 printf ("Philosopher %d is done eating.\n", id); 81 return (NULL); 82 } 83 84 int 85 food_on_table () 86 { 87 static int food = FOOD; 88 int myfood; 89 90 pthread_mutex_lock (&food_lock); 91 if (food > 0) { 92 food--; 93 } 94 myfood = food; 95 pthread_mutex_unlock (&food_lock); 96 return myfood; 97 } 98 99 void 100 grab_chopstick (int phil, 101 int c, 102 char *hand) 103 { 104 pthread_mutex_lock (&chopstick[c]); 105 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c); 106 } 107 108 void 109 down_chopsticks (int c1, 110 int c2) 111 { 112 pthread_mutex_unlock (&chopstick[c1]); 113 pthread_mutex_unlock (&chopstick[c2]); 114 } 115 116 117 void 118 get_token () 119 { 120 sem_wait(&num_can_eat_sem); 121 } 122 123 void 124 return_token () 125 { 126 sem_post(&num_can_eat_sem); 127 }
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. Thread Analyzer recognizes the calls to sem_wait() and sem_post(), and determines that not all philosophers attempt to eat concurrently.
To compile din_philo_fix2.c, use the following command:
% cc -g -lrt -o din_philo_fix2 din_philo_fix2.c
If you run this new implementation of the program din_philo_fix2 several times, you will find that it terminates normally each time and does not hang.
To create an experiment on this new binary:
% collect -r deadlock -o din_philo_fix2.1.er din_philo_fix2
You will find that Thread Analyzer does not report any actual or potential deadlocks in the din_philo_fix2.1.er experiment, as the following figure shows.
Figure 3-7 Deadlocks Not Reported in din_philo_fix2.c
See Appendix A, APIs Recognized by Thread Analyzer for a listing of the threading and memory allocation APIs that Thread Analyzer recognizes.