☕ JavaMultithreading

Deadlock

Deadlock is a situation in which two or more threads are permanently blocked, each waiting to acquire a lock held by another thread in the same cycle. No thread in the cycle can ever make progress because each is waiting for a resource that will never be released. Deadlock is silent — no exception is thrown, no timeout occurs, the threads simply stop doing useful work forever while appearing to be alive. Unlike exceptions or incorrect output, deadlock produces programs that hang, making it one of the most serious concurrency defects. Java's intrinsic locks provide no built-in deadlock prevention or detection, so understanding deadlock fully — its four necessary conditions, reliable detection, proven prevention strategies, and avoidance via lock ordering and tryLock — is essential for writing correct concurrent code. This entry covers the four Coffman conditions, the two-thread canonical example and its generalization to N threads, programmatic deadlock detection via ThreadMXBean, lock ordering as the primary prevention strategy, tryLock with timeout as an escape mechanism, open-call discipline, and the differences between deadlock and related liveness failures.

The Four Coffman Conditions and the Canonical Example

Deadlock requires four conditions to hold simultaneously. Mutual exclusion: at least one resource must be held in a non-shareable mode — only one thread can hold a lock at a time. Hold and wait: a thread holds at least one lock and is waiting to acquire additional locks held by other threads. No preemption: locks cannot be forcibly taken from a thread; a thread releases its locks only voluntarily. Circular wait: there exists a set of threads T1, T2, ..., Tn such that T1 waits for a lock held by T2, T2 waits for a lock held by T3, and Tn waits for a lock held by T1. All four conditions are necessary — eliminating any one of them prevents deadlock. The canonical two-thread example: Thread A acquires lock X then waits for lock Y; Thread B acquires lock Y then waits for lock X. If both threads acquire their first lock before either acquires their second lock, they are deadlocked. Thread A holds X and blocks on Y; Thread B holds Y and blocks on X. Neither can release what the other needs. The deadlock is permanent — nothing in Java's runtime resolves it. The same pattern generalizes to N threads in a ring: T1 holds L1 and wants L2; T2 holds L2 and wants L3; ... Tn holds Ln and wants L1. The cycle length does not matter — the behavior is identical. Multi-party deadlocks are harder to diagnose because the dependency chain spans more threads and the locks may be acquired in many different methods across a large codebase. Deadlocks often manifest intermittently because they depend on timing — the threads must acquire their locks in the wrong interleaving. In testing, the interleaving may never occur, and the deadlock only surfaces in production under high concurrency or specific load patterns. This timing dependency makes deadlocks far harder to reproduce and diagnose than deterministic bugs.

Java

// ── Canonical two-thread deadlock ─────────────────────────────────────
public class TwoThreadDeadlock {
    private final Object lockA = new Object();
    private final Object lockB = new Object();

    // Thread 1: acquires lockA, then tries for lockB
    public void methodA() throws InterruptedException {
        synchronized (lockA) {
            System.out.println(Thread.currentThread().getName() + ": holding A, waiting for B");
            Thread.sleep(50);   // sleep to increase likelihood of interleaving
            synchronized (lockB) {
                System.out.println(Thread.currentThread().getName() + ": holding A and B");
            }
        }
    }

    // Thread 2: acquires lockB, then tries for lockA — opposite order
    public void methodB() throws InterruptedException {
        synchronized (lockB) {
            System.out.println(Thread.currentThread().getName() + ": holding B, waiting for A");
            Thread.sleep(50);
            synchronized (lockA) {
                System.out.println(Thread.currentThread().getName() + ": holding B and A");
            }
        }
    }
}

TwoThreadDeadlock example = new TwoThreadDeadlock();

Thread t1 = new Thread(() -> {
    try { example.methodA(); }
    catch (InterruptedException e) { Thread.currentThread().interrupt(); }
}, "Thread-1");

Thread t2 = new Thread(() -> {
    try { example.methodB(); }
    catch (InterruptedException e) { Thread.currentThread().interrupt(); }
}, "Thread-2");

t1.start(); t2.start();
// Output (then hangs forever):
// Thread-1: holding A, waiting for B
// Thread-2: holding B, waiting for A
// [both threads blocked permanently — program never terminates]

