Overview

	Chapter 7 - Concurrent Access to Objects and Variables
	Java Thread Programming
	Paul Hyde


Deadlocks


Using locks to control concurrent access to data is critical to avoid subtle race conditions within applications. However, trouble can arise when a thread needs to hold more than one lock at a time.

Imagine a situation where threadA currently has exclusive access to lock1 . While threadA is holding its lock on lock1 , threadB comes along and gets exclusive access to lock2 . Next, while threadA still holds lock1 , it tries to acquire lock2 . Because threadB currently holds lock2 , threadA blocks waiting for threadB to release it. So far, this is not a dangerous situation because when threadB releases lock2 , threadA will unblock, acquire lock2 , and complete its work.

A situation that will make trouble is ifwhile threadB is holding lock2 it needs to acquire lock1 . Now threadA has exclusive access to lock1 and is trying to get exclusive access to lock2 . At the same time, threadB has exclusive access to lock2 and is trying to get exclusive access to lock1 . Both threadA and threadB will block forever waiting for the other to release its lock (see Figure 7.1). This situation is called a deadlock (it can also be called a deadly embrace ).


Figure 7.1: A deadlock scenario.


The class Deadlock in Listing 7.29 demonstrates a situation where two threads end up in a deadlock with each other. Because of this, you will have to manually terminate the application after the main thread prints its last message.


Listing 7.29 Deadlock.javaDeadlock Between Two Threads


1: public class Deadlock extends Object {

2: private String objID;

4: public Deadlock(String id) {

5: objID = id;

6: }

8: public synchronized void checkOther (Deadlock other) {

9: print(entering checkOther());

10:

11: // simulate some lengthy process

12: try { Thread.sleep(2000); }

13: catch (InterruptedException x) { }

14:

15: print(in checkOther() - about to +

16: invoke ˜other.action());

17: other.action();

18:

19: print(leaving checkOther());

20: }

21:

22: public synchronized void action () {

23: print(entering action());

24:

25: // simulate some work here

26: try { Thread.sleep(500); }

27: catch (InterruptedException x) { }

28:

29: print(leaving action());

30: }

31:

32: public void print(String msg) {

33: threadPrint(objID= + objID + - + msg);

34: }

35:

36: public static void threadPrint(String msg) {

37: String threadName = Thread.currentThread().getName();

38: System.out.println(threadName + : + msg);

39: }

40:

41: public static void main(String[] args) {

42: final Deadlock obj1 = new Deadlock(obj1) ;

43: final Deadlock obj2 = new Deadlock(obj2) ;

44:

45: Runnable runA = new Runnable() {

46: public void run() {

47: obj1.checkOther(obj2) ;

48: }

49: };

50:

51: Thread threadA = new Thread(runA, threadA);

52: threadA.start();

53:

54: try { Thread.sleep(200); }

55: catch (InterruptedException x) { }

56:

57: Runnable runB = new Runnable() {

58: public void run() {

59: obj2.checkOther(obj1);

60: }

61: };

62:

63: Thread threadB = new Thread(runB, threadB);

64: threadB.start();

65:

66: try { Thread.sleep(5000); }

67: catch (InterruptedException x) { }

68:

69: threadPrint(finished sleeping);

70:

71: threadPrint(about to interrupt() threadA);

72: threadA.interrupt();

73:

74: try { Thread.sleep(1000); }

75: catch (InterruptedException x) { }

76:

77: threadPrint(about to interrupt() threadB);

78: threadB.interrupt();

79:

80: try { Thread.sleep(1000); }

81: catch (InterruptedException x) { }

82:

83: threadPrint(did that break the deadlock?);

84: }

85: }

In the main() method (lines 4184), two instances of Deadlock are created and two threads are startedeach one running one of the instances. The first instance has its objID set to obj1 ; the second is known as obj2 (lines 4243). threadA is started and invokes the checkOther() method of obj1 passing in a reference to obj2 (line 47). After a quick 200 millisecond sleep, threadB is started and invokes the checkOther() method of obj2 passing in a reference to obj1 (line 59).

