Home/Learn/Operating Systems/Deadlock: Four Necessary Conditions

Deadlock: Four Necessary Conditions

Beginner

Deadlocks

A deadlock occurs only when all four Coffman conditions hold simultaneously: mutual exclusion, hold and wait, no preemption, and circular wait.

Overview

Deadlock is a state where a set of processes are permanently blocked, each waiting for a resource held by another. E.W. Dijkstra and others identified four necessary conditions — all four must hold simultaneously for deadlock to occur. Removing even one condition prevents deadlock entirely. Think of it like a four-lane roundabout where each lane is blocked by the car ahead: every car holds its lane (mutual exclusion), refuses to back up (no preemption), is waiting for the next lane (hold and wait), and the chain circles back (circular wait).

The Four Coffman Conditions

Mutual Exclusion: a resource can be held by at most one process at a time. Hold and Wait: a process holds at least one resource while waiting to acquire additional resources. No Preemption: resources cannot be forcibly taken from a process; they must be released voluntarily. Circular Wait: a set of processes P1, P2, …, Pn exists such that P1 waits for a resource held by P2, P2 waits for P3, and Pn waits for P1.

Java — Two-lock deadlock demonstration

// Classic two-lock deadlock: Thread A locks L1 then L2,
// Thread B locks L2 then L1 — circular wait guaranteed.
Object L1 = new Object();
Object L2 = new Object();

Thread threadA = new Thread(() -> {
    synchronized (L1) {                        // holds L1
        System.out.println("A: acquired L1");
        try { Thread.sleep(50); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        synchronized (L2) {                    // waits for L2
            System.out.println("A: acquired L2");
        }
    }
}, "Thread-A");

Thread threadB = new Thread(() -> {
    synchronized (L2) {                        // holds L2
        System.out.println("B: acquired L2");
        try { Thread.sleep(50); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        synchronized (L1) {                    // waits for L1 → DEADLOCK
            System.out.println("B: acquired L1");
        }
    }
}, "Thread-B");

threadA.start();
threadB.start();
threadA.join();
threadB.join();
// Program hangs — both threads blocked forever

Detecting Deadlock Programmatically

Java's ThreadMXBean can detect deadlocked threads at runtime. A thread dump (jstack) also prints "Found one Java-level deadlock" and shows the cycle. This is invaluable in production diagnosis.

Java — ThreadMXBean deadlock detection

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

ThreadMXBean tmx = ManagementFactory.getThreadMXBean();

// Detect deadlocked threads (synchronized blocks / ReentrantLock)
long[] deadlockedIds = tmx.findDeadlockedThreads();

if (deadlockedIds != null) {
    ThreadInfo[] infos = tmx.getThreadInfo(deadlockedIds, true, true);
    System.out.println("DEADLOCK DETECTED involving " + deadlockedIds.length + " threads:");
    for (ThreadInfo info : infos) {
        System.out.println("  Thread: " + info.getThreadName());
        System.out.println("  State:  " + info.getThreadState());
        System.out.println("  Waiting to lock: " + info.getLockName());
        System.out.println("  Lock held by:    " + info.getLockOwnerName());
    }
} else {
    System.out.println("No deadlock detected.");
}

// Thread states useful for manual inspection:
// Thread.State.BLOCKED  — waiting to enter synchronized block
// Thread.State.WAITING  — waiting on Object.wait() / LockSupport.park()

Key Points to Remember

1All four Coffman conditions must hold simultaneously; removing any one prevents deadlock.
2Mutual Exclusion is often unavoidable for inherently non-shareable resources like write locks.
3Hold and Wait can be broken by requiring processes to request all resources upfront or release existing ones before requesting new ones.
4Circular Wait is the easiest condition to break in practice: enforce a global total ordering on lock acquisition.
5Java's jstack and ThreadMXBean.findDeadlockedThreads() are the primary tools for diagnosing deadlocks in production.
6A deadlock differs from a livelock (threads active but making no progress) and starvation (one thread indefinitely delayed).

Interview Questions

What are the four necessary conditions for deadlock? Must all four be present?

EasyAmazon

How would you break the circular wait condition in a system with multiple database locks?

MediumGoogle

You see a Java service hang in production with 100% blocked threads. Walk me through your diagnosis.

HardUber

Why is mutual exclusion considered the hardest Coffman condition to eliminate?

MediumMicrosoft

Ask Aria about Deadlock: Four Necessary Conditions

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Dining Philosophers Problem

Resource Allocation Graph