Dining philosophers problem

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.

In 1965, Edsger Dijkstra used the example of a group of philosophers to solve a synchronization problem. Five philosophers are sitting around a circular table and each has a plate of spaghetti in front of him with a fork at either side (i.e. five philosophers, five plates, and five forks).

Suppose that the life of a philosopher consists of periods of eating and thinking, that each philosopher needs two forks to eat, and that forks are picked up one at a time. After successfully picking up two forks, a philosopher eats for a while and then puts down the forks and thinks. The problem consists in developing an algorithm to avoid starvation and deadlock. Deadlock might occur if each of the five philosophers has one fork and no one can get a second fork. The 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 of deadlock. Starvation might also happen independently of deadlock if a philosopher is unable to acquire both forks.

The lack of available forks is an analogy to the locking of scarce 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 resources 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.

Solution

One solution is to order the forks and require the philosophers to pick the forks up in increasing order. In this solution the philosophers are labeled P₁, P₂, P₃, P₄, and P₅ and the forks are likewise labeled F₁, F₂, F₃, F₄, and F₅. The first philosopher (P₁) will pick up the first fork (F₁) before he is allowed to pick up the second fork (F₂). Philosophers P₂ through P₄ will behave in a similiar fashion, picking up the fork F_x before picking up fork F_x+1. Philosopher P₅ however picks up fork F₁ before picking up fork F₅. This change in behavior for P₅ creates an asymmetry that prevents deadlock.

Prevention of starvation is dependent on the method of mutual exclusion enforcement employed. 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.

This solution can also be generalized to allow for an arbitray number of agents (A₁...A_m) needing access to an arbitrary number of resources (R₁...R_n) requiring exclusive access. Under this solution all agents must abide by the following rules:

1. All resources must request access to the resources in increasing order (i.e. Access to R₃ must be acquired before requesting access to R₄).
2. If an agent has access to a resource R_x and needs access to resource R_y it must release R_x before making the request if x > y (i.e. The agent controls resources R₂, R₅, R₉, R₁₅, and R₂₀. It must release R₁₅ and R₂₀ before requesting access to R₁₂).

References

See also

• Sleeping barber problem
• Spontaneous symmetry breaking

External links

• Discussion of the problem with solution code for 2 or 4 philosophers
• A solution to the dining philosophers problem
• Discussion of various solutions 1
• Discussion of various solutions 2
• Distributed symmetric solutions
• Interactive example of the Philosophers problem (Java required)