The checkOther() method (lines 820) is synchronized and requires a thread to get exclusive access to the instances object-level lock before entering. After a thread gets inside, it prints a message (line 9) and then sleeps for two seconds to simulate a long-running task (line 12). After it wakes up, it prints a message and attempts to invoke the action() method of the other Deadlock instance (line 17). This will require that it get exclusive access to the object-level lock of the other instance because action() is synchronized (line 22).

Neither threadA nor threadB will ever get into the action() method of the other instance. While inside checkOther() , threadA is holding the object-level lock on obj1 . threadB is simultaneously inside the checkOther() method of obj2 and is holding its object-level lock. When threadA tries to invoke the action() method on obj2 , it will block waiting for threadB to release the lock. A fraction of a second later, threadB tries to invoke the action() method on obj1 and blocks waiting for threadA to release its lock. The two threads are deadlocked.


The main thread sleeps for five seconds while the deadlock is created (line 66). When it wakes up, it tries to break the deadlock by interrupting threadA (line 72). After one second, it tries to interrupt threadB (line 78). Unfortunately, this does not break the deadlock. When a thread is blocked waiting to acquire a lock, it does not respond to interrupts (refer to Chapter 6 ).


Listing 7.30 shows the output produced when Deadlock is run. Your output should match. Remember that you will have to manually terminate the application after about 15 seconds.


Listing 7.30 Output Produced from Deadlock (Your Output Should Match)


1: threadA: objID=obj1 - entering checkOther()

2: threadB: objID=obj2 - entering checkOther()

3: threadA: objID=obj1 - in checkOther() - about to invoke ˜other.action()

4: threadB: objID=obj2 - in checkOther() - about to invoke ˜other.action()

5: main: finished sleeping

6: main: about to interrupt() threadA

7: main: about to interrupt() threadB

8: main: did that break the deadlock?

First threadA enters the checkObject() method of obj1 (line 1). Shortly thereafter, threadB enters the checkObject() method of obj2 (line 2). threadA wakes up first and tries to invoke the action() method of obj2 , but blocks waiting for threadB to release the lock. Then threadB wakes up and tries to invoke the action() method of obj1 , and also blocks waiting for the lock that is currently held by threadA . The attempts to interrupt the blocked threads have no effect (lines 67).


This is a bit of a contrived situation, but deadlocks are a very real problem and can arise in other ways too. Nothing limits a deadlock to only two threads. Any number of threads can get into a deadlock situation with each other.


Deadlock Avoidance

Deadlocks can be extremely difficult to track down. Generally, most of an application will continue to run, but a couple of threads will be stuck in a deadlock. To make matters worse , deadlocks can hide in code for quite a while, waiting for a rare condition to occur. An application can run fine 99 out of 100 times and only deadlock when the thread scheduler happens to run the threads in a slightly different order. Deadlock avoidance is a difficult task.


Most code is not vulnerable to deadlocks, but for the code that is, try following these guidelines to help avoid deadlocks:


		Hold locks for only the minimal amount of time necessary. Consider using synchronized statement blocks instead of synchronizing the whole method.


		Try to write code that does not need to hold more than one lock at a time. If this is unavoidable, try to make sure that threads hold the second lock only for a brief period of time.


		Create and use one big lock instead of several small ones. Use this lock for mutual exclusion instead of the object-level locks of the individual objects.


		Check out the InterruptibleSyncBlock class in Chapter 17 . It uses another object to control concurrent access to a section of code. Additionally, instead of having a thread block on the synchronized statement, the thread is put into a wait-state that is interruptible. Ill tell you more about the wait-notify mechanism in Chapter 8 .


Toc

Chapter 7 - Concurrent Access to Objects and Variables