closed by
1,000 views
0 votes
0 votes
closed with the note: resolved
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.

 

 

closed by

Related questions

5 votes
5 votes
1 answer
1
Suman Acharya asked Sep 13, 2017
4,286 views
In dining philosophers Algorithm the minimum number of forks or chopsticks to avoid deadlock is (assume there are 5 philosophers)a. 5b. 6c. 10d. None of these