Wednesday, March 2, 2011

Deadlock despite consistent lock acquisition ordering

Consistent lock acquisition ordering (further as lock ordering) is one of the techniques of deadlock prevention. Deadlock is caused by circular dependency of threads trying to acquire locks. The consistent ordering prevents such dependency.

There is a common example of code which is vulnerable to deadlock:

public void someMethod() {
    synchronized (lock1) {
        synchronized (lock2) {
            // do something here
        }
    }
}

public void someOtherMethod() {
    synchronized (lock2) {
        synchronized (lock1) {
            // do something here
        }
    }
}

If 2 threads concurrently execute these methods they can end up in deadlock where thread1 holds lock1 while waiting for lock2 and thread2 holds lock2 while waiting for lock1. More detailed explanation of deadlock can be found for example here.

This article will use even simpler model code:

public void someMethod() {
    synchronized (lock1) {
        synchronized (lock2) {
            // do something here
        }
    }
}

This code can be executed concurrently by more threads without the risk of deadlock as threads acquire the locks in the same order. It is not 100% deadlock proof though because the lock ordering can be broken by wait(). This program:

public class BrokenOrderingBasic implements Runnable {
    private Object lock1 = new Object();
    private Object lock2 = new Object();

    public static void main(String[] args) throws InterruptedException {
        BrokenOrderingBasic runnable = new BrokenOrderingBasic();
        Thread thread1 = new Thread(runnable, "thread1");
        Thread thread2 = new Thread(runnable, "thread2");
        thread1.start();
        Thread.sleep(500);
        thread2.start();
    }

