The Dining Philosophers Problem

The dining philosophers problem is a famous problem in computer science used to illustrate common issues in concurrent programming. The problem was originally formulated in 1965 by Edsger Dijkstra, and is stated as follows:

Five silent philosophers sit at a round table with bowls of food. Forks are placed between each pair of philosophers. All day the philosophers take turns eating and thinking. A philosopher must have two forks in order to eat, and each fork may only be used by one philosopher at a time. At any time a philosopher can pick up or set down the fork on their right or left, but cannot start eating until picking up both forks.

Benjamin D. Esham / Wikimedia Commons CC BY-SA 3.0, via Wikimedia Commons

The problem asks you to develop a single algorithm that is followed by all philosophers and allows each to alternate between eating and thinking without reaching a state of deadlock. The problem is somewhat more difficult to solve that it initially appears, which is illustrated in the following example. Suppose that you attempted to use the following algorithm as a solution:

• think until the left fork is available; when it is, pick it up
• think until the right fork is available; when it is, pick it up
• eat for a fixed amount of time
• put the right fork down
• put the left fork down
• think for a fixed amount of time
• repeat

Each philosopher must follow this algorithm exactly, so each will initially pick up the fork on their left. Because there are five philosophers and only five forks they will all wait for the fork on their right to become available and will eventually starve. You can attempt to improve this solution by adding conditions like “wait a certain amount of time before picking up the fork,” but doing so only leads to other problems like livelock. Instead of modifying this attempt, we will consider a different solution.

Resource Hierarchy Solution

There are many valid solutions to the problem, but my favorite is the resource hierarchy solution originally proposed by Dijkstra. The solution assigns a number to each fork and adds one additional rule. Note that all philosophers are adjacent to two forks, and therefore have two options when choosing which fork to pick up first. This solution simply requires that the philosophers pick up the the fork with the smaller number first. This rule ensures that at least one philosopher will always be without a fork, which means that there will always be one extra fork, which means that at least one philosopher will always be able to eat. The algorithm then looks like this:

• think until the small number fork is available; when it is, pick it up
• think until the large number fork is available; when it is, pick it up
• eat for a fixed amount of time
• put the small number fork down
• put the large number fork down
• repeat

The worst case scenario is described above; in this case we simply ensure that one philosopher will always be able to eat. In the real world this solution tends to be more efficient, as not all requests for forks will come in at the exact same time. Such a scenario results in some philosophers holding no forks with others holding two, which increases the algorithm's efficiency.

Code Example

The code for the resource hierarchy solution can be found here. In this code example each philosopher is implemented as a thread, while the forks are implemented as semaphores. Each philosopher thinks for a random amount of time, waits to pick up the forks in the correct order, eats for a random amount of time, and repeats. A different number of philosophers is randomly chosen for each execution to illustrate the flexibility of the solution.