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.

Related Topics:
Computer science - Concurrency - Multi-process - Synchronization

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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).

Related Topics:
1965 - Edsger Dijkstra

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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 P1 waits for the fork grabbed by philosopher P2 who is waiting for the fork of philosopher P3 and so forth, making a circular chain of deadlock. 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.

Related Topics:
Algorithm - Starvation - Deadlock

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~