The Dining Philosophers Problem — Using Java
One of the best classic examples which is used to describe synchronization issues in a multi-threaded background is the Dining Philosophers problem.
In this article we discuss what this problem is and what is the solution using following four segments.
01. Introduction
02. Solution
03. Implementation
04. Errors when implementing & How to overcome those errors
Now let’s see what are above mentioned segments with details.
01. Introduction
Above diagram represents the problem. There are five philosophers(silent) who are marked as P1-P5 sitting around a circular table. They are spending their lives by eating and thinking. To eat there are five forks for them to share named 1–5. Also, to eat a philosopher needs to have forks in both of his hands. After eating the philosopher puts down the forks(both) and those forks can be picked by another philosopher who repeats the same thing. This is a cyclic procedure.
02. Solution
The goal is to come up with a procedure that the philosophers achieve their goal of eating and thinking without getting starved to death. Following pseudo code is the procedure to follow when solving this problem.
while(true){
think(); //Initially thinking about the whole universal things.
pick_up_left_fork(); //Readying to eat as philosopher gets hungry eventually.
pick_up_right_fork();
eat();
put_down_right_fork();
put_down_left_fork();
think(); //Back to start thinking as hungry is over.
}
According to above pseudo code each philosopher is initially thinking. After some time, the philosopher gets hungry and wishes to eat. To achieve this the philosopher reaches for the forks on his either side. When the philosopher is successful in getting both folks, he begins to eat. When he puts down both forks, those forks are available for his neighbor philosopher. This is how this works.
03. Implementation
Initially we take philosophers as classes that implement the Runnable interface so that we can turn them as separate threads. Each philosopher has access to two forks on his left and right sides.
Also, there is another method that instructs a philosopher to perform his preferred action: eat, think or getting two forks to eat.
According to above code each action is simulated by suspending the invoking thread for a random amount of time. So, from that the execution order is not enforced by time alone.
To simulate acquiring a fork, we need to lock it so that no two philosopher threads acquire it at the same time. To achieve this, we use the synchronized keyword to acquire the internal monitor of the fork object and prevent other threads from doing the same. This is done in run() method in Philosopher class.
This code segment describes: a philosopher thinks for a while and then decides to eat. Also, timestamps were added to each action, in order to understand the order in which events occur.
To start the whole process we create a class named DiningPhilosophers to create five philosophers as threads and to start all of them.
We model each of the forks as generic Java objects and make as many of them as there are philosophers. We pass each Philosopher his left and right forks that he attempts to lock using the synchronized keyword.
Output is like following.
04. Errors when implementing & How to overcome those errors
Above code is without the problem: Deadlock. If the DiningPhilosophers class is like following we have the problem.
In this situation, each of the Philosophers has acquired his left fork, but can’t acquire right fork. Because his neighbor philosopher has already acquired it. This situation is commonly known as the circular wait and is one of the conditions that results in a deadlock and prevents the progress of the system.
Output of this code is as follows.
Hence, to avoid a deadlock situation we need to make sure that the circular wait condition is broken. The simplest way to solve that is like follows:
All Philosophers reach for their left fork first, except one who first reaches for his right fork.
Following red colored section is the changed code segment to avoid deadlock situation. In this we introduced the condition that makes the last philosopher reach for his right fork first, instead of the left. This breaks the circular wait condition and we can avoid deadlock.
Now this code shows the output that indicates: all the philosophers get their chance to think and eat, without causing deadlock.
In this article we analyzed the famous Dining Philosophers problem using threads.
