Consider the below code as a solution to dining philosopher problem
#define N 5 /* number of philosophers */
#define LEFT (i+N−1)%N /* number of i’s left neighbor */
#define RIGHT (i+1)%N /* number of i’s right neighbor */
#define THINKING 0 /* philosopher is thinking */
#define HUNGRY 1 /* philosopher is trying to get forks */
#define EATING 2 /* philosopher is eating */
typedef int semaphore; /* semaphores are a special kind of int */
int state[N]; /* array to keep track of everyone’s state */
semaphore mutex = 1; /* mutual exclusion for critical regions */
semaphore s[N]; /* one semaphore per philosopher */
void philosopher(int i) /* i: philosopher number, from 0 to N−1 */
{
while (TRUE) { /* repeat forever */
think( ); /* philosopher is thinking */
take_forks(i); /* acquire two forks or block */
eat( ); /* yum-yum, spaghetti */
put_forks(i); /* put both forks back on table */
}
}
void take_forks(int i) /* i: philosopher number, from 0 to N−1 */
{
down(&mutex); /* enter critical region */
state[i] = HUNGRY; /* record fact that philosopher i is hungry */
test(i); /* try to acquire 2 forks */
up(&mutex); /* exit critical region */
down(&s[i]); /* block if forks were not acquired */
}
void put_forks(i) /* i: philosopher number, from 0 to N−1 */
{
down(&mutex); /* enter critical region */
state[i] = THINKING; /* philosopher has finished eating */
test(LEFT); /* see if left neighbor can now eat */
test(RIGHT); /* see if right neighbor can now eat */
up(&mutex); /* exit critical region */
}
void test(i) /* i: philosopher number, from 0 to N−1 */
{
if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
state[i] = EATING;
up(&s[i]);
}
}
Consider we have five philosophers as $P_0,P_1,P_2,P_3,P_4$
Intially mutex=1, state[] array is initialized to THINKING for all philosophers, and s[] array for all philosophers is initialized to 0.
Process |
LEFT |
RIGHT |
$P_0$ |
$P_4$ |
$P_1$ |
$P_1$ |
$P_0$ |
$P_2$ |
$P_2$ |
$P_1$ |
$P_3$ |
$P_3$ |
$P_2$ |
$P_4$ |
$P_4$ |
$P_3$ |
$P_0$ |
Now process $P_2$ wants to eat and executes take_forks(i) and it succeeds.
State P[2]=Eating and s[2] changes from 0 to 1 and then back to 0. And all other philosophers are in the THINKING state.
Now suppose P1 wants to eat and calls take_fork(1), which marks state[1]=HUNGRY and finally P1 gets blocked on semaphore s[1].
Similarly, say P3 wants to eat and calls take_fork(3), which marks state[3]=HUNGRY and finally P3 gets blocked on semaphore s[3].
Now P2. stops eating and wants to put down forks so calls put_forks(2);
This puts P2 into THINKING state,test(LEFT) means test(1) is called, which succeeds and marks state of P1 EATING, and unblocks P1 from semaphore s[1] but s[1] stays 0.
Then, test(RIGHT)=test(3) called, which succeeds, marks P3 into EATING state and unblocks P3 from s[3] with s[3]=0.
Now, my query is
How can philosophers P1 and P3 eat at the same time when they share a common neighbour P2? I mean if we look at the left and right table of philosophers, how can 2 forks each be available to P1 and P3 at the same time?
Please help.
The code is taken from Andre Tanenbaum as a reference.