Figure shows a diagram
of the classic Dining Philosophers problem [Dij71].
This problem features five philosophers who do nothing but think and
eat a ``very difficult kind of spaghetti'' which requires two forks
to eat.
A given philosopher is permitted to use only the forks to his or her
immediate right and left, and once a philosopher picks up a fork,
he or she will not put it down until sated.
The object is to construct an algorithm that, quite literally, prevents starvation. One starvation scenario would be if all of the philosophers picked up their leftmost forks simultaneously. Because none of them would put down their fork until after they ate, and because none of them may pick up their second fork until at least one has finished eating, they all starve.
Dijkstra's solution used a global semaphore, which works fine assuming
negligible communications delays, an assumption that has become invalid
in the ensuing decades.
Therefore, recent solutions number the forks as shown in
Figure .
Each philosopher picks up the lowest-numbered fork next to his or her
plate, then picks up the highest-numbered fork.
The philosopher sitting in the uppermost position in the diagram thus
picks up the leftmost fork first, then the rightmost fork, while the
rest of the philosophers instead pick up their rightmost fork first.
Because two of the philosophers will attempt to pick up fork 1 first,
and because only one of those two philosophers will succeed,
there will be five forks available to four philosophers.
At least one of these four will be guaranteed to have two forks,
and thus be able to proceed eating.
This general technique of numbering resources and acquiring them in numerical order is heavily used as a deadlock-prevention technique. However, it is easy to imagine a sequence of events that will result in only one philosopher eating at a time even though all are hungry:
Please think about ways of partitioning the Dining Philosophers Problem before reading further.
One approach is shown in
Figure ,
which includes four philosophers rather than five to better illustrate the
partition technique.
Here the upper and rightmost philosophers share a pair of forks,
while the lower and leftmost philosophers share another pair of forks.
If all philosophers are simultaneously hungry, at least two will
be able to eat concurrently.
In addition, as shown in the figure, the forks can now be bundled
so that the pair are picked up and put down simultaneously, simplifying
the acquisition and release algorithms.
Quick Quiz 7.1: Is there a better solution to the Dining Philosophers Problem? End Quick Quiz
This is an example of ``horizontal parallelism'' [Inm85] or ``data parallelism'', so named because there is no dependency among the philosophers. In a data-processing system, a given item of data would pass through only one of a replicated set of software components.
Quick Quiz 7.2: And in just what sense can this ``horizontal parallelism'' be said to be ``horizontal''? End Quick Quiz
Paul E. McKenney 2011-12-16