🧵 Section 9 · Question #17

What is deadlock

A Deadlock is a critical failure state in concurrent programming where two or more threads are permanently blocked because each thread holds a lock on a resource that another th...

🧵 Multithreading 📄 Source Markdown

🟢 Junior Level

30-Second Summary

A Deadlock is a critical failure state in concurrent programming where two or more threads are permanently blocked because each thread holds a lock on a resource that another thread needs, while simultaneously awaiting a resource held by another.

The quintessential real-world analogy is a simultaneous two-way account fund transfer:

  • Thread 1 locks Account $A$ and attempts to acquire Account $B$.
  • Thread 2 simultaneously locks Account $B$ and attempts to acquire Account $A$.
  • Result: Neither thread can proceed. Both threads enter permanent BLOCKED or WAITING states, causing the subsystem to freeze indefinitely.

Unlike relational database engines, the Java Virtual Machine does not possess an automated deadlock resolution mechanism (such as automatic rollback or aborting transactions). A Java deadlock cannot be resolved without restarting the application or external intervention.

Comparative Overview: Deadlock vs. Livelock vs. Starvation

Phenomenon Thread State CPU Utilization Underlying Root Cause
Deadlock Passive freeze (BLOCKED / WAITING), waiting indefinitely 0% CPU Circular resource dependency
Livelock Active spin (RUNNABLE), state changes continuously without progress 100% CPU Symmetric resource yield collision
Starvation Ready to run, but thread scheduler continually starves worker Variable Unfair locks, thread priority bias

Classic Java 21 Deadlock Demonstration

public class DeadlockDemo {
    private final Object lockA = new Object();
    private final Object lockB = new Object();

    public void executeTask1() {
        synchronized (lockA) {
            System.out.println("Thread 1: holds lockA, waiting for lockB...");
            sleep(50);
            synchronized (lockB) {
                System.out.println("Thread 1: acquired both locks successfully");
            }
        }
    }

    public void executeTask2() {
        synchronized (lockB) {
            System.out.println("Thread 2: holds lockB, waiting for lockA...");
            sleep(50);
            synchronized (lockA) {
                System.out.println("Thread 2: acquired both locks successfully");
            }
        }
    }

    private void sleep(long ms) {
        try { Thread.sleep(ms); } catch (InterruptedException ignored) {}
    }
}

🟡 Middle Level

The 4 Coffman Conditions

In operating systems theory, a deadlock is mathematically possible if and only if all four Coffman conditions (Edward G. Coffman Jr., 1971) hold simultaneously:

                  The 4 Necessary Coffman Conditions
+-----------------------------+     +-----------------------------+
| 1. Mutual Exclusion         |     | 2. Hold and Wait            |
| Resource cannot be shared:  |     | Thread holds one resource   |
| only one thread holds the   |     | while actively requesting   |
| resource at any given time. |     | an additional resource.     |
+--------------+--------------+     +--------------+--------------+
               │                                   │
               v                                   v
+--------------+--------------+     +--------------+--------------+
| 3. No Preemption            |     | 4. Circular Wait            |
| Resources cannot be forcibly|     | A closed chain of threads   |
| confiscated; release must be|     | exists such that each thread|
| completely voluntary.       |     | waits for the next in cycle.|
+-----------------------------+     +-----------------------------+

[!IMPORTANT] Deadlock Prevention Principle: To guarantee that a deadlock can never occur, it is sufficient to break at least one of the four Coffman conditions! In enterprise software design, breaking the 4th condition (Circular Wait) through strict, global lock ordering is the most robust and common approach.

Hidden Deadlock Scenarios in Real Applications

In enterprise architectures, deadlocks rarely appear as clean, nested synchronized blocks inside a single class.

1. Thread Pool Starvation Deadlock

Occurs when parent tasks executing in a fixed-size thread pool submit child tasks to the exact same pool and block awaiting their completion:

// Single-threaded pool
ExecutorService pool = Executors.newFixedThreadPool(1);

pool.submit(() -> {
    System.out.println("Executing parent task...");
    // Parent task submits a child task to the SAME pool and blocks:
    Future<String> childTask = pool.submit(() -> "Child task result");
    
    // DEADLOCK TRAP:
    // The only thread in the pool is blocked waiting on childTask.get(),
    // while the child task sits unexecuted in the work queue forever!
    return childTask.get(); 
});

