093Automatically Detecting Thread Deadlocks

Author: Dr. Heinz M. KabutzDate: 2004-07-28Java Version: 5Category: Concurrency

Abstract: Deadlocks between synchronized monitors are impossible to resolve in Java. In this newsletter we look at a new MXBean that can detect deadlocks between threads and use it to warn us.

Welcome to the 93rd edition of The Java(tm) Specialists' Newsletter. I posted a link to our last newsletter to The Serverside. Didn't get too many comments (maybe not controversial enough ?!) but at least it made the front page for a few days :-)

Here is a really funny animated cartoon about what Sun Microsystems could do with their $2,000,000,000 [Sorry, not available anymore]. I was teaching last week about Swing, and coincidentally a friend sent me a hilarious animated cartoon about GridBagLayout. The nicest approach to GUI development that I have seen is in IntelliJ IDEA. They separate the layout from the rest of the GUI, and inject bytecode into your classes, instead of generating loads of source code. Once you get the hang of IDEA's GUI editor tool, you can smack together a GridBagLayout GUI in seconds, rather than minutes or days.

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

Automatically Detecting Thread Deadlocks

After our last newsletter, Kris Schneider mentioned that he had seen the Permanent Generation run out of space. He has kindly posted his improved version of my MemoryWarningSystem on The Serverside.

Scott Sobel brought up the issue of OOME occuring when too many threads were created. The problem with too many threads is that they need stack space. Both Scott and I have experienced where increasing the maximum heap space actually decreased the number of threads that we could create before getting an OOME. Unfortunately this maximum number of threads seems to be kind-of magical, and depends on the operating system and on the initial stack size per thread.

This brought me to this new warning system, that notifies me if we have too many threads. In order to not get too many notifications, I take the approach that you get one warning when we pass the thread count threshold. If you slip below the threshold, and go above it again, you will get another warning notification. This is the same approach taken by the memory bean. Better would probably be to have a high- and low-water mark.

In addition, it can also tell if there are deadlocked threads. My very first Java newsletter, sent in 2000 to some friends and colleagues gleaned from my contact list, demonstrated how you could find thread deadlocks by hand. This system finds them automatically for you. Seems we have progressed in the last 4 years! Looking for deadlocked threads is potentially slow, so this code could affect your performance. However, I would rather have a slower correct program than a lightning fast incorrect program.

There is absolutely nothing you can do with a deadlocked thread. You cannot stop it, you cannot interrupt it, you cannot tell it to stop trying to get a lock, and you also cannot tell it to let go of the locks that it owns. This is one of the criticism in Doug Lea's book [ISBN 0201310090] about the primitive monitor-based locking mechanisms. Once you try to get a lock, you will forever try and never give up. The concurrency handling mechanisms of Doug's book are now in the java.util.concurrent package of JDK 5.

This brought me to the question, what is the definition of a deadlock? In Webopedia.com, they describe it nicely:

A condition that occurs when two processes are each waiting for the other to complete before proceeding. The result is that both processes hang. Deadlocks occur most commonly in multitasking and client/server environments. Ideally, the programs that are deadlocked, or the operating system, should resolve the deadlock, but this doesn't always happen. A deadlock is also called a deadly embrace. (Source Webopedia.com)

Enough theory, here is the code to the ThreadWarningSystem, that detects when there are too many threads, and finds thread deadlocks:

import java.lang.management.*;
import java.util.*;

public class ThreadWarningSystem {
  private final Timer threadCheck = new Timer("Thread Monitor", true);
  private final ThreadMXBean mbean = ManagementFactory.getThreadMXBean();
  private final Collection<Listener> listeners = new ArrayList<Listener>();
  /**
   * The number of milliseconds between checking for deadlocks.
   * It may be expensive to check for deadlocks, and it is not
   * critical to know so quickly.
   */
  private static final int DEADLOCK_CHECK_PERIOD = 500;
  /**
   * The number of milliseconds between checking number of
   * threads.  Since threads can be created very quickly, we need
   * to check this frequently.
   */
  private static final int THREAD_NUMBER_CHECK_PERIOD = 20;
  private static final int MAX_STACK_DEPTH = 30;
  private boolean threadThresholdNotified = false;
  private Set deadlockedThreads = new HashSet();

  /**
   * Monitor only deadlocks.
   */
  public ThreadWarningSystem() {
    threadCheck.schedule(new TimerTask() {
      public void run() {
        long[] ids = mbean.findMonitorDeadlockedThreads();
        if (ids != null && ids.length > 0) {
          for (Long l : ids) {
            if (!deadlockedThreads.contains(l)) {
              deadlockedThreads.add(l);
              ThreadInfo ti = mbean.getThreadInfo(l, MAX_STACK_DEPTH);
              fireDeadlockDetected(ti);
            }
          }
        }
      }
    }, 10, DEADLOCK_CHECK_PERIOD);
  }

