JAVA-240 · Lesson 9 of 12 · 25 min

Deadlock, livelock and starvation

▶ Video coming soon A video version of this lesson is on the way.

Monday, March 13, 2028. Hamza's prototype now has two kinds of booking. A repair booking takes a place on Tamsin's rack, which holds 12 bikes, and then records the deposit in the shop's ledger. A rental booking takes a bike from the rental fleet, which is also counted on the rack, and records its deposit too. He has put a lock on the rack and another on the ledger. On Friday's test run the program stopped. It did not crash, did not print an error, and did not use any processor time. It just sat there. Ingrid recognizes it at once. "That," she says, "is a deadlock, and tonight you will learn to see one, prove it and prevent it."

What deadlock is

A deadlock happens when two or more threads each hold a lock and wait for a lock that another of them holds, so that none of them can ever continue. The simplest case has two threads and two locks. The repairs thread takes the rack lock and then wants the ledger lock. At the same moment the rentals thread takes the ledger lock and then wants the rack lock. Each waits for the other forever. Nothing in Java breaks the tie: synchronized waits without a time limit, and the JVM does not step in.

Java Example · Main.java
public class Main {
    static final Object rackLock = new Object();
    static final Object ledgerLock = new Object();

    public static void main(String[] args) throws InterruptedException {
        Thread repairs = new Thread(() -> {
            synchronized (rackLock) {
                pause();
                synchronized (ledgerLock) { System.out.println("repairs: booked"); }
            }
        }, "repairs");
        Thread rentals = new Thread(() -> {
            synchronized (ledgerLock) {
                pause();
                synchronized (rackLock) { System.out.println("rentals: booked"); }
            }
        }, "rentals");
        repairs.start();
        rentals.start();
        repairs.join();
        rentals.join();
        System.out.println("done");
    }

    static void pause() {
        try { Thread.sleep(200); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
    }
}

What this code does

The repairs thread locks the rack and then the ledger, and the rentals thread locks the ledger and then the rack. The short pause inside each outer lock makes it almost certain that both threads have taken their first lock before either asks for its second. Each then waits for the lock the other holds, so neither booking is printed, done is never reached and the program hangs.

Two threads, repairs and rentals, and two locks, rack and ledger, drawn in a square. Solid arrows show repairs holding rack and rentals holding ledger. Dashed arrows show repairs waiting for ledger and rentals waiting for rack. The four arrows form a closed loop, labelled a cycle means deadlock.
A deadlock is a cycle of threads waiting for locks

Seeing a deadlock in a thread dump

A deadlocked program gives no error, so the first step is to look inside it. A thread dump lists every thread in a running JVM with its state and its stack, including which locks it holds and which it is waiting for. The JDK includes tools that take one: jcmd lists running Java processes, and jstack, or jcmd with the command Thread.print, prints the dump. HotSpot's thread dump also searches for deadlocks among monitor locks and explicit locks and reports any it finds at the end. Here is part of a real dump of the program above, taken while it was hung:

A real thread dump of the hung program
$ javac Main.java
$ java Main &
$ jcmd -l
3088 Main
$ jstack 3088
...
"repairs" #18 [3106] prio=5 os_prio=0 cpu=0.66ms elapsed=2.27s tid=0x00007ff36c1235b0 nid=3106 waiting for monitor entry  [0x00007ff2faafe000]
   java.lang.Thread.State: BLOCKED (on object monitor)
	at Main.lambda$main$0(Main.java:9)
	- waiting to lock <0x00000000a8517ad8> (a java.lang.Object)
	- locked <0x00000000a8517ac8> (a java.lang.Object)
	at Main$$Lambda/0x00007ff2fc000a08.run(Unknown Source)
	at java.lang.Thread.runWith(java.base@21.0.12.1/Thread.java:1596)
	at java.lang.Thread.run(java.base@21.0.12.1/Thread.java:1583)

"rentals" #19 [3107] prio=5 os_prio=0 cpu=0.46ms elapsed=2.27s tid=0x00007ff36c124710 nid=3107 waiting for monitor entry  [0x00007ff2fa9fe000]
   java.lang.Thread.State: BLOCKED (on object monitor)
	at Main.lambda$main$1(Main.java:15)
	- waiting to lock <0x00000000a8517ac8> (a java.lang.Object)
	- locked <0x00000000a8517ad8> (a java.lang.Object)
	at Main$$Lambda/0x00007ff2fc000c28.run(Unknown Source)
	at java.lang.Thread.runWith(java.base@21.0.12.1/Thread.java:1596)
	at java.lang.Thread.run(java.base@21.0.12.1/Thread.java:1583)
...
Found one Java-level deadlock:
=============================
"repairs":
  waiting to lock monitor 0x00007ff2d0068ce0 (object 0x00000000a8517ad8, a java.lang.Object),
  which is held by "rentals"

"rentals":
  waiting to lock monitor 0x00007ff2dc0018d0 (object 0x00000000a8517ac8, a java.lang.Object),
  which is held by "repairs"
...
Found 1 deadlock.

What this code does

The dump shows both threads in the BLOCKED state. repairs has locked one object and is waiting to lock a second, and rentals has locked the second and is waiting for the first. The JVM's deadlock check spells it out at the end: each thread is waiting for a monitor that the other holds, which is a cycle.

Ingrid shows Hamza how to read it. Every thread has a name in quotation marks, which is why naming threads matters. java.lang.Thread.State gives the state from lesson 2. The lines beginning with a dash say which monitor the thread has locked and which it is waiting to lock, identified by the object's address in angle brackets. Matching the addresses across threads shows the cycle even without the summary.

The four conditions

Deadlock can only happen when four conditions all hold at once. Computer scientists call them the Coffman conditions, after a 1971 paper. Breaking any one of them prevents deadlock:

