7.1.1 Dining Philosophers Problem

Figure: Dining Philosophers Problem
\includegraphics[scale=.7]{SMPdesign/DiningPhilosopher5}

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.

Figure: Dining Philosophers Problem, Textbook Solution
\includegraphics[scale=.7]{SMPdesign/DiningPhilosopher5TB}

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:

  1. P2 picks up fork 1, preventing P1 from taking a fork.
  2. P3 picks up fork 2.
  3. P4 picks up fork 3.
  4. P5 picks up fork 4.
  5. P5 picks up fork 5 and eats.
  6. P5 puts down forks 4 and 5.
  7. P4 picks up fork 4 and eats.

Please think about ways of partitioning the Dining Philosophers Problem before reading further.

Figure: Dining Philosophers Problem, Partitioned
\includegraphics[scale=.7]{SMPdesign/DiningPhilosopher4part-b}

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