Dining Philosophers

A classic problem in ConcurrentProgramming classes, proposed by EwDijkstra.

Five philosophers are sitting around a circular table. On the table is a bowl of noodles. Between each pair of philosophers is a chopstick laid out on the table such that the first philosopher's right chopstick is the left chopstick of the second philosopher, whose right chopstick is the left chopstick of the third philosopher and so forth. Hence there are five chopsticks available in total.

Each philosopher thinks for a while, then gets hungry and decides to eat. In order to eat, a philosopher has to have a pair of chopsticks. He picks up the chopsticks on either side of him to grab some noodles from the bowl and then eats. If one of the chopsticks is already being used, the philosopher must wait for it to become available.

In a concurrent system, each philosopher is implemented as a thread and each chopstick is a shared resource.

The intuitive approach to solving this problem is to have each philosopher first pick up his left chopstick then his right. However, this will lead to deadlock as all four of the necessary and sufficient conditions for deadlock come into play: blocking shared resources (chopsticks), no pre-emption (one philosopher cannot ask his adjacents to drop their chopsticks), holding while acquiring (a philosopher holds his left chopstick before trying to pick up his right) and circular waiting (each philosopher shares chopsticks).

Clearly our naive scheme doesn't quite work as planned. However, as all conditions for deadlock are both necessary and sufficient, we should be able to prevent the deadlock by breaking any one of the conditions above.

An obvious way around this is that philosophers who can't get both chopsticks should put them down, go back to thinking and try again later. This is trying to break the third deadlock property above: 'holding while acquiring'. However, if the philosophers are unlucky and keep doing this all in synchrony, none of them will actually get to eat! Each will drop a chopstick only to try and grab it once more. This solution breaks the problem of deadlock but in doing so, we have introduced another potential problem - that of livelock. The philosophers will not grind to a halt but instead can just go round in circles trying to decide who should have the chopsticks but never getting anywhere. The philosophers won't eat and will starve (quite literally!). This solution isn't much good either.

There are several possible viable solutions that solve both the issue of deadlock and ensure liveness, four of which are presented here:

One article on EeLanguage suggests a variant on this problem as an example of how to make a capability-security model, and designs a solution that ensures that even an evil philosopher, who only wants to eat (thereby depriving all other philosophers of food), cannot deadlock the system. Their solution can be summarized as:

"Order the chopsticks"

Okay, but this means that two philosophers will be trying to pick up the same chopstick at the same time. How is this decided?

Each philosopher represents a thread in a multi-threaded system.

We're really modelling a single-processor system here... only one philosopher can actually move at a time. With multiple processors, you're correct, we have to deal with two philosophers grabbing a chopstick, and the ensuing tug-of-war

There are several ways for this to be decided:


"solution" that changes the problem:

Let philosophers use *any* chopstick, not just the one adjacent to him.

Counterpoint

This entire discussion is invalid, because the system's resources (the chopsticks) are not supposed to be assigned singly, but in pairs. Any proper analysis of the system would discover this. Therefore, a proper resource allocation system would see five resource sinks and two and one half resource sources. (The resource pairs may be shuffled through a use balancing system that looks at usage history.) The resource allocator gives chopsticks to two of the five philosophers and maintains the other three philosophers as waiting in a queue. As soon as one of the pairs of chopsticks becomes free the next philosopher in the queue gets a chance to eat. If one of the philosophers who has already eaten asks for chopsticks again his request is further down in the queue than a philosopher who hasn't eaten at all. Eventually all the philosophers eat.

[Note that by the constraints of the problem, philosopher i cannot use any free chopsticks. He can only use chopsticks i and i+1. This consideration has apparently been ignored in the "counterpoint", but it could be added.] NOTE: This constraint was never placed on the original problem. Nevertheless, it could be accommodated quite easily.

The counterpoint might be a valid algorithm when it is possible to allocate the resource only a pair at a time, but completely misses the point in saying that it's an invalid discussion and implying that DiningPhilosophers is a trivial problem. Quite the contrary, the real problem is what to do when the resource is not allocated a pair at a time, only individually, and you can't control that for some reason.

For instance, let's say you're a bank in the middle of the U.S. and you need to do a wire transfer of money; one resource ("fork"/"chopstick") is the source account, which is located at a second bank on the west coast, and the other resource is the destination account, at a third bank on east coast.

