CREATE OWN LIBRARY

Dining Philosopher problem 

Dining Philosopher problem Algorithm and Example

Five philosophers sit around a table. A plate with food is kept in front of each philosopher, and a fork is placed between each pair of philosophers (see Figure 24). 

To take food, a philosopher must pick up the two forks placed between him and the neighbors on either side, one at a time. 

But this situation may lead to a deadlock.

Example:  Dining Philosopher’s problem

Both algorithms are the same just the representation is different.

P means Down or Wait operation of binary semaphore.

V means Up or Signal operation of binary semaphore.

take_fork and P are the same as the down operation and put_fork and V is the same as the up operation.

Let there are four  philosophers (Pi∶ 0, 1, 2, 3) and four  fork (0, 1, 2, 3)

(Philosopher) Pi∶ 0, 1, 2, 3 

(Fork) Fi∶ 0, 1, 2, 3 

The sequence by which philosophers pickup forks

As we know take_fork operation is the same as the down operation.

So, we know the concept of down operation i.e down operation cannot execute by two processes together for a single semaphore variable. If one process already runs a P or Down operation, then for the next process P or Down operation will be blocked for the same semaphore variable.

So, we can’t take a fork that is already used by some other philosopher.

Now let philosophers taking the fork in such a way

It became a deadlock where every philosopher preempted after taking the first fork (down operation).

The problem is to design processes to represent the philosophers such that each philosopher can eat when hungry and none dies of hunger.

Solution

Here one solution can impose the restriction that a philosopher may pick up her fork only if both are available.

• # There is four philosopher and four forks and each philosopher require 2 forks to have food.
•  
• # But if everybody takes the left fork first then the right one then it must in deadlock.
•  
• # We can solve that if there is at least one philosopher who takes in the opposite way right one first then left one then everyone will get fork i.e no deadlock will arise.

We can code this above solution if one of the philosopher processes changes its down operation sequence. 

Previously it was take_fork(3) and take_fork(0)

Here P3 changes the sequence of take_fork(down operation), now check for deadlock is removed or not.

Here P2 is not blocked so, it enters into Critical Section and release F2 and F3 then P1 is getting Critical Section, and release F1 and F2 then P1 getting Critical Section. 

So, there is no deadlock.

Basic concept of Dining Philosopher problem

If P or down operation of every process is doing clockwise then it may lead to deadlock.

But above all processes, if one of the processes is run its P or down operation anti-clockwise then it removes deadlock.

This is concept is called dining philosopher.