The Dining Philosophers

One of the most famous concurrency problems posed, and solved, by Dijkstra, is known as the dining philosopher’s problem“Hierarchical ordering of sequential processes” by E.W. Dijkstra. Available online here: http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD310.PDF. Presents numerous concurrency problems, including Dining Philosophers. The Wikipedia page about this problem is also useful.. The problem is famous because it is fun and somewhat intellectually interesting; however, its practical utility is low. However, its fame forces its inclusion here; indeed, you might be asked about it in some interview, and you’d really hate us if you miss that question and don’t get the job. Conversely, if you get the job, please feel free to send us a nice note, or some stock options.

The basic setup for the problem is this (as shown in the figure above): assume there are five “philosophers” sitting around a table. Between each pair of philosophers is a single fork (and thus, ...