intermediate~2h

Deadlocks, Livelocks & Starvation

A deadlocked program doesn't crash - it just quietly stops, with no exception and no stack trace. this topic teaches you to diagnose and prevent deadlock from first principles, and to tell it apart from its two close cousins, livelock and starvation.

Learning objectives

State the four Coffman conditions and identify which one a given fix breaks
Detect a live deadlock programmatically using ThreadMXBean
Apply lock ordering, tryLock with timeout, and lock coarsening to prevent deadlock
Tell deadlock, livelock, and starvation apart by thread state and root cause
Use fair locks correctly, understanding the throughput cost

Most bugs announce themselves. A null pointer throws an exception. A bad array index throws an exception. Even an infinite loop pegs a CPU core at 100% and shows up on a dashboard. A deadlock does none of this. Two threads sit in the BLOCKED state forever, the JVM process keeps running, memory usage looks normal, and CPU usage might even sit near zero on the affected threads. Nothing in the logs screams for attention, because nothing failed - the threads are just waiting, patiently, for something that will never happen.

This is what makes deadlock uniquely painful to operate around. It reproduces only under a specific, often narrow window of timing, so it can pass through weeks of testing without ever showing up, then appear the moment real production traffic hits two code paths at once. By the time it surfaces, the symptom an on-call engineer sees is a service that stopped responding to some fraction of its requests, with a thread pool slowly filling up with threads that never return. There's no stack trace pointing at a line of broken code, because no line of code is broken in isolation - the bug lives in the relationship between two pieces of code that each look completely reasonable on their own.

The good news is that deadlock is not a vague or fuzzy phenomenon. It has a precise definition: four specific conditions that must all be true simultaneously. Understanding those four conditions turns "why did my server hang" from a mystery into a checklist, and turns "how do I stop it from happening again" into a decision about which one of the four is cheapest to break in your specific situation. That's the entire subject of this topic: naming the conditions, reproducing the failure on purpose so you can recognize it, proving it's happening in a live process, and then walking through the standard fixes along with the two subtler failure modes - livelock and starvation - that can sneak in when a fix is applied carelessly.

A deadlock is precisely characterized by four conditions, first formalized by Edward Coffman in 1971. All four must hold at the same time for a deadlock to occur - which means you don't need to eliminate deadlocks in the abstract, you only need to make it structurally impossible for any one of the four to hold, and the cycle can never form.

Mutual exclusion - at least one resource is held in a non-shareable way, so only one thread can use it at a time. Locks, database row locks, and file handles all work this way.
Hold and wait - a thread is holding at least one resource while it waits to acquire another resource that a different thread currently holds.
No preemption - resources can't be forcibly taken away from a thread. A thread has to voluntarily release what it holds; nothing can reach in and take it.
Circular wait - there's a cycle of threads, each waiting on a resource held by the next thread in the chain: thread A waits for something thread B holds, and thread B waits for something thread A holds.

The classic way to see this is the two-lock deadlock: two methods each need both of two shared resources, but they acquire them in opposite order. In the example below, methodA locks accountA then accountB; methodB locks accountB then accountA. A short sleep between the two acquisitions widens the timing window so the failure happens reliably instead of only occasionally - without it, the same bug could still occur, just rarely, which is exactly why deadlocks are so hard to reproduce on demand.

💻 Code example

package concurrency.deadlocks;

/**
 * Demonstrates a classic two-lock deadlock: transferOut locks accountA then
 * accountB; transferIn locks accountB then accountA. Under concurrent calls,
 * each thread can end up holding one lock while waiting on the other forever.
 */
public class OppositeOrderLockingDemo {
    // Two independent shared resources, each guarded by its own monitor lock.
    // Any plain Object works as a synchronized lock target in Java.
    private final Object accountA = new Object();
    private final Object accountB = new Object();

