A Simpler Solution to the Dining Philosophers Problem

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.

9 thoughts on “A Simpler Solution to the Dining Philosophers Problem

  1. somehndude

    That doesn’t make too much sense as taking two chopsticks at once requires synchronization.

    Yes, Chopsticks are the better metaphore.

    Reply
    1. Gregor Ulm Post author

      The philosophers take chopsticks one after the other, as I elaborate in the more detailed discussion. This is easy to ensure in an implementation. Just check whether the stack or queue C contains at least two chopsticks, and if it does, the philosopher waiting for two chopsticks first takes one chopstick, and then another one. Of course he doesn’t take them simultaneously in the actual implementation. However, when you describe the algorithm in high-level terms it seems appropriate to just say that you take two chopsticks from the top of the stack or queue C.

      Reply
  2. Martin

    So you are just making the grabbing of two chopsticks an atomic transaction? Yea that is one of the well-known solutions for the dining philosophers

    Reply
    1. Gregor Ulm Post author

      I didn’t write that this was a novel idea. In fact, I would have been surprised if that had been the case. However, in the various discussions of the Dining Philosophers problem I found online, and two textbooks I have easy access to, did not mention that particular approach. (It is related to the arbitrator solution, though.) In a way it sidesteps the original problem. On the other hand, the original problem is highly artificial to begin with, so it is not surprising that people aim to simplify it.

      Reply
  3. Dontknow

    See, by saying “the philosopher waiting for two chopsticks first takes one chopstick, and then another one” the word WAITS already means you chose solution #2.

    Your solution isn’t really a solution, it’s just that you elaborated a more complicated way of describing a semaphore for the dining philosophers. (aka: you didn’t get it right, so you thought you had an idea but it already exists, you just didn’t understand it).

    Short: your solution requires synchronization which is already one of the answers for the problem.

    Reply
  4. Pascal Bourguignon

    Putting the chopsticks in common in a queue changes the problem.

    You could imagine a circular pipe, that you could create in unix with a named pipe n: an
    Then the chopsticks are named (between two given philosophers/processes). An additionnal constraint beeing that a process needs to lock access to both pipes (this doesn’t exist in unix unless you use threads or asynchronous I/O to use both pipes at the same time).

    Reply

Leave a Reply to YK Shar Cancel reply

Your email address will not be published. Required fields are marked *

Spammer prevention; the answer is an integer: * Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.