// ── N-thread ring deadlock ─────────────────────────────────────────────
public static void ringDeadlock(int n) {
    Object[] locks = new Object[n];
    for (int i = 0; i < n; i++) locks[i] = new Object();

    for (int i = 0; i < n; i++) {
        final int index = i;
        new Thread(() -> {
            Object first  = locks[index];
            Object second = locks[(index + 1) % n];
            synchronized (first) {
                System.out.println(Thread.currentThread().getName()
                    + " holds lock " + index + ", wants lock " + (index + 1) % n);
                try { Thread.sleep(50); } catch (InterruptedException e) {}
                synchronized (second) {   // waits for next thread's lock — ring closes
                    System.out.println(Thread.currentThread().getName() + " got both");
                }
            }
        }, "Thread-" + i).start();
    }
}

ringDeadlock(5);   // 5-thread ring: T0→L0→L1, T1→L1→L2, ..., T4→L4→L0

// ── Deadlock is silent — the JVM does not throw or terminate ──────────
// A deadlocked thread's state is BLOCKED (not TERMINATED or ERROR)
// Thread.getState() == Thread.State.BLOCKED  for deadlocked threads
// ThreadMXBean can detect the cycle — see detection section below

Detection — ThreadMXBean and Thread Dumps

Java provides programmatic deadlock detection through java.lang.management.ThreadMXBean. The method findDeadlockedThreads() returns an array of thread IDs involved in deadlock cycles, or null if no deadlock exists. findMonitorDeadlockedThreads() detects only intrinsic (synchronized) lock deadlocks; findDeadlockedThreads() detects both intrinsic locks and java.util.concurrent.locks.Lock deadlocks. These methods can be called from a monitoring thread, a health-check endpoint, or a watchdog timer to detect deadlocks at runtime. Once deadlocked thread IDs are identified, ThreadInfo objects obtained via getThreadInfo() provide the full stack trace of each deadlocked thread, the lock it is waiting for, and the thread that owns that lock. This information is sufficient to identify exactly which locks are involved and which code paths acquired them. The most common operational tool for deadlock diagnosis is a thread dump. On Unix-like systems, sending SIGQUIT (kill -3 <pid>) to a Java process causes the JVM to print all thread states and a deadlock analysis to stderr. The output includes a "Found one Java-level deadlock" section that names the deadlocked threads, shows each thread's stack trace, and identifies which lock each thread is waiting on and who owns it. On Windows, Ctrl+Break produces the same output. Tools like jstack (part of the JDK), jcmd Thread.print, VisualVM, and JConsole all produce thread dumps. Automated monitoring systems often trigger thread dumps when threads have been BLOCKED for longer than a threshold duration. Deadlock detection is useful for diagnosing existing deadlocks but not for preventing them. Once a deadlock is detected programmatically, the options are: kill and restart the involved threads (possible with java.util.concurrent.locks.Lock if the code is structured to handle InterruptedException), restart the entire application, or alert a human operator. The detection-and-recovery approach is complex and brittle; prevention is always preferable.

Java

// ── Programmatic detection via ThreadMXBean ───────────────────────────
import java.lang.management.*;

public class DeadlockDetector {

    public static void detectAndReport() {
        ThreadMXBean threadBean = ManagementFactory.getThreadMXBean();

        // findDeadlockedThreads: intrinsic AND j.u.c.locks deadlocks (Java 6+)
        long[] deadlockedIds = threadBean.findDeadlockedThreads();

        if (deadlockedIds == null) {
            System.out.println("No deadlock detected");
            return;
        }

        System.out.println("DEADLOCK DETECTED — " + deadlockedIds.length + " threads involved:");

        ThreadInfo[] infos = threadBean.getThreadInfo(deadlockedIds, true, true);
        for (ThreadInfo info : infos) {
            System.out.printf("%n=== Thread: %s (id=%d) ===%n",
                info.getThreadName(), info.getThreadId());
            System.out.printf("State: %s%n", info.getThreadState());
            System.out.printf("Waiting for lock: %s%n", info.getLockName());
            System.out.printf("Lock owned by: %s%n",   info.getLockOwnerName());
            System.out.println("Stack trace:");
            for (StackTraceElement frame : info.getStackTrace()) {
                System.out.println("  at " + frame);
            }
        }
    }

