Deadlock
Because threads can become blocked and because objects can have synchronized methods that prevent threads from accessing that object until the synchronization lock is released, it’s possible for one thread to get stuck waiting for another thread, which in turn waits for another thread, etc., until the chain leads back to a thread waiting on the first one. You get a continuous loop of threads waiting on each other, and no one can move. This is called deadlock.
If you try running a program and it deadlocks right away, you immediately know you have a problem and you can track it down. The real problem is when your program seems to be working fine but has the hidden potential to deadlock. In this case you may get no indication that deadlocking is a possibility, so it will be latent in your program until it unexpectedly happens to a customer (and you probably won’t be able to easily reproduce it). Thus, preventing deadlock by careful program design is a critical part of developing concurrent programs.
Let’s look at the classic demonstration of deadlock, invented by Dijkstra: the dining philosophers problem. The basic description specifies five philosophers (but the example shown here will allow any number). These philosophers spend part of their time thinking and part of their time eating. While they are thinking, they don’t need any shared resources, but when they are eating, they sit at a table with a limited number of utensils. In the original problem description, the utensils are forks, and two forks are required to get spaghetti from a bowl in the middle of the table, but it seems to make more sense to say that the utensils are chopsticks; clearly, each philosopher will require two chopsticks in order to eat.
A difficulty is introduced into the problem: As philosophers, they have very little money, so they can only afford five chopsticks. These are spaced around the table between them. When a philosopher wants to eat, he or she must get the chopstick to the left and the one to the right. If the philosopher on either side is using the desired chopstick, then our philosopher must wait.
Note that the reason this problem is interesting is because it demonstrates that a program can appear to run correctly but actually be deadlock prone. To show this, the command-line arguments allow you to adjust the number of philosophers and a factor to affect the amount of time each philosopher spends thinking. If you have lots of philosophers and/or they spend a lot of time thinking, you may never see the deadlock even though it remains a possibility. The default command-line arguments tend to make it deadlock fairly quickly:
//: c13:DiningPhilosophers.java
// Demonstrates how deadlock can be hidden in a program.
// {Args: 5 0 deadlock 4}
import java.util.*;
class Chopstick {
private static int counter = 0;
private int number = counter++;
public String toString() {
return "Chopstick " + number;
}
}
class Philosopher extends Thread {
private static Random rand = new Random();
private static int counter = 0;
private int number = counter++;
private Chopstick leftChopstick;
private Chopstick rightChopstick;
static int ponder = 0; // Package access
public Philosopher(Chopstick left, Chopstick right) {
leftChopstick = left;
rightChopstick = right;
start();
}
public void think() {
System.out.println(this + " thinking");
if(ponder > 0)
try {
sleep(rand.nextInt(ponder));
} catch(InterruptedException e) {
throw new RuntimeException(e);
}
}
public void eat() {
synchronized(leftChopstick) {
System.out.println(this + " has "
+ this.leftChopstick + " Waiting for "
+ this.rightChopstick);
synchronized(rightChopstick) {
System.out.println(this + " eating");
}
}
}
public String toString() {
return "Philosopher " + number;
}
public void run() {
while(true) {
think();
eat();
}
}
}
public class DiningPhilosophers {
public static void main(String[] args) {
if(args.length < 3) {
System.err.println("usage:\n" +
"java DiningPhilosophers numberOfPhilosophers " +
"ponderFactor deadlock timeout\n" +
"A nonzero ponderFactor will generate a random " +
"sleep time during think().\n" +
"If deadlock is not the string " +
"'deadlock', the program will not deadlock.\n" +
"A nonzero timeout will stop the program after " +
"that number of seconds.");
System.exit(1);
}
Philosopher[] philosopher =
new Philosopher[Integer.parseInt(args[0])];
Philosopher.ponder = Integer.parseInt(args[1]);
Chopstick
left = new Chopstick(),
right = new Chopstick(),
first = left;
int i = 0;
while(i < philosopher.length - 1) {
philosopher[i++] =
new Philosopher(left, right);
left = right;
right = new Chopstick();
}
if(args[2].equals("deadlock"))
philosopher[i] = new Philosopher(left, first);
else // Swapping values prevents deadlock:
philosopher[i] = new Philosopher(first, left);
// Optionally break out of program:
if(args.length >= 4) {
int delay = Integer.parseInt(args[3]);
if(delay != 0)
new Timeout(delay * 1000, "Timed out");
}
}
} ///:~
Both Chopstick and Philosopher use an auto-incremented static counter to give each element an identification number. Each Philosopher is given a reference to a left and right Chopstick object; these are the utensils that must be picked up before that Philosopher can eat.
The static field ponder indicates whether the philosophers will spend any time thinking. If the value is nonzero, then it will be used to randomly generate a sleep time inside think( ). This way, you can show that if your threads (philosophers) are spending more time on other tasks (thinking) then they have a much lower probability of requiring the shared resources (chopsticks) and thus you can convince yourself that the program is deadlock free, even though it isn’t.
Inside eat( ), a Philosopher acquires the left chopstick by synchronizing on it. If the chopstick is unavailable, then the philosopher blocks while waiting. When the left chopstick is acquired, the right one is acquired the same way. After eating, the right chopstick is released, then the left.
In run( ), each Philosopher just thinks and eats continuously.
The main( ) method requires at least three arguments and prints a usage message if these are not present. The third argument can be the string “deadlock,” in which case the deadlocking version of the program is used. Any other string will cause the non-deadlocking version to be used. The last (optional) argument is a timeout factor, which will abort the program after that number of seconds (whether it’s deadlocked or not). The timeout is necessary for the program to be run automatically as part of the book code testing process.
After the array of Philosopher is created and the ponder value is set, two Chopstick objects are created, and the first one is also stored in the first variable for use later. Every reference in the array except the last one is initialized by creating a new Philosopher object and handing it the left and right chopsticks. After each initialization, the left chopstick is moved to the right and the right is given a new Chopstick object to be used for the next Philosopher.
In the deadlocking version, the last Philosopher is given the left chopstick and the first chopstick that was stored earlier. That’s because the last Philosopher is sitting right next to the very first one, and they both share that first chopstick. With this arrangement, it’s possible at some point for all the philosophers to be trying to eat and waiting on the philosopher next to them to put down their chopstick, and the program will deadlock.
Try experimenting with different command-line values to see how the program behaves, and in particular to see all the ways that the program can appear to be executing without deadlock.
To repair the problem, you must understand that deadlock can occur if four conditions are simultaneously met:
- Mutual exclusion: At least one resource used by the
threads must not be shareable. In this case, a chopstick can be used by only one
philosopher at a time.
- At least one process must be holding a resource and waiting to acquire a
resource currently held by another process. That is, for deadlock to occur, a
philosopher must be holding one chopstick and waiting for the other one.
A resource cannot be preemptively taken away from a process. All processes
must only release resources as a normal event. Our philosophers are polite and
they don’t grab chopsticks from other philosophers.
- A circular wait must happen, whereby a process waits on a resource held by
another process, which in turn is waiting on a resource held by another process,
and so on, until one of the processes is waiting on a resource held by the first
process, thus gridlocking everything. In this example, the circular wait happens
because each philosopher tries to get the left chopstick first and then the
right. In the preceding example, the deadlock is broken by swapping the
initialization order in the constructor for the last philosopher, causing that
last philosopher to actually get the right chopstick first, then the left.
There is no Java language support to help prevent deadlock; it’s up to you to avoid it by careful design. These are not comforting words to the person who’s trying to debug a deadlocking program.
