Programming Interviews Exposed: Secrets to Landing Your Next Job, Second Edition

8.3. The Dining Philosophers

NOTE

Five introspective and introverted philosophers are sitting at a circular table. In front of each philosopher is a plate of food. A fork (or a chopstick) lies between each philosopher, one by the philosopher's left hand and one by the right hand. A philosopher cannot eat until he or she has both forks in hand. Forks are picked up one at a time. If a fork is unavailable, the philosopher simply waits for the fork to be freed. When a philosopher has two forks, he or she eats a few bites and then returns both forks to the table. If a philosopher cannot obtain both forks for a long time, he or she will starve. Is there an algorithm that will ensure that no philosophers starve?

This is another concurrency classic, and although it may seem quite contrived — in the real world no one would starve because each philosopher would simply ask the adjacent philosophers for their forks — it accurately reflects real-world concurrency issues involving multiple shared resources. The point of the problem is to see whether you understand the concept of deadlock and know how it avoid it.

Start by trying a few simple tests to determine when deadlock happens and what you can do to avoid it. It won't take you long to figure out that deadlock occurs quite readily. Consider the following implementation in which each philosopher picks up the forks in the same order, left followed by right:

public class DiningPhilosophers { // Each "fork" is just an Object we synchronize ...