The labs on this site need JavaScript to run. The same content is written out below.

Learn › Java › Threads and concurrency

Deadlock

Two threads wait for each other, and both stop

Thread 1 transfers money from account A to B, and thread 2 transfers from B to A. To make a transfer, a thread must acquire the locks of both accounts. Depending on the order in which the locks are acquired and on the timing, the two threads can stop forever, each waiting for the lock that the other holds.

Checked against real execution · Checked by running it on JDK 21

Concepts in this lab

Deadlock

This is a state in which two or more threads (or transactions) can never make progress, because each is waiting for a resource that the other holds. The typical case is that A holds resource 1 and waits for 2 while B holds resource 2 and waits for 1. It can be prevented by always acquiring resources in the same order.

Critical section and mutual exclusion

A critical section is a section of code that causes problems if several threads run it at the same time. Mutual exclusion guarantees that only one thread at a time runs that section, and it is implemented with a lock. While one thread holds the lock, the other threads wait.

synchronized

This Java keyword marks a critical section. Only one thread at a time can run a method or block marked with it, and a thread that wants to run it must first acquire the monitor lock of the object involved. It is simple, but a thread that waits for the lock is stopped, so keep the scope only as large as needed.

Heap dump and thread dump

A heap dump is a file that saves information about every object in the heap at a certain moment. You analyze which objects take up a lot of memory and what refers to them, to find the cause of a memory leak. A thread dump records what every thread is running at that moment (its stack), and it is used to find the cause of an unresponsive application or a deadlock.

Try these

• Default settings — The threads acquire the locks in opposite orders and start at the same time. The result is a deadlock.
• Using the same lock order — Both threads acquire A first. One waits, and they finish one after the other.
• When the timing does not overlap — The orders are opposite, but both threads finish without a problem. That is why tests do not catch it.
• Limiting the waiting time — A thread that cannot acquire a lock releases the lock it holds and tries again.

Running with the default settings

1. Thread 1: It acquired the lock of the sending account, A.
2. Thread 2: It acquired the lock of the sending account, B.
3. Thread 1: It tries to acquire the lock of the receiving account, B. Thread 2 holds it, so thread 1 waits. It keeps holding the lock of A.
4. Thread 2: It tries to acquire the lock of the receiving account, A. Thread 1 holds it, so thread 2 waits. Thread 1 waits for thread 2, and thread 2 waits for thread 1. Neither releases its lock first, so the wait never ends. This is a deadlock.

Result of this run

• A deadlock occurred. Neither transfer finishes, and the two threads are stopped without even an exception. If you take a thread dump, you can see them as threads in the BLOCKED state, each waiting for the lock that the other holds.
• A deadlock occurs when four conditions all hold: a resource that only one thread can use at a time, holding one resource while waiting for another, no way to take a resource away from its holder, and waits that form a cycle. It is enough to break just one of them. Using the same lock order breaks the cycle. tryLock stops threads from waiting forever, so after the time limit a thread gives up and releases the lock it holds.

Code

void transfer(Account from, Account to, long amount) {
    synchronized (from) {                 // lock the sending account first
        synchronized (to) {
            from.withdraw(amount);
            to.deposit(amount);
        }
    }
}

// Thread 1: transfer(A, B, 100)
// Thread 2: transfer(B, A, 50)

Assumptions of this model

The model assumes the worst order, in which the two threads interleave exactly: each acquires its first lock and then requests its second lock. In reality, the timing more often lets the threads pass without a problem, and that is why a deadlock is hard to reproduce. synchronized cannot limit the waiting time, so when a limit is needed, use tryLock of ReentrantLock. In a database too, the same thing happens when two transactions lock rows in opposite orders, and the database detects it and forces one of them to roll back. This was checked by actually running it on JDK 21 on this PC. When the locks were acquired in opposite orders at the same time, the two threads stopped in the BLOCKED state and the JVM detected 2 deadlocked threads. When the locks were acquired in the same order, or the threads ran one after the other, both finished, and with tryLock both finished after 1 retry.

Previous lab: Race condition · Next lab: Thread pool