1. Introduction
The Dining Philosophers problem is one of the classical problems used to describe synchronization problems in a multithreaded environment and illustrate the technical ways to solve them. Dijkstra first raised and presented this problem involving computers accessing tape drive peripherals.
The current formula was given by Tony Hoare who is also known for inventing the quicksort sort algorithm. In this article we’ll break down this famous problem and code a common solution.
2. Math problem
The diagram above represents the problem. There are five silent philosophers (P1 – P5) sitting around a round table, spending their lives eating and thinking.
There are five forks for them to share (1 – 5) and to be able to eat, a philosopher needs to hold the fork in both hands. After he finished eating, he put both things down and they could then be picked up by another philosopher who repeated the same cycle.
The goal was to provide a flowchart/process that would help philosophers achieve their goals of eating and thinking without starving to death.
3. Solution
An initial solution would be to make each philosopher follow the following protocol:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | while(true) { // Initially, thinking about life, universe, and everything think(); // Take a break from thinking, hungry now pick_up_left_fork(); pick_up_right_fork(); eat(); put_down_right_fork(); put_down_left_fork(); // Not hungry anymore. Back to thinking! } |
As the code above describes, every philosopher is thinking at first. After a certain period of time, the philosopher feels hungry and wants to eat.
At this point, he reaches for the fork on either side, and once he has both, he will continue to eat. After eating, the philosopher would put down his forks, leaving them available to his neighbor.
4. Implementation
We model each of our philosophers as classes that implement the Runnable interface so that we can run them as separate threads. Each Philosopher has access to two forks to his left and right:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | public class Philosopher implements Runnable { // The forks on either side of this Philosopher private Object leftFork; private Object rightFork; public Philosopher(Object leftFork, Object rightFork) { this.leftFork = leftFork; this.rightFork = rightFork; } @Override public void run() { // Yet to populate this method } } |
We also have a function that instructs a Philosopher to perform an action – eat, think or grab a fork to prepare to eat:
1 2 3 4 5 6 7 8 9 10 11 12 13 | public class Philosopher implements Runnable { // Member variables, standard constructor private void doAction(String action) throws InterruptedException { System.out.println( Thread.currentThread().getName() + " " + action); Thread.sleep(((int) (Math.random() * 100))); } // Rest of the methods written earlier } |
As shown in the above code, each action is simulated by pausing the calling thread for a random amount of time, so the execution instruction is not executed only in time.
Now, let’s implement Philosopher’s core logic.
To simulate grabbing a fork, we need to lock it so that no two Philosopher threads can grab it at the same time.
To achieve this, we use the synchronized keyword to get the internal monitor of the fork object and prevent other threads from doing the same. Now we proceed to implement the run() method in the Philosopher class:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | public class Philosopher implements Runnable { // Member variables, methods defined earlier @Override public void run() { try { while (true) { // thinking doAction(System.nanoTime() + ": Thinking"); synchronized (leftFork) { doAction( System.nanoTime() + ": Picked up left fork"); synchronized (rightFork) { // eating doAction( System.nanoTime() + ": Picked up right fork - eating"); doAction( System.nanoTime() + ": Put down right fork"); } // Back to thinking doAction( System.nanoTime() + ": Put down left fork. Back to thinking"); } } } catch (InterruptedException e) { Thread.currentThread().interrupt(); return; } } } |
This plan executes exactly the one described earlier: a Philosopher thinks for a moment and then decides to eat.
Then he took the forks to his left and right and began to eat. When he was done, he put down his fork. We also add a timestamp for each action, which will help us understand the order in which events occur.
To start the whole process, we write a client that creates 5 Philosophers as threads and starts them all:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | public class DiningPhilosophers { public static void main(String[] args) throws Exception { Philosopher[] philosophers = new Philosopher[5]; Object[] forks = new Object[philosophers.length]; for (int i = 0; i < forks.length; i++) { forks[i] = new Object(); } for (int i = 0; i < philosophers.length; i++) { Object leftFork = forks[i]; Object rightFork = forks[(i + 1) % forks.length]; philosophers[i] = new Philosopher(leftFork, rightFork); Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1)); t.start(); } } } |
We model each branch as generic Java objects and generate as many branches as the number of philosophers. We pass each Philosopher his left and right branches which he tries to lock with the synchronized keyword.
Running this code results in output similar to the following. Your output will most likely be different from the one given below, mainly because the sleep() method is called in a different amount of time:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | Philosopher 1 8038014601251: Thinking Philosopher 2 8038014828862: Thinking Philosopher 3 8038015066722: Thinking Philosopher 4 8038015284511: Thinking Philosopher 5 8038015468564: Thinking Philosopher 1 8038016857288: Picked up left fork Philosopher 1 8038022332758: Picked up right fork - eating Philosopher 3 8038028886069: Picked up left fork Philosopher 4 8038063952219: Picked up left fork Philosopher 1 8038067505168: Put down right fork Philosopher 2 8038089505264: Picked up left fork Philosopher 1 8038089505264: Put down left fork. Back to thinking Philosopher 5 8038111040317: Picked up left fork |
All the Philosophers start thinking at first, and we see that Philosopher 1 keeps picking up the left and right forks, then eats and puts them both down, then Philosopher 5 picks it up.
5. Problem with solution: DeadLock
Although it seems that the above solution is correct, there is still a deadlock problem that arises.
Deadlock is a situation in which the process of a system is halted because each process is waiting to get a resource held by some other process.
We can confirm the same by running the above code a few times and checking if the code crashes. Here is a sample output demonstrating the above problem:
1 2 3 4 5 6 7 8 9 10 11 | Philosopher 1 8487540546530: Thinking Philosopher 2 8487542012975: Thinking Philosopher 3 8487543057508: Thinking Philosopher 4 8487543318428: Thinking Philosopher 5 8487544590144: Thinking Philosopher 3 8487589069046: Picked up left fork Philosopher 1 8487596641267: Picked up left fork Philosopher 5 8487597646086: Picked up left fork Philosopher 4 8487617680958: Picked up left fork Philosopher 2 8487631148853: Picked up left fork |
In this situation, each Philosopher gets his left fork, but can’t get his right fork because his neighbor already has it. This condition is often referred to as a waiting loop and is one of the conditions that lead to deadlock and system progress.
6. Solve deadlock
As we have seen above, the main reason for deadlock is a circular wait condition where each process waits for a resource being held by some other process. Therefore, to avoid deadlock, we need to ensure that the waiting condition for the circle is broken. There are several ways to achieve this, the simplest is the following:
All the Philosophers reach for their left fork first, except for the first one who reaches for his right fork.
We implement this in our existing code by making a relatively small change in the code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | public class DiningPhilosophers { public static void main(String[] args) throws Exception { final Philosopher[] philosophers = new Philosopher[5]; Object[] forks = new Object[philosophers.length]; for (int i = 0; i < forks.length; i++) { forks[i] = new Object(); } for (int i = 0; i < philosophers.length; i++) { Object leftFork = forks[i]; Object rightFork = forks[(i + 1) % forks.length]; if (i == philosophers.length - 1) { // The last philosopher picks up the right fork first philosophers[i] = new Philosopher(rightFork, leftFork); } else { philosophers[i] = new Philosopher(leftFork, rightFork); } Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1)); t.start(); } } } |
The change comes in lines 17-19 of the above code, where we introduce a condition that causes the last philosopher to hit his right fork first, instead of the left. This breaks the circular wait condition and we can prevent deadlock.
The following output shows one of the cases where all the Philosophers have a chance to think and eat without causing a deadlock:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | Philosopher 1 88519839556188: Thinking Philosopher 2 88519840186495: Thinking Philosopher 3 88519840647695: Thinking Philosopher 4 88519840870182: Thinking Philosopher 5 88519840956443: Thinking Philosopher 3 88519864404195: Picked up left fork Philosopher 5 88519871990082: Picked up left fork Philosopher 4 88519874059504: Picked up left fork Philosopher 5 88519876989405: Picked up right fork - eating Philosopher 2 88519935045524: Picked up left fork Philosopher 5 88519951109805: Put down right fork Philosopher 4 88519997119634: Picked up right fork - eating Philosopher 5 88519997113229: Put down left fork. Back to thinking Philosopher 5 88520011135846: Thinking Philosopher 1 88520011129013: Picked up left fork Philosopher 4 88520028194269: Put down right fork Philosopher 4 88520057160194: Put down left fork. Back to thinking Philosopher 3 88520067162257: Picked up right fork - eating Philosopher 4 88520067158414: Thinking Philosopher 3 88520160247801: Put down right fork Philosopher 4 88520249049308: Picked up left fork Philosopher 3 88520249119769: Put down left fork. Back to thinking |
It can be verified by running the code multiple times to get the system out of the deadlock that happened before.
7. Conclusion
In this article, we have explored the famous philosopher’s dinner problem and the concepts of waiting and circular deadlock. We’ve coded a simple solution that causes deadlocks and made a simple change to break the wait loop and avoid deadlocks. This is just a start and more complex solutions still exist.