The Four Necessary Conditions & Detection

Language-specific mechanics: Concurrency Language Manual →

What deadlock actually is

Deadlock is what happens when synchronization succeeds too well: every thread involved is correctly respecting the locks it holds, and the system still stops making progress. The canonical shape is two threads and two locks, acquired in opposite orders:

Thread 1: acquire A, then acquire B
Thread 2: acquire B, then acquire A

If Thread 1 grabs A and Thread 2 grabs B at roughly the same time, Thread 1 now blocks waiting for B (held by Thread 2), and Thread 2 blocks waiting for A (held by Thread 1). Neither will ever release what it holds, because releasing happens after the code that's currently blocked. Nothing crashed, no exception was thrown, no invariant was violated — the program simply hangs forever. This is why deadlock is classified as a liveness bug rather than a safety bug: safety bugs mean something bad happened, liveness bugs mean nothing (good) ever happens.

This is the natural sequel to locks, semaphores, and condition variables: those tools fix races by making threads wait for each other, and deadlock is the failure mode you introduce the moment two or more threads can end up waiting for each other in a cycle.

The four Coffman conditions

For a deadlock to occur, four conditions — first formalized by Coffman, Elphick, and Shoshani in 1971 — must all hold simultaneously:

#	Condition	What it means
1	Mutual exclusion	At least one resource is held in a non-shareable mode — only one thread can hold it at a time.
2	Hold and wait	A thread holding at least one resource is simultaneously waiting to acquire additional resources held by others.
3	No preemption	A resource can only be released voluntarily by the thread holding it; the system cannot forcibly take it back.
4	Circular wait	There exists a cycle of threads `T1, T2, ..., Tn` where each `Ti` is waiting for a resource held by `T(i+1)`, and `Tn` is waiting for a resource held by `T1`.

In the two-lock example above: A and B are exclusively held (1), each thread holds one lock while waiting for the other (2), neither thread will be forced to give up its lock (3), and Thread1 → Thread2 → Thread1 forms a two-node cycle (4). All four are present, so the system deadlocks.

The key interview insight: all four, simultaneously

This is the single most important fact to internalize about deadlock, and the one interviewers most want to hear you say explicitly: removing any one of the four conditions makes deadlock structurally impossible, because the conditions are individually necessary and only jointly sufficient. This is exactly why prevention (the next subtopic) works at all — you don't need to solve deadlock in general, you just need to permanently violate one condition for a given code path.