You need to grab both resources (let's say you must have both resources simultaneously to do this transaction because of various banking laws). But the only way to get either of the resources is via a network, and the two requests, although they are issued at the same time (that is, you try to get both resources simultaneously), have no guarantees about being granted, so you may get 0, 1, or 2 resources every time you ask for 2.

And you can't change this because the resources are thousands of miles apart and are in two different databases, and you can't insist that all the banks that you're going to talk to must merge their databases into one central one.

<ahem> Nice try. If you have three components involved in a single operation ("by law," heh) then you must allocate resources to deal with all three components and the simultaneous tasks at the same time. Therefore, resources are allocated by threes. A scheduling system could make sure that no operation gets left out in the cold too long. For instance, Originator asks Source and Sink for a slot to deal with a particular transaction. Sink has a slot available, but Source doesn't. Originator then tells Sink to put the slot on high priority standby while waiting for Source to free up a slot. In the mean time Source is chopping wood furiously, but is still aware that Originator and Sink are waiting on him. Eventually Originator's request rises in the priority queue high enough to earn a slot. Originator then tells Sink to activate that hot standby slot, and the three components complete the transaction. This may potentially have issues with PriorityInversion

[You missed the point. Assume Alice wants to transfer money to Bob and meanwhile Bob wants to transfers money to Alice. Alice's bank grabs a lock on Alice's account, then asks Bob's bank for a lock on Alice's account. Meanwhile, Bob's bank locked Bob's account and is now asking for a lock on Alice's account. Bang, you have a deadlock. Alice and Bob are philosophers, their accounts are chopsticks. Add people as needed to get to a total number of five.]

If an operation can't be completed with less than the required resources then it's just plain stupid to allocate resources in chunks less than the necessary amount. This is a systemic problem and needs to be addressed by a competent architect. If you are JustaProgrammer then please let the Big Kids deal with this kinda stuff.

I feel a slight RudenessObjection here. I think that the author of the above comments should perhaps consider some extra-curricular reading to try and understand the crux of the DiningPhilosophers problem, rather than trying to explain it away as a problem for a "competent architect" (which it isn't at all - the problem is a theoretic one, not one of architecture).


"solution" that changes the problem:

Get more chopsticks, so there are plenty for each philosopher.

You know, I can solve any problem whatsoever. Yep, all I have to do is change the problem definition into one I already know how to solve. ;-)


Moved PhilosophicalSilliness
It seems that DiningPhilosophers is not the typical SynchronizationProblem?, since it requires to grab several resources at once. Philosophers do not eat spaghetti using chopsticks, but one fork and one spoon. Also you need to consider that at least one Philosopher needs to talk an the rest listen. In the original problem, they just either eat or think, they do not talk, that's not a very funny meal. Well maybe it is, because it must take ages to eat spaghetti with chopsticks.

Somebody doesn't eat much Asian food... but let me assure you, eating spaghetti is quite straightforward with chopsticks.

DeadLock seems to be a problem in many systems. DeadLock can only occur when threads try to grab several resources at once. Perhaps we should collect a list of "real" programming problems that risk DeadLock.

Note: The claim that "DeadLock can only occur when threads try to grab several resources at once" is necessary but not sufficient. See the page on DeadLock and note that all four criteria must hold (the claim being only one of them).


While there is a DeadLock-free solution to the DiningPhilosophers problem; it has been proven that any system consisting of n philosophers (for n > 2) sitting 'round the table ruminating about the DefinitionOfLife will always enter a LiveLock state (with assertions being repeated and counter-assertions ignored). This is especially true when the philosophers in question are actually employed as computer programmers, and philosophy is merely an amateur diversion which they undertake for the purpose of blowing off steam.

The Drinking Philosophers problem (see http://www.cs.utexas.edu/users/misra/scannedPdf.dir/DrinkingPhil.pdf) is a much more enjoyable problem to solve; the solution was first given in Python.


Instead of holding the salt shaker all the time the philosopher is eating, you can hold it only while performing resource acquisition. If you have the shaker, you can attempt to acquire both the chopsticks, but if you fail, you have to release all of the chopsticks that you've acquired. (Then the salt shaker can be picked up by the next philosopher.) This would solve the problem of only one philospher eating at once. Not sure how fair it would be to the philosphers though.

This solution, in fairness, reduces our problem of how not to deadlock multiple resources down to how not to deadlock one resource, the salt shaker. -- MatthewFarwell

That is a sensible reduction: you can't deadlock on one resource.


See also DiningPhilosophersChallenge, PartingPhilosophersProblem


CategoryConcurrency

EditText of this page (last edited May 12, 2011) or FindPage with title or text search