The JavaTM Tutorial

Trail: Essential Java Classes

The story of the dining philosophers is often used to illustrate various problems that can occur when many synchronized threads are competing for limited resources. The story goes like this. Five philosophers are sitting at a round table. In front of each philosopher is a bowl of rice. Between each pair of philosophers is one chopstick. Before taking a bite of rice, an individual philosopher must have two chopsticks: one taken from the left and one taken from the right. The philosophers must find a way to share chopsticks so that they all get to eat.

The dining philosophers algorithm is implemented by the `DiningPhilosophers` applet, which works as follows:

1. Duke always reaches for the chopstick on his left first. If the chopstick is there, Duke takes it and raises his left hand.
2. Duke tries for the right chopstick. If the chopstick is available, Duke picks it up and raises his right hand.
3. When Duke has both chopsticks, he takes a bite of rice and says, Good!
4. He then puts both chopsticks down, thereby allowing either of his two neighbors to get the chopsticks.
5. Duke then starts all over again by trying for the right chopstick. Between each attempt to grab a chopstick, Duke pauses for a random period of time.

This is a picture of the applet's GUI. To run the applet, click the picture. The applet will appear in a new browser window.

Dining Philosophers Applet

The slider at the bottom of the applet controls the amount of time that each philosopher waits before attempting to pick up a chopstick. When the slider is set to 0, the philosophers dont wait—they just grab—and the applet often ends up in deadlock—that is, all the philosophers are frozen with their right hands in the air. Why? Because each immediately has one chopstick and is waiting on a condition that cannot be satisfied. That is, each is waiting for the chopstick on the left, which is held by the philosopher to the left.

When you move the slider so that the waiting period is longer, the applet may proceed for a while without deadlocking. However, deadlock is always possible with this particular implementation of the dining philosophers problem because it is possible for all five philosophers to be holding their right chopsticks. Rather than rely on luck to prevent deadlock, you must either explicitly prevent it or detect it.

For most programmers, the better choice is to prevent deadlock rather than to try to detect it. The simplest approach to preventing deadlock is to impose ordering on the condition variables. In the dining philosopher applet, no ordering is imposed on the condition variables because the philosophers and the chopsticks are arranged in a circle. All chopsticks are equal.

However, you can change the rules in the applet by numbering the chopsticks 1 through 5 and insisting that the philosophers pick up first the chopstick that has the lower number. The philosopher who is sitting between chopsticks 1 and 2 and the philosopher who is sitting between chopsticks 1 and 5 must now reach for the same chopstick first (chopstick 1) rather than picking up the one on the right. Whoever gets chopstick 1 first is then free to take another chopstick. Whoever doesnt get chopstick 1 must now wait for the first philosopher to release it. Deadlock is not possible.