  /**
   * Monitor deadlocks and the number of threads.
   */
  public ThreadWarningSystem(final int threadThreshold) {
    this();
    threadCheck.schedule(new TimerTask() {
      public void run() {
        if (mbean.getThreadCount() > threadThreshold) {
          if (!threadThresholdNotified) {
            fireThresholdExceeded();
            threadThresholdNotified = true;
          }
        } else {
          threadThresholdNotified = false;
        }
      }
    }, 10, THREAD_NUMBER_CHECK_PERIOD);
  }

  private void fireDeadlockDetected(ThreadInfo thread) {
    // In general I avoid using synchronized.  The surrounding
    // code should usually be responsible for being threadsafe.
    // However, in this case, the timer could be notifying at
    // the same time as someone is adding a listener, and there
    // is nothing the calling code can do to prevent that from
    // occurring.  Another tip though is this: when I synchronize
    // I use a private field to synchronize on, instead of
    // "this".
    synchronized (listeners) {
      for (Listener l : listeners) {
        l.deadlockDetected(thread);
      }
    }
  }

  private void fireThresholdExceeded() {
    ThreadInfo[] allThreads = mbean.getThreadInfo(mbean.getAllThreadIds());
    synchronized (listeners) {
      for (Listener l : listeners) {
        l.thresholdExceeded(allThreads);
      }
    }
  }

  public boolean addListener(Listener l) {
    synchronized (listeners) {
      return listeners.add(l);
    }
  }

  public boolean removeListener(Listener l) {
    synchronized (listeners) {
      return listeners.remove(l);
    }
  }

  /**
   * This is called whenever a problem with threads is detected.
   * The two events are deadlockDetected() and thresholdExceeded().
   */
  public interface Listener {
    /**
     * @param deadlockedThread The deadlocked thread, with stack
     * trace of limited depth.
     */
    void deadlockDetected(ThreadInfo deadlockedThread);
    /**
     * @param allThreads All the threads in the JVM, without
     * stack traces.
     */
    void thresholdExceeded(ThreadInfo[] allThreads);
  }
}

The following test code creates many threads, then waits a few seconds before creating a whole new batch. We will see the warning system go off when we exceed the treshhold for the first time, then again after we have waited for the first batch of threads to die.

import java.lang.management.*;

public class TooManyThreadsTest {
  public static void main(String[] args) throws InterruptedException {
    ThreadWarningSystem tws = new ThreadWarningSystem(500);
    tws.addListener(new ThreadWarningSystem.Listener() {
      public void deadlockDetected(ThreadInfo thread) { }
      public void thresholdExceeded(ThreadInfo[] threads) {
        System.out.println("Threshold Exceeded");
        System.out.println("threads.length = " + threads.length);
      }
    });
    createBatchOfThreads();
    Thread.sleep(10000);
    System.out.println("We should've dipped below the threshold");
    createBatchOfThreads();
  }

  private static void createBatchOfThreads() {
    for (int i=0; i<1000; i++) {
      new Thread() { {start();}
        public void run() {
          try {
            Thread.sleep(5000);
          } catch (InterruptedException e) { }
        }
      };
    }
  }
}

On my machine I get the following output:

    Threshold Exceeded
    threads.length = 571
    We should've dipped below the threshold
    Threshold Exceeded
    threads.length = 507

Testing for deadlocks is even more interesting. I have the classic case where two threads want lock1 and lock2, but in opposite orders. Then I have a more difficult case, where we have three threads that lock each other out:

import java.lang.management.ThreadInfo;

public class DeadlockedThreadsTest {
  public static void main(String[] args) {
    ThreadWarningSystem tws = new ThreadWarningSystem();
    tws.addListener(new ThreadWarningSystem.Listener() {
      public void deadlockDetected(ThreadInfo inf) {
        System.out.println("Deadlocked Thread:");
        System.out.println("------------------");
        System.out.println(inf);
        for (StackTraceElement ste : inf.getStackTrace()) {
          System.out.println("\t" + ste);
        }
      }
      public void thresholdExceeded(ThreadInfo[] threads) { }
    });

    // deadlock with three locks
    Object lock1 = new String("lock1");
    Object lock2 = new String("lock2");
    Object lock3 = new String("lock3");

    new DeadlockingThread("t1", lock1, lock2);
    new DeadlockingThread("t2", lock2, lock3);
    new DeadlockingThread("t3", lock3, lock1);

    // deadlock with two locks
    Object lock4 = new String("lock4");
    Object lock5 = new String("lock5");

    new DeadlockingThread("t4", lock4, lock5);
    new DeadlockingThread("t5", lock5, lock4);
  }

