Understanding Java Thread DeadLock

In a multi-threaded environment, it is ok that multiple threads simultaneously handles their tasks to improve the CPU utilization instead of keeping CPU as idle. In such an environment, it is ok if multiple threads try to access a shared resource, only one of them can acquire lock and the others should wait for that thread. This wait time can be infinite for various reasons that can cause a DeadLock in Java Threads. Let’s revisit a couple of terms that can be useful to understand DeadLock and support it with a real-life example.

Monitor Lock

This also known Intrinsic Lock or simply Monitor, and it is responsible for providing synchronization (we will cover this soon). Monitor is attached to every instance of an object and whenever one thread tries to access this object’s state, it needs to acquire lock first in a multi-threaded environment. Let’s take a look at synchronization, then we will see how monitor and synchronization work together in a diagram

Synchronization

This is the mechanism of controlling the access of multiple threads to any shared resource. In Java, if any method, block is synchronized, only one thread can access that thread at the same time. The main motivation behind synchronization is preventing data consistency problem which mostly caused by being able to be accessed by multiple threads.

Without Synchronization

Let say that you have a stock counter class which is responsible for maintaining the number of available products. In a concurrent environment, multiple threads can access that to decrease number whenever a product is sold. You can see the simple explanation in code level as follows.

package com.huseyin.threadlock;

import lombok.Data;
import lombok.extern.slf4j.Slf4j;

@Slf4j
@Data
class StockCounter {

    private int count = 180;

    void decrease(int amount) {
        int decreasedCount = count - amount;
        log.info("Current Count: {}, New Count: {}", count, decreasedCount);
        this.count = decreasedCount;
        try {
            Thread.sleep(500);
        }
        catch (InterruptedException e) {
            log.error("interrupted.", e);
        }
    }
}

@Slf4j
class Discounter2 extends Thread {
    StockCounter stockCounter;
    Discounter2(StockCounter t) {
        super("discounter-2");
        this.stockCounter = t;
    }

    public void run(){
        stockCounter.decrease(2);
    }
}

@Slf4j
class Discounter3 extends Thread {
    StockCounter stockCounter;
    Discounter3(StockCounter t) {
        super("discounter-3");
        this.stockCounter = t;
    }

    public void run(){
        stockCounter.decrease(3);
    }
}

@Slf4j
public class ThreadsWithoutSynchronization {

    public static void main(String[] args) throws InterruptedException {
        StockCounter stockCounter = new StockCounter();
        Discounter2 discounter21 = new Discounter2(stockCounter);
        Discounter2 discounter22 = new Discounter2(stockCounter);
        Discounter3 discounter31 = new Discounter3(stockCounter);
        Discounter3 discounter32 = new Discounter3(stockCounter);
        discounter21.start();
        discounter22.start();
        discounter31.start();
        discounter32.start();

        // wait for all the threads finishes their tasks.
        discounter21.join();
        discounter22.join();
        discounter31.join();
        discounter32.join();
        log.info("Final stock count is {}", stockCounter.getCount());
    }
}

You can see the full source code of this example here, and you can use following command to run above example.

./gradlew :deadlock:run \
-PmainClass=com.huseyin.deadlock.ThreadsWithoutSynchronization

Once it is executed, you can see something like following. Can you see something weird?

Threads without synchronization

Yes, exactly! Since there is no synchronization, all the threads access the field of StockCounter class at the same time (nearly) and they decrease total count by either 2 or 3. The final thread just decreases 180 by 3 since it is discounter-3 thread, then result becomes 177. However, it should be 170 since 4 thread should decrease with following amounts

180-(2+3+2+3)=170

With this kind of problem, you could sell non existent products to your customer since, stock counter shows the bigger value than actual one. Now that we see the potential problem without synchronization, let’s take a look how can we prevent concurrent access to a shared resources.

With Synchronization

There are different kind of synchronization, in this example we will use synchronized keyword for functions to make resource access more controlled. You can see the below magic to make stock counter logic a bit more consistent.

...
@Slf4j
@Data
class ConcurrentStockCounter implements StockCounter {

    private int count = 180;

    public synchronized void decrease(int amount) {
        int decreasedCount = count - amount;
        log.info("Current Count: {}, New Count: {}", count, decreasedCount);
        this.count = decreasedCount;
        try {
            Thread.sleep(500);
        }
        catch (InterruptedException e) {
            log.error("interrupted.", e);
        }
    }
}
...

And the result would be as follows.

As always, you can run this example with following command

./gradlew :deadlock:run \
-PmainClass=com.huseyin.deadlock.ThreadsWithSynchronization

Now that we se how can we protect shared resource, let’s check how can a deadlock occur in a multi-threading environment.

DeadLock

No, you hang up first...
https://www.flickr.com/photos/absurdperson/6816359292

A thread should acquire a monitor lock first to access a resource. This resource relates to object’s instance and every object instance just have one monitor to control resource access for multiple threads. If Thread A acquires lock on a shared resource, Thread B should wait for Thread A to release lock, then Thread B can acquire it.

Thread Wait Time

