So far we have learned about Race Conditions, Critical Section Problem and its solutions in process synchronization bu now we will be learning about another problem in the process synchronization called The Dining-Philosophers Problem which was proposed by the famous Programmer Edsger Dijkstra.
The Dining-Philosophers Problem
Consider there are five diners who spend their lives just thinking and eating. They share a circular table with five chairs around it, each belonging to one philosopher. There is a bowl of rice in the middle of the table. Each philosopher has one chopstick placed on their right side, A total of five chopsticks. Whenever a philosopher gets hungry, he picks one chopstick from its right and the other one from its left and starts eating rice and when he finishes, places the chopsticks on both sides from where he picked them and start thinking again.
A philosopher cannot pick two chop sticks if some other is already eating with two chopsticks. It is classic synchronization problem. It is a simple representation of the nedd to allocate several resources among several processes in a starvation-free and deadlock-free manner.
There are many solutions to Dining-Philosophers Problem but we will be looking at only one which we have already learned about.
Semaphore Solution To Dining Philosophers Problem
One way to represent this problem is to represent each chopstick as a semaphore. When a philosopher has to pick up a chopstick he can do so by executing the Wait() operation and when he wants to release the chopsticks he can do so by executing the Signal() operation.
while True:
Wait(chopstick[i])
Wait(chopstick[(i + 1) % 5])
# Eat for a while
Signal(chopstick[i])
Signal(chopstick[(i + 1) % 5])
# think for awhile
This solution works but in some situtaion it can cause a dealock where every philosopher have picked the chopstick on its left and is waiting for other philosopher to release the chopstick. This can cause all the philosopher to starve to death.
There are some possible remedies to the deadlock problem.
- Allow only four philosophers to be sitting at the table at the same time
- Allow only the philosopher to pick up chopstick only if both chopsticks on his left and right are present
No matter what way you try to handle the deadlock situation there will be most likely one philosopher that will starve because of not having to pick up both chopsticks.
zainsci