2.6 Deadlock

< Day Day Up >

2.6.1 Coordinating Threads

One problem that occurs frequently in concurrent programming is the need to allow the threads to coordinate. For example, a program may require two or more threads to take turns running. An example of two threads running but not taking turns is shown in Exhibit 23 (Program2.9). In this program, the two threads share a TurnPrinter component that is created in the main and saved in an instance variable for each UnsafeTurns objects. Even though these two threads share the TurnPrinter component, and the TurnPrinter component is completely synchronized, no mechanism for coordinating the two threads to take turns has been implemented, so they can run in any order. It is important to note that the solution to concurrent programming problems is not always simply synchronization, as shown here. Synchronization makes the object thread safe (it can be used safely with threads) but does not solve the problem of making the threads take turns.

Exhibit 23: Program2.9: Two Cooperating Threads Not Taking Turns

 import java.util.*; public class UnsafeTurns implements Runnable {   private static Random rand = new Random();   private TurnPrinter tp;   private int myNum;   public UnsafeTurns(TurnPrinter tp, int myNum) {     this.tp = tp;     this.myNum = myNum;   }   public void run() {     for (int i = 0; i < 10; i++) {       tp.printTurn(myNum);       try {         Thread.sleep(rand.nextInt(100));       } catch (InterruptedException e) {       }     }   }   public static void main(String args[]) {     TurnPrinter tp = new TurnPrinter();     (new Thread(new UnsafeTurns(tp, 1))).start();     (new Thread(new UnsafeTurns(tp, 2))).start();   } } /**  *    Purpose: This TurnPrinter is intended to coordinate threads  *             that want to take turns printing. It does not  *             work.  */ class TurnPrinter {   public synchronized void printTurn(int turn) {     System.out.println("turn is" + turn);   } }

One possible solution to this problem is given in Exhibit 24 (Program2.10). In this program, the first thread enters the printTurn method, prints its turn, and then waits for a notify call to occur. This can only happen when the second thread calls the printTurn method to print its turn, executes notify, and calls wait. In this way, each thread prints, calls notify, and waits, resulting in the threads taking turns.

Exhibit 24: Program2.10: Two Cooperating Threads Taking Turns but Resulting in Deadlock

 import java.util.Random; public class SafeTurns implements Runnable {   private static Random rand = new Random();   private TurnPrinter tp;   private int myNum;   public SafeTurns(TurnPrinter tp, int myNum) {     this.tp = tp;     this.myNum = myNum;   }   public void run() {     for (int i = 0; i < 10; i++) {       tp.printTurn(myNum);       try {         Thread.sleep(rand.nextInt(100));       } catch (InterruptedException e) {       }     }   }   public static void main(String args[]) {     TurnPrinter tp = new TurnPrinter();     (new Thread(new SafeTurns(tp, 0))).start();     (new Thread(new SafeTurns(tp, 1))).start();   } } /**  *    Purpose: This TurnPrinter is intended to coordinate threads  *             and make them take turns. It works; however, the  *             first notify occurs before the first wait and is  *             lost. Because the number of notifies matches the  *             number of waits, one thread ends up stuck waiting  *             for a notify that never occurs.  */ class TurnPrinter {   public synchronized void printTurn(int turn) {     try {       System.out.println("turn is" + turn);       notify();       wait();     } catch (InterruptedException e) {     }   } }

Exhibit 24 (Program2.10) does correctly take turns, but the program never stops running. This problem occurs because, although the number of wait and notify calls are equal, the first notify call is lost because no thread is available to be moved from the wait set to the ready set. This means that one wait call will not be matched with a notify call, resulting in a thread that is permanently in the wait set and unable to finish. This situation is called deadlock.

2.6.2 Deadlock

Deadlock occurs when active threads are still in the system, but no thread can continue so the program cannot finish executing. In the case of Exhibit 24 (Program2.10), this is a result of the first notify being called before the second thread has called wait. As was said earlier, all a notify call does is move a thread from a wait list to a ready list. If no threads are in the wait set, then the notify is simply ignored. Because the first notify is ignored, an imbalance exists between the notify and wait calls in the program, with one wait not matched with a notify. This means that the second thread will always be left in a wait set that it cannot leave, and that thread can never complete. This example illustrates the need to be careful in implementing components, as even simple components can use locking schemes that can lead to deadlock.

One easy way to remove the deadlock in this program is shown in Exhibit 25 (Program2.11). The thread using the TurnPrinter component simply recognizes the presence of a bug in the TurnPrinter component (the extra wait) and compensates for it by putting a notify in the using programming after it is done using the component to print. While this solution is correct, it is a very bad way to program. A program that uses the TurnPrinter component should not have to compensate for programming errors in the component in order to work. In fact, any component that does not produce a valid result if used correctly is wrong. It is the component writer's responsibility to make sure that a component works as advertised and to try to take into consideration as many errors that users will make as possible.