2. ClassLoader Deadlock (Static Class Initialization)

The Java Virtual Machine specification (JLS §12.4.2) enforces class-level synchronization during static initialization:

  • Static block of class A references class B.
  • Static block of class B references class A.
  • Two concurrent threads that trigger the initialization of these two classes simultaneously will deadlock on the JVM’s internal class-initialization monitors.

🔴 Senior Level

Production Diagnostics: jstack and ThreadMXBean

1. Thread Dump Analysis (jstack)

The JVM thread dump analyzer maps the thread wait graph and surfaces deadlocks automatically:

Found one Java-level deadlock:
=============================
"Thread-1":
  waiting to lock monitor 0x00007f90c8004b00 (object 0x000000076ad89010, a java.lang.Object),
  which is held by "Thread-2"

"Thread-2":
  waiting to lock monitor 0x00007f90c8005e00 (object 0x000000076ad89000, a java.lang.Object),
  which is held by "Thread-1"

Java stack information for the threads listed above:
===================================================
"Thread-1":
        at com.example.DeadlockDemo.executeTask1(DeadlockDemo.java:12)
        - waiting to lock <0x000000076ad89010> (a java.lang.Object)
        - locked <0x000000076ad89000> (a java.lang.Object)
"Thread-2":
        at com.example.DeadlockDemo.executeTask2(DeadlockDemo.java:23)
        - waiting to lock <0x000000076ad89000> (a java.lang.Object)
        - locked <0x000000076ad89010> (a java.lang.Object)

2. Programmatic Detection via ThreadMXBean

import java.lang.management.ManagementFactory;
import java.lang.management.ThreadInfo;
import java.lang.management.ThreadMXBean;

public class DeadlockDetector {
    public static void checkForDeadlocks() {
        ThreadMXBean bean = ManagementFactory.getThreadMXBean();
        // Detects deadlocks across synchronized monitors and AQS Lock instances
        long[] deadlockedThreadIds = bean.findDeadlockedThreads();

        if (deadlockedThreadIds != null) {
            ThreadInfo[] infos = bean.getThreadInfo(deadlockedThreadIds, true, true);
            for (ThreadInfo info : infos) {
                System.err.printf("[FATAL DEADLOCK] Thread %s is waiting for lock %s held by %s%n",
                    info.getThreadName(), info.getLockName(), info.getLockOwnerName());
            }
        }
    }
}

[!WARNING] bean.findDeadlockedThreads() executes Tarjan’s cycle-finding algorithm over the entire dependency graph of active threads ($O(V+E)$). It is a heavyweight diagnostic operation requiring a safepoint pause. Executing this continuously inside a tight loop in production is prohibited (a scheduled diagnostic poll every 30–60 seconds is acceptable).

Architectural Prevention Patterns

1. Deterministic Global Lock Ordering

When all threads acquire shared locks in an identical, predetermined order, circular wait becomes mathematically impossible:

public class SafeAccountTransfer {
    public void transfer(Account from, Account to, int amount) {
        // Enforce deterministic lock ordering using natural business keys:
        Account firstLock = from.getId() < to.getId() ? from : to;
        Account secondLock = from.getId() < to.getId() ? to : from;

        synchronized (firstLock) {
            synchronized (secondLock) {
                from.withdraw(amount);
                to.deposit(amount);
            }
        }
    }
}

2. Tie-Breaker Lock for Identity Collisions

If domain objects lack a unique numeric ID, order by System.identityHashCode(obj). Because identity hash codes can collide due to the pigeonhole principle, a global Tie-Breaker Lock guarantees serialization on hash collisions:

private static final Object tieLock = new Object();

public void transferByIdentity(Object from, Object to) {
    int fromHash = System.identityHashCode(from);
    int toHash = System.identityHashCode(to);

    if (fromHash < toHash) {
        synchronized (from) { synchronized (to) { /* perform transfer */ } }
    } else if (fromHash > toHash) {
        synchronized (to) { synchronized (from) { /* perform transfer */ } }
    } else {
        // Hash collision! Acquire global tie-breaker to serialize access:
        synchronized (tieLock) {
            synchronized (from) {
                synchronized (to) { /* perform transfer */ }
            }
        }
    }
}

3. Breaking “No Preemption”: ReentrantLock.tryLock() with Jitter

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

