Concurrency Basics

Deadlocks & Liveness

15 min Lesson 9 of 13

Deadlocks & Liveness

Getting the synchronized keyword right stops race conditions, but it opens a new category of hazard: liveness failures. A liveness failure means threads stop making progress — not because of a bug in your data, but because the threads themselves are stuck waiting on each other. The three classic forms are deadlock, livelock, and starvation.

Deadlock

A deadlock occurs when two or more threads each hold a lock the other needs, so every thread waits forever and none can proceed. The classic pattern is a lock-ordering problem:

public class DeadlockDemo {

    private final Object lockA = new Object();
    private final Object lockB = new Object();

    public void transfer(boolean reverse) {
        Object first  = reverse ? lockB : lockA;
        Object second = reverse ? lockA : lockB;

        synchronized (first) {
            System.out.println(Thread.currentThread().getName() + " holds " + (reverse ? "B" : "A"));
            try { Thread.sleep(50); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }

            synchronized (second) {           // may wait forever
                System.out.println("Transfer complete");
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        DeadlockDemo demo = new DeadlockDemo();

        Thread t1 = new Thread(() -> demo.transfer(false), "T1");  // acquires A then B
        Thread t2 = new Thread(() -> demo.transfer(true),  "T2");  // acquires B then A

        t1.start(); t2.start();
        t1.join();  t2.join();
        // Very likely to hang indefinitely
    }
}

T1 grabs lockA and waits for lockB. T2 grabs lockB and waits for lockA. Neither can continue.

How to Avoid Deadlock

1. Consistent lock ordering. The most reliable fix: every thread always acquires locks in the same global order. If all code acquires A before B, no circular wait can form.

// Safe: always lock by System.identityHashCode — a global, consistent ordering
public void safeTransfer(Object resource1, Object resource2) {
    Object first, second;
    int hash1 = System.identityHashCode(resource1);
    int hash2 = System.identityHashCode(resource2);

    if (hash1 < hash2) { first = resource1; second = resource2; }
    else                { first = resource2; second = resource1; }

    synchronized (first) {
        synchronized (second) {
            // critical section
        }
    }
}

2. Use timed lock attempts. ReentrantLock.tryLock(timeout, unit) lets you back off and retry instead of blocking forever. This turns a deadlock into a recoverable situation:

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

ReentrantLock lockA = new ReentrantLock();
ReentrantLock lockB = new ReentrantLock();

boolean acquired = false;
while (!acquired) {
    if (lockA.tryLock(100, TimeUnit.MILLISECONDS)) {
        try {
            if (lockB.tryLock(100, TimeUnit.MILLISECONDS)) {
                try {
                    // critical section
                    acquired = true;
                } finally { lockB.unlock(); }
            }
        } finally { lockA.unlock(); }
    }
    // back off briefly before retrying
    Thread.sleep(10);
}

3. Avoid holding locks while calling unknown code. A common mistake is calling a user-supplied callback or an external method while holding a lock. If that external code acquires another lock, you have an ordering you did not control.

Detecting deadlocks at runtime: Java's built-in thread dump (via jstack <pid> or ThreadMXBean.findDeadlockedThreads()) reports "Found one Java-level deadlock" with the full stack of each stuck thread. In production, capturing a thread dump is your first diagnostic step when a service stops responding.

Livelock

In a livelock, threads are not blocked — they are actively running — but each one keeps reacting to the other's state change, so no progress is made. Think of two people in a corridor who both step the same way to let the other pass, again and again.

// Simplified livelock sketch — two threads each "politely" back off
// whenever they see the other is also trying, so neither ever succeeds.
class Polite {
    volatile boolean active = true;

    void tryWork(Polite other) throws InterruptedException {
        while (active) {
            if (other.active) {
                System.out.println(Thread.currentThread().getName() + " steps aside");
                Thread.sleep(1);  // back off
                continue;         // check again — other is STILL active, loop forever
            }
            // do work (never reached in the symmetric case)
            active = false;
        }
    }
}

Fix: introduce asymmetry or randomness. Give one thread higher priority, or back off for a random duration (exponential back-off), so both threads do not react identically at the same moment.

Starvation

Starvation means one or more threads are perpetually denied access to a resource because other threads monopolise it. Common causes:

A high-priority thread keeps running so a low-priority thread never gets CPU time.
A lock is released and immediately re-acquired by the same thread before a waiting thread can grab it (barging).
One writer thread continuously holds a read-write lock, starving readers (or vice versa).

import java.util.concurrent.locks.ReentrantLock;

// Non-fair lock (default): the JVM can let the same thread re-acquire immediately.
ReentrantLock unfair = new ReentrantLock();          // false = non-fair
ReentrantLock fair   = new ReentrantLock(true);      // true  = fair (FIFO queue)

A fair ReentrantLock uses a FIFO queue: the thread that has waited the longest gets the lock next. This eliminates starvation but reduces throughput slightly because the JVM can no longer let the current thread (which is already scheduled on a CPU core) re-acquire without a context switch.

Fair locks are not always the right tool. Use them when starvation is a real concern (e.g., a low-priority background task that must eventually run). For high-throughput hot paths, prefer non-fair locks or lock-free structures from java.util.concurrent.

Diagnosing Liveness Problems in Production

Thread dump: kill -3 <pid> on Linux or jstack <pid> prints all thread states. Blocked threads show the lock they are waiting on and the thread that owns it.
JConsole / VisualVM / JMC: GUI tools that highlight deadlocked threads graphically.
ThreadMXBean: Call ManagementFactory.getThreadMXBean().findDeadlockedThreads() programmatically to detect deadlocks from a monitoring thread or health-check endpoint.

Reducing lock scope is your best preventive medicine. The shorter the time a lock is held, the smaller the window for circular waits to form. If you find yourself nesting synchronized blocks more than one level deep, step back and consider whether a higher-level concurrent structure (e.g., ConcurrentHashMap, BlockingQueue, or a lock-free algorithm) can eliminate the nesting entirely.

Summary

Deadlock is a circular wait between threads holding each other's required locks — fix it with consistent lock ordering or timed tryLock. Livelock is active thrashing with no progress — fix it with randomness or asymmetry. Starvation is a thread perpetually losing the lock race — fix it with a fair lock or redesigned access patterns. All three are liveness failures: the code may be logically correct yet the program stops making useful progress. Recognising which failure you have is the first step to solving it.