Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

.NET

Java Deadlock


Dr. Dobb's Journal September 1997: Java Deadlock

The woes of multithreaded design

Allan is chief technical officer for RogueWave Software. He can be contacted at [email protected].


Anyone who has written more than a few lines of C or C++ code has seen their programs stop abruptly with the dreaded messages "segmentation violation," "bus error," or "general-protection fault." The cause is almost always illegal manipulation of a pointer -- deleting memory twice, a bad cast, or following a runaway pointer. These errors are notoriously difficult to track down.

One of the primary motivations for using Java -- and one of its biggest advantages to developers -- is safety. Java provides a garbage collector to prevent accidentally freeing memory twice. Runaway pointers have been designed out of the system. You can still do a bad cast or dereference a NULL pointer in Java, but unlike a C++ program, a Java program throws an exception immediately and lets you know exactly where the error happened. The result: Java programmers sleep better than their C++ colleagues -- as long as they are writing single-threaded programs.

Threads

Multithreaded programs can do more than one task at a time. They let you take advantage of the multiple CPU machines that are now appearing in the market, by using each CPU to execute a different thread of control. Multithreaded applications feel snappier, even on a single-processor machine, because you can have a thread taking care of user input while another thread does something else. In general, multithreaded programs run much faster than single threaded programs on a box with multiple CPUs, and will be more responsive even on a single CPU box. The downside? Writing multithreaded code is hard. If you want multithreaded code that works correctly everytime, well...that's really hard.

Java makes writing multithreaded code easier by building support for multithreading into the language. The mechanics of writing multithreaded programs -- starting and stopping threads, controlling access to data by multiple threads, and communicating between threads -- are made easy and portable, much as C made pointer mechanics easy. The downside is that, as with C pointers, the mechanics are not the tricky part -- the trick is making applications that run reliably, repeatedly. With multithreading, one of the most common problems in this vein is deadlock -- a condition where all of the threads have stopped and are waiting for each other.

Launching Threads

How are threads launched and run in Java? The first step is to instantiate an object of a class that implements the Runnable interface. Runnable objects have a method, run, that contains the code to run in the thread. Once you have a Runnable object, you instantiate a Thread object, passing the Runnable object to the Thread's constructor. Calling start on the Thread object creates a new thread, which executes the Runnable's code.

The Resource class (see Listing One) is a simple abstraction of a corporate worker: It has a boss, and knows how to assign projects. ully commented source code is available electronically; see "Availability," page 3.) When run, a resource pauses for a moment, asks the boss for a project, then exits. The mainline code in Listing Two constructs three resources (a Boss and two developer resources, Wally and Dilbert), assigns threads to the two developers, and starts the threads. When run, Dilbert and Wally each get a project from the Boss, and the program exits.

