The dining philosophers

We only mention that this problem exists, and that it can be solved using semaphores. The solution is in the book if you are interested (section 2.3.1), and it will be on the Web site eventually.

The problem is that there are five obesely corpulant philosophers who sit around a table and eat spaghetti all day, pausing only to stare into space and speculate on life's great inponderables. They have an infinite supply of spaghetti, and probably colotomy bags, so that's not the problem. The problem is the forks. The restaurant only supplied five forks (which is reasonable), but the philosophers have very little coordination, and each requires two forks to eat spaghetti. So what a philosopher wishes to eat, she or he must pick up a fork from either side.

One algorithm is for a philosopher who is hungry to wait on the left fork, then wait on the right fork. Trouble is, what if all the philosophers want to eat simultaneously, and each picks up their left fork simultaneously: then all of them wait for their respective right-hand neightbours, and are stuck waiting forever. This is deadlock.

Or they could try for their left fork, then try for the right fork, but if it is not available, put the left fork down and wait a while, and try again. If all the philosophers do this simultaneously, no one gets to eat, and it is called starvation. (It isn't deadlock, because they're not waiting.)

Anyway, a solution is possible.


last updated 17 February 1998