About the Pi-Generating Algorithm

Deadlock

Synchronization saves the day when it comes to thread race conditions, and it is indispensable for enabling interthread notification but it does come at a price. There is some overhead and loss of speed associated with the acquiring and releasing of locks. And what about the fact that blocked threads make no forward progress? That is why, for instance, when Java 1.2 introduced the Collections framework, they chose to not make any of their Collection classes thread-safe even though the previous Java 1.0 collection-type classes were thread-safe. Why pay the price of synchronization when most applications won’t need it? A multi-threaded application can always synchronize as necessary to accommodate a thread-unsafe class just as SynchedBreaker safely managed the thread-unsafe LongSetter.

There is another price that synchronization brings with it, and that is the danger of deadlock which can occur in certain circumstances when threads can hold more than one lock at the same time. Deadlock is the situation where two or more threads remain permanently blocked by each other because they are waiting for locks that each other already holds. Without some sort of tie-breaking mechanism, the threads block forever, resources are tied up and the application loses whatever functionality the deadlocked threads had provided. In figure 16-15, while a thread holding A’s lock is blocked waiting to acquire B’s lock, another thread holding B’s lock is blocked waiting to acquire A’s lock.

Figure 16-15: Deadlocked Threads

The following program creates a real-life example of deadlock. Be forewarned that you will have to forcibly terminate this program. Consider the Caller class (example 16.24) and the Breaker program (example 16.25) that uses it. At first glance there may not appear to be any nested synchronization but there is. The answer() and call() methods are both synchronized on the Caller instance. When a thread invokes the call() method on a Caller instance the current thread must acquire that Caller’s lock. Since the call() method invokes the answer() method on another Caller instance, the thread must acquire the other Caller’s lock also. Therefore, in order for a thread to completely execute the call() method of a Caller instance, there is a moment when it must own the locks of both Callers. This vulnerability is cruelly exploited by the Breaker program. The program runs smoothly as long as one caller calls the other and the other answers right away. But it will freeze if at some point the caller calls and, before the would-be answerer has a chance to answer, it calls the caller. At this point, the program will have achieved deadlock.

Example 16.24: chap16.deadlock.Caller.java

 1     package chap16.deadlock; 2 3     public class Caller { 4       private String name; 5 6       public Caller(String s) { 7         name = s; 8       } 9       public synchronized void answer() { 10        System.out.println(name + " is available!"); 11      } 12      public synchronized void call(Caller other) { 13        System.out.println(this +" calling " + other); 14        other.answer(); 15      } 16      public String toString() { 17        return name; 18      } 19    }

Example 16.25: chap16.deadlock.Breaker.java

 1     package chap16.deadlock; 2 3     public class Breaker extends Thread { 4       private Caller caller; 5       private Caller answerer; 6     7       public Breaker(Caller caller, Caller answerer) { 8         this.caller = caller; 9         this.answerer = answerer; 10      } 11      public void run() { 12        while (true) { 13          caller.call(answerer); 14        } 15      } 16      public static void main(String[] arg) { 17        Caller a = new Caller("A"); 18        Caller b = new Caller("B"); 19     20        Breaker breakerA = new Breaker(a, b); 21        Breaker breakerB = new Breaker(b, a); 22     23        breakerA.start(); 24        breakerB.start(); 25      } 26    }

Use the following commands to compile and execute the example. From the directory containing the src folder:

    javac –d classes -sourcepath src src/chap16/deadlock/Breaker.java    java –cp classes chap16.deadlock.Breaker

Figure 16-16 shows the output to the console from running example 16.24. Figure 16-17 illustrates what happens when the two threads enter the deadlock state.

 A calling B B is available! A calling B B is available! [this continues for a while until]... B calling A A is available! B calling A A is available! [this continues for a while until]... A calling B B calling A [deadlock]

Figure 16-16: Results of Running Example 16.25(Output edited and annotated for brevity.)

Figure 16-17: Deadlock Due to Nested Synchronization

Unfortunately, the Java language provides no facility for detecting or freeing deadlocked threads beyond shutting the JVM down. The best way to fix deadlock is to avoid it, so use extreme caution when writing multi-threaded programs where threads can hold multiple locks. Do not synchronize more than necessary and understand the various ways the threads you write might interact with each other. Keep the use of synchronization to a minimum and be especially careful about situations where a thread can hold multiple locks.

Quick Review

Deadlock is the situation where two or more threads remain permanently blocked because they are waiting for locks each other already holds. Deadlock should be avoided and cannot be easily detected. The only sure method for avoiding deadlock is to understand the threads you write and their potential interactions, and to program in such a way that deadlock is never a possibility.