Dining Philosophers Problem

parallel (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)