What is Dining Philosophers problem? Discuss the solution to Dining philosophers problem using monitors.

Dining Philosophers problem:

• Five philosophers are sitting around a circular table.
• Dining table has five chopsticks and bowl of rice in the middle.
• Philosopher can either eat or think.
• When a philosopher wants to eat, he uses two chopsticks.
• When philosopher wants to think, he keeps down both chopsticks.
• Problem is “ no philosopher will starve ”.

* Each philosopher can forever continue to think and eat alternatively. It is assumed that

no philosopher can know when others want to eat or think.*

Monitor-based Solution to Dining Philosophers:

Illustrating monitor concepts by presenting a deadlock-free solution to the dining philosophers problem. Monitor is used to control access to state variables and condition variables. It only tells when to enter and exit the segment. This solution imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available.

• pick up 2 chopsticks only if both are free

   – this avoids deadlock

   – reword insight: a philosopher moves to his/her eating state only if both neighbors are not in their eating states 

•  thus, need to define a state for each philosopher 

    – 2nd insight: if one of my neighbors is eating, and I’m hungry, ask them to signal() me when they’re done 

• thus, states of each philosopher are: thinking, hungry, eating 

• thus, need condition variables to signal() waiting hungry philosopher(s) 

    – Also, need to Pickup() and Putdown() chopsticks 

• Some basic pseudocode for monitor (we’ll abbreviate DP for Dining Philosophers): 

monitor DP {

 status state[5];

 condition self[5];

 Pickup(int i);

 Putdown(int i);

 }

 • Each philosopher i runs pseudo-code: 

DP.Pickup( i);

 ... 

DP.Putdown( i);

monitor DP {

 status state[5];

 condition self[5];

 Pickup(int i) {

 state[i] = hungry;

 test(i);

 if(state[i]!=eating) self[i].wait;

 }

 Putdown(int i) {

 state[i] = thinking;

 test((i +1)% 5);

 test((i-1)% 5);

 }

• Pickup chopsticks

     – indicate that I’m hungry

     – set state to eating in test() only if my left and right neighbors are not eating  

     – if unable to eat, wait to be signalled 

• Put down chopsticks 

     – if right neighbor R=(i+1)%5 is hungry and both of R’s neighbors are not eating, set R’s state to
eating and wake it up by signalling R’s CV 

test(int i) {

 if (state[(i+1)%5] != eating &&

 state[(i-1) %5] != eating &&

 state[i] = = hungry) {

state[i] = eating;

 self[i].signal();

 }

 }

 init() {

 for i = 0 to 4

 state[i] = thinking;

 }

} // end of monitor

• signal() has no effect during Pickup(), but is important to wake up waiting hungry philosophers during Putdown() 

• Execution of Pickup(), Putdown() and test() are all mutually exclusive, i.e. only one at a time can be executing 

• Verify that this monitor-based solution is 

    – deadlock-free 

    – mutually exclusive in that no 2 neighbors can eat simultaneously