If you run this program you might find that it doesn't really exit, depending on which version of the Java Developer's Kit you have. With Sun JDK 1.1 (available at this writing), things work fine. However, due to bugs in the JDK 1.0, unfortunately, the program hangs forever. If you want to experiment with the code using JDK 1.0 (or other environments that have inherited Sun's bugs) add print statements (System.out.println(".")) liberally so you can see what is happening when the program is running. Even if you are not using a buggy JDK, you may find it interesting to add some output to the code.

Monitors

One of the challenges of multithreaded programming is synchronization -- coordinating what the threads are doing so they don't interfere with each other. A monitor is a set of code in which only one thread at a time may be running. A thread running in a monitor's code is said to have locked the monitor. In Java, each object has an associated monitor. A method's code is made a part of the monitor by adding the synchronized keyword to the signature. Before a thread starts executing code in a synchronized method, it must lock the object's monitor. If the monitor is already locked by another thread, the thread waits until the monitor is unlocked.

Going back to the example, you can see that all of the methods in the Resource class are synchronized. This means that each Resource has only one thread running its functions at a time. Figure 1 shows what happens during a run of the program. Both Dilbert and Wally get locked as the threads begin execution. Each now calls the Boss's assignProject() method. Since assignProject() is synchronized, the thread must lock the monitor before it can execute the function. Only one of the two threads will succeed in locking the monitor. Let's say Dilbert's thread gets the monitor. Then Wally's thread stops and waits, while Dilbert's thread completes execution of the Boss's function. Once Dilbert's thread returns, it unlocks the monitor, and Wally's thread can execute the function.

Circular Deadlock

Deadlock is a nasty problem where a program simply stops executing because all threads are waiting for a resource that will never become available. In Java, the most common problem is that all threads are waiting to acquire a monitor that will never be unlocked. Java does nothing to protect you from deadlock, so you have to keep on your toes!

The first example of deadlock uses the same Resource class described earlier. This time, Dilbert and Wally have figured out that each of them has what it takes to be a boss (they have an assignProject() method), so they decide to become each other's boss; see Listing Three.

Figure 2 shows what can happen when this code executes. As before, Dilbert and Wally each get their own thread, and each locks the monitor associated with themselves as they begin executing. Dilbert now calls Wally's assignProject() method. Since Wally's thread has already locked Wally's monitor, Dilbert's thread waits for Wally's monitor to become available. At the same time, Wally calls Dilbert's assignProject() method and also starts waiting for Dilbert's monitor to become available.

In reality, if you simply type in the example code presented here, you may not encounter deadlock. That's because deadlock is, in general, not reproducible. Often, it depends on the timing of when threads are allocated time slices by the system. This makes deadlock a particularly nasty problem to track down and debug. I've checked the code examples here by adding sleep() statements at strategic places to ensure that we can see deadlock.

Signaling

Monitors as described thus far are great for keeping threads from interfering with each other, but fall a little short in helping threads cooperate to get something done. This is where signaling comes in. When a thread, executing in a monitor, needs to wait for another thread to do something, it calls wait(). This causes the thread to unlock the monitor and go to sleep. Since the monitor is unlocked, another thread can enter the monitor and supply the information the first thread was waiting for. The thread signals the waiting thread by calling notify(). Once the first thread is signaled it wakes up and begins waiting for the monitor to become available. When the second thread finishes its processing, it unlocks the monitor, allowing the first thread to reacquire the monitor and finish what it started.

In the Resource example, the Manager class (see Listing Four) is derived from Resource. Unlike a regular Resource, a Manager only assigns projects after receiving them. The manager contains a flag, called hasProject, to indicate whether a project is available for assigning. The assignProject() method loops while hasProject is false, calling wait() inside the loop. This means that as long as the manager has no project to assign, it will go to sleep and wait until it does have a project. Once it has a project, it sets the hasProject flag to false and returns. Since the code is executing in a monitor, it is guaranteed that the project won't be assigned by another thread between verifying that we have a project and setting the flag to false, even if several threads are awaiting projects. Projects are given to the manager for assignment by the receiveProject() method. This method sets hasProject to true, and awakens the next waiting thread by calling notify().

Having a class like Manager where one thread provides data and another uses that data is an example of a producer-consumer pattern. Of course, in most producer-consumer models the class retains data provided by producer threads rather than just a flag.

Listing Five shows the Manager in action. Catbert is an object of class Marketer (see Listing Six), which is a type of Resource where the run() method has been overridden to call receiveProject() on its Boss; so a Marketer, when executed or run), gives a new project to the Boss. Figure 3 shows what happens when the program is run. As in the previous examples, Dilbert's thread starts up and asks the Boss for a project. This time, the boss realizes he has no project to give Dilbert, and executes wait(), thus unlocking the monitor. Catbert's thread is now free to acquire the monitor and begin executing the Boss's receiveProject() method. Part way through this function, the thread signals Dilbert's thread to wake up and begin waiting for the monitor. Catbert's thread finishes executing and releases the monitor, allowing Dilbert's thread to take over and complete.

Nested Monitor Deadlock

When writing a class, it is good programming style to encapsulate member variables, allowing access to them only via method calls. Unfortunately, if the member variable uses signaling, and your class uses synchronized methods, this can lead to another problem -- nested monitor deadlock.

To illustrate, I'll add a new class to the example. WimpManager is a special kind of resource that acts like a manager, but actually refers all decisions to his boss. The WimpManager class (see Listing Seven) has methods that simply turn around and call his boss's functions. The Boss is effectively encapsulated by the WimpManager.

Listing Eight is almost the same as in the previous example, but this time Dilbert and Catbert's boss has assigned a WimpManager, wimp, as their new boss. Wimp, in turn, reports to Boss. This shields Boss from Dilbert and Catbert, whose requests must now all go through the WimpManager.

Figure 4 shows what happens at run time. First, Dilbert's thread asks the wimp for a thread by calling the assignProject() function. This locks wimp's monitor. The wimp goes on and calls assignProject() on the Boss, locking the Boss's monitor. The Boss, realizing that he has no project to assign, calls wait(), thereby unlocking his monitor, and begins waiting to be signaled by a call to his receiveProject() method. In the meantime, Catbert's thread has started up and attempted to call the WimpManager's receiveProject() method. Unfortunately, Dilbert's thread has acquired the lock on the WimpManager, so Catbert's thread waits. Forever. Deadlock!

Avoiding Deadlock

