Deadlock is a situation where two or more threads permanently block each other, each waiting for a resource held by another. Unlike normal resource competition (where a thread simply waits for some time), deadlock is a complete standstill that will not resolve without external intervention.

---

Junior Level

Basic Understanding

Deadlock is not a coincidence — it’s the result of a mathematical combination of factors. In 1971, Edward Coffman formulated 4 conditions that must hold SIMULTANEOUSLY for deadlock to occur. If at least one condition is violated — deadlock is impossible.

Coffman’s 4 Conditions

#	Condition	Simple Explanation
1	Mutual Exclusion	A resource can be occupied by only one thread. Why it matters: if the resource is shared (e.g., read-only data), multiple threads can work simultaneously without waiting
2	Hold and Wait	A thread already holds one resource and requests another, without releasing the first. This creates a “blocking point” — the thread doesn’t move forward but also doesn’t free what it already has
3	No Preemption	The JVM or OS cannot forcibly take a resource from a thread. synchronized, for example, has no timeout — if a thread acquired a lock, only it can release it
4	Circular Wait	Threads wait for each other in a circle: T1 waits for a resource from T2, T2 waits for a resource from T1. Without a cycle — deadlock is impossible

Example

// Thread 1:
synchronized(resourceA) {   // Acquires resourceA — Mutual Exclusion: no one else enters
    synchronized(resourceB) { // Holds A, waits for B — Hold and Wait activated
        // ...
    }
}

// Thread 2:
synchronized(resourceB) {   // Acquires resourceB — Mutual Exclusion: no one else enters
    synchronized(resourceA) { // Holds B, waits for A — Hold and Wait activated
        // ...
    }
}

// No Preemption: synchronized cannot be "taken away" — only the owner releases it
// Circular Wait: Thread 1 waits for B (held by Thread 2), Thread 2 waits for A (held by Thread 1) — CYCLE!
// All 4 conditions met = DEADLOCK

Important Fact

Theoretically, if you violate at least one condition — deadlock is impossible. In practice, complete violation is not always achievable: for example, Mutual Exclusion cannot be violated for file writes or counter updates. Therefore, the strategy depends on the resource type.

---

When NOT to Study Coffman Conditions

• You’re writing a single-threaded application — deadlock is impossible without multiple threads
• You only use immutable data and functional style — no shared mutable state means no locks
• Your team has fully moved to the actor model (Akka) — actors don’t use shared locks by design

But in real Java projects, there’s always at least one synchronized or ReentrantLock, so understanding these conditions is useful for any Middle+ developer.

---

Deadlock vs Livelock vs Starvation

These concepts are often confused:

Problem	What Happens	Example
Deadlock	Threads permanently block each other	T1 waits for T2, T2 waits for T1 — complete standstill
Livelock	Threads are active but make no progress	Two people in a corridor trying to pass, both step in the same direction
Starvation	A thread never gets the resource	Low-priority thread always waits for high-priority ones

Deadlock is the most dangerous because it requires a JVM restart to resolve. Livelock and starvation can (theoretically) resolve themselves.

---

Middle Level

Detailed Breakdown of Conditions

1. Mutual Exclusion

A resource can be occupied by only one thread at a time.

// Mutual Exclusion: synchronized
synchronized(lock) {
    // Only one thread here
}

// NO Mutual Exclusion: ReadWriteLock.readLock()
ReadWriteLock rwLock = new ReentrantReadWriteLock();
rwLock.readLock().lock();
// Multiple threads can read simultaneously → deadlock on readLock is impossible!

How to violate: Use shared-access resources (ReadLock, Atomic classes, lock-free structures).

2. Hold and Wait

A thread already holds one resource and requests additional ones.

// Hold and Wait:
synchronized(lockA) {
    // Holding lockA
    synchronized(lockB) { // Requesting lockB — HOLD AND WAIT
        // ...
    }
}

How to violate: Request all resources “in one batch”:

// Violation: request all or nothing
if (lockA.tryLock() && lockB.tryLock()) {
    try {
        // Both acquired — no Hold and Wait
    } finally {
        lockB.unlock();
        lockA.unlock();
    }
} else {
    // Failed — we hold nothing
    lockA.unlock(); // Release if we managed to acquire
}

3. No Preemption

A resource can only be released voluntarily by its owner.

// No Preemption: synchronized
synchronized(lock) {
    // JVM cannot take the lock from the thread
}

// Violation: ReentrantLock can be "taken" via interrupt
lock.lockInterruptibly();
try {
    // Thread can be interrupted → lock will be released
} finally {
    lock.unlock();
}

How to violate: Use lockInterruptibly() or tryLock(timeout).

4. Circular Wait

There is a circular chain: T1 waits for a resource from T2, T2 from T3, …, Tn from T1.

Thread 1 ──waits lockB──→ Thread 2
  ▲                         │
  │                         │
  └────waits lockA──────────┘

How to violate: Introduce a strict lock ordering:

// Always acquire in ascending ID order
void safeOperation(Resource r1, Resource r2) {
    Resource first = r1.id < r2.id ? r1 : r2;
    Resource second = r1.id < r2.id ? r2 : r1;

    synchronized(first) {
        synchronized(second) {
            // Impossible to create a cycle!
        }
    }
}

Strategy for Violating Conditions

Condition	How to Violate	Cost
Mutual Exclusion	Lock-free, ReadLock	Medium
Hold and Wait	tryLock() all or nothing	Low
No Preemption	lockInterruptibly()	Low
Circular Wait	Lock Ordering	Lowest

---

Senior Level

