Java - Deadlock

[Updated: May 23, 2017, Created: Apr 1, 2016]

A deadlock is a situation which occurs when a thread enters a indefinite waiting state because a lock requested is being held by another thread, which in turn is waiting for another lock held by the first thread.

For example in the following code a thread attempts to move an item from one list object 'list1' to another list object 'list2' and at the same time, another thread attempts to move an item from list2 to list1:

public class DeadLockDemo {

    public static void main (String[] args) throws InterruptedException {
        List<Integer> list1 = new ArrayList<>(Arrays.asList(2, 4, 6, 8, 10));
        List<Integer> list2 = new ArrayList<>(Arrays.asList(1, 3, 7, 9, 11));

        Thread thread1 = new Thread(() -> {
            moveListItem(list1, list2, 2);
        });
        Thread thread2 = new Thread(() -> {
            moveListItem(list2, list1, 9);
        });

        thread1.start();
        thread2.start();
    }

    private static void moveListItem (List<Integer> from, List<Integer> to, Integer item) {
        synchronized (from) {
            synchronized (to) {
                if(from.remove(item)){
                  to.add(item);
                }
            }
        }
    }
}

If we run above code multiple times there are good chances that we will have a deadlock soon. Deadlocks only occurs at some unfortunate timing of the two or more threads. When that happens, the program stops progressing at a particular point. It doesn't always necessarily hang or freeze. In above simple example though, we will experience a freeze when deadlock happens.



Let's add some logging with above example code to see the states of the two threads when deadlock occurs. Also to increase the probability of the deadlock to occur, we are adding a sleep call after the first lock has been acquired by each thread:

public static void main (String[] args) throws InterruptedException {
        List<Integer> list1 = new ArrayList<>(Arrays.asList(2, 4, 6, 8, 10));
        List<Integer> list2 = new ArrayList<>(Arrays.asList(1, 3, 7, 9, 11));

        Thread thread1 = new Thread(() -> {
            moveListItem(list1, list2, 2);
        });
        Thread thread2 = new Thread(() -> {
            moveListItem(list2, list1, 9);
        });

        thread1.start();
        thread2.start();
    }

    private static void moveListItem (List<Integer> from, List<Integer> to, Integer item) {
        log("attempting lock for list", from);
        synchronized (from) {
            log("lock acquired for list", from);
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            log("attempting lock for list ", to);
            synchronized (to) {
                log("lock acquired for list", to);
                if(from.remove(item)){
                  to.add(item);
                }
                log("moved item to list ", to);
            }
        }
    }

    private static void log (String msg, Object target) {
        System.out.println(Thread.currentThread().getName() +
                                           ": " + msg + " " +
                             System.identityHashCode(target));
    }
}

I'm able to have the deadlock at the first attempt. I'm using windows 10 home with a 4 core/8 logical processors machine.

Output:

Thread-0: attempting lock for list 2052470939
Thread-1: attempting lock for list 571142194
Thread-1: lock acquired for list 571142194
Thread-0: lock acquired for list 2052470939
Thread-0: attempting lock for list  571142194
Thread-1: attempting lock for list  2052470939

It's obvious from the last two lines that the two threads are waiting on the locks which are already held by each other in reversed order.

To investigate deadlocks, we can use JConsole.

For above example:

Here's a depiction of the deadlock scenario:

Preventing Deadlocks

Java doesn't provide any kind of construct or indication to warn about deadlocks during compile time. I guess no programming language can do that. It's the developer responsibility to avoid deadlock scenarios.

If a method already holds some locks and it's trying to acquired another lock then it's likely to have some deadlock scenario like we saw above. Another scenario can be directly or indirectly recursive callback to the same method which is holding a lock. There we have to be careful and do some investigations. Deadlocks are not immediately discoverable but we can do some quick tests to avoid them, like we did by introducing the sleep call.


To fix above deadlock issue either we have to use finer-grained locking or some sort of composite locking mechanism (just one lock composing of a pair of lists). The method has to be, of course, synchronized on the lists if it's accessed by multiple threads. In other words if we want to make the method thread-safe on the input lists, we need synchronization.

In the following fix we are going to use finer-grained locking, that is, using separate locking blocks:

public class DeadLockFixDemo {

    public static void main (String[] args) throws InterruptedException {
        List<Integer> list1 = new ArrayList<>(Arrays.asList(2, 4, 6, 8, 10));
        List<Integer> list2 = new ArrayList<>(Arrays.asList(1, 3, 7, 9, 11));

        Thread thread1 = new Thread(() -> {
            moveListItem(list1, list2, 2);
        });
        Thread thread2 = new Thread(() -> {
            moveListItem(list2, list1, 9);
        });

        thread1.start();
        thread2.start();
    }

    private static void moveListItem (List<Integer> from, List<Integer> to, Integer item) {

        boolean removedSuccessful = false;

        synchronized (from) {
              removedSuccessful = from.remove(item);
        }

        if (removedSuccessful) {
            synchronized (to) {
                to.add(item);
            }
        }
    }
}

Example Project

Dependencies and Technologies Used :

  • JDK 1.8
  • Maven 3.0.4

Thread Deadlock Example Select All Download
  • java-thread-deadlock
    • src
      • main
        • java
          • com
            • logicbig
              • example

See Also