dining philosopher’s problem

Table of Content

1. Introduction to Dining Philosopher’s Problem

The dining philosopher’s problem is another most important example of
synchronization in which there are Five philosophers are seated around a
circular table and what they are going to do. They think and eat food in
alternatively manner. A food is placed at the center of the table along with
five forks for each of the philosophers. To eat a food philosopher needs both
their right and a left fork. A philosopher can only able to eat food if and only
if both left and right fork of the philosopher is available to him. In case if both
immediate left and right fork of the philosopher are not available then the
philosopher puts down their (either left or right) fork and starts thinking again. 

dining philosopher’s problem

Void philosopher (int I) 
{
 While (TRUE) 
{ 
    Thinking (); 
    Take fork (I); // this is left fork 
    Take fork ((I+1) %N); // this is right fork 
    Eat ();Put fork (I); // this is for putting left fork back 
    Put fork ((I+1) %N); // this is for putting right fork back 
   } 
} 
Let’s try to understand the above code:
Suppose Philosopher P0 wants to eat food, so it will execute Philosopher ()
procedure, and take fork by executing Take fork[I] function by doing this it
holds F0 fork after that in order to complete food or get second fork it will
execute Take fork [ (i+1) % 5] by doing this it holds F1 Fork (since I =0,
therefore value for second fork is (0 + 1) % 5 = 1 mean F1) 
Similarly suppose now Philosopher P1 wants to eat food, it will execute
Philosopher () procedure, and execute Take fork[I] function by doing this it
holds F1 fork after that it execute second procedure Take fork [ (i+1) % 5]
by doing this it holds F2 Fork (since i =1, therefore value for second fork is
(1 + 1) % 5 = 2 mean F2)
But if we think about this situation as process are executing simultaneously
Fork F1 is not available as it has already been taken by philosopher P0,
hence the above code generates problems results in dead lock as no
philosopher can able to eat food. 

3. The solution of the Dining Philosophers Problem is semaphore. 

Note Mutex is a binary semaphore use by philosopher to achieve
synchronization. 

In order to understand it we have to make use of following variable 
#define N 5 
#define LEFT (I+N-1) %N //Left of philosopher 
#define RIGHT (I+1%N) //Right of philosopher 
#define THINKING 0 
#define HUNGARY 1
#define EATING 2 

Semaphore mutex = 1; 
Binary Semaphore
Semaphore S[N]; 

Note: Initially S[I]’s is Initialized to Zero 

Int State[N]; 

Note: array keep track of every ones’ state and initially all will be in thinking
state 
 

Void philosopher (int I) 
{ 
    While (TRUE) 
        { 
            Thinking (); 
            Take Fork(I); 
            Eat (); 
            Put Fork(I); 
        }
   } 

Take Fork (int I) 
{ 
DOWN (mutex); 
State[I]=HUNGARY; 
Test(I); 
UP (mutex); 
DOWN (S [I]); // this will be ensuring that no two philosophers go to eating
state if left and right are eating 
} 

Put Fork (int I)
{ 
DOWN (mutex); 
State[I]=THINKING; 
Test (LEFT); 
Test (RIGHT); 
UP(mutex);
} 

Void Test (int I) 
{ 
If (State[I]==HUNGRY && State [LEFT]! =EATING && State [RIGHT]!
=EATING) 
{ 
State [I]=EATING; 
UP(S[I]); 
} 
}

FAQ 1.  Discuss Dining Philosopher’s Problem in detail?

FAQ 2. State and describe the Dining Philosopher’s Problem with its suitable solution?