    // Watchdog thread: polls for deadlock every 5 seconds
    public static Thread startWatchdog() {
        Thread watchdog = new Thread(() -> {
            while (!Thread.currentThread().isInterrupted()) {
                detectAndReport();
                try { Thread.sleep(5000); }
                catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }, "DeadlockWatchdog");
        watchdog.setDaemon(true);   // don't prevent JVM shutdown
        watchdog.start();
        return watchdog;
    }
}

// ── Usage: inject watchdog into application startup ───────────────────
DeadlockDetector.startWatchdog();
// Now create the deadlock:
TwoThreadDeadlock d = new TwoThreadDeadlock();
new Thread(() -> { try { d.methodA(); } catch (InterruptedException e) {} }).start();
new Thread(() -> { try { d.methodB(); } catch (InterruptedException e) {} }).start();

// After ~5 seconds, watchdog prints:
// DEADLOCK DETECTED — 2 threads involved:
// === Thread: Thread-0 (id=12) ===
// State: BLOCKED
// Waiting for lock: java.lang.Object@1234 (lockB)
// Lock owned by: Thread-1
// Stack trace:
//   at TwoThreadDeadlock.methodA(TwoThreadDeadlock.java:14)
//   ...
// === Thread: Thread-1 (id=13) ===
// State: BLOCKED
// Waiting for lock: java.lang.Object@5678 (lockA)
// Lock owned by: Thread-0

// ── Thread dump via jstack (command line) ────────────────────────────
// jstack <pid>   produces:
//
// Found one Java-level deadlock:
// =============================
// "Thread-1":
//   waiting to lock monitor 0x00007f... (object 0x..., a java.lang.Object [lockA]),
//   which is held by "Thread-0"
// "Thread-0":
//   waiting to lock monitor 0x00007f... (object 0x..., a java.lang.Object [lockB]),
//   which is held by "Thread-1"
//
// Java stack information for the threads listed above:
// ===================================================
// "Thread-1":
//         at TwoThreadDeadlock.methodB(TwoThreadDeadlock.java:24)
//         - waiting to lock <0x...> (lockA)
//         - locked <0x...> (lockB)
// "Thread-0":
//         at TwoThreadDeadlock.methodA(TwoThreadDeadlock.java:14)
//         - waiting to lock <0x...> (lockB)
//         - locked <0x...> (lockA)

Prevention — Lock Ordering, tryLock, and Open Calls

Lock ordering is the most reliable and widely applicable deadlock prevention strategy. It eliminates the circular-wait condition — the fourth Coffman condition — by imposing a global total order on all locks in the system and requiring every thread to acquire locks in that order. If every thread that needs both lock X and lock Y always acquires X before Y, the cycle cannot form: thread A holds X and waits for Y; thread B cannot hold Y and wait for X because it must acquire X first — and X is held by A. Thread B therefore blocks before acquiring Y, and Y is not held. No cycle exists. Establishing a lock order requires a system-wide discipline. For objects of the same class, use System.identityHashCode() to derive a consistent order: the object with the lower identity hash code is always acquired first. When two objects have the same hash code (a collision), a tie-breaking lock (a third lock acquired by any thread that encounters a tie) prevents the cycle. This pattern is used in java.util.Collections.sort() and in the classic dining philosophers solution. tryLock() with a timeout, available through java.util.concurrent.locks.ReentrantLock, allows a thread to attempt acquiring a lock and give up if it cannot succeed within a time bound. On failure, the thread releases all locks it holds, backs off (optionally sleeping for a random interval to reduce re-contention), and retries. This breaks the hold-and-wait condition: the thread does not hold locks while indefinitely waiting for another. The complexity is managing the retry loop and ensuring that released work can be safely retried. Open calls — calling a method without holding any lock — eliminate a class of deadlocks caused by calling external or user-supplied code while holding a lock. If your synchronized method calls a callback, listener, or any method on an object you did not write, that external code may acquire locks in an order that conflicts with yours. Restructuring to release your lock before making the call, then reacquire it afterward if needed, eliminates this vulnerability.

Java

// ── Lock ordering by System.identityHashCode() ────────────────────────
public class SafeTransfer {