  // There is absolutely nothing you can do when you have
  // deadlocked threads.  You cannot stop them, you cannot
  // interrupt them, you cannot tell them to stop trying to
  // get a lock, and you also cannot tell them to let go of
  // the locks that they own.
  private static class DeadlockingThread extends Thread {
    private final Object lock1;
    private final Object lock2;

    public DeadlockingThread(String name, Object lock1, Object lock2) {
      super(name);
      this.lock1 = lock1;
      this.lock2 = lock2;
      start();
    }
    public void run() {
      while (true) {
        f();
      }
    }
    private void f() {
      synchronized (lock1) {
        g();
      }
    }
    private void g() {
      synchronized (lock2) {
        // do some work...
        for (int i = 0; i < 1000 * 1000; i++) ;
      }
    }
  }
}

Not surprisingly, it takes longer for the deadlock to happen with the three threads than with the two threads. Here is the output from the program:

Deadlocked Thread:
------------------
Thread t5 (Id = 13) BLOCKED java.lang.String@de6ced
	DeadlockedThreadsTest$DeadlockingThread.g(DeadlockedThreadsTest.java:65)
	DeadlockedThreadsTest$DeadlockingThread.f(DeadlockedThreadsTest.java:61)
	DeadlockedThreadsTest$DeadlockingThread.run(DeadlockedThreadsTest.java:56)
Deadlocked Thread:
------------------
Thread t4 (Id = 12) RUNNABLE null
	DeadlockedThreadsTest$DeadlockingThread.g(DeadlockedThreadsTest.java:65)
	DeadlockedThreadsTest$DeadlockingThread.f(DeadlockedThreadsTest.java:61)
	DeadlockedThreadsTest$DeadlockingThread.run(DeadlockedThreadsTest.java:56)
Deadlocked Thread:
------------------
Thread t3 (Id = 11) BLOCKED java.lang.String@c17164
	DeadlockedThreadsTest$DeadlockingThread.g(DeadlockedThreadsTest.java:65)
	DeadlockedThreadsTest$DeadlockingThread.f(DeadlockedThreadsTest.java:61)
	DeadlockedThreadsTest$DeadlockingThread.run(DeadlockedThreadsTest.java:56)
Deadlocked Thread:
------------------
Thread t1 (Id = 9) BLOCKED java.lang.String@1fb8ee3
	DeadlockedThreadsTest$DeadlockingThread.g(DeadlockedThreadsTest.java:65)
	DeadlockedThreadsTest$DeadlockingThread.f(DeadlockedThreadsTest.java:61)
	DeadlockedThreadsTest$DeadlockingThread.run(DeadlockedThreadsTest.java:56)
Deadlocked Thread:
------------------
Thread t2 (Id = 10) RUNNABLE null
	DeadlockedThreadsTest$DeadlockingThread.g(DeadlockedThreadsTest.java:65)
	DeadlockedThreadsTest$DeadlockingThread.f(DeadlockedThreadsTest.java:61)
	DeadlockedThreadsTest$DeadlockingThread.run(DeadlockedThreadsTest.java:56)

You can get back to the original Thread from the ThreadInfo class if necessary by calling Thread.getAllStackTraces(). I would presume that this is an expensive operation, so use it with caution. The Thread's ID matches the ThreadInfo's ID, so we can always get back to the Thread from the ThreadInfo.

  private static Thread findMatchingThread(ThreadInfo inf) {
    Map<Thread, StackTraceElement[]> all = Thread.getAllStackTraces();
    for (Map.Entry<Thread, StackTraceElement[]> entry : all.entrySet()) {
      if (entry.getKey().getId() == inf.getThreadId()) {
        return entry.getKey();
      }
    }
    throw new NoSuchElementException();
  }

Apparently, JDK 5 beta 3 has been released. Exciting stuff and I can hardly wait for it to be properly released, so that I can start slowly bringing this into some products. In the past, I would say to customers: "If the application stops responding, please go to the console and press CTRL+Break and then email me the threads that are printed on the screen." Now we can get notified automatically. Ohhhh, what joy!

Even though the actual code of this newsletter was easy, it took a long time to write this newsletter, and I don't know why. Maybe I have been too distracted of late. In Germany, I went to visit my good friend Dr Jung, who wrote the masterpiece on dynamic proxies. We were a bit late for the train, so Christoph drove at breakneck speed to the train station, then grabbing my luggage ran full steam and hopped onto the train. A few minutes later, Christoph appeared and informed me that I had gotten onto the wrong train! Perhaps I am getting older, or maybe I am just becoming more nutty :-)

Kind regards

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive