DINING PHILOSOPHERS PROBLEM

Domain	Definition
Computing	Dining Philosophers Problem (DPP) A problem introduced by Dijkstra concerning resource allocation between processes. The DPP is a model and universal method for testing and comparing theories on resource allocation. Dijkstra hoped to use it to help create a layered operating system, by creating a machine which could be consider to be an entirely deterministic automaton. The problem consists of a finite set of processes which share a finite set of resources, each of which can be used by only one process at a time, thus leading to potential deadlock. The DPP visualises this as a number of philosophers sitting round a dining table with a fork between each adjacent pair. Each philosopher may arbitrarily decide to use either the fork to his left or the one to his right but each fork may only be used by one philosopher at a time. Several potential solutions have been considered. Semaphores - a simple, but unfair solution where each resources is a binary semaphore and additional semaphores are used to avoid deadlock and/or starvation. Critical Regions - each processor is protected from interference while it exclusively uses a resource. Monitors - the process waits until all required resources are available then grabs all of them for use. The best solution allows the maximum parallelism for any number of processes (philosophers), by using an array to track the process' current state (i.e. hungry, eating, thinking). This solution maintains an array of semaphores, so hungry philosophers trying to acquire resources can block if the needed forks are busy. (1998-08-09). Source: The Free On-line Dictionary of Computing.
Source: compiled by the editor from various references; see credits.

Specialty Definition: Dining philosophers problem

In computer science, the dining philosophers problem is an illustrative example of a common computing problem.

In 1965, Edsger Dijkstra used the example of a group of philosophers to solve a synchronization problem. Five philosophers are sat around a circular table and each has a plate of spaghetti in front of him with a fork 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 a waits for the fork grabbed by philosopher b who is waiting for the fork of philosopher c 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 solution consists of having the philosophers report their state as hungry, thinking, and eating. A philosopher cannot eat unless he has declared his state as hungry and both of his neighboring philosophers are not eating. The status of the philosophers is kept using a shared data struture (e.g an array). A philosopher may enter the eating state only if both of its neighbors are not in that state. To ensure this, the philosopher obtains a mutex lock and then changes his state from thinking to hungry. After he changes his state, he tries to obtain both forks and will not do so until both of his neighbors have left the eating state. At which point the philosopher, changes his state to eating and releases the lock. The philosopher then eats. After the philosopher is done eating, he again obtains a mutex lock, changes his state to thinking and sees, one at a time, if any of its two neighbors is hungry. If at least one is hungry, that philosopher enters the eating state and the cycle continues.

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 never happens.