As you can see above, Thread B should wait between t2 and t3 due to Thread A, then it can acquire the lock. However, what if t3 – t2 = infinite? Following scenarios might better explain some use cases of deadlock.

  • Thread A acquires lock on Resources 1
  • Thread B acquires lock on Resource 2
  • Thread A requests lock on Resource 2
  • Thread B requests lock on Resource 1
Deadlock

So this is something like circular dependency, and let’s see how it can happen in a Java example.

package com.huseyin.deadlock;

import lombok.extern.slf4j.Slf4j;

@Slf4j
public class ThreadsDeadlock {

    public static void main(String[] args) throws InterruptedException {
        StockCounter stockCounter1 = new DefaultStockCounter();
        StockCounter stockCounter2 = new DefaultStockCounter();

        Thread threadA = new Thread(() -> {
            synchronized (stockCounter1) {
                log.info("Locked stockCounter1");
                try {
                    Thread.sleep(400);
                }
                catch (InterruptedException e) {
                    log.error("interrupted", e);
                }
                synchronized (stockCounter2) {
                    log.info("Locked stockCounter2");
                }
            }
        });

        Thread threadB = new Thread(() -> {
            synchronized (stockCounter2) {
                log.info("Locked stockCounter2");
                try {
                    Thread.sleep(400);
                }
                catch (InterruptedException e) {
                    log.error("interrupted", e);
                }
                synchronized (stockCounter1) {
                    log.info("Locked stockCounter1");
                }
            }
        });
        threadA.start();
        threadB.start();

    }
}

As you can also guess from the codebase, there are 2 instances of DefaultStockCounter and Thread A locks stockCounter1 instance, Thread B locks stockCounter2. In Thread A, it tries to lock stockCounter2, but it is already locked by Thread B. In same way Thread B tries to lock stockMonitor1, but it is not possible since it is already locked by Thread A. If you run example with following command.

./gradlew :deadlock:run \
-PmainClass=com.huseyin.deadlock.ThreadsDeadlock

And as an outcome, application will never finish its execution as follows since both of the threads are stuck.

It is running for 6m! Here I was lucky that I could understand the root cause, but the problem is a bit complicated than this. In order to get more insight about that, you can use thread dump as follows.

  • List java processes with jps command
  • Execute kill -3 <pid> to see thread dump analysis

In my case thread dump analysis is as follows.

Found one Java-level deadlock:
=============================
"Thread-0":
  waiting to lock monitor 0x00007fc6d000e100 (object 0x000000061f743930, a com.huseyin.deadlock.DefaultStockCounter),
  which is held by "Thread-1"
"Thread-1":
  waiting to lock monitor 0x00007fc6d000e300 (object 0x000000061f743920, a com.huseyin.deadlock.DefaultStockCounter),
  which is held by "Thread-0"

Java stack information for the threads listed above:
===================================================
"Thread-0":
        at com.huseyin.deadlock.ThreadsDeadlock.lambda$main$0(ThreadsDeadlock.java:22)
        - waiting to lock <0x000000061f743930> (a com.huseyin.deadlock.DefaultStockCounter)
        - locked <0x000000061f743920> (a com.huseyin.deadlock.DefaultStockCounter)
        at com.huseyin.deadlock.ThreadsDeadlock$$Lambda$19/0x0000000800106440.run(Unknown Source)
        at java.lang.Thread.run(java.base@11.0.10/Thread.java:834)
"Thread-1":
        at com.huseyin.deadlock.ThreadsDeadlock.lambda$main$1(ThreadsDeadlock.java:37)
        - waiting to lock <0x000000061f743920> (a com.huseyin.deadlock.DefaultStockCounter)
        - locked <0x000000061f743930> (a com.huseyin.deadlock.DefaultStockCounter)
        at com.huseyin.deadlock.ThreadsDeadlock$$Lambda$20/0x0000000800105840.run(Unknown Source)
        at java.lang.Thread.run(java.base@11.0.10/Thread.java:834)

Found 1 deadlock.

You can learn more about thread dump analysis here.

This problem might be more complicated than as follows.

  • Thread A acquired lock on resource 1, requests lock for resource 2
  • Thread B acquired lock on resource 2, requests lock for resource 3
  • Thread C acquired lock on resource 3, requests lock for resource 4
  • Thread D acquired lock on resource 4, and requests lock on resource 1
Complex Deadlock

So, thread dump analysis would be good idea to understand what is going on in the system.

Conclusion

To wrap up, in a multi-threaded environment, to prevent data consistency problem, we need to use synchronization techniques in java codebase. Even we protect data consistency, there can be cases which causes deadlock situation. In order to understand what is going on, you can use thread dump analysis. In this article, we only focused on how Synchronization is handled in java and provided a use case example for Thread DeadLock. We will be visiting “how to avoid deadlocks” in next article.

You can see the example code base here

2 thoughts on “Understanding Java Thread DeadLock

  1. Nice article,

    A point that could worth to be mentioned (maybe in a subsequent article) is that it is possible to have a single thread to deadlock itself with a ReentrantReadWriteLock by acquiring the readlock and then the writelock. This particular case is not obvious (it is barely mentioned in the javadoc) and in the thread dump, the read and write locks don’t have the same ids.

    Like

Leave a Reply to Benoit Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s