Prevention & Avoidance (Lock Ordering, Banker's Algorithm)

Language-specific mechanics: Concurrency Language Manual →

Prevention vs. avoidance: two different bets

Both strategies exist to guarantee deadlock never happens, but they make opposite trade-offs between simplicity and flexibility:

Prevention passes a permanent, static "law" against one of the four Coffman conditions. Every legal code path is unconditionally deadlock-free, at the cost of sometimes being more restrictive or less efficient than necessary.
Avoidance makes no static rule at all. Instead, threads declare their maximum resource needs up front, and a request manager grants each individual request only if doing so leaves the system in a state from which some ordering of completions is still guaranteed possible. It's more flexible than prevention, but requires threads to know (and honestly declare) their worst-case resource usage in advance — a strong assumption that limits how often avoidance is used outside of specialized systems.

Both are strictly more conservative than detection & recovery (the approach from the previous subtopic): prevention and avoidance both refuse to ever let a deadlock happen, whereas detection lets the system run optimistically and only pays a cost when things actually go wrong.

Prevention: attack one of the four conditions

Revisiting the four conditions with prevention in mind:

Condition attacked	Typical technique	Cost
Mutual exclusion	Make the resource shareable (read-write locks, immutable data)	Only works when the resource genuinely tolerates concurrent access
Hold-and-wait	Acquire all needed locks atomically up front, or release everything before requesting more	Requires knowing all locks needed in advance; can reduce concurrency
No preemption	Use `tryLock` with a timeout; release everything held and retry from scratch on failure	Wasted work on retries; needs idempotent or rollback-safe critical sections
Circular wait	Impose a single global total order on lock acquisition	The dominant real-world technique — see below

Global lock ordering is the one to know cold. If every thread that needs multiple locks always acquires them in the same fixed order (e.g., by comparing lock addresses, or an assigned numeric ID), a cycle in the wait-for graph becomes impossible by construction: a cycle would require some thread to acquire a "lower-ordered" lock while holding a "higher-ordered" one, which the discipline forbids. This is exactly the fix for the two-lock example from the previous subtopic — if both threads acquire A before B, whichever thread gets A first is guaranteed to also get B (nobody else can be holding it), finish, and release both, and the second thread simply waits its turn instead of deadlocking.

The catch: a global order turns locks into part of every function's public contract. If module M1 must call into module M2 while holding a lock, and M2's internals need to acquire a lock that comes "before" M1's in the agreed order, you have a structural conflict that no amount of careful coding fixes — you have to restructure which code holds which lock, or introduce lock-free hand-off. Real production kernels (e.g., xv6, Linux) maintain these orderings as explicit, documented conventions precisely because violating them is a common and hard-to-test source of production deadlocks.

One more subtlety worth naming: a mandatory acquisition order can itself create a form of unfairness — if a thread must acquire resources "23, 24, 25, ... 88, 89" before finally needing resource "0," it may be forced to release and re-acquire a long chain repeatedly. Prevention buys you a deadlock-free guarantee, not a fairness guarantee; that distinction becomes important in the next subtopic.

Avoidance: the Banker's Algorithm

Where prevention imposes a rule on how locks are acquired, avoidance reasons about whether granting a specific request right now is safe, using more information: each thread's declared maximum demand for each resource type.

Safe state. A system is in a safe state if there exists at least one ordering of the remaining threads — a safe sequence — such that each thread, in turn, could obtain its full remaining maximum demand from currently-free resources plus what earlier threads in the sequence will release upon completing. If such a sequence exists, every thread is guaranteed to finish eventually, even in the worst case where every thread immediately asks for its entire declared maximum. If no such sequence exists, the state is unsafe — not necessarily deadlocked yet, but one bad request away from it.

The Banker's Algorithm (Dijkstra) operationalizes this with three tracked quantities per resource type: Available (free instances), Allocation[i] (currently held by thread i), and Need[i] (still required by thread i, i.e. Max[i] - Allocation[i]). Its safety algorithm simulates completion in the best possible order:

function isSafe(available, allocation, need):
    work = copy(available)
    finished = set of threads with Need == 0 already, false for the rest

    repeat:
        progressed = false
        for each thread i where finished[i] == false:
            if need[i] <= work:                  # thread i could finish right now
                work += allocation[i]            # pretend it finishes and releases
                finished[i] = true
                progressed = true
    until not progressed

    return all(finished)                          # true => safe state (and a safe sequence exists)

The resource-request algorithm wraps this: when thread i requests some resources, the system tentatively grants them, re-runs the safety check on the resulting hypothetical state, and either commits the grant (if still safe) or rolls it back and makes the thread wait (if not) — even though enough resources might be physically free to satisfy the request right now. That last point is the crux of avoidance and a favorite interview trap: a request can be denied even when it could be immediately satisfied, purely because granting it would leave no safe path forward for everyone else.

Prevention vs. avoidance vs. detection: the trade-off to say out loud

Approach	Guarantee	Assumption required	Downside
Prevention	Deadlock structurally impossible	None beyond following the rule	Rigid; can be inefficient or awkward to retrofit
Avoidance	Deadlock never entered	Threads pre-declare max resource usage	Conservative — rejects some requests that would've been fine
Detection & recovery	Deadlock allowed, then cleaned up	Ability to abort/preempt a thread	Rollback cost; wrong victim choice risks starvation

In practice, most production systems lean on prevention (global lock ordering, tryLock timeouts) because avoidance's requirement — that every thread accurately declares its worst-case resource needs before it starts — is rarely realistic outside of constrained domains like static resource schedulers or embedded systems. Banker's Algorithm shows up far more often as an interview/exam topic than as literal production code, but the underlying idea — "only grant a request if the resulting state is still recoverable" — reappears constantly in capacity planning and admission control.

Pitfalls and interview gotchas

Confusing "unsafe" with "deadlocked." An unsafe state means no safe sequence can be proven to exist right now — it does not mean deadlock is inevitable. Threads might still finish early or never request their full declared maximum. Avoidance is conservative precisely because it refuses to gamble on that.
Forgetting that Banker's Algorithm needs the maximum claim in advance. If you can't ask "what's the most resources this thread will ever hold at once?" before it starts, you can't run this algorithm at all — this is its single biggest practical limitation and worth naming unprompted.
Applying single-instance cycle detection where multiple instances exist. With multiple interchangeable instances of a resource type, a cycle in the naive wait-for graph doesn't automatically imply deadlock — you need the fuller safety-algorithm-style reasoning (or a proper resource-allocation-graph reduction), not simple cycle detection.
Treating "acquire locks in address order" as a complete solution. It solves circular wait for locks you can compare, but says nothing about hold-and-wait across calls into other modules, or about resources that aren't lock objects at all (file handles, connection-pool slots, distributed leases).

The circular-wait fix for the previous subtopic's repro: every caller funnels through one helper that always acquires lockA before lockB, so a cycle in the wait-for graph is no longer constructible.

var lockA, lockB sync.Mutex // order 1, order 2

// Every caller funnels through here, so lockA is always acquired before lockB.
func withBothLocks(work func()) {
    lockA.Lock()
    defer lockA.Unlock()
    lockB.Lock()
    defer lockB.Unlock() // LIFO: B released before A, matching acquisition order
    work()
}

A single chokepoint is the only place that acquires both mutexes, always in the same order, so a wait-for cycle is no longer constructible. Nested defer Unlock() runs LIFO, releasing B then A. Don't copy these mutexes, and don't lock lockA again from work — Mutex is not reentrant.

The safety algorithm from the theory above: simulate completions in the best possible order and check whether every process can eventually finish. need[i][j] is assumed precomputed as max[i][j] - allocation[i][j].

// True if available plus some release order can satisfy every process's need.
func isSafe(available []int, allocation, need [][]int) bool {
    n, m := len(allocation), len(available)
    work := append([]int(nil), available...)
    finished := make([]bool, n)

    for round := 0; round < n; round++ {
        progressed := false
        for i := 0; i < n; i++ {
            if finished[i] {
                continue
            }
            canFinish := true
            for j := 0; j < m; j++ {
                if need[i][j] > work[j] {
                    canFinish = false
                    break
                }
            }
            if canFinish {
                for j := 0; j < m; j++ {
                    work[j] += allocation[i][j]
                }
                finished[i] = true
                progressed = true
            }
        }
        if !progressed {
            break
        }
    }
    for _, f := range finished {
        if !f {
            return false
        }
    }
    return true
}

work tracks resources freed by pretending finished processes have completed and released everything — exactly the simulation in the theory's safety algorithm. Pure numeric code; no goroutines involved.

Prevention & Avoidance (Lock Ordering, Banker's Algorithm)

Prevention vs. avoidance: two different bets

Prevention: attack one of the four conditions

Avoidance: the Banker's Algorithm

Prevention vs. avoidance vs. detection: the trade-off to say out loud

Pitfalls and interview gotchas

Fixing the Two-Lock Deadlock with a Global Lock Order

Banker's Algorithm — Safety Check

Further Resources (Optional)