The Dining Philosophers Problem

Five philosophers spend their time eating and thinking. The college where they live has a dining table with a large bowl of spaghetti in the center of the table. There are five plates at the table and five forks set between the plates.



Eating the spaghetti requires the use of two forks (often, the problem is explained with chopsticks instead of forks, because it is easier to understand requiring two chopsticks to eat spaghetti than two forks) which the philosophers pick up one at a time. The philosophers never speak to each other which creates a dangerous possibility of deadlock in which every philosopher holds a left fork and waits perpetually for a right fork (or vice versa).

So how do we write out a procedure such that this procedure applies to each and every philosopher, and so that the philisophers can eat using two forks when they are hungry and not starve?


This is the dining philosophers problem, originally proposed by none other than EW Dijkstra in 1971. It is perhaps one the most famous example of a common computing problem in concurrency.