Dining Philosophers Problem definition
<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)
Nearby terms:
DIN « DIN-8 « ding « Dining Philosophers Problem » dink » DinnerBell » DINO
|
