DiningPhilosophers

From Epowiki

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.

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

We're really modelling a single-processor-multiple-thread 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

• 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:ForTheCurious,IfWeNumberThePhilosophers1To5,OneSuchScheduleWouldBe(3,5)->(1,4)->(2,4)->(1,3)->(5,2)OrAnyPermutationThereof.ThisAlwaysEnsuresEachPhilosopherCanPickUpBothChopsticksInTurn,IsFair-EachPhilosopherGetsToEatTwiceDuringTheSchedule-AndWillNeitherDeadlockNorStarve. | [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 preemption 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.