As with most things, the first step in fixing deadlock is to be aware of the problem, so you can diagnose it and treat it, or, better still, avoid it.

Nested monitor deadlock can often be avoided by using wait() sparingly, if at all, in foundation level classes. For example, the java.util.stack class could have been written to use wait if pull() was called with an empty stack. Instead, an exception is thrown.

Something that looks tempting at first is to modify Java so that calling wait unlocks all monitors a thread has acquired. This would be a mistake. It would imply that anytime you call a function that could in turn potentially call wait, you cannot guarantee that another thread won't change the state of the object -- even if you are using the synchronized keyword.

Summary

Without a great deal of care, both types of deadlock discussed here will arise regularly in hard-to-diagnose situations. At this point, the Java compiler and run time offer no help in detecting code that may deadlock. I fear that using monitors routinely in day to day programming will have the same results as the cavalier use of casts and pointers in C/C++ -- applications that regularly need to be restarted for reasons no one can quite diagnose. The challenge of the Java community (that's us!) is to educate programmers, and to provide higher level mechanisms to avoid this fate.


Listing One

public class Resource implements Runnable {  private Resource boss_;   // a property
  public void setBoss(Resource boss)  {boss_=boss;}
  public Resource getBoss() {return boss_;}


</p>
  public synchronized void assignProject() {pause();}
  public synchronized void receiveProject() {}
  public synchronized void run() {
    pause();
    getBoss().assignProject();
  }
  public static void pause() {
    try { Thread.sleep(700); }
    catch(InterruptedException e) { }
  }
}

Back to Article

Listing Two

public class Launch {  public static void main(String argv[]) {
    Resource boss    = new Resource();
    Resource dilbert = new Resource();
    Resource wally   = new Resource();
    dilbert.setBoss(boss);
    wally.setBoss(boss);


</p>
    // Build project threads
    Thread dilbertThread = new Thread(dilbert);
    Thread wallyThread = new Thread(wally);


</p>
    // Run the project threads
    dilbertThread.start();
    wallyThread.start();
  }
}

Back to Article

Listing Three

public class Dead1 {  public static void main(String argv[]) {
    // Create an organization that gets no work done
    Resource dilbert = new Resource();
    Resource wally   = new Resource();
    dilbert.setBoss(wally);
    wally.setBoss(dilbert);


</p>
    // Build project threads
    Thread dilbertThread = new Thread(dilbert);
    Thread wallyThread = new Thread(wally);


</p>
    // Run the project threads
    dilbertThread.start();
    wallyThread.start();
  }
}

Back to Article

Listing Four

public class Manager extends Resource {  private boolean hasProject_ = false;
  public synchronized void receiveProject() {
    hasProject_ = true;
    notify();
  }
  public synchronized void assignProject() {
    while (hasProject_ == false) {
      try { wait(); }
      catch(InterruptedException e) { }
    }
    hasProject_ = false;
  }
}

Back to Article

Listing Five

public class Signal {  public static void main(String argv[]) {
    // Create an organization to get work done
    Resource boss    = new Manager();
    Resource dilbert = new Resource();
    Resource catbert = new Marketer();
    dilbert.setBoss(boss);
    catbert.setBoss(boss);


</p>
    // Build the threads in which projects will be done
    Thread dilbertThread = new Thread(dilbert);
    Thread catbertThread = new Thread(catbert);


</p>
    // Run the project threads
    dilbertThread.start();
    Resource.pause(); // Dilbert starts first
    catbertThread.start();
  }
}

Back to Article

Listing Six

public class Marketer extends Resource {  // Submit a project to the boss.
  public synchronized void run() {
     getBoss().receiveProject();
  }
}

Back to Article

Listing Seven

public class WimpManager extends Resource {  public synchronized void receiveProject()
    { getBoss().receiveProject(); }
  public synchronized void assignProject()
    { getBoss().assignProject(); }
}

Back to Article

Listing Eight

public class Dead2 {  public static void main(String argv[]) {
    // Create an organization to get work done
    Resource wimp    = new WimpManager();
    Resource boss =    new Manager();
    Resource dilbert = new Resource();
    Resource catbert = new Marketer();
    wimp.setBoss(boss);
    dilbert.setBoss(wimp);


</p>
    // Build the threads in which projects will be done
    Thread dilbertThread = new Thread(dilbert);
    Thread catbertThread = new Thread(catbert);


</p>
    // Run the project threads
    dilbertThread.start();
    Resource.pause();  // Dilbert asks first
    catbertThread.start();
  }
}

Back to Article

DDJ


Copyright © 1997, Dr. Dobb's Journal


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.