Introduction
When I was first introduced to the Dining Philosophers problem, my initial reaction was that it is a silly problem with a touch of obscurantism. As I read, it was originally created by Dijkstra as an exam problem in the 1960s. Some teachers do indeed have a predilection for whimsical problem formulations, which more often than not, though, are distracting more than they are illuminating. Later on the Dining Philosophers problem was promoted to a canonical problem in computer science, arguably after Tony Hoare discussed it in his book Communicating Sequential Processes. Now it is a standard problem in any course on Operating Systems or Concurrent Programming.
In this article, I will first highlight the issue that the original problem is poorly formulated. Second, I will propose a solution that is simpler than the three typical solutions that are commonly taught, and similar in spirit to a fourth but non-canonical solution.
First of all, what bugs me the most is that this problem appears to be much deeper than it actually is, by giving it this utterly pretentious name, Dining Philosophers. It is as follows: there are five philosophers, five forks, and an infinite amount of spaghetti. For some odd reason, philosophers need two forks to eat. They cannot eat and think at the same time, and they all want to both eat and think. Since nobody eats with two forks, I’ll replace the forks with chopsticks, and the spaghetti with rice. I will still refer to them as philosophers, to retain the pretentious nature of this problem. “Guys with chopsticks” just does not have the same ring as “Dining Philosophers”.
Let me now run through the typical issues discussed in the context of the Dining Philosophers problem:
1) Deadlock: if every philosopher grabs just one chopstick, they all wait forever until a second chopstick becomes available.
2) Livelock: if every philosopher can only hold on to chopsticks only a given amount of time, and they manage to perfectly synchronize this, you end up with the situation that they all pick up and release one chopstick at the same time, over and over.
Canonical Solutions
The three canonical solutions are:
1) Resource hierarchy (Dijkstra): Number the chopsticks from 1 to 5; introduce the convention that each philosopher has to pick up a chopstick with a lower number first. This prevents deadlock because, after allocating four chopsticks to four philosophers, the last philosopher cannot pick up chopstick number 5, since 5 is the highest number.
2) Create an arbitrator: implemented as a mutex, an arbitrator gives permission to philosophers to pick up two chopsticks at a time.
3) Introduce the notion of cleanliness (Chandy/Misra): label philosophers with an id ranging from 1 to n. For each pair of philosophers fighting over one particular chopstick, give it to the philosopher with the lower id. Each chopstick can be dirty or clean, and initially they are all dirty. When a philosopher wants to eat, he needs to request chopsticks. Any philosopher who receives a request keeps a chopstick if it is clean, but if it is dirty, he relinquishes it. Before handing over a chopstick, he cleans it. After a philosopher is done eating, all chopsticks are marked as dirty.
Those are the three canonical solutions to the Dining Philosophers problem, but I came across a fourth one:
4) Remove one chair (Stallings): Take n philosophers and n chopsticks. Now, remove one chair so that only n-1 philosophers can take a seat.
A different, and simple, solution
I thought about the dining philosophers problem a bit, and came up with a solution that retains the original conventions. In that regard, it is unlike the fourth approach, even though it is similar in spirit, as it equally aims for a rather straightforward solution. Obviously, chopsticks can only be used in pairs. Thus, the solution is to simply let philosophers only take two chopsticks at a time — and we are done! Concretely, put all n philosophers in a queue P, and all n chopsticks in a separate queue C (a stack would work just as well). While C contains at least two chopsticks, the philosopher at the top of P takes two chopsticks from C and eats, and so on.
It should be obvious why this approach works. If not: The philosopher at the top of P takes two chopsticks from C, and starts eating. When he is done (feel free to have him eat until he receives a request to release his chopsticks; it does not matter), he adds both chopsticks to C again. Continue until all chopsticks have been distributed. If there are no two chopsticks available, the remaining philosophers wait for their turn. Thus, the first philosopher takes two chopsticks, and eats. Then the second philosopher takes the next two chopsticks, and eats. The third philosopher would only get one chopstick, for the time being, so he waits. Eventually, though, the first philosopher will be done eating, and subsequently put his two chopsticks back to C. Because you always take two chopsticks from C, and philosophers only eat for a finite amount of time, there is neither deadlock nor starvation.
[EDIT: On Reddit is was pointed out that the stack is the arbitrator (waiter) in disguise. This is correct. There was also an issue that the chopsticks are treated as commodities, while they should be distinguishable. For instance, philosopher 1 can only take chopsticks 1 and 2, philosopher 2 only chopstick 2 and 3, and so on. To salvage my approach, which now makes it even clearer that C is just the waiter in disguise, have it store pairs of neighboring chopsticks. A more complicated bookkeeping mechanism is needed for the chopsticks, though. Anyway, using that approach, philosopher 1 takes the pair (1, 2), and leaves the waiting queue. Philosopher 2 would like to take pair (2, 3), but chopstick 2 is taken, so he has to move to the end of the waiting queue. Philosopher 3 can take chopsticks (3, 4), though, and so on. Once philosopher 1 is done, he returns the pair of chopsticks, and moves to the back of the waiting queue, etc.]
Lastly, note that there is no need to have exactly five philosophers. Presumably, this number is only used due to the historical accident of Dijkstra using that particular number. You need at least two. Some of the solutions we have seen have an administrative overhead, so it will only get more cumbersome the more philosophers we add to the table. However, by using a queue, you could feed an arbitrarily large number of philosophers without any overhead. Also note that whenever there is an odd number of chopsticks, there is one superfluous chopstick, since you cannot properly eat rice with just one chopstick. Thus, there are at least three aspects in the original problem statement that obscure the problem: the number 5, the strange convention of using two forks, and the fact that the fifth fork is superfluous. Lastly, calling the diners philosophers is potentially distracting.