Dining Philosophers Problem

(redirected from Dining philosophers)

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.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
Mentioned in ?
References in periodicals archive ?
In particular, we illustrate MP-synthesis by applying it to the K-process mutual exclusion problem, the K-process dining philosophers problem, and the K-process drinking philosophers problem [Chandy and Misra 1984; Chandy and Misra 1988] for arbitrarily large finite K.
One thousand dining philosophers arranged in a ring:
From this we synthesize the process [P.sub.1] in the solution for the original dining philosophers problem (five philosophers in a circle), which is shown in Figure 6.
Consider the solution for the generalized dining philosophers problem given in Figure 7.
King, sponsor University of Pennsylvania ACM (Philadelphia, PA) The Dining Philosophers Rachel White, chairman Insup Lee, sponsor
With its seventy lines of (incomplete) code, six procedures, and four illustrative figures, Ringwood's Parlog86 program for solving the dining philosophers problem is indeed an easy mark.
Sure the picture of Linda versus concurrent logic languages looks different after rehabilitating the dining philosophers. But is this the whole story?
Compare the following occam code with the CLinda example for the Dining Philosophers Problem.
Turning to the dining philosophers example with which Shapiro begins-if we were members of the CLP community, we would find this demonstration deeply alarming.
A classic problem in concurrent programming is that of the "dining philosophers" which challenges the power of any aspiring concurrent program language.
This complexity is illustrated by an explanation of the dining philosophers problem.
Though the problem of the dining philosophers [10] appears to have greater entertainment value than practical importance, it has had huge theoretical influence.