🧵 Section 9 · Question #18

What conditions are necessary for deadlock to occur

For a Deadlock to materialize in any concurrent system, all four Coffman conditions (formulated by Edward G. Coffman Jr. in 1971) must hold simultaneously:

🧵 Multithreading 📄 Source Markdown

🟢 Junior Level

30-Second Summary

For a Deadlock to materialize in any concurrent system, all four Coffman conditions (formulated by Edward G. Coffman Jr. in 1971) must hold simultaneously:

  1. Mutual Exclusion: Resources cannot be shared; at any given instant, a resource is held exclusively by at most one thread.
  2. Hold and Wait: A thread currently holding at least one resource is actively requesting additional resources currently held by other threads.
  3. No Preemption: Resources cannot be forcibly seized from a thread; a resource is released only voluntarily by the holding thread upon task completion.
  4. Circular Wait: A closed chain of threads ${T_1, T_2, \dots, T_n}$ exists such that $T_1$ waits for a resource held by $T_2$, $T_2$ waits for $T_3$, …, and $T_n$ waits for a resource held by $T_1$.

[!IMPORTANT] Fundamental Law of Deadlock Prevention: If you break even one of the four Coffman conditions, the occurrence of a deadlock becomes mathematically impossible.

Demonstrating Coffman Conditions in Java 21 Code

public class CoffmanConditionsDemo {
    private final Object resourceA = new Object();
    private final Object resourceB = new Object();

    public void threadOneAction() {
        // Condition 1 (Mutual Exclusion): synchronized claims monitor exclusively
        synchronized (resourceA) {
            // Condition 2 (Hold and Wait): holding resourceA, thread requests resourceB
            // Condition 3 (No Preemption): JVM cannot forcibly revoke resourceA from this thread
            synchronized (resourceB) {
                doWork();
            }
        }
    }

    public void threadTwoAction() {
        synchronized (resourceB) {
            // Condition 4 (Circular Wait): thread 2 waits for resourceA, completing circular chain
            synchronized (resourceA) {
                doWork();
            }
        }
    }

    private void doWork() {}
}

🟡 Middle Level

Breaking the Coffman Conditions in Enterprise Java

Each Coffman condition can be deliberately dismantled using established concurrency patterns:

              Strategies to Eliminate Coffman Conditions in Java
