Solutions to the Dining Philosopher problem
CS 300 (PDC)
It's difficult to find a correct solution to the dining philosophers problem. How can we avoid starvation, deadlock, and race conditions? Can we find an algorithm that is fair (all philosophers get comparable opportunities to eat), has a high degree of concurrency (e.g., allows multiple philosophers to eat at the same time), and does not require philosophers to wait long to eat when they're ready? Will a solution remain feasible for a very large number of processors?
Deadlock and starvation are very bad, but nothing compares to debugging race conditions: if the correct behavior of an algorithm depends on timing (definition of race condition), then incorrect behavior can't be reproduced, because we can't expect exact duplication of a sporadic sequence of events.
Fortunately, the cause of race conditions is known:
between checking on a critical resource and acting on that check,
another process intervenes, making that check out of date and the
action incorrect. For example, in the first race condition example for the
dining philosophers problem, a race occurs during the if
statement
if (!myturn[p])
sleep() /* to be awakened by prev philosopher */
If another process B changes myturn[p] to true
after this process A evaluates the guard
(!myturn[p] and before process A calls
sleep(), then B's wakeup() call may
be wasted before A has called sleep(), meaning
that there will be no way to wake up A. Here, the guard
(!myturn[p] is the "check" and the sleep()
call is the action that should only be perfomed if
myturn[p] is false.
Therefore, to avoid race conditions, we must somehow guarantee
that no process B can intervene during process A's
evaluation of conditionals that involve shared computing resources. That would
make for an atomic (or indivisible) if
statement.
One way to make operations indivisible is to locate them in a separate synchronization process that receives requests and sends responses through message passing. If all processes use the synchronization process to access the shared resources, then the synchronization process can guarantee that no two processes interfere with each other to cause a race.
There are other strategies for implementing atomicity for correct interprocess communication besides message-passing approaches. But message passing fits parallel computing well, especially in distributed computing environments (many of the other solutions depend on all processes being on one computer and one operating system).
______
In the solutions to the Dining Philosophers problem below, we will assume that race conditions are avoided using some kind of atomicity strategy.
The waiter solution provides a simple way to solve the Dining Philosophers problem, assuming an external entity called the waiter.
Strategy:
Every philosopher must request each of their (shared) chopsticks from a waiter, who may refuse the request at first in order to avoid a deadlock.
For convenience, we assume that all philosophers request their left chopstick first, then their right chopstick.
The waiter always provides chopsticks upon request unless only one chopstick remains unused. In that case, the waiter honors the request only if a right chopstick is requested; requests for a left chopstick are deferred until another philosopher finishes eating.
Argument for correct deadlock avoidance: The last chopstick will only be assigned if the waiter is certain that at least one philosopher can finish eating (thereupon releasing chopsticks). Therefore, the "circular wait" required for deadlock can't occur.
No starvation; fairness (depending on your waiter); degree of concurrency...
Downside: Scalability (the waiter could become a bottleneck if the number of processors is large).
In 1984, K. Chandy and J. Misra proposed a solution to a generalized Dining Philosophers problem, which doesn't require the philosophers to be in a circle or to share only two resources with only nearest neighbors.
Chandy-Misra's algorithm may be described in terms of "clean" and "dirty" chopsticks. Each chopstick is shared with a pair of philosophers.
Each chopstick is always in the possession of one of it's two philosophers.
Also, a dirty chopstick is always cleaned just before it is given to its other philosopher.
Initialization. Every process receives a unique integer ID number. For every pair of philosophers who contend for a chopstick, one chopstick is created, assigned to the philosopher with the lower ID number (lower neighbor), and marked as "dirty."
Thinking. When a philosopher p is thinking, if that philosopher p receives a request for a particular chopstick c from one of that philosopher's neighbors, then p gives the neighbor that chopstick c (after cleaning it).
Hungry. When a philosopher p is preparing to eat, p requests any chopsticks that p doesn't already have from the appropriate neighbor.
During this time, if a neighbor asks p for a chopstick that p possesses, then p sends that chopstick (after cleaning it) if it's dirty, and keeps that chopstick for the present if it's clean. p defers the requests for already-clean chopsticks (i.e., remembers the clean requests for later delivery).
Eating. A philosopher p may start eating as soon as p has all of p's chopsticks. While eating, all requests for chopsticks are deferred, and all chopsticks become dirty.
Cleanup. Immediately after eating, a philosopher delivers any chopsticks for which there are deferred requests (after cleaning them). That philosopher then proceeds to eat.
Deadlock avoidance of the Chandy-Misra algorithm can be proven using directed graphs: each philosopher represents a vertex, and each edge represents a chopstick, with an arrow going from "dirty towards clean". The ID ordering of philosophers can be used to show that this graph never has a closed cycles (i.e., deadlock circular waits), by reassigning a (lower) ID to philosophers just after they finish eating, thus insuring that the graph's arrows always point from lower towards higher IDs.
No starvation: Since a hungry philosopher p always keeps p's clean chopsticks, and since each of p's neighbors must deliver their shared chopstick to p, cleaned, either immediately (if the neighbor is thinking) or as soon as that neighbor finishes eating, then we conclude that a hungry philosopher p cannot be passed up more than once by any neighbor. By transitivity, each of p's hungry or eating neighbors must eventually finish eating, which guarantees that p won't starve. (But p may have to fast for a long time.)
Fairness (after eating, all resources are designated for the neighbors); high degree of concurrency; scalable (because after initialization; the resource management is local -- no central authority needed); generalizes to any number of processes and resources (as long as each resource is shared by exactly two processes).
Downside: potentially long wait chains when hungry.