Deadlock, Livelock and Starvation

Deadlock is the concurrency failure everyone can name and few can diagnose from a thread dump. It is also the one with a clean theory: four conditions must all hold, and preventing any one of them prevents the deadlock.

The four conditions#

Breaking circular wait is almost always the right approach in application code: it costs nothing at runtime and requires only a convention.

The classic#

public void transfer(Account from, Account to, BigDecimal amount) {
    synchronized (from) {
        synchronized (to) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}
 
// Thread 1: transfer(accountA, accountB, ...)  — locks A, wants B
// Thread 2: transfer(accountB, accountA, ...)  — locks B, wants A
// Both wait forever.

This needs a specific interleaving, so it typically passes every test and appears in production under load — which is exactly what makes it a good interview question.

Fix 1: order the locks#

public void transfer(Account from, Account to, BigDecimal amount) {
    // Any consistent, total ordering works. An account id is stable and unique.
    Account first  = from.id().compareTo(to.id()) < 0 ? from : to;
    Account second = first == from ? to : from;
 
    synchronized (first) {
        synchronized (second) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}

Because every thread acquires locks in the same order, a cycle cannot form. System.identityHashCode is the fallback ordering key when objects have no natural id, with a tie-breaker lock for the rare collision.

The same principle scales beyond locks. Two transactions updating the same rows in different orders deadlock in the database, and the fix is identical: always update rows in a deterministic order, usually by primary key.

Fix 2: give up#

public boolean transfer(Account from, Account to, BigDecimal amount) throws InterruptedException {
    long deadline = System.nanoTime() + TimeUnit.SECONDS.toNanos(1);
 
    while (System.nanoTime() < deadline) {
        if (from.lock().tryLock(50, MILLISECONDS)) {
            try {
                if (to.lock().tryLock(50, MILLISECONDS)) {
                    try {
                        from.debit(amount);
                        to.credit(amount);
                        return true;
                    } finally { to.lock().unlock(); }
                }
            } finally { from.lock().unlock(); }
        }
        // Randomised backoff — without it, two threads can retry in lockstep forever.
        Thread.sleep(ThreadLocalRandom.current().nextInt(1, 20));
    }
    return false;
}

This breaks the no preemption condition: a thread that cannot get the second lock releases the first and retries. Note the randomised backoff — without it, this is exactly how a livelock forms.

Livelock#

// Two threads, both "politely" backing off when they detect a conflict,
// both retrying immediately, both detecting the conflict again.
while (!acquired) {
    if (lockA.tryLock()) {
        if (lockB.tryLock()) { acquired = true; }
        else { lockA.unlock(); }        // no backoff — immediate retry
    }
}

A livelock has the opposite signature from a deadlock: CPU usage is high, threads are RUNNABLE, and throughput is zero. It is easy to mistake for a legitimate CPU spike, and the tell is that the thread dumps taken seconds apart show the same threads cycling through the same few frames.

Randomised, exponential backoff is the standard cure. The same pattern appears at the distributed level in retry storms — see Cascading failure.

Starvation#

Starvation is progress for the system and none for one thread. Three usual causes:

Unfair locks. An intrinsic monitor has no queue, so a thread that just released the lock can barge back in ahead of long-waiting threads. Under sustained contention a particular thread may wait indefinitely. new ReentrantLock(true) guarantees FIFO ordering at a significant throughput cost.

Thread priorities. Thread.setPriority is a hint the OS is free to ignore, and on Linux it does almost nothing by default. Never rely on it for correctness.

Long critical sections. One thread holding a lock while doing I/O starves everything else that needs it. The rule is to never make a network or disk call while holding a lock — compute what you need, release, then call.

Reading a thread dump#

jcmd <pid> Thread.print > dump.txt
# or
jstack -l <pid> > dump.txt

Found one Java-level deadlock:
=============================
"order-worker-3":
  waiting to lock monitor 0x00007f8e1c0064f8 (object 0x000000076ab3f1a8, a Account),
  which is held by "order-worker-7"
"order-worker-7":
  waiting to lock monitor 0x00007f8e1c008a10 (object 0x000000076ab3f0c0, a Account),
  which is held by "order-worker-3"
 
Java stack information for the threads listed above:
"order-worker-3":
    at com.acme.TransferService.transfer(TransferService.java:42)
    - waiting to lock <0x000000076ab3f1a8> (a com.acme.Account)
    - locked <0x000000076ab3f0c0> (a com.acme.Account)

The JVM builds the wait-for graph and reports cycles automatically. Two lines to look for in each stack: - locked for what the thread holds, - waiting to lock for what it wants. The line numbers name the exact source locations to fix.

For a programmatic check, ThreadMXBean.findDeadlockedThreads() returns the same information and is worth exposing as a health indicator in a long-running service.

The pool deadlock#

ExecutorService pool = Executors.newFixedThreadPool(4);
 
Future<Report> outer = pool.submit(() -> {
    // Runs on a pool thread, and blocks waiting for work that must ALSO
    // run on a pool thread.
    Future<Section> inner = pool.submit(() -> buildSection());
    return new Report(inner.get());        // deadlocks when all 4 threads are here
});

With four threads all executing the outer task and all blocked in inner.get(), there is no thread left to run any inner task. The pool is stuck forever. The JVM reports no deadlock because there is no lock cycle — just four threads in WAITING on a FutureTask.

Three fixes: use separate pools for the two levels; restructure so a task never waits for another task on the same pool (thenCompose instead of get()); or use virtual threads, where blocking does not consume a limited resource.

This is the most common deadlock shape in modern Java services, precisely because it looks nothing like the textbook example.

What gets asked#

"Write me a deadlock" and "how would you find one in production" are the two standard questions. The answer that distinguishes you is the pool version — describing a deadlock with no locks in it shows you have debugged a real system rather than memorised the two-accounts example.