The JavaTM Tutorial
Previous Page Lesson Contents Next Page Start of Tutorial > Start of Trail > Start of Lesson Search
Feedback Form

Trail: Essential Java Classes
Lesson: Threads: Doing Two or More Tasks at Once

Starvation and Deadlock

If you write a program in which several concurrent threads are competing for resources, you must take precautions to ensure fairness. A system is fair when each thread gets enough access to limited resources to make reasonable progress. A fair system prevents starvation and deadlock. Starvation occurs when one or more threads in your program are blocked from gaining access to a resource and, as a result, cannot make progress. Deadlock, the ultimate form of starvation, occurs when two or more threads are waiting on a condition that cannot be satisfied. Deadlock most often occurs when two (or more) threads are each waiting for the other(s) to do something.

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.
Note: If you don't see the applet running above, you need to install Java Plug-in, which happens automatically when you install the J2SE JRE or JDK. This applet requires JDK 5.0 or later. You can find more information in the Java Plug-in home page.

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 don't wait — they just grab.

Thus, 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. In other words, 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 can proceed for a while without deadlocking. However, deadlock is always possible with this particular implementation of the DiningPhilosophers 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 first pick up 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 doesn't get chopstick 1 must now wait for the first philosopher to release it. Deadlock is not possible.


Previous Page Lesson Contents Next Page Start of Tutorial > Start of Trail > Start of Lesson Search
Feedback Form

Copyright 1995-2005 Sun Microsystems, Inc. All rights reserved.