Dining Philosopher Problem and Solution
The dining philosopher is a classic synchronization problem as it demonstrates a large class of concurrency control problems.
The Problem
There are five philosophers sharing a circular table and they eat and think alternatively. There is a bowl of rice for each of the philosophers and five chopsticks. A philosopher needs both their right and a left chopstick to eat. A hungry philosopher may only eat if there are both chopsticks available. Other wise, a philosopher puts down their chopstick and begin thinking again.
Solution for Dining philosopher problem
Solution-1
do{
wait[chopstick[i];
wait [chopstick[i+1]%5];
//Critical Section
eat
signal[chopstick[i]];
signal[chopstick[i+1]%5];
think
}while(true);
By using above code,
The deadlock occurs, when each philosopher tries to access left chopstick at same time.
Solution for deadlock: Philosopher must be allowed to pick up chopsticks if both left and right chopsticks are available.
Solution using mutex:
Left chopstick
do{
wait(chopstick[i]);
wait(chopstick[i+1]%5];
//Critical section
eat();
signal(chopstick[i]);
signal(chopstick[i+1]%5];
think();
}while(true);
Right chopstick
do{
wait(chopstick[i+1]%5];
wait(chopstick[i]);
//Critical section
eat();
signal(chopstick[i+1]%5];
signal(chopstick[i]);
think();
}while(true);
By using the above code, protect critical sections with a mutex,prevents deadlock. But has performance issues -Only one philosopher can eat at a time.
Solution using semaphores:
The following source code is the solution for dining philosophers problem.
https://github.com/zeenayouhan/DiningPhilosopherProblem/blob/master/DiningPhilosopher.java
A semaphore object maintains a private integer which can only be accessed by the operations P and V. These are declared as synchronized which means the procedures(methods) execute indivisibly on the semaphore’s value when they are invoked by different threads. And semaphore is a tool based on process synchronization. It defines two functions as wait() and post().
Here wait() is used when access to critical section and post() is used when leaving the critical section.
Lets initialize the semaphore as s,
wait(s):
s.value=s.value-1;
if (s.value≤0)
{
add the process to s.list of process
block
}
post(s):
s.value=s.value+1;
if(s.value<0)
{
remove a process P from s.list of processes
wake up(p)
}
What is value mention above?
Here the value is determines the behavior of the process.
ex:
value=1: means there is no process in waiting queue and the critical section is empty.
value=0: means there are no processes in waiting queue and the critical section is occupied by a process.
value=-3: means there are 3 processes in waiting queue.
The diningphilosophers class in our code contains the main program and this is where execution begins
The philosopher class in our code is a runnable object class and when an object of this class is created and then started, it starts executing a method called run().
The semaphore class in our code contains methods declared as synchronized. It will ensure that access to Semaphore methods is mutually exclusive among threads.
