Dining philosophers problem and solution

Dining philosophers problem is synchronization problem created by E. Dijkstra in 1965. In this problem, there are 5 philosophers who are seated in a round dining table with 5 bowls of spaghetti for each one of them. Between the bowls there are 5 forks as shown in below given figure:

Dining philosophers problem

Now, when a philosopher wants to eat, he will pick two forks, eat the spaghetti and then keep the forks back. Then, he will start thinking and the other philosopher will pick the forks and so on. However, if all 5 philosophers take their left forks simultaneously, then there will be a deadlock:

#define P 5
void philosopher(int i)
{
while (TRUE) {
think();
take_ fork(i);
take_fork((i+ 1) % P);
eat( );
put_ fork(i);
put_ fork( (i+ 1 ) % P);
}
}

Here is the solution of the problem with no deadlocks:

#define P 5
#define LEFT (i+P-1 )%P
#define RIGHT (i+ 1 )%P
#define THINK 0
#define HUNGRY 1
#define EAT 2
typedef int semaphore;
int state[P];
semaphore mutex = 1 ;
semaphore s[P];
void philosopher(int i)
{
while (TRUE) {
think( );
take_ forks(i);
eat();
put_ forks(i);
}
}
void take_forks(int i)
{
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down( &s[i]);
}
void put_forks(i)
{
down(&mutex);
state[i] = THINK;
test(LEFT);
test( RIGHT);
up(&mutex);
}
void test(i)
{
if (state[i] == HUNGRY && state[LEFT] != EAT && state[RIGHT] != EAT) {
state[i] = EAT;
up(&s[i]);
}
}

Leave a Reply