Deadlock Detection in Java

In this post, I want to talk about deadlock detection in Java and some pitfalls you might run into.

What is a deadlock?

Every programmer knows what a deadlock is but for completeness sake, I’ll give a brief description. Imagine you have two threads, thread1 and thread2. Thread1 acquires lock1 and is about to acquire lock2 while thread2 acquires lock2 and is about to acquire lock1. In this case, threads are deadlocked because they are each waiting for the other thread to release the other lock and your application just hangs. Deadlocks usually occur when the order of locks is not consistent throughout the application.

Deadlock sample with regular sync blocks

Here is a a quick sample that shows the deadlock situation explained above with good old sync blocks.

    private static void test1() {
        final Object lock1 = new Object();
        final Object lock2 = new Object();

        Thread thread1 = new Thread(new Runnable() {
            @Override public void run() {
                synchronized (lock1) {
                    System.out.println("Thread1 acquired lock1");
                    try {
                        TimeUnit.MILLISECONDS.sleep(50);
                    } catch (InterruptedException ignore) {}
                    synchronized (lock2) {
                        System.out.println("Thread1 acquired lock2");
                    }
                }
            }

        });
        thread1.start();

        Thread thread2 = new Thread(new Runnable() {
            @Override public void run() {
                synchronized (lock2) {
                    System.out.println("Thread2 acquired lock2");
                    try {
                        TimeUnit.MILLISECONDS.sleep(50);
                    } catch (InterruptedException ignore) {}
                    synchronized (lock1) {
                        System.out.println("Thread2 acquired lock1");
                    }
                }
            }
        });
        thread2.start();

        // Wait a little for threads to deadlock.
        try {
            TimeUnit.MILLISECONDS.sleep(100);
        } catch (InterruptedException ignore) {}
    }

The sample prints the following and then just hangs due to deadlocked threads:

Thread1 acquired lock1
Thread2 acquired lock2

Manual Deadlock Detection

While your app is hanging like in the example above, you can get a thread dump and see the deadlocked threads. For example, on Mac, you can either do Ctrl-\ or simply use jstack and process id to get the thread dump which makes it very obvious where the deadlock is. In this example, the thread dump looks like this:

Found one Java-level deadlock:
=============================
"Thread-2":
  waiting to lock monitor 102054308 (object 7f3113800, a java.lang.Object),
  which is held by "Thread-1"
"Thread-1":
  waiting to lock monitor 1020348b8 (object 7f3113810, a java.lang.Object),
  which is held by "Thread-2"

Java stack information for the threads listed above:
===================================================
"Thread-2":
	at DeadlockTest$2.run(DeadlockTest.java:42)
	- waiting to lock <7f3113800> (a java.lang.Object)
	- locked <7f3113810> (a java.lang.Object)
	at java.lang.Thread.run(Thread.java:680)
"Thread-1":
	at DeadlockTest$1.run(DeadlockTest.java:26)
	- waiting to lock <7f3113810> (a java.lang.Object)
	- locked <7f3113800> (a java.lang.Object)
	at java.lang.Thread.run(Thread.java:680)

Found 1 deadlock.

Programmatic Deadlock Detection

In more recent JDKs, there’s programmatic deadlock detection where you can get more information about the deadlocked threads and even stacktraces leading to deadlock as explained in this stackoverflow.com entry. In our example, let’s just detect the number of blocked threads in our application:

    private static void detectDeadlock() {
        ThreadMXBean threadBean = ManagementFactory.getThreadMXBean();
        long[] threadIds = threadBean.findMonitorDeadlockedThreads();
        int deadlockedThreads = threadIds != null? threadIds.length : 0;
        System.out.println("Number of deadlocked threads: " + deadlockedThreads);
    }

If you call detectDeadlock to the end of the test1 method, you get the following nice output with the number of deadlocked threads:

Thread1 acquired lock1
Thread2 acquired lock2
Number of deadlocked threads: 2

Deadlock sample with other locks

This is all nice but what about advanced locks like ReentrantLock, does programmatic detection work in that case? Let’s use this sample:

    private static void test2() {
        final ReentrantLock lock1 = new ReentrantLock();
        final ReentrantLock lock2 = new ReentrantLock();

        Thread thread1 = new Thread(new Runnable() {
            @Override public void run() {
                try {
                    lock1.lock();
                    System.out.println("Thread1 acquired lock1");
                    try {
                        TimeUnit.MILLISECONDS.sleep(50);
                    } catch (InterruptedException ignore) {}
                    lock2.lock();
                    System.out.println("Thread1 acquired lock2");
                }
                finally {
                    lock2.unlock();
                    lock1.unlock();
                }
            }
        });
        thread1.start();

        Thread thread2 = new Thread(new Runnable() {
            @Override public void run() {
                try {
                    lock2.lock();
                    System.out.println("Thread2 acquired lock2");
                    try {
                        TimeUnit.MILLISECONDS.sleep(50);
                    } catch (InterruptedException ignore) {}
                    lock1.lock();
                    System.out.println("Thread2 acquired lock1");
                }
                finally {
                    lock1.unlock();
                    lock2.unlock();
                }
            }
        });
        thread2.start();

        // Wait a little for threads to deadlock.
        try {
            TimeUnit.MILLISECONDS.sleep(100);
        } catch (InterruptedException ignore) {}

        detectDeadlock();
    }

And the output we get is:

Thread1 acquired lock1
Thread2 acquired lock2
Number of deadlocked threads: 0

Whoa! What happened? Deadlock detection does not work with ReentrantLocks?

findMonitorDeadlockedThreads vs. findDeadlockedThreads

Well, part of the blame is mine. There are two methods in ThreadMXBean to detect deadlocks: findMonitorDeadlockedThreads and findDeadlockedThreads. I carelessly used the former but there’s a subtle difference between the two.

As JavaDocs point out, findMonitorDeadlockThreads “Finds cycles of threads that are in deadlock waiting to acquire object monitors” whereas findDeadlockedThreads “Finds cycles of threads that are in deadlock waiting to acquire object monitors or ownable synchronizers“.

What’s an ownable synchornizer? Again according to JavaDocs: “An ownable synchronizer is a synchronizer that may be exclusively owned by a thread and uses AbstractOwnableSynchronizer (or its subclass) to implement its synchronization property. ReentrantLock and ReentrantReadWriteLock are two examples of ownable synchronizers provided by the platform.”

In plain English, if you want to detect ReentrankLock or ReentrantReadWriteLock, make sure you use findMonitorThreads method. If we change our deadlock method to the following:

    private static void detectDeadlock() {
        ThreadMXBean threadBean = ManagementFactory.getThreadMXBean();
        long[] threadIds = threadBean.findDeadlockedThreads();
        int deadlockedThreads = threadIds != null? threadIds.length : 0;
        System.out.println("Number of deadlocked threads: " + deadlockedThreads);
    }

We get the following expected output with test2:

Thread1 acquired lock1
Thread2 acquired lock2
Number of deadlocked threads: 2

So, you might ask at this point, why even bother with findMonitorDeadlockedThreads? Well, findDeadlockedThreads was added in JDK6. So, if your project is using JDK5 still, you need to use findMonitorDeadlockedThreads and hopefully this post will remind you the caveats of using findMonitorDeadlockedThreads.