    @Override
    public void run() {
        try {
            String threadName = Thread.currentThread().getName();
            synchronized (lock1) {
                System.out.println(threadName + " has lock1");
                synchronized (lock2) {
                    System.out.println(threadName + " has lock2");
                    lock1.wait(1000);
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

prints:

thread1 has lock1
thread1 has lock2
thread2 has lock1

and hangs. Thread dump confirms a deadlock:

Found one Java-level deadlock:
=============================
"thread2":
  waiting to lock monitor 0x092807b0 (object 0x9f182210, a java.lang.Object),
  which is held by "thread1"
"thread1":
  waiting to lock monitor 0x09281fe8 (object 0x9f182208, a java.lang.Object),
  which is held by "thread2"

The reason is wait() will break the lock ordering. The program's lock ordering is lock1 -> lock2. thread1 acquires lock1 and lock2 at first. But then it releases lock1 by lock1.wait() while still holding lock2. When thread1 later timeouts from wait() it will try to acquire lock1 again and that way it practically establishes lock ordering lock2 -> lock1. As lock1 was acquired by thread2 in the meantime we have standard deadlock scenario here.

The above example is not quite realistic scenario as calling wait() on outer lock does not make much sense. If it appeared in real code, it would be very likely a bug.

Let us look on variation of the first scenario. This program:

public class BrokenOrderingReentredLock implements Runnable {
    private Object lock1 = new Object();
    private Object lock2 = new Object();

    public static void main(String[] args) throws InterruptedException {
        BrokenOrderingReentredLock runnable = new BrokenOrderingReentredLock();
        Thread thread1 = new Thread(runnable, "thread1");
        Thread thread2 = new Thread(runnable, "thread2");
        thread1.start();
        Thread.sleep(500);
        thread2.start();
    }

    @Override
    public void run() {
        try {
            String threadName = Thread.currentThread().getName();
            synchronized (lock1) {
                System.out.println(threadName + " has lock1");
                synchronized (lock2) {
                    System.out.println(threadName + " has lock2");
                    synchronized (lock1) {
                        System.out.println(threadName + " reenters lock1");
                        lock1.wait(1000);
                    }
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

prints:

thread1 has lock1
thread1 has lock2
thread1 reenters lock1
thread2 has lock1

and it hangs too:

Found one Java-level deadlock:
=============================
"thread2":
  waiting to lock monitor 0x02b7fdcc (object 0x229bf910, a java.lang.Object),
  which is held by "thread1"
"thread1":
  waiting to lock monitor 0x02b816fc (object 0x229bf908, a java.lang.Object),
  which is held by "thread2"

The reasoning is the same as for the previous scenario. The program's lock ordering is lock1 -> lock2. thread1 acquires lock1 and lock2 and reenters lock1. It releases lock1 by lock1.wait() while still holding lock2. When it later timeouts from wait() it will try to acquire lock1 again and that way it practically establishes lock ordering lock2 -> lock1. lock1 was acquired by thread2 in the meantime.

This scenario does not seem to be realistic either but the lock acquisitions can spread over multiple methods. In case of the complex code base + 3rd party libraries/frameworks is such situation more likely. On the other hand it also strongly suggests some redesign is needed.

The deadlock "property" of wait() is not limited to Java built-in synchronization and monitors. It is inherent with any wait-like feature (suspend the current thread and release the associated lock). The following program is equivalent to the previous one but using the java.util.concurrent.locks package:

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public class BrokenOrderingReentrantLock implements Runnable {
    private ReentrantLock lock1 = new ReentrantLock();
    private ReentrantLock lock2 = new ReentrantLock();
    private Condition condition = lock1.newCondition();

    public static void main(String[] args) throws InterruptedException {
        BrokenOrderingReentrantLock runnable = new BrokenOrderingReentrantLock();
        Thread thread1 = new Thread(runnable, "thread1");
        Thread thread2 = new Thread(runnable, "thread2");
        thread1.start();
        Thread.sleep(500);
        thread2.start();
    }

    @Override
    public void run() {
        try {
            String threadName = Thread.currentThread().getName();
            lock1.lock();
            try{
                System.out.println(threadName + " has lock1");
                lock2.lock();
                try{
                    System.out.println(threadName + " has lock2");
                    lock1.lock();
                    try{
                        System.out.println(threadName + " reenters lock1");
                        condition.await(1, TimeUnit.SECONDS);
                    } finally {
                        lock1.unlock();
                    }
                } finally {
                    lock2.unlock();
                }
            } finally {
                lock1.unlock();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}
When executed it behaves the same way. It prints:
thread1 has lock1
thread1 has lock2
thread1 reenters lock1
thread2 has lock1

and it hangs too:

Found one Java-level deadlock:
=============================
"thread2":
  waiting for ownable synchronizer 0x9f142860,
  (a java.util.concurrent.locks.ReentrantLock$NonfairSync),
  which is held by "thread1"
"thread1":
  waiting for ownable synchronizer 0x9f142838,
  (a java.util.concurrent.locks.ReentrantLock$NonfairSync),
  which is held by "thread2"

To summarize - the consistent lock acquisition ordering helps to prevent deadlock but one has to be aware that wait() can mess up with seemingly obvious correct ordering. But if such situation happens it is probably a bug or a superficial code design.

8 comments:

  1. really good one dear n thanx..

    ReplyDelete
  2. Correct understanding of deadlock is one of the must have ability for concurrent programming. your article shows a good way to avoid deadlock. I have also shared my experience as How to fix deadlock in Java , may be useful to your reader.

    ReplyDelete
  3. Nice post :). If you've got code the locks up like that you better have some really smart programers on your team.

    ReplyDelete
  4. Thanks a lot I have learned something new :).

    ReplyDelete
  5. Great post Kara Thanks

    ReplyDelete
  6. can you please tell the signifiacant use of Reentrant api ?

    as abaove example of reentrant is not clear... as we still in deadlock

    thanks
    amit

    ReplyDelete
  7. Never considered the possibility of this, thanks for the enlightening article

    ReplyDelete
  8. Very nice article indeed. I used to think when a thread enters in wait state it gives up all the locks it has. But you caught it right it only gives up lock on which it is waiting.
    I have a doubt here..Why do you think that above situations can not occur in real design? I can synchrnoise on two objects in order and might end up waiting on one of them genuinely.

    ReplyDelete