+--------------------------------------------------------------------------+
| 1. Breaking Mutual Exclusion:                                            |
|    - Replace mutual exclusion locks with lock-free structures (Atomic*).  |
|    - Use shared reader-writer locks (ReentrantReadWriteLock.readLock()). |
+--------------------------------------------------------------------------+
| 2. Breaking Hold and Wait:                                               |
|    - "All-or-Nothing" atomic acquisition via tryLock():                  |
|      if subsequent resource acquisition fails, immediately release first! |
+--------------------------------------------------------------------------+
| 3. Breaking No Preemption:                                               |
|    - Employ ReentrantLock.tryLock(timeout) or lockInterruptibly() to     |
|      forcibly abandon stalled resource acquisition attempts.            |
+--------------------------------------------------------------------------+
| 4. Breaking Circular Wait (THE MOST POWERFUL & COST-EFFECTIVE):          |
|    - Enforce Global Lock Ordering (Havender's Linear Ordering).          |
|    - Acquire locks in strict, deterministic ascending order of IDs.      |
+--------------------------------------------------------------------------+

In-Depth Elimination Strategies

1. Breaking Mutual Exclusion

If multiple execution units can safely share a resource concurrently, deadlocks cannot occur.

  • Application: Partition read access from write access using ReentrantReadWriteLock or StampedLock. Dozens of concurrent readers can hold readLock() simultaneously without mutual contention.
  • Limitation: Inapplicable to write operations that mutate internal state.

2. Breaking Hold and Wait

Threads must not hold locked resources while blocked waiting for others:

// "All-or-Nothing" Acquisition Pattern
boolean acquiredA = lockA.tryLock();
boolean acquiredB = false;
try {
    if (acquiredA) {
        acquiredB = lockB.tryLock();
    }
    if (acquiredA && acquiredB) {
        // Both locks acquired successfully: execute business logic
        process();
    }
} finally {
    if (!acquiredB && acquiredA) {
        lockA.unlock(); // IMMEDIATELY RELEASE lockA if lockB acquisition failed!
    } else if (acquiredB) {
        lockB.unlock();
        lockA.unlock();
    }
}

3. Breaking No Preemption

Standard synchronized monitors are non-preemptible. Replacing them with explicit locks allows timeout-based retreats:

// If resource acquisition stalls beyond 100ms, back off gracefully
if (lock.tryLock(100, TimeUnit.MILLISECONDS)) {
    try {
        execute();
    } finally {
        lock.unlock();
    }
}

4. Breaking Circular Wait (Havender’s Linear Ordering)

The most resilient enterprise strategy is enforcing strict global acquisition ordering:

public void transferMoney(Account from, Account to, int amount) {
    // Deterministic ordering: lowest account ID is unconditionally acquired first!
    Account first = from.getId() < to.getId() ? from : to;
    Account second = from.getId() < to.getId() ? to : from;

    synchronized (first) {
        synchronized (second) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}

Because every thread throughout the cluster acquires locks in the identical order, a cycle in the dependency graph cannot form.

🔴 Senior Level

Graph Theory: Wait-For Graph (WFG) & Resource Allocation Graph (RAG)

In distributed systems theory, deadlocks are modeled via directed bipartite graphs (RAG):

       Resource Allocation Graph (RAG)           Wait-For Graph (WFG)
          [ R1 ] ───────> ( T1 )                    ( T1 ) ◄───────┐
            ▲               │                         │            │
            │               │                         │            │
            │               v                         v            │
          ( T2 ) <─────── [ R2 ]                    ( T2 ) ────────┘
      (T2 awaits R1,  (R2 held by T2,             (Cycle in WFG denotes
       R1 held by T1)  T1 awaits R2)               mathematical Deadlock)
  1. Single-Unit Resources: A cycle in the Wait-For Graph (WFG) is both a necessary and sufficient condition for deadlock.
  2. Multi-Unit Resources: A cycle is a necessary condition, but not sufficient (evaluated using Dijkstra’s Banker’s Algorithm).

The Dining Philosophers Problem (Edsger Dijkstra, 1965)

The textbook canonical model exhibiting all four Coffman conditions:

  • 5 philosophers sit at a circular dining table with 5 shared forks.
  • Each philosopher requires two adjacent forks (left and right) to eat.
                            Philosopher 1
                          /               \
                      Fork 1             Fork 5
                      /                     \
                Philosopher 2               Philosopher 5
                  |                           |
                Fork 2                     Fork 4
                    \                     /
                   Philosopher 3 ── Fork 3 ── Philosopher 4

Mapping to Coffman Conditions:

  1. Mutual Exclusion: Each fork can be used by only one philosopher at a time.
  2. Hold and Wait: Each philosopher picks up their left fork and waits for the right fork.
  3. No Preemption: No philosopher can snatch a fork from their neighbor’s hand.
  4. Circular Wait: If all 5 philosophers simultaneously grab their left fork, all 5 wait for their right fork—causing systemic deadlock.

Dijkstra’s Solution (Breaking Circular Wait):

Designate one philosopher (e.g., the last) as a “left-hander” who picks up their right fork first, while the other four pick up their left fork first. The circular dependency is broken instantly.

Real-World Diagnostic: False Deadlocks

APM monitoring tools frequently raise alarms for perceived “deadlocks” that are actually distinct concurrency bottlenecks:

Latency Bottleneck Thread State CPU Usage Is it a Deadlock?
Java Thread Deadlock BLOCKED on monitors 0% ✅ Yes
HikariCP Pool Starvation WAITING on getConnection() 0% ❌ No (Resource Starvation)
Network Socket Hang RUNNABLE in kernel socket read 0% ❌ No (Missing Socket Timeout)
Stop-the-World GC Pause Stopped at Safepoints 100% (GC threads) ❌ No (GC Latency)

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

Deadlocks occur if and only if all four Coffman conditions hold simultaneously: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. Breaking any single condition mathematically eliminates deadlock possibility. In enterprise systems, the gold standard is breaking Circular Wait through deterministic lock ordering (by unique numeric ID) or breaking No Preemption using timed attempts via ReentrantLock.tryLock(timeout).

2. 4 Tricky Follow-up Questions with Deep Answers

Question 1: Which of the four Coffman conditions is safest and most practical to break in enterprise Java code?

Answer: Condition 4 — Circular Wait, achieved through Global Lock Ordering.
Rationale:

  • Breaking Mutual Exclusion on mutable data breaks consistency and induces race conditions.
  • Breaking Hold and Wait (e.g., acquiring multiple resources via uncoordinated tryLock loops) risks Livelock.
  • Enforcing deterministic lock acquisition (e.g., sorting entity IDs before locking) prevents cycles in the wait-for graph with zero algorithmic overhead.

Question 2: Does ReentrantReadWriteLock completely eliminate Mutual Exclusion?

Answer: Only for readers. Shared read locks (readLock()) allow concurrent acquisition, breaking mutual exclusion for read-only workloads. However, write locks (writeLock()) remain strictly mutually exclusive. Furthermore, attempting lock upgrading (acquiring writeLock() while already holding readLock()) within concurrent threads guarantees immediate deadlock.

Question 3: How does Dijkstra’s Dining Philosophers problem illustrate Coffman conditions and its resolution?

Answer: It maps all four conditions: forks are non-sharable (Mutual Exclusion), a philosopher holds one fork while waiting for the next (Hold and Wait), forks cannot be seized (No Preemption), and grabbing forks symmetrically creates a closed loop (Circular Wait). Dijkstra resolves this by breaking symmetry (e.g., having one philosopher acquire forks in reverse order, or enforcing ascending numeric order on forks), eliminating the circular wait.

Question 4: Does calling Thread.interrupt() break the “No Preemption” condition for synchronized blocks?

Answer: No. A thread blocked on intrinsic monitor entry (synchronized / monitorenter) resides in Thread.State.BLOCKED. In Java, this state is uninterruptible. interrupt() merely flips the thread’s interrupt status bit; it will not wake the thread or throw InterruptedException. Breaking No Preemption requires explicit lock interfaces supporting Lock.lockInterruptibly() or Lock.tryLock().

3. Red Flags & Common Gotchas

❌ “Satisfying any three of the Coffman conditions is sufficient for a deadlock.”
Correction: All four conditions must be met simultaneously. If even one condition is absent, a deadlock cannot occur.

❌ “Marking variables volatile protects against Coffman conditions.”
Correction: volatile provides cache visibility and ordering barriers, but zero mutual exclusion for compound operations.

❌ “If code does not use synchronized, Coffman conditions do not apply.”
Correction: Coffman conditions apply universally to all exclusive computing resources, including database connection pools, file handles, and distributed locks.