Attack mutual exclusion: make the resource shareable (rarely possible — it's usually a property of the resource itself, like "only one thread can hold a write lock").
Attack hold-and-wait: require threads to request all resources they'll ever need up front, or to release everything before requesting more.
Attack no preemption: allow the system (or the thread itself, via tryLock-with-timeout) to forcibly reclaim a held resource.
Attack circular wait: impose a total order on resource acquisition — this is by far the most common and most practical fix in real systems, and is covered in depth in the next subtopic.

Note that circular wait implies hold-and-wait (each thread in the cycle is, by definition, holding one resource while waiting for another), so conditions 2 and 4 aren't fully independent — but treating all four as separate levers is still the standard framing, because each one suggests a genuinely different prevention strategy.

Detecting deadlock: the wait-for graph

If you aren't preventing or avoiding deadlock (the next subtopic), you need a way to notice it's happened. The standard model is a wait-for graph: each thread is a node, and a directed edge Ti → Tj means Ti is blocked waiting for a resource currently held by Tj. (This is a simplified version of a resource-allocation graph with the resource nodes collapsed out — valid when every resource type has exactly one instance.)

The central theorem is simple and powerful:

A deadlock exists if and only if the wait-for graph contains a cycle.

That single sentence is why this subtopic sits next to graph algorithms on this roadmap: detecting deadlock reduces exactly to cycle detection in a directed graph, which you can do with a DFS that tracks nodes currently on the recursion stack (the same "white/gray/black" coloring you'd use for detecting a cycle in any directed graph):

function hasCycle(graph):
    state = map(node -> UNVISITED) for all nodes
    for each node in graph:
        if state[node] == UNVISITED and dfs(node, graph, state):
            return true
    return false

function dfs(node, graph, state):
    state[node] = IN_PROGRESS
    for neighbor in graph.edgesFrom(node):
        if state[neighbor] == IN_PROGRESS:
            return true               # back edge -> cycle -> deadlock
        if state[neighbor] == UNVISITED and dfs(neighbor, graph, state):
            return true
    state[node] = DONE
    return false

This runs in O(V + E) — cheap enough that a database or a distributed lock manager can afford to re-run it periodically, but expensive enough (and disruptive enough, since you typically need to freeze allocation activity while you scan) that "detect and recover" systems have to be deliberate about when they scan: too often and you waste throughput on scans that usually find nothing; too rarely and a real deadlock sits unnoticed, silently eating threads.

Two caveats worth stating out loud in an interview:

This single-instance-per-resource-type version is exact: cycle ⟺ deadlock. The moment a resource type has multiple interchangeable instances (e.g., a pool of 5 database connections), a cycle in the naive graph no longer guarantees deadlock — you need the fuller reachability/reduction algorithm that the Banker's Algorithm's machinery is built on (next subtopic).
Once you've detected a cycle, recovery is its own hard problem: you must abort or preempt at least one thread in the cycle, and naive "always pick the lowest-numbered thread" policies can starve that thread across repeated deadlocks — a first taste of the starvation theme that closes out this topic.

Pitfalls and interview gotchas

Reciting the four conditions without the "why." Anyone can memorize "mutual exclusion, hold-and-wait, no preemption, circular wait." What separates a strong answer is immediately following up with "and breaking any single one prevents deadlock" — that's the insight the conditions exist to support.
Confusing necessary with sufficient for the general case. All four conditions being present guarantees deadlock only when there's an actual cycle of waiting; for multi-instance resources, you can have all four conditions and no deadlock, because there's enough slack in the resource counts for everyone to eventually finish. This is precisely the "safe state" idea the next subtopic formalizes.
Forgetting that a lock a thread already holds counts. A thread re-entering a non-reentrant lock it already owns is a degenerate one-node cycle — a common self-deadlock bug that's easy to miss when you're only thinking about multi-thread scenarios.
Treating detection as free. Building and scanning a wait-for graph has real cost and real synchronization overhead of its own (you need to atomically snapshot who's waiting on what); it is not a substitute for good lock discipline, only a safety net for when discipline fails.

Two threads acquiring the same two locks in opposite order — the canonical circular-wait setup from the theory above. The sleep just widens the race window so it reproduces reliably.

var lockA, lockB sync.Mutex
var wg sync.WaitGroup
wg.Add(2)

go func() {
    defer wg.Done()
    lockA.Lock()
    time.Sleep(50 * time.Millisecond) // widen the race window
    lockB.Lock() // holds A, waits for B
    lockB.Unlock()
    lockA.Unlock()
}()
go func() {
    defer wg.Done()
    lockB.Lock()
    time.Sleep(50 * time.Millisecond)
    lockA.Lock() // holds B, waits for A
    lockA.Unlock()
    lockB.Unlock()
}()
wg.Wait()

t1 holds lockA and blocks on lockB; t2 holds lockB and blocks on lockA — a two-node cycle. If these are the only goroutines, the runtime crashes with fatal error: all goroutines are asleep - deadlock! plus a dump; if anything else is runnable, it hangs silently. Mutexes are not reentrant, so a single goroutine locking the same mutex twice is the even simpler self-deadlock.

A minimal wait-for graph plus the same DFS-with-recursion-stack cycle check from the theory pseudocode. A real detector would populate waitsFor edges from actual lock-holder/lock-waiter records rather than by hand.

type WaitForGraph struct {
    edges map[string][]string // from -> nodes it waits on
}

func (g *WaitForGraph) WaitsFor(from, to string) {
    if g.edges == nil {
        g.edges = map[string][]string{}
    }
    g.edges[from] = append(g.edges[from], to)
}

func (g *WaitForGraph) HasDeadlock() bool {
    state := map[string]int{} // 0=unvisited, 1=inProgress, 2=done
    var dfs func(string) bool
    dfs = func(node string) bool {
        state[node] = 1
        for _, next := range g.edges[node] {
            switch state[next] {
            case 1:
                return true // back edge -> cycle
            case 0:
                if dfs(next) {
                    return true
                }
            }
        }
        state[node] = 2
        return false
    }
    for node := range g.edges {
        if state[node] == 0 && dfs(node) {
            return true
        }
    }
    return false
}

Same three-color DFS: state == 1 means on the current path, and hitting one again is the back edge that signals a cycle. Pure graph traversal — no goroutine involved — so this is as expressible in Go as anywhere else. The runtime's all-asleep detector is a different tool: it catches the fully stuck program, not an arbitrary wait-for subgraph.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Course ScheduleMedium!!!3/525m

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Find Eventual Safe StatesMedium!3/525m