There are N philosophers spending their lives thinking and eating in a room. In their round table there is a plate of infinite rice and N chopsticks. From time to time, a philosopher gets hungry. He tries to pick up the two chopsticks that are on his right and his left. A philosopher that picks both chopsticks successfully (one at a time) starts eating. A philosopher may pick one chopstick at a time.
When a philosopher finishes eating, he puts down both of his chopsticks to their original position and he starts thinking again. The question is to write a program which does not let any philosopher to die due to hunger (i.e. no deadlocks).
#define N 6 /* number of philosophers */
semaphore chopstick[N] /* a semaphore for each chopstick,
each to be initialized to 1 */
void philosopher(int i) /* which philosopher (0 to N-1) ? */
{
while (TRUE)
{
think(); /* philosopher is thinking */
down(chopstick[i]); /* take left chopstick */
down(chopstick [(i+1) % N]); /* take right chopstick */
eat(); /* yum-yum, rice */
up(chopstick[i]); /* put left chopstick */
up(chopstick [(i+1) % N]); /* put left chopstick */
}
}
Unfortunately, this program fails in the situation when all philosophers take their left chopsticks simultaneously. None will able to take their right chopsticks, there will be a deadlock, and all of them will die because of hunger.
We can modify the program so that after taking the left chopstick, the program checks whether the right chopstick is available. If it is not, the philosopher puts down the left one, waits for some time, and then repeats the whole process. This proposal too fails, although for a different reason. With a little bit of bad luck, all the philosophers could start the algorithm simultaneously, picking up their left chopsticks, seeing that their right chopsticks
are not available, putting down their left chopsticks, waiting, picking up their left chopsticks
again simultaneously, and so on till death.
We have defined this situation in former chapters. This is the situation in which all the programs continue to run indefinitely but fail to make any progress, namely starvation.
Now, you may think, “If the philosophers would just wait a random time instead of the same time after failing to acquire the right chopstick.” That is true, but in some application one would prefer a solution that always works and cannot fail due to an unlikely series of random numbers. (Think about safety control in a nuclear plant)
The following program uses an array state, to keep track of whether a philosopher is eating, thinking, or hungry (trying to acquire chopsticks). A philosopher may move into eating state only if neither neighbour is eating. The neighbors are defined by the macros LEFT and RIGHT.
#define N 6 /* number of philosophers */
#define LEFT (i-1) % N /* number i’s left neighbor */
#define RIGHT (i+1) % N /* number i’s right neighbor */
#define THINKING 0 /* mode of thinking */
#define HUNGRY 1 /* mode of hunger */
#define EATING 2 /* mode of eating */
typedef int semaphore; /* semaphores are a special kind of int */
int state[N]; /* array to keep track of states */
semaphore mutex = 1; /* mutual exclusion for CS */
semaphore s[N] ; /* one semaphore per philosopher */
void philosopher(int i) /* i : Which philosopher (0 to N-1) ? */
{
while (TRUE) /* infinite loop */
{
think(); /* philosopher is thinking */
take_sticks(i); /* acquire two chopsticks or block */
eat(); /* yum-yum, rice */
put_sticks(i); /* put both chopsticks back */
}
}
void take_sticks(int i) /* i : Which philosopher (0 to N-1) ? */
{
down(mutex); /* enter CS */
state[i] = HUNGRY; /* record that the philosopher is hungry */
test(i); /* try to acquire 2 chopsticks */
up(mutex); /* leave CS */
down(s[i]) ; /* block if chopsticks were not acquired */
}
void put_sticks(int i) /* i : Which philosopher (0 to N-1) ? */
{
down(mutex); /* enter CS */
state[i] = THINKING; /* philosopher has finished eating */
test(LEFT); /* see if the left neighbor can eat now */
test(RIGHT); /* see if the right neighbor can eat now */
up(mutex); /* leave CS */
}
void test(int i) /* i : Which philosopher (0 to N-1) ? */
{
if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING)
{
state[i] = EATING;
up(s[i]);
}
}