Under the Hood: Resource Allocation Graph (RAG)

RAG — a deadlock analysis tool:

Processes (P) ───→ Resources (R): request
Resources (R) ───→ Processes (P): allocation

P1 ──request──→ R2 ──allocated──→ P2
▲                                  │
│                                  │
R1 ◄──allocated── P1 ──request──→ P2
         │                          │
         └──────── R3 ◄─────────────┘

CYCLE in RAG = Potential DEADLOCK

Dynamic Resource Allocation

In complex systems, resources are created dynamically (DB rows, objects). How to define ordering?

// Hashing resource names for ordering
void safeOperation(Resource r1, Resource r2) {
    int h1 = System.identityHashCode(r1);
    int h2 = System.identityHashCode(r2);

    // Always in hash order
    if (h1 < h2) {
        synchronized(r1) { synchronized(r2) { /* ... */ } }
    } else if (h1 > h2) {
        synchronized(r2) { synchronized(r1) { /* ... */ } }
    } else {
        // Hash collision — global tie-breaker
        synchronized(globalTieBreaker) {
            synchronized(r1) { synchronized(r2) { /* ... */ } }
        }
    }
}

Lock-free as Violation of Mutual Exclusion

// Instead of synchronized (Mutual Exclusion):
synchronized(counter) { count++; }

// Use Atomic (no exclusive ownership):
AtomicInteger counter = new AtomicInteger(0);
counter.incrementAndGet();
// No lock → no Mutual Exclusion → no deadlock!

Try-Lock as Violation of Hold and Wait

ReentrantLock lock1 = new ReentrantLock();
ReentrantLock lock2 = new ReentrantLock();

public void safeOperation() {
    while (true) {
        if (lock1.tryLock()) {
            try {
                if (lock2.tryLock()) {
                    try {
                        // Both acquired — do the work
                        return;
                    } finally {
                        lock2.unlock();
                    }
                }
            } finally {
                lock1.unlock(); // Release the first — violates Hold and Wait
            }
        }
        // Failed — pause and retry
        Thread.sleep(10);
    }
}

Diagnostics

Thread Dump Analysis

jstack <pid>

"Thread-1" BLOCKED
  - waiting to lock <0x000000076af0c8d0> (Resource B)
  - locked <0x000000076af0c8e0> (Resource A)

"Thread-2" BLOCKED
  - waiting to lock <0x000000076af0c8e0> (Resource A)
  - locked <0x000000076af0c8d0> (Resource B)

By the <0x000...> addresses, you can find the specific objects in the heap via MAT.

False Deadlock

Sometimes monitoring tools can mistakenly flag a long-running operation as deadlock:

"Deadlock" symptoms:
- Threads BLOCKED for a long time
- No progress

But it is NOT deadlock if:
- Heavy SQL query (minutes)
- GC pause (can be long)
- I/O timeout

Programmatic Detection

public class DeadlockDetector {
    public static Optional<DeadlockInfo> detect() {
        ThreadMXBean mxBean = ManagementFactory.getThreadMXBean();
        long[] ids = mxBean.findDeadlockedThreads();

        if (ids != null) {
            return Optional.of(new DeadlockInfo(ids, mxBean));
        }
        return Optional.empty();
    }

    // Warning: expensive operation — don't call frequently!
}

Best Practices

1. Lock Ordering — the most reliable method (violates Circular Wait)
2. tryLock(timeout) — violates Hold and Wait + No Preemption
3. Lock-free structures — violates Mutual Exclusion
4. One global lock — violates Circular Wait (but reduces parallelism)
5. Thread-specific resources — sharding, independent data
6. Monitor via ThreadMXBean — but not too often
7. Analyze RAG during design — prevent at the architecture level

---

Interview Cheat Sheet

Must know:

• 4 Coffman conditions: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait — all must hold SIMULTANEOUSLY
• Violating at least one condition makes deadlock impossible
• Lock Ordering — violates Circular Wait — the most reliable prevention method
• TryLock violates Hold and Wait, lockInterruptibly — No Preemption
• For diagnostics: jstack <pid>, ThreadMXBean.findDeadlockedThreads()
• Deadlock vs Livelock vs Starvation: deadlock — complete standstill, livelock — activity without progress, starvation — thread never gets the resource
• Resource Allocation Graph (RAG): a cycle in the graph = potential deadlock

Frequent follow-up questions:

• Can you violate Mutual Exclusion? — Yes, via lock-free structures (Atomic, ConcurrentHashMap) or ReadWriteLock.readLock()
• How to detect deadlock in production? — ThreadMXBean.findDeadlockedThreads(), jstack, JFR events, monitoring BLOCKED threads
• What is a false deadlock? — When monitoring tools confuse a long operation (heavy SQL, GC pause) with deadlock
• How does a hashCode collision affect Lock Ordering? — When identityHashCode of two objects matches, a global tie-breaker (additional lock) is needed

Red flags (DO NOT say):

• “Deadlock is a random problem” — no, it’s a deterministic consequence of 4 conditions
• “synchronized can be interrupted via interrupt()” — synchronized does NOT support interrupt, need ReentrantLock
• “Deadlock can be handled inside the JVM without restart” — in most cases, deadlock requires a JVM restart
• “If you use ReentrantLock instead of synchronized — deadlock is impossible” — ReentrantLock only provides more tools, but deadlock is still possible with misuse

Related topics:

• [[20. How to prevent deadlock]]
• [[21. What is race condition]]
• [[22. How to avoid race condition]]
• [[27. What is the difference between Thread and Runnable]]
• [[28. What are Callable and Future]]