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:

Order the chopsticks, so that the philosopher has to pick up chopstick N, then chopstick N+1. This means that one of the philosophers will pick up his right chopstick first, while all of the others are picking up the left chopstick first. This is the same as having odd numbered philosophers pick up their chopsticks left/right, and even numbered philosophers pick up theirs right/left. This solution relies on breaking the circular wait. Also, every philosopher will get to eat at some point.
A philosopher who wants to eat first picks up the sole salt shaker on the table, then picks up his chopsticks, eats and then puts the salt shaker back. This solution while viable isn't great, as it means that only one philosopher can eat at any one time. This solution breaks the 'holding while acquiring' deadlock condition and if we further stipulate that the philosophers agree to go around the table and pick up the salt shaker in turn, this solution is also fair and ensures no philosopher starves.
Each philosopher flips a coin. Heads, he picks up the right chopstick first, tails, the left. If the second chopstick is busy, he puts down the first and tries again. With probability 1, he will eventually eat. Again, this solution relies on defeating circular waiting whenever possible and then resorts to breaking 'acquiring while holding' as assurance for the case when two adjacent philosophers' coins both come up the same. Again, this solution is fair and ensures all philosophers can eat eventually.
The chef sees the philosopher's predicament, scorns the philosophers for letting his fine meal of noodles go cold and agrees with the philosophers that he'll dictate who should eat and when to prevent any confusion. This breaks the 'blocking shared resources' condition. The chef assures all philosophers that when they try to pick up their chopsticks, they will be free. Effectively the chef enforces a fair, serialized schedule of chopstick use over the philosophers. This is the most efficient solution (no shared resources/locking involved) but is in practice the hardest to achieve (the chef must know how to instruct the philosophers to eat in a fair, interference-free fashion). [Aside: For the curious, if we number the philosophers 1 to 5, one such schedule would be (3, 5)->(1, 4)->(2, 4)->(1, 3)->(5, 2) or any permutation thereof. This always ensures each philosopher can pick up both chopsticks in turn, is fair - each philosopher gets to eat twice during the schedule - and will neither deadlock nor starve.]
The philosophers use a pre-emption scheme based on hunger. As a philosopher nears starvation his hunger index rises above the "acquire while holding" value of one or both of his neighbors; at that point they must relinquish the use of their chopsticks and allow the starving philosopher to eat. Once the hungry philosopher is satiated his hunger index drops below the value of another starving philosopher's index and he has to give up his chopsticks.

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:

Access to the chopsticks is granted through a forwarder. After enough time has passed/N noodles are eaten, remove acess to chopsticks by disengaging the forwarder. (In the real world, that would be "have the chopsticks on strings, yoink them back once each philosopher has had enough to eat for now.")

"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:

turn off task-switching, set the lock to the current task, turn on task-switching. Often done by turning interrupts on and off. Works fine with single-processor system, but not with multiple processors.
Use a single special instruction such as "CompareAndSet?" to set the lock. Works fine with shared-memory multiprocessor systems (as well as single-processor systems), but not networked processors. If multiple processors try to access RAM at the same time, the bus arbitrator arbitrarily allows only one processor to go at a time (and it allows processors to execute the full CompareAndSet? instruction without interruption). (the "bus arbitrator" plays the role of the chef).
Use .... for networked processors.

"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.

Didn't a recent NASA mars lander [MarsPathfinder] have a (temporary) DeadLock problem? It was PriorityInversion (leading to a failure to meet timing constraints), not DeadLock. See <http://research.microsoft.com/~mbj/Mars_Pathfinder/>.
A much better SynchronizationProblem? would be a BankMoneyTransfer.

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.

I'd be interested to see a link to the proof claim above. For example, my fourth bullet point above discussing solutions to the DiningPhilosophers problem gives a solution for n = 5 which does not DeadLock or LiveLock (as it is fair). This seems to me to be a counter-example to the above claim, hence I'd be very interested to see the above proof.
- You seem to have missed the point - it's supposed to be a joke.

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.

A philosopher who wants to eat first picks up the sole salt shaker on the table, then picks up his chopsticks, eats and then puts the salt shaker back. This solution while viable isn't great, as it means that only one philosopher can eat at any one time. This solution breaks the 'holding while acquiring' deadlock condition and if we further stipulate that the philosophers agree to go around the table and pick up the salt shaker in turn, this solution is also fair and ensures no philosopher starves.

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.

CategoryConcurrency