Dining philosophers problem

From Wikipedia, the free encyclopedia

In computer science, the dining philosophers problem is an illustrative example of a common computing problem in concurrency. It is a classic multi-process synchronization problem, and is included in nearly all college-level computer science curriculums.

In 1971, Edsger Dijkstra set an examination question on a synchronization problem where five computers competed for access to five shared tape drive peripherals. Soon afterwards the problem was retold by Tony Hoare as the dining philosopher's problem.

Five philosophers spend their time eating and thinking. The college where they live has a dining table with a large bowl of spaghetti in the center of the table. There are five plates at the table and five forks set between the plates.

Illustration of the dining philosophers problem

Eating the spaghetti requires the use of two forks (often, the problem is explained with chopsticks instead of forks, because it is easier to understand requiring two chopsticks to eat spaghetti than two forks) which the philosophers pick up one at a time. The philosophers never speak to each other which creates a dangerous possibility of deadlock in which every philosopher holds a left fork and waits perpetually for a right fork (or vice versa).

Originally used as a means of illustrating the problem of deadlock, this system reaches deadlock when there is a 'cycle of ungranted requests'. In this case philosopher P₁ waits for the fork grabbed by philosopher P₂ who is waiting for the fork of philosopher P₃ and so forth, making a circular chain.

Starvation (and the pun was intended in the original problem description) might also occur independently of deadlock if a philosopher is unable to acquire both forks due to a timing issue. For example there might be a rule that the philosophers put down a fork after waiting five minutes for the other fork to become available and wait a further five minutes before making their next attempt. This scheme eliminates the possibility of deadlock (the system can always advance to a different state) but still suffers from the problem of livelock. If all five philosophers appear in the dining room at exactly the same time and each picks up their left fork at the same time the philosophers will wait five minutes until they all put their forks down and then wait a further five minutes before they all pick them up again.

The lack of available forks is an analogy to the locking of shared resources in real computer programming, a situation known as concurrency. Locking a resource is a common technique to ensure the resource is accessed by only one program or chunk of code at a time. When the resource the program is interested in is already locked by another one, the program waits until it is unlocked. When several programs are involved in locking resources, deadlock might happen, depending on the circumstances. For example, one program needs two files to process. When two such programs lock one file each, both programs wait for the other one to unlock the other file, which will never happen.

1 Solutions
- 1.1 Dijkstra's Solution
- 1.2 Chandy / Misra Solution
2 References
3 See also
4 External links

[edit] Solutions

This article or section may be confusing or unclear for some readers.
Please improve the article or discuss this issue on the talk page. This article has been tagged since December 2006.

[edit] Dijkstra's Solution

Positions of philosophers and forks in ordering solution.

One solution is to order the forks and require the philosophers to pick up the forks in increasing order. To illustrate this solution, label the philosophers P₁, P₂, P₃, P₄, and P₅, and label the forks F₁, F₂, F₃, F₄, and F₅. Each philosopher must pick up forks in a prescribed order and cannot pick up a fork another philosopher already has. Upon acquiring two forks, a philosopher may eat. Philosophers P₁ through P₄ follow the rule that P_x must pick up fork F_x first and then may pick up fork F_x+1. For example, P₁ must pick up F₁ first and F₂ second. Philosopher P₅ follows a slightly different rule, picking up fork F₁ before picking up fork F₅. If P₅ followed the same rule as the others, F₅ would come before F₁. This change in behavior for P₅ creates an asymmetry that prevents deadlock.

Preventing starvation depends on the method of mutual exclusion enforcement used. Implementations using spinlocks or busy waiting can cause starvation through timing problems inherent in these methods. Other methods of mutual exclusion that utilize queues can prevent starvation by enforcing equal access to a fork by the adjacent philosophers.

Dijkstra's solution can be extrapolated to represent arbitrary contention between philosophers, but requires all the forks to be labeled correctly for such configurations.

[edit] Chandy / Misra Solution

In 1984, K. M. Chandy and J. Misra proposed a different solution to the Dining Philosophers problem to allow for arbitrary agents (numbered P₁, ..., P_n) to contend for an arbitrary number of resources (numbered R₁, ..., R_m). Unlike in Dijkstra's solution, these labelings can be arbitrary. They solved this general problem using an elegant solution:

For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID. Each fork can either be dirty or clean. Initially, all forks are dirty.
When a philosopher wants to use a set of resources (i.e. eat), he must obtain the forks from his contending neighbors. For all such forks he does not have, he sends a request message.
When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but gives it up when it is dirty. If he sends the fork over, he cleans the fork before doing so.
After a philosopher is done eating, all his forks become dirty. If another philosopher had previously requested one of the forks, he cleans the fork and sends it.

This solution also allows for a large degree of concurrency.

[edit] References

Silberschatz, Abraham; Peterson, James L. (1988). Operating Systems Concepts. Addison-Wesley. ISBN 0-201-18760-4.
Chandy, K.M.; Misra, J. (1984). The Drinking Philosophers Problem. ACM Transactions on Programming Languages and Systems.
Dijkstra, E. W. (1971, June). Hierarchical ordering of sequential processes. Acta Informatica 1(2): 115-138.
Lehmann, D. J., Rabin M. O, (1981). On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. Principles Of Programming Languages 1981 (POPL'81), pages 133-138