    public static void transfer(Account from, Account to, double amount) {
        // Derive acquisition order from identity hash code:
        int fromHash = System.identityHashCode(from);
        int toHash   = System.identityHashCode(to);

        if (fromHash < toHash) {
            synchronized (from) { synchronized (to) { doTransfer(from, to, amount); } }
        } else if (fromHash > toHash) {
            synchronized (to) { synchronized (from) { doTransfer(from, to, amount); } }
        } else {
            // Hash collision: use a tie-breaking lock to ensure ordering
            synchronized (Account.TIE_LOCK) {   // static final Object TIE_LOCK = new Object()
                synchronized (from) { synchronized (to) { doTransfer(from, to, amount); } }
            }
        }
    }

    private static void doTransfer(Account from, Account to, double amount) {
        if (from.getBalance() < amount) throw new IllegalStateException("Insufficient funds");
        from.debit(amount);
        to.credit(amount);
    }
}

// Any two threads calling transfer(A, B) and transfer(B, A) will both
// acquire locks in the same hash-code-determined order — no cycle possible.

// ── tryLock() with timeout and backoff ────────────────────────────────
import java.util.concurrent.locks.*;
import java.util.concurrent.ThreadLocalRandom;

public class TryLockTransfer {
    private final ReentrantLock lock;
    private double balance;

    public TryLockTransfer(double balance) {
        this.lock    = new ReentrantLock();
        this.balance = balance;
    }

    public static boolean transfer(TryLockTransfer from, TryLockTransfer to, double amount)
            throws InterruptedException {
        long deadline = System.nanoTime() + 1_000_000_000L;  // 1 second total budget

        while (true) {
            // Try to acquire 'from' lock:
            if (from.lock.tryLock(50, TimeUnit.MILLISECONDS)) {
                try {
                    // Try to acquire 'to' lock without blocking forever:
                    if (to.lock.tryLock(50, TimeUnit.MILLISECONDS)) {
                        try {
                            // Both locks acquired — safe to transfer:
                            if (from.balance < amount) return false;
                            from.balance -= amount;
                            to.balance   += amount;
                            return true;
                        } finally { to.lock.unlock(); }
                    }
                    // Could not get 'to' — release 'from' and retry
                } finally { from.lock.unlock(); }
            }
            // Neither held — check timeout and backoff before retry:
            if (System.nanoTime() > deadline) return false;  // give up
            Thread.sleep(ThreadLocalRandom.current().nextLong(1, 10)); // random backoff
        }
    }
}

// ── Open calls — don't hold locks when calling external code ──────────
public class EventDispatcher {
    private final List<EventListener> listeners = new ArrayList<>();
    private final Object listenerLock = new Object();

    // UNSAFE: holds listenerLock while calling listener — listener may acquire
    // another lock in an order that conflicts with some other lock we hold elsewhere
    public void fireEventUnsafe(Event event) {
        synchronized (listenerLock) {
            for (EventListener listener : listeners) {
                listener.onEvent(event);   // external code called under lock — dangerous
            }
        }
    }

    // SAFE: open call — snapshot listeners first, release lock, then call
    public void fireEventSafe(Event event) {
        List<EventListener> snapshot;
        synchronized (listenerLock) {
            snapshot = new ArrayList<>(listeners);  // copy while locked
        }
        // Lock released before calling external code:
        for (EventListener listener : snapshot) {
            listener.onEvent(event);   // listener acquires its own locks without interference
        }
    }

    public void addListener(EventListener l) {
        synchronized (listenerLock) { listeners.add(l); }
    }
}

// ── Lock ordering with an explicit ordering field ─────────────────────
// When objects have natural IDs, use ID order instead of identity hash:
public class OrderedAccount {
    private static final AtomicLong ID_COUNTER = new AtomicLong(0);
    private final long id = ID_COUNTER.incrementAndGet();  // unique, stable, ordered
    private double balance;

    public static void transfer(OrderedAccount from, OrderedAccount to, double amount) {
        // Always lock the lower-ID account first — guaranteed consistent order:
        OrderedAccount first  = from.id < to.id ? from : to;
        OrderedAccount second = from.id < to.id ? to   : from;

        synchronized (first) {
            synchronized (second) {
                from.balance -= amount;
                to.balance   += amount;
            }
        }
    }
}

Deadlock

The Four Coffman Conditions and the Canonical Example

Detection — ThreadMXBean and Thread Dumps

Prevention — Lock Ordering, tryLock, and Open Calls

Related Topics in Multithreading