What is Dining Philosopher Problem in OS

What is Dining Philosopher Problem in OS:

The Dining Philosopher Problem is a problem with 5 philosopher siting at a table. The 5 Philosopher sit at a circular table with a bowl of rice in the center.

A Chopsticks is placed in the between each pair of adjacent Philosopher, each Philosopher has one chopstick to his right. 

Each Philosopher requires two chopsticks to eat the rice.

Each Philosopher can only use the chopstick on his imediate left and imediat right.

each philosopher can be one of the following states.

( i ). Hungry

(ii). Thinking

(iii). Eating.

 

Safety :

•  No  two philosopher can simultaneously can hold a chopsticks.
• Both neighboring chopsticks must be held while eating.

semaphore chopstick[5];

repeat

    wait ( chopstick [i] ) // wait for left chopstick

    wait ( chopstick [ ( i + 1 ) mod 5 ] ) // wait for right chopstick

< EAT  >

signal ( chopstick [ ( i +1 )mod 5 ]    // putup the right chopstick

signal (chopstick [ i] ) ; // put up the left chopstick

< Think >

until false;

 

The above solution for Dining Philosopher Problem suffers from deadlock.

Each Philosopher will pickup the chopstick on the left and wait for others to release the right chopsticks and hence all the philosopher have one chopstick.

Dining Philosopher Problem Deadlock Free solution :

To remove the Deadlock from the above solution we ensure that at a time all the odd numbers of Philosopher are eating or all the even number of philosopher is eating.

semaphore chopstick[5] ;

repeat

if (i % 2 == 0 )

wait ( chopstick[i] )

wait ( chopstick [ ( i + 1 ) mod 5 ]

wait ( chopstick [ i ] );

 <EAT >

signal ( chopstick [i] )

signal ( chopstick [ (i + 1 ) mod 5 ]

< Think >

 do until false;