    // Deadlock-prone: locks accountA then accountB.
    public void transferOut() {
        synchronized (accountA) {
            // Hold accountA while sleeping, widening the window so the other
            // thread has time to grab accountB before this thread tries it too.
            try { Thread.sleep(50); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            // Attempt to acquire accountB WHILE STILL HOLDING accountA. If
            // transferIn currently owns accountB, this thread blocks right here.
            synchronized (accountB) {
                System.out.println("transferOut acquired both locks");
            }
        }
    }

    // Deadlock-prone: locks accountB then accountA - the opposite order.
    public void transferIn() {
        synchronized (accountB) {
            try { Thread.sleep(50); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            // If transferOut currently owns accountA, this thread blocks here,
            // completing the circular wait between the two threads.
            synchronized (accountA) {
                System.out.println("transferIn acquired both locks");
            }
        }
    }

    public static void main(String[] args) {
        OppositeOrderLockingDemo demo = new OppositeOrderLockingDemo();
        System.out.println("Starting demo - watch it hang.");
        new Thread(demo::transferOut).start();
        new Thread(demo::transferIn).start();
        // Neither "acquired both locks" line ever prints. Both threads sit in
        // BLOCKED state forever; the process must be killed externally.
    }
}

Every standard deadlock fix is really a choice about which of the four Coffman conditions is cheapest to break for your situation.

Lock ordering breaks circular wait. Make every code path acquire accountA before accountB, with no exceptions anywhere in the codebase, and a cycle becomes structurally impossible - there's no longer any pair of threads that could be waiting on each other in a loop. This is usually the first fix to reach for: it costs nothing at runtime and needs no retry logic, only discipline enforced across every call site that touches more than one of the same locks. A common technique when the "natural" order isn't obvious - two bank accounts, say - is to order by a stable identity, such as System.identityHashCode() or a database primary key.

tryLock() with a timeout breaks hold-and-wait. Instead of synchronized, use ReentrantLock.tryLock(timeout, unit): a thread that can't acquire the second lock within the timeout gives back what it holds and retries, rather than sitting and waiting indefinitely for the other lock. It never spends unbounded time holding one resource while blocked on another.

Lock coarsening breaks circular wait a different way, by removing the choice entirely: replace the two fine-grained locks with a single lock guarding both resources together. There's only ever one lock to acquire, so no ordering conflict is even possible. The cost is reduced concurrency, since operations that used to run independently now serialize behind one lock.

There's a trap hiding inside the second fix. tryLock() avoids deadlock, but naively retried, it introduces a new problem: grab lock 1, try lock 2, fail, release lock 1, retry immediately. If two threads do this in lockstep, they can keep "politely" backing off for each other forever - neither is blocked, both look busy, and neither ever finishes. That failure mode is livelock, and the fix is to randomize the retry delay so the two threads can't stay synchronized.

💻 Code example

package concurrency.deadlocks;

import java.util.Random;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * tryLock() plus randomized backoff. Never holds a partial set of locks
 * while retrying, and jitters the retry delay so two threads contending for
 * the same pair of locks can't stay locked in step with each other forever.
 */
public class TryLockWithRandomBackoff {
    private final Lock lockA = new ReentrantLock();
    private final Lock lockB = new ReentrantLock();
    private final Random rnd = new Random();

    public void doWork() throws InterruptedException {
        while (true) {
            // Non-blocking attempt: returns immediately instead of parking
            // the thread, so we never sit forever waiting for one lock while
            // holding another.
            if (lockA.tryLock()) {
                try {
                    if (lockB.tryLock()) {
                        try {
                            System.out.println(Thread.currentThread().getName() + " got both locks");
                            return; // success
                        } finally {
                            lockB.unlock();
                        }
                    }
                    // lockB was not acquired - lockA is released by the
                    // outer finally below. We never hold lockA while retrying.
                } finally {
                    lockA.unlock();
                }
            }
            // Randomized backoff breaks any lockstep retry pattern that would
            // otherwise cause perpetual mutual failure between two threads.
            Thread.sleep(rnd.nextInt(20));
        }
    }

    public static void main(String[] args) throws InterruptedException {
        TryLockWithRandomBackoff demo = new TryLockWithRandomBackoff();
        Thread t1 = new Thread(() -> {
            try { demo.doWork(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        }, "worker-1");
        Thread t2 = new Thread(() -> {
            try { demo.doWork(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        }, "worker-2");
        t1.start();
        t2.start();
        t1.join();
        t2.join();
    }
}

▲ Common mistake

Replacing the random backoff with a fixed delay. If every thread sleeps exactly the same number of milliseconds before retrying, the anti-livelock guarantee disappears - under real contention, two threads using the same fixed delay can stay permanently synchronized in their retries, right back to the lockstep failure the randomization was meant to prevent. The randomization is not a minor detail; it's the entire fix.

▲ Common mistake

Releasing a lock outside of a finally block. If an exception is thrown between acquiring a lock and releasing it, and the release isn't in a finally, the lock leaks - it's never released, and every other thread waiting on it blocks forever. This looks like a deadlock in a thread dump but has a different root cause: a bug, not a design flaw in the locking order.

▲ Common mistake

Applying lock ordering only to "the obvious" call sites. Lock ordering only works if it's applied with zero exceptions across the entire codebase that touches those two locks. A single code path that acquires them in the wrong order - added six months later by someone unaware of the convention - reopens the cycle. This is why lock ordering benefits from being enforced structurally (a wrapper type, a code review checklist, a static analysis rule) rather than relying on memory.

▲ Edge case

Reentrant locks don't deadlock against themselves. A thread that already holds a ReentrantLock (or is inside a synchronized block on an object) can re-acquire the same lock without blocking - the JVM tracks a hold count per owning thread. This matters when refactoring: recursive methods or methods that call other synchronized methods on this are safe by default, but the equivalent pattern across two different locks is exactly the two-lock deadlock scenario above.

▲ Edge case

Deadlock detection tools only see locks they know about. ThreadMXBean.findDeadlockedThreads() covers both synchronized monitors and java.util.concurrent.locks ownable synchronizers like ReentrantLock. It does not see a deadlock caused by, say, two threads waiting on each other through a custom blocking queue or an external resource like a database row lock - those need their own detection mechanism (the database's own deadlock detector, for instance).

Deadlock, livelock, and starvation all describe a thread failing to make progress, but they look completely different from the outside, and they need different fixes.

In a deadlock, threads are in the BLOCKED or WAITING state, consuming roughly 0% CPU, and the failure is permanent - nothing will ever unstick them without external intervention. The classic mental picture is two people in a hallway who each grab an object the other needs and refuse to let go.

In a livelock, threads are RUNNABLE and burning real CPU, but still make zero useful progress, because they keep changing state in direct response to each other without ever advancing. The classic picture is two people in a hallway who each step aside to let the other pass - but they step to the same side, mirror each other, and never get through. Ethernet's old CSMA/CD collision-avoidance protocol uses exponential random backoff for exactly this reason: two devices that collided and both retry after the same fixed delay will just collide again.

In starvation, a thread is technically able to run - there's no cycle and no mirroring - it just keeps losing out to other threads indefinitely, because the scheduler or the lock implementation keeps favoring someone else. The most common cause in Java is an unfair lock: synchronized blocks and the default ReentrantLock have no fairness guarantee at all, so a thread that's been waiting the longest can still keep losing the race to newly-arriving threads that happen to get scheduled first (a phenomenon called "barging"). A second common cause is one thread holding a lock for an unusually long time - doing I/O while holding it, say - which pushes everyone else's wait time up indefinitely.

The fix for starvation is a fair lock: new ReentrantLock(true) grants the lock strictly in the order threads requested it, backed by an internal FIFO wait queue (AQS - AbstractQueuedSynchronizer). This is a genuine throughput trade-off, not a free upgrade: fairness costs more context switches and forfeits the "barging" optimization where a thread that just released the lock lets a freshly-arriving thread grab it immediately without a full queue handoff. That's exactly why unfair is the default - it's measurably faster in the common case. Reach for a fair lock specifically when you've observed or strongly suspect real starvation risk and bounded per-thread wait time matters more than raw throughput.

💻 Code example

package concurrency.deadlocks;

import java.util.concurrent.locks.ReentrantLock;

/**
 * A fair ReentrantLock grants access strictly in the order threads requested
 * it, backed by an AQS FIFO wait queue - the standard fix for lock-related
 * starvation.
 */
public class FairLockDemo {
    // The `true` argument enables fair mode: waiting threads are served
    // strictly in arrival order, instead of the default unfair mode where a
    // newly-arriving thread may "barge" ahead of threads that have waited longer.
    private final ReentrantLock fairLock = new ReentrantLock(true);

    public void runJob() {
        fairLock.lock();
        try {
            System.out.println(Thread.currentThread().getName() + " acquired the fair lock");
        } finally {
            fairLock.unlock(); // Always release in finally, even on exception.
        }
    }

    public static void main(String[] args) {
        FairLockDemo demo = new FairLockDemo();
        // With fairness enabled, whichever thread joins the wait queue first
        // is guaranteed to be served first under sustained contention.
        new Thread(demo::runJob, "worker-1").start();
        new Thread(demo::runJob, "worker-2").start();
    }
}

Deadlock detection and prevention show up constantly in production systems, often invisibly, because the engineers who built the platform already did the work.

Relational databases run their own deadlock detector under the hood. When two transactions hold row locks that would deadlock, engines like MySQL's InnoDB detect the cycle automatically and abort one of the transactions (choosing the "victim" by cost heuristics), returning a deadlock error to the application - which is expected to catch it and retry. This is the database-level equivalent of ThreadMXBean.findDeadlockedThreads(): a background process constantly walking a lock-ownership graph looking for cycles.

Watchdog threads are the standard production pattern for the in-process version: spin up a low-priority daemon thread that calls findDeadlockedThreads() on a timer - every 30 seconds is typical - and pages an on-call engineer or logs a full thread dump the moment it returns non-null. This turns a silent hang into an actionable, observable event instead of something discovered only when a customer complains.

Distributed locks, such as those built on Redis or ZooKeeper, apply the same lock-ordering discipline across service boundaries: when a workflow needs to lock multiple distributed resources, services agree on a canonical ordering (often by resource ID) to make circular waits between services structurally impossible, exactly as with in-process locks on two objects.

Connection pools are a form of resource limiting closely related to starvation prevention: a bounded pool with a fair acquisition queue ensures no single caller can indefinitely starve others of a database connection, the same fairness trade-off as new ReentrantLock(true) applied to a pool of resources instead of a single lock.

Message queue consumer groups can exhibit livelock-like symptoms when consumers repeatedly rebalance in response to each other without ever settling into a stable assignment - frameworks like Kafka mitigate this with cooperative rebalancing protocols and backoff between rebalance attempts, the same principle as randomized retry backoff applied at a different layer of the system.

Deadlock - the four conditions : Mutual exclusion, hold and wait, no preemption, circular wait. All four must hold simultaneously; break any one and deadlock becomes impossible. Circular wait is usually the cheapest to break, via consistent lock ordering.

How do you detect a deadlock in a running JVM? : ThreadMXBean.findDeadlockedThreads() walks the JVM's live lock-ownership graph for a cycle - the same mechanism jstack and JConsole use. It returns null when the graph is free of cycles, or the IDs of every thread in the cycle otherwise. Run it on a timer in production so a hang becomes an alert, not a mystery.

What's the difference between deadlock and livelock? : In deadlock, threads are BLOCKED (near-0% CPU) and stuck forever. In livelock, threads are RUNNABLE (high CPU) but keep responding to each other without ever advancing - the fix is randomized retry backoff, not a fixed delay.

What's the difference between livelock and starvation? : Livelock affects all the contending threads equally and simultaneously; starvation affects one specific thread while everyone else keeps making progress. Starvation's usual cause is an unfair lock or a lock held too long; the fix is a fair lock or shorter critical sections.

Why isn't new ReentrantLock(true) the default? : Fairness is a real throughput cost - more context switches, and no "barging" optimization for a freshly-released lock. Unfair is faster in the common case, so fairness should be an intentional choice made once starvation risk is observed or strongly suspected, not a blanket default.

Want a visual for this concept?

Generate a diagram tailored to “Deadlocks, Livelocks & Starvation” — the AI picks whichever visual (flowchart, comparison, sequence, etc.) best fits.

Practice quiz

Next Step

Continue to Performance Optimization: Latency, Throughput & Amdahl's Law →← Back to all Java Concurrency & Multithreading chapters