public class TimedLockAcquisition {
    public boolean tryTransfer(ReentrantLock lockA, ReentrantLock lockB, long timeout, TimeUnit unit) 
            throws InterruptedException {
        long stopTime = System.nanoTime() + unit.toNanos(timeout);
        while (System.nanoTime() < stopTime) {
            if (lockA.tryLock(50, TimeUnit.MILLISECONDS)) {
                try {
                    if (lockB.tryLock(50, TimeUnit.MILLISECONDS)) {
                        try {
                            return true; // Successfully acquired both locks!
                        } finally {
                            lockB.unlock();
                        }
                    }
                } finally {
                    lockA.unlock(); // Release first lock if second lock failed!
                }
            }
            // Randomized back-off jitter to eliminate Livelock synchronization
            Thread.sleep(ThreadLocalRandom.current().nextInt(10, 50));
        }
        return false;
    }
}

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

A Deadlock is an unrecoverable state where two or more threads are permanently blocked waiting for resources locked by each other, resulting in 0% CPU consumption. It strictly requires all four Coffman conditions: mutual exclusion, hold and wait, no preemption, and circular wait. Java diagnoses deadlocks via jstack dumps and ThreadMXBean. The primary architectural defense is eliminating circular wait via deterministic lock ordering (by entity ID or hash code with a tie-breaker lock) or using ReentrantLock.tryLock() with randomized jitter back-off to prevent livelocks.

2. 4 Tricky Follow-up Questions with Deep Answers

Question 1: What is the distinction between ThreadMXBean.findDeadlockedThreads() and findMonitorDeadlockedThreads()?

Answer:

  • findMonitorDeadlockedThreads() scans solely for deadlocks formed by Java’s built-in object monitors (synchronized).
  • findDeadlockedThreads() (added in Java 6) scans both synchronized monitors and explicit synchronizers from java.util.concurrent (such as ReentrantLock and other derivatives of AbstractQueuedSynchronizer implementing AbstractOwnableSynchronizer). It provides complete coverage across modern concurrency primitives.

Question 2: Why is a Tie-Breaker Lock mandatory when ordering locks via System.identityHashCode()?

Answer: System.identityHashCode(obj) returns a 31-bit integer. Under the birthday paradox, collisions are mathematically inevitable in long-running systems with thousands of allocated objects. If two different objects share the identical identity hash code, simple ordering fails and the acquisition order becomes arbitrary, re-introducing deadlock risk. The tieLock serializes execution for the rare collision branch, guaranteeing atomic evaluation.

Question 3: Can Thread.interrupt() rescue a thread trapped in a synchronized monitor deadlock?

Answer: No. A thread waiting to acquire an intrinsic monitor via the synchronized keyword (monitorenter bytecode instruction) enters Thread.State.BLOCKED and is fundamentally uninterruptible. Calling interrupt() flags the thread but will not wake it from the monitor’s entry queue. To achieve interruptible locking, the system must utilize explicit lock interfaces supporting Lock.lockInterruptibly().

Question 4: What is Thread Pool Starvation Deadlock, and why does increasing pool size fail as a permanent solution?

Answer: It happens when tasks in a thread pool submit subtasks to the exact same pool and block on future.get(). If concurrent parent tasks occupy all worker threads ($N$), no threads remain to process the queued child tasks. The pool deadlocks permanently. Increasing the thread pool size merely elevates the failure ceiling: under burst traffic, the larger pool will still be exhausted. Permanent fixes include segregating pools for parent vs. child tasks, employing non-blocking composition (CompletableFuture.thenCompose()), or migrating to Java 21 Virtual Threads.

3. Red Flags & Common Gotchas

❌ “Deadlock and Livelock are identical.”
Correction: Deadlock threads are inert (BLOCKED/WAITING) consuming 0% CPU. Livelock threads remain active (RUNNABLE) burning 100% CPU yielding to one another without accomplishing forward progress.

❌ “The JVM throws an exception when a deadlock occurs.”
Correction: The JVM never throws exceptions or logs warnings automatically during a deadlock; threads hang silently until process termination.

❌ “Using tryLock() without timeouts eliminates all concurrency bugs.”
Correction: Naive retry loops with tryLock() without random back-off jitter convert deadlocks into livelocks, where competing threads repeatedly lock and unlock in lockstep.