Dining Philosopher Problem and Solution

The Dining Philosopher Problem – The Dining Philosopher Problem states that K philosophers seated around a circular table with one chopstick between each pair of philosophers. There is one chopstick between each philosopher. A philosopher may eat if he can pick up the two chopsticks adjacent to him.

1. What is Dining Philosophers Problem ? Five philosophers are in a thinking - eating cycle . When a philosopher gets hungry , he sits down, picks up two nearest chopsticks and eats . A philosopher can eat only if he has both chopsticks . After eating, he puts down both chopsticks and thinks . This cycle continues.

2. What is Semaphore? Semaphore is a simply a variable. This variable is used to solve critical section problem and to achieve process synchronization in the multi processing environment. It consists of a counter , a waiting list of processes and two methods (e.g., functions): signal and wait .

3. Chopsticks are shared items (by two philosophers) and must be protected . Each chopstick has a semaphore with initial value 1 . A philosopher calls wait () before picks up a chopstick and calls signal () to release it. Solution for Dining Philosophers Problem using Semaphore

4. Does this solution works all the time? No Why? Let’s see

5. Circular Waiting & Deadlock If all five philosophers sit down and pick up their left chopsticks at the same time, this program has a circular waiting and deadlocks .

6. Any Solutions for Deadlocks? Introduce a weirdo who picks up his right chopstick first! Allow at most 4 philosophers at the same table when there are 5 resources Allow a philosopher to pick up chopsticks only if both are free. This requires protection of critical sections to test if both chopsticks are free before grabbing them.

7. Now Fourth person act as an weirdo and there is no circular wait. Introducing Weirdo

8. The native solution to the dining philosophers causes circular waiting. If only four philosophers are allowed to sit down, no deadlock can occur. Why ? If all four of them sit down at the same time, the right-most philosopher can have both chopsticks! How about fewer than four? This is obvious. Allow at most four Philosophers to sit

9. Allow at most four Philosophers to sit Cont.. Introducing a new semaphore for previews problem with initial value of 4 This will allow to sit only 4 persons

10. Semaphores can result in deadlock due to programming errors Forgot to add a P() or V(), or miss ordered them , or duplicated them to reduce these errors, introduce high-level synchronization primitives like Monitors with condition variables

11. What is Monitor ? In concurrent programming, a monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become true. Monitors also have a mechanism for signaling other threads that their condition has been met. 1. It is the collection of condition variables and procedures combined together in a special kind of module or a package . 2. The processes running outside the monitor can’t access the internal variable of monitor but can call procedures of the monitor . 3. Only one process at a time can execute code inside monitors .

12. Condition Variables Two different operations are performed on the condition variables of the monitor. Wait & Signal let say we have 2 condition variables condition x, y; //Declaring variable Wait operation x.wait () : Process performing wait operation on any condition variable are suspended. The suspended processes are placed in block queue of that condition variable . Note: Each condition variable has its unique block queue . Signal operation x.signal (): When a process performs signal operation on condition variable, one of the blocked processes is given chance. What is Monitor ? Cont..

13. Monitor-based Solution to Dining Philosophers Problem For prevent deadlock 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 . Key insight: 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

14. Monitor-based Solution to Dining Philosophers Problem monitor DiningPhilosoper { status state[5]; // thinking , hungry, eating condition self[5]; void pickup( int i ) ; // Pickup Chopstick void putdown( int i ) ; // Put down chopsticks void test( int i ) ; void init () { for ( int i = 0; i < 5; i ++) state[ i ] = thinking; } }

15. Monitor-based Solution to Dining Philosophers Problem Cont.. void pickup ( int i ) { state[ i ] = hungry; //indicate that I’m hungry test[ i ]; //set state to eating in test() only if my left and right neighbors are not eating if (state[ i ] != eating) self[ i ]. wait(); //if unable to eat, wait to be signaled } void putdown ( int i ) { state[ i ] = thinking; // test left and right neighbors test((i+4) % 5); //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 signaling R’s CV test((i+1) % 5); }

16. Monitor-based Solution to Dining Philosophers Problem Cont.. • 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

17. Any Questions ?

18. Thank You