deadlocks and liveness in java · java.lang.everything

a deadlock is a set of threads each holding a lock while waiting for another lock held by someone else in the set: a cycle, and nobody can ever move. livelock is threads that keep reacting to each other and never get anywhere. starvation is a thread that could run but never gets its turn. the main fix for deadlock is boring and absolute: always take locks in the same order.

the picture

four cars at a four-way stop, each pulled halfway into the intersection, each waiting for the car on its left to go first. no car is broken. every driver is following a sensible rule. and none of them will ever move again.

that's the frustrating thing about deadlock: every thread is doing something reasonable on its own. the bug is in the combination.

a real one

two transfers in opposite directions, each locking its source account first:

Deadlock.java

public class Deadlock {
    static final Object accountA = new Object();
    static final Object accountB = new Object();
 
    static void transfer(Object from, Object to, String name) {
        synchronized (from) {
            sleep(100);                       // just long enough for the other thread to lock its first account
            synchronized (to) {
                System.out.println(name + " done");
            }
        }
    }
 
    static void sleep(long ms) {
        try { Thread.sleep(ms); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
    }
 
    public static void main(String[] args) {
        Thread.ofPlatform().name("alice").start(() -> transfer(accountA, accountB, "alice"));
        Thread.ofPlatform().name("bob").start(() -> transfer(accountB, accountA, "bob"));
    }
}

alice locks A and wants B. bob locks B and wants A. this one hangs every time, printing nothing (the sleep makes sure both get their first lock). no exception, no CPU use, nothing in the logs. the only way to see it is a thread dump. here's the real jstack output from jdk 25, trimmed to the interesting part:

jstack <pid>

"alice" #25 [43011] prio=5 os_prio=31 cpu=0.14ms elapsed=2.26s ... waiting for monitor entry
   java.lang.Thread.State: BLOCKED (on object monitor)
	at Deadlock.transfer(Deadlock.java:9)
	- waiting to lock <0x0000007018418418> (a java.lang.Object)
	- locked <0x0000007018418408> (a java.lang.Object)
 
Found one Java-level deadlock:
=============================
"alice":
  waiting to lock monitor 0x00000079254be680 (object 0x0000007018418418, a java.lang.Object),
  which is held by "bob"
 
"bob":
  waiting to lock monitor 0x00000079254be760 (object 0x0000007018418408, a java.lang.Object),
  which is held by "alice"
 
Found 1 deadlock.

the JVM found the cycle for you. read it as a graph: each thread holds one lock and waits for another, and following the arrows brings you back to the start.

the wait-for graph for alice and bob. purple: which thread holds each lock. red: which lock each thread waits for. any cycle in this graph is a deadlock.

you can ask the JVM for that cycle from inside the program too, which is how monitoring tools detect deadlocks in prod:

Main.java

import java.lang.management.ManagementFactory;
import java.util.Arrays;
 
void lockBoth(Object first, Object second) {
    synchronized (first) {
        try { Thread.sleep(100); } catch (InterruptedException e) { return; }
        synchronized (second) {
            IO.println("never printed");
        }
    }
}
 
void main() throws InterruptedException {
    Object a = new Object();
    Object b = new Object();
    Thread.ofPlatform().name("alice").daemon().start(() -> lockBoth(a, b));
    Thread.ofPlatform().name("bob").daemon().start(() -> lockBoth(b, a));
    Thread.sleep(500);
 
    var threads = ManagementFactory.getThreadMXBean();
    long[] stuck = threads.findDeadlockedThreads();
    String[] names = Arrays.stream(threads.getThreadInfo(stuck))
            .map(info -> info.getThreadName() + " waits for " + info.getLockOwnerName())
            .sorted()
            .toArray(String[]::new);
    IO.println(String.join("\n", names));
}

output, from jdk 25

alice waits for bob
bob waits for alice

this one needs a real JVM (JVM internals), so it doesn't run in the browser. copy it into java Main.java to try it.

(the threads are daemons so the program can exit while they're still stuck.) findDeadlockedThreads covers synchronized monitors and java.util.concurrent locks; jstack and jcmd <pid> Thread.print report both kinds too.

the dining philosophers

the classic, from Dijkstra. five philosophers around a table, five forks, one between each pair. to eat you need both forks next to you. so each philosopher is a thread, and each fork is a lock shared by two neighbours.

each one takes =

P0holds nothing0 meals

P1holds nothing0 meals

P2holds nothing0 meals

P3holds nothing0 meals

P4holds nothing0 meals

tick 0

five philosophers think, get hungry, grab two forks, eat, and put them down. press run.

press everyone hungry at once with "left, then right": every philosopher picks up their left fork, and the wait-for cycle closes. switch to "lower fork first" and try again: P4 reaches for fork 0 first, competes with P0 instead of grabbing fork 4, and the cycle can't form. "tryLock, back off" never deadlocks, but watch the meal counts for hungry philosophers who keep losing.

four conditions, break one

a deadlock needs all four of these at once (the Coffman conditions). take any one away and deadlock is impossible:

condition	meaning	how to break it
mutual exclusion	a lock has one owner at a time	use lock-free structures or immutable data, so no lock is needed
hold and wait	threads hold one lock while waiting for another	acquire everything at once, or never hold a lock while calling unknown code
no preemption	nobody can take a lock away from its owner	`tryLock` with a timeout: give up your locks and retry
circular wait	a cycle in the wait-for graph	a global lock order: everybody locks in the same order

lock ordering is the one to reach for first. for the transfer example, order by account id, so both directions lock the lower id first:

Main.java

class Account {
    final int id;
    int balance;
    Account(int id, int balance) { this.id = id; this.balance = balance; }
}
 
void transfer(Account from, Account to, int amount) {
    Account first = from.id < to.id ? from : to;    // always lock the lower id first
    Account second = first == from ? to : from;
    synchronized (first) {
        synchronized (second) {
            from.balance -= amount;
            to.balance += amount;
        }
    }
}
 
void main() throws InterruptedException {
    Account a = new Account(1, 1000);
    Account b = new Account(2, 1000);
    Thread t1 = Thread.ofPlatform().start(() -> { for (int i = 0; i < 100_000; i++) transfer(a, b, 1); });
    Thread t2 = Thread.ofPlatform().start(() -> { for (int i = 0; i < 100_000; i++) transfer(b, a, 1); });
    t1.join();
    t2.join();
    IO.println(a.balance + " " + b.balance);
}

output

1000 1000

200,000 transfers in opposite directions, no deadlock, every unit of money accounted for.

livelock

tryLock-and-retry prevents deadlock, but if two threads back off and retry in perfect lockstep, they can keep colliding forever. nobody is blocked, every thread is busy, and nothing finishes.

sharedA

freefree

two threads, both need locks A and B, and both use tryLock to avoid deadlock. politely.

step 1/8

both threads are always doing something, which is what makes livelock harder to spot than deadlock: the CPU is busy and the thread dump shows RUNNABLE. a random back-off breaks the symmetry.

starvation

starvation is a thread that's able to run but never gets what it needs, because others keep winning:

a non-fair lock lets running threads barge in, so an unlucky thread can lose the race over and over. a fair ReentrantLock fixes that at a throughput cost.
a steady stream of readers can starve a writer on a read-write lock (which is why ReentrantReadWriteLock queues new readers behind a waiting writer).
thread priorities are hints the OS mostly ignores, and relying on them for correctness invites starvation.

and one that's halfway to deadlock: thread-starvation deadlock in a pool. a task submits a subtask to the same bounded pool and waits for it. if every pool thread is busy waiting like that, the subtasks are queued with nobody left to run them:

Main.java

import java.util.concurrent.*;
 
void main() throws Exception {
    try (ExecutorService pool = Executors.newSingleThreadExecutor()) {
        Future<String> outer = pool.submit(() -> {
            Future<String> inner = pool.submit(() -> "inner result");  // queued behind outer
            return inner.get(500, TimeUnit.MILLISECONDS);             // waits for the only thread: itself
        });
        try {
            IO.println(outer.get());
        } catch (ExecutionException e) {
            IO.println("outer failed: " + e.getCause().getClass().getSimpleName());
        }
    }
}

output, from jdk 25

outer failed: TimeoutException

this one needs a real JVM (executors and futures), so it doesn't run in the browser. copy it into java Main.java to try it.

without the timeout, that hangs forever, and no thread dump calls it a deadlock, because no lock is involved, just a queue. don't make pool tasks wait on other tasks from the same pool; fork/join and structured concurrency are built for that shape.

quick check

two threads are deadlocked on two ReentrantLocks acquired with lock(). which tool won't help you break out at runtime?

keylines

deadlock: a cycle of threads each holding a lock the next one wants. it never resolves itself.
jstack / jcmd Thread.print find it for you: "Found one Java-level deadlock".
break any one of the four conditions. lock ordering breaks the cycle, and is the default fix.
tryLock with back-off can't deadlock, but needs randomness to avoid livelock.
starvation: runnable but always losing. unfair locks, reader floods, tasks waiting on their own pool.