Dining Philosophers Problem


Dining Philosophers Problem

(parallel)(DPP) A problem introduced by Dijkstra concerningresource allocation between processes. The DPP is a model anduniversal method for testing and comparing theories onresource allocation. Dijkstra hoped to use it to help createa layered operating system, by creating a machine whichcould be consider to be an entirely deterministicautomaton.

The problem consists of a finite set of processes which sharea finite set of resources, each of which can be used by onlyone process at a time, thus leading to potential deadlock.

The DPP visualises this as a number of philosophers sittinground a dining table with a fork between each adjacent pair.Each philosopher may arbitrarily decide to use either the forkto his left or the one to his right but each fork may only beused by one philosopher at a time.

Several potential solutions have been considered.

Semaphores - a simple, but unfair solution where eachresources is a binary semaphore and additional semaphoresare used to avoid deadlock and/or starvation.

Critical Regions - each processor is protected frominterference while it exclusively uses a resource.

Monitors - the process waits until all required resources areavailable then grabs all of them for use.

The best solution allows the maximum parallelism for anynumber of processes (philosophers), by using an array to trackthe process' current state (i.e. hungry, eating, thinking).This solution maintains an array of semaphores, so hungryphilosophers trying to acquire resources can block if theneeded forks are busy.