Exhibit 25: Program2.11: Incorrect Usage of a Component to Compensate for an Error in Implementing the TurnPrinter Component

 import java.util.Random; public class SafeTurns1 implements Runnable {   static private Random rand = new Random();   private TurnPrinter tp;   private int myNum;   public SafeTurns1(TurnPrinter tp, int myNum) {     this.tp = tp;     this.myNum = myNum;   }   public void run() {     for (int i = 0; i < 10; i++) {       tp.printTurn(myNum);       try {         Thread.sleep(rand.nextInt(100));       } catch (InterruptedException e) {       }       synchronized(tp) {         tp.notify();       }     }   }   public static void main(String args[]) {     TurnPrinter tp = new TurnPrinter();     (new Thread(new SafeTurns1(tp, 0))).start();     (new Thread(new SafeTurns1(tp, 1))).start();   } } /**  *    Purpose: This TurnPrinter is intended to coordinate threads  *             and make them take turns. It works; however, the  *             first notify occurs before the first wait and is  *             lost. Because the number of notifies matches the  *             number of waits, one thread ends up stuck waiting  *             for a notify that never occurs. This is accounted  *             for in the program using the component.  */ class TurnPrinter {   public synchronized void printTurn(int turn) {     try {       notify();       System.out.println("turn is" + turn);       wait();     } catch (InterruptedException e) {     }   } }

Exhibit 26 (Program2.12) provides a more appropriate solution to this problem, as it is solved entirely within the TurnPrinter object. Problems frequently arise due to a poorly designed component causing incorrect programs (an example is provided in Chapter 7). This is another reason why programs should rely on sound principles to implement concurrent programs and not try to implement them by reasoning about the program logic.

Exhibit 26: Program2.12: Correct TurnPrinter Component

 import java.util.Random; public class SafeTurns2 implements Runnable {   static Random rand = new Random();   TurnPrinter tp;   int myNum;   public SafeTurns2(TurnPrinter tp, int myNum) {     this.tp = tp;     this.myNum = myNum;   }   public void run() {     for (int i = 0; i < 10; i++) {       tp.printTurn(myNum);       try {         Thread.sleep(rand.nextInt(100));       } catch (InterruptedException e) {       }     }   }   public static void main(String args[]) {     TurnPrinter tp = new TurnPrinter();     (new Thread(new SafeTurns2(tp, 0))).start();     (new Thread(new SafeTurns2(tp, 1))).start();   } } /**  *    Purpose: This TurnPrinter coordinates threads so they  *             take turns. It works by keeping track of whose  *             turn it is to run the method and allowing only  *             that thread to run.  */ class TurnPrinter {   int currentTurn = 0;   public synchronized void printTurn(int turn) {     try {       if (currentTurn ! = turn)         wait();       System.out.println("turn is" + turn);       currentTurn = (currentTurn + 1)% 2;       notify();     } catch (InterruptedException e) {     }   } }

Deadlock is not only a problem when designing components; it can also occur in any concurrent program. One simple cause of deadlock is the use of circularity in locking objects. For example, consider Exhibit 27 (Program2.13), which is an example of deadlock that occurs with a race condition. The two threads lock Objects A and B in the opposite order. If thread_1 is able to lock both A and B, it is able to complete, and then thread_2 will be able to lock both B and A, thus avoiding the deadlock. However, thread_1 could lock object A before thread_2 and thread_2 could lock object B before thread_1, which leads to a situation where neither thread can proceed, and the system is deadlocked.

Exhibit 27: Program2.13: Circular Deadlock Example

 public class MakeDeadlock{   public static void main(String args[]){     Object a = new Object(), b = new Object();     Thread thread_1 = new Thread(new LockAB(a,b));     thread_1.start();     Thread thread_2 = new Thread(new LockBA(a,b));     thread_2.start();   } } class LockAB implements Runnable {   private Object a, b;   public LockAB(Object a, Object b) {     this.a = a; this.b = b;   }   public void run() {     try {       Thread.sleep((int)(Math.random() * 100));       synchronized(a) {         Thread.sleep((int)(Math.random() * 100));         synchronized(b) {           System.out.println("LockAB worked");         }       }     } catch (InterruptedException e) {     }   } } class LockBA implements Runnable {   private Object a, b;   public LockBA(Object a, Object b) {     this.a = a; this.b = b;   }   public void run() {     try {       Thread.sleep((int)(Math.random() * 100));       synchronized(b) {         Thread.sleep((int)(Math.random() * 100));         synchronized(a) {           System.out.println("LockBA worked");         }       }     } catch (InterruptedException e) {     }   } }

The deadlock example in Exhibit 27 (Program2.13) is probably the most common type of deadlock. It occurs because of circularity in the order in which the resources are locked. If both threads had locked them in the same order, a deadlock would not have occurred. This type of deadlock is very common in many systems; for example, it occurs frequently in database management systems. Deadlock can arise in many other ways, some of which are covered in subsequent chapters.

< Day Day Up >