  • Mutual exclusion: a resource can be held by only one thread at a time. Locks exist to give exactly this, so it usually stays.
  • Hold and wait: a thread holds one resource while waiting for another. Avoid it by taking all the locks a task needs at once, or none.
  • No preemption: a resource cannot be taken away from the thread holding it. tryLock with a time limit breaks this by letting the waiter give up.
  • Circular wait: there is a cycle of threads, each waiting for the next. Avoid it by always taking locks in the same global order.

Prevention by lock ordering

The most common and most reliable fix is a lock order: decide once, for the whole program, the order in which locks are taken, and make every thread follow it. If every thread takes the rack lock before the ledger lock, no cycle can form, because no thread can hold the ledger while waiting for the rack. Hamza writes the rule at the top of the booking class as a comment: rack before ledger, always.

Java Example · Main.java
import java.util.*;

public class Main {
    static final Object rackLock = new Object();
    static final Object ledgerLock = new Object();
    static final List<String> booked = Collections.synchronizedList(new ArrayList<>());

    static void book(String who) {
        synchronized (rackLock) {
            pause();
            synchronized (ledgerLock) {
                booked.add(who + ": booked");
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Thread repairs = new Thread(() -> book("repairs"), "repairs");
        Thread rentals = new Thread(() -> book("rentals"), "rentals");
        repairs.start();
        rentals.start();
        repairs.join();
        rentals.join();
        booked.stream().sorted().forEach(System.out::println);
        System.out.println("done");
    }

    static void pause() {
        try { Thread.sleep(200); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
    }
}
Output
rentals: booked
repairs: booked
done

What this code does

Both kinds of booking now go through one method that always takes the rack lock first and the ledger lock second. Whichever thread gets the rack first finishes both steps, and the other waits briefly and then does the same, so no cycle is possible. The bookings are collected in a list and printed sorted, because which thread finishes first varies.

When the locks belong to objects of the same kind, such as two cash drawers in a transfer, there is no natural first and second. A standard trick is to order them by a stable key, such as an account number, and always lock the smaller one first. The exercise at the end of this lesson asks you to do this.

Prevention by trying and backing off

When a global order is awkward, tryLock from lesson 4 breaks the no-preemption condition. A thread takes the first lock, then tries for the second with a time limit. If it cannot get it, it releases the first lock, waits a short, slightly random time, and starts again. No thread ever waits forever while holding a lock, so a permanent deadlock cannot form. The cost is that work may be retried, and the code is more complicated.

Java Example · Main.java
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;

public class Main {
    static final ReentrantLock rack = new ReentrantLock();
    static final ReentrantLock ledger = new ReentrantLock();

    static boolean bothOrNeither(ReentrantLock first, ReentrantLock second, Runnable work) throws InterruptedException {
        while (true) {
            if (first.tryLock(50, TimeUnit.MILLISECONDS)) {
                try {
                    if (second.tryLock(50, TimeUnit.MILLISECONDS)) {
                        try {
                            work.run();
                            return true;
                        } finally {
                            second.unlock();
                        }
                    }
                } finally {
                    first.unlock();
                }
            }
            Thread.sleep(ThreadLocalRandom.current().nextInt(5, 30));
        }
    }

    public static void main(String[] args) throws InterruptedException {
        List<String> done = Collections.synchronizedList(new ArrayList<>());
        Thread repairs = new Thread(() -> {
            try { bothOrNeither(rack, ledger, () -> done.add("repair booked")); }
            catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        });
        Thread rentals = new Thread(() -> {
            try { bothOrNeither(ledger, rack, () -> done.add("rental booked")); }
            catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        });
        repairs.start();
        rentals.start();
        repairs.join();
        rentals.join();
        done.stream().sorted().forEach(System.out::println);
    }
}
Output
rental booked
repair booked

What this code does

The two threads still ask for the locks in opposite orders, which deadlocked before. This time each takes its first lock, tries for the second for only 50 milliseconds, and if that fails releases everything and tries again after a short random pause. Sooner or later one thread gets both, so both bookings always complete; how many retries that takes varies, so the program prints only the outcome.

Detecting deadlock from inside a program

Long-running servers sometimes check themselves for deadlock and raise an alarm. The class ThreadMXBean, from java.lang.management, has a method findDeadlockedThreads that returns the IDs of threads caught in a cycle of locks, or null if there are none. The program below deadlocks on purpose, using daemon threads so that the JVM can still exit, and then finds the deadlock.

Java Example · Main.java
import java.lang.management.*;
import java.util.*;

public class Main {
    static final Object rackLock = new Object();
    static final Object ledgerLock = new Object();

    static Thread worker(String name, Object first, Object second) {
        Thread t = new Thread(() -> {
            synchronized (first) {
                try { Thread.sleep(100); } catch (InterruptedException e) { return; }
                synchronized (second) { System.out.println(name + " finished"); }
            }
        }, name);
        t.setDaemon(true);
        return t;
    }

    public static void main(String[] args) throws InterruptedException {
        worker("repairs", rackLock, ledgerLock).start();
        worker("rentals", ledgerLock, rackLock).start();

        ThreadMXBean mx = ManagementFactory.getThreadMXBean();
        long[] ids = null;
        while (ids == null) {
            Thread.sleep(50);
            ids = mx.findDeadlockedThreads();
        }

        List<String> names = new ArrayList<>();
        for (ThreadInfo info : mx.getThreadInfo(ids)) names.add(info.getThreadName() + " " + info.getThreadState());
        Collections.sort(names);
        System.out.println("deadlocked threads: " + ids.length);
        names.forEach(System.out::println);
    }
}
Output
deadlocked threads: 2
rentals BLOCKED
repairs BLOCKED

What this code does

Two daemon threads take the same two locks in opposite orders and deadlock. Main polls ThreadMXBean.findDeadlockedThreads every 50 milliseconds until it reports the cycle, then prints the two threads' names and states, sorted. Because the stuck threads are daemons, the JVM exits normally when main returns.

Detection is a safety net, not a fix: the threads involved cannot be rescued, only reported. In practice a server that finds a deadlock logs a thread dump and restarts, and the team fixes the lock order.

Livelock

In a livelock, threads are not blocked, they keep running, but they make no progress because each keeps reacting to the other. The everyday picture is two people meeting in a narrow corridor who both step left, then both step right, then both step left again. The back-off strategy above could livelock if both threads always waited exactly the same time before retrying: they would take their first locks together, fail together, back off together, and repeat. That is why the pause is random. The model below shows the difference without real threads.

Java Example · Main.java
import java.util.Random;

public class Main {
    static int roundsUntilProgress(Random a, Random b, int limit) {
        for (int round = 1; round <= limit; round++) {
            int waitA = a == null ? 10 : 5 + a.nextInt(25);
            int waitB = b == null ? 10 : 5 + b.nextInt(25);
            if (waitA != waitB) return round;
        }
        return -1;
    }

    public static void main(String[] args) {
        int fixed = roundsUntilProgress(null, null, 1000);
        int random = roundsUntilProgress(new Random(7), new Random(11), 1000);
        System.out.println("same fixed pause:  " + (fixed < 0 ? "no progress in 1000 rounds" : "progress in round " + fixed));
        System.out.println("random pauses:     progress in round " + random);
    }
}
Output
same fixed pause:  no progress in 1000 rounds
random pauses:     progress in round 1

What this code does

This is a model of two clerks who collide, back off and retry: they make progress in the first round in which their pauses differ. With the same fixed pause they collide forever, which is a livelock. With pauses drawn from seeded random number generators they break the tie at once; the seeds make the model print the same thing every time.

Starvation

Starvation happens when a thread is ready to run but never gets the resource it needs, because others keep getting it first. With an unfair lock, a busy thread that releases a lock and immediately asks for it again can win over and over, while another thread waits. A low-priority thread on a busy system, or a reader that is always overtaken by writers in a poorly designed read-write lock, can starve in the same way.

The usual cures are fairness and limits. A fair ReentrantLock, created with new ReentrantLock(true), grants the lock to the longest waiter, at some cost in throughput. Short critical sections help everyone. And designs that hand work through a first-in, first-out queue, as lesson 10 shows, are naturally fair: work is done in the order it arrived.

Three ways for threads to stop making progress
ProblemThreads areProgressTypical cure
DeadlockBlocked, waiting for each otherNone, everA global lock order, or tryLock with back-off
LivelockRunning, reacting to each otherNone, but busyRandom or staggered back-off
StarvationSome waiting, others runningSome threads make noneFair locks, short critical sections, queues

Habits that keep programs deadlock-free

Ingrid's list for OrderDesk: take as few locks as possible, and never hold one while calling code you do not control, such as a listener or a supplier client, because you cannot know what locks that code takes. Hold locks for as short a time as possible. Document the lock order and follow it everywhere. Prefer higher-level tools, a ConcurrentHashMap's compute, a BlockingQueue, an executor, which take and release their own locks correctly. And name every thread, so that the dump, if it ever comes, can be read in a minute.

Try it yourself

Transfers in a safe order

Two threads move money between the same two drawers in opposite directions: one makes 10,000 transfers of 3 cents from drawer 1 to drawer 2, the other 10,000 transfers of 1 cent back. Start them as the comment describes, and make transfer deadlock-free by always locking the drawer with the smaller id first.

The program should print drawer 1: 30000, drawer 2: 70000 and total: 100000. With the starter's transfer, the threads will usually deadlock and the program prints deadlocked.

public class Main {
    static class Drawer {
        final int id;
        int cents;
        Drawer(int id, int cents) { this.id = id; this.cents = cents; }
    }

    static void transfer(Drawer from, Drawer to, int cents) {
        synchronized (from) {
            synchronized (to) {
                from.cents -= cents;
                to.cents += cents;
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Drawer a = new Drawer(1, 50_000), b = new Drawer(2, 50_000);
        // start two daemon threads: one does 10,000 transfers of 3 cents from a to b,
        // the other 10,000 transfers of 1 cent from b to a; join each for up to 2 seconds
        System.out.println("drawer 1: " + a.cents);
        System.out.println("drawer 2: " + b.cents);
        System.out.println("total: " + (a.cents + b.cents));
    }
}

Try it yourself

Give up instead of waiting forever

Main holds the ledger lock. Write tryBoth, which takes the rack lock, then tries the ledger lock for 100 milliseconds, and returns false (releasing the rack lock) if it cannot get it. Run it on another thread while main holds the ledger, then again after main has unlocked it.

The program should print while ledger is held: false and after ledger is free: true.

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

public class Main {
    static final ReentrantLock rack = new ReentrantLock(), ledger = new ReentrantLock();

    static boolean tryBoth() throws InterruptedException {
        return true;
    }

    static boolean onAnotherThread() throws InterruptedException {
        boolean[] r = new boolean[1];
        Thread t = new Thread(() -> { try { r[0] = tryBoth(); } catch (InterruptedException e) { } });
        t.start(); t.join();
        return r[0];
    }

    public static void main(String[] args) throws InterruptedException {
        ledger.lock();
        System.out.println("while ledger is held: " + onAnotherThread());
        ledger.unlock();
        System.out.println("after ledger is free: " + onAnotherThread());
    }
}

Common mistakes

  • MistakeTaking the same two locks in different orders in different places.

    InsteadChoose one global lock order, write it down, and follow it everywhere.

  • MistakeCalling unknown code, such as a listener, while holding a lock.

    InsteadCopy what you need, release the lock, then call out.

  • MistakeRetrying with tryLock after the same fixed pause every time.

    InsteadUse a short random pause, or threads can livelock.

  • MistakeRestarting a deadlocked server without taking a thread dump.

    InsteadTake a dump first with jcmd or jstack; it shows exactly which locks form the cycle.

  • MistakeExpecting the JVM to break a deadlock.

    InsteadIt never does for synchronized; prevent the cycle in the design.

Summary and key terms

  • A deadlock is a cycle of threads, each holding a lock and waiting forever for a lock another holds; the program hangs without an error.
  • A thread dump, from jstack or jcmd with Thread.print, shows each thread's state, the locks it holds and waits for, and reports any deadlock found.
  • Deadlock needs four conditions at once: mutual exclusion, hold and wait, no preemption and circular wait.
  • A global lock order breaks circular wait, and ordering by a stable key handles locks of the same kind. tryLock with a time limit and a random back-off breaks no preemption.
  • ThreadMXBean.findDeadlockedThreads lets a program detect deadlock in itself.
  • In a livelock threads keep running but make no progress, usually from identical retries; randomness breaks the symmetry.
  • Starvation leaves a thread waiting while others keep winning; fair locks, short critical sections and first-in, first-out queues reduce it.
Deadlock
A state in which threads wait forever for locks held by each other.
Thread dump
A listing of every thread in a JVM with its state, stack and locks.
jstack
A JDK tool that prints a thread dump of a running Java process.
jcmd
A JDK tool that sends commands such as Thread.print to a running Java process.
Coffman conditions
The four conditions that must all hold for deadlock: mutual exclusion, hold and wait, no preemption and circular wait.
Lock order
A rule, followed by every thread, about the order in which locks are taken.
Back-off
Releasing locks and waiting a short time before trying again.
ThreadMXBean
A management interface that reports on threads, including deadlocked ones.
Livelock
Threads that keep running and reacting to each other without making progress.
Starvation
A thread that is ready to run but never gets the resource it needs.
Fair lock
A lock that is granted to the thread that has waited longest.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. Two threads each hold one lock and wait for the other's. What is this?

    Show answer

    A deadlock.

  2. Which of the four conditions does a global lock order break?

    Show answer

    Circular wait.

  3. Why is the back-off pause random?

    Show answer

    So that two threads do not keep retrying in step, which would be a livelock.

  4. What does findDeadlockedThreads return when there is no deadlock?

    Show answer

    null.

  5. Which tool would you run to see why a Java program has hung?

    Show answer

    jcmd to find its process ID, then jstack or jcmd with Thread.print.

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz