Deadlock: Four Conditions, and Which One You Actually Break

Two threads are stuck forever. Is that deadlock?

Not necessarily — and "they're waiting on each other" isn't a precise enough answer to build on. Naming it properly takes four conditions, all holding at the same time, and the useful follow-up is never what are they but which one would you break, and what does breaking it cost?

You already know what a mutex does: a thread that can't acquire one blocks and waits. That happens constantly in healthy systems — blocking is normal. Deadlock is a specific arrangement of blocking that no thread can ever escape. The gap between "blocked" and "deadlocked" is the whole topic.

One place that intuition misleads, though: "waiting forever" also describes starvation, and starvation is a different problem with a different fix. Settling that distinction is further down, because interviewers love it.

All four conditions have to hold at once

The load-bearing word is simultaneously. Deadlock requires all four at once, so removing any single one makes deadlock impossible. That isn't trivia — it's the entire prevention strategy, and it's why the four conditions are worth memorizing in the first place.

Notice that the first three are true of almost every mutex in every program you've written. The one that's usually optional is circular wait. Hold that thought.

The example you should be able to trace cold

Two threads, two mutexes, acquired in opposite order:

// Thread A                    // Thread B
lock(mutex1);                  lock(mutex2);
lock(mutex2);                  lock(mutex1);
// critical section            // critical section
unlock(mutex2);                unlock(mutex1);
unlock(mutex1);                unlock(mutex2);

Trace it as an interleaving, not as two programs:

1. Thread A acquires mutex1.
2. Thread B acquires mutex2.
3. Thread A requests mutex2 — held by B, so A blocks.
4. Thread B requests mutex1 — held by A, so B blocks.

Now check all four conditions: the mutexes are exclusive, each thread holds one while waiting for another, neither can be forced to release, and the wait chain closes into a cycle. All four hold, so this is deadlock rather than slow progress.

flowchart LR
    TA["Thread A"] -->|holds| M1["mutex1"]
    M1 -->|wanted by| TB["Thread B"]
    TB -->|holds| M2["mutex2"]
    M2 -->|wanted by| TA

The detail that makes this vicious in production: it's timing dependent. If Thread A finishes both acquisitions before B starts, everything works. The code can run correctly thousands of times and deadlock only under load, which is exactly when you can least afford it.

This isn't a contrived teaching example, either. The single most common real deadlock is its database cousin: two transactions updating the same two rows in opposite order. Transaction 1 updates row X then row Y; transaction 2 updates row Y then row X. Same shape, same cycle — which is why engines like InnoDB and Postgres ship with deadlock detection that kills one transaction and makes it the "victim," rather than trying to prevent the situation at all.

The trap: a cycle doesn't always prove deadlock

Here's where exam questions catch people. The rule most students carry is "cycle in the resource-allocation graph ⇒ deadlock." That's only true with one instance per resource type.

When a resource type has multiple instances, a cycle is necessary but not sufficient. The cycle can exist while some thread outside it holds a spare instance it's about to release, which breaks the chain without anyone intervening. So:

• One instance per type: cycle ⇔ deadlock
• Multiple instances per type: deadlock ⇒ cycle, but cycle ⇏ deadlock

The reason the wrong version is tempting is that every textbook diagram uses single-instance resources, because they're the ones that draw cleanly. The multi-instance case is the one that gets examined.

The second confusion worth settling is the three-way distinction, since "stuck" is used loosely for all of them:

Livelock is the one people forget. Two threads politely backing off and retrying in lockstep are consuming CPU, changing state constantly, and never blocking — so every "is anything blocked?" check says the system is healthy. It isn't.

The four responses, and what each one costs

What real systems actually choose is worth knowing, because the honest answer surprises people: Linux ignores it for most kernel resources — the "ostrich algorithm," on the reasoning that prevention machinery costs more than the rare hang. Databases detect and recover, since they already track lock waits and can roll a transaction back cleanly. Application code prevents, via lock ordering.

The mental model

Four conditions, all required at once. So prevention is always "break exactly one" — and the real question is which is cheapest to give up.

Rank them by what they cost you:

• Mutual exclusion — can't drop it. It's the reason the lock exists.
• No preemption — needs rollback. Databases can do this; your application usually can't.
• Hold and wait — possible, by acquiring everything at once, but it serializes work you wanted concurrent.
• Circular wait — cheap. A global ordering convention, no runtime cost.

That ranking is the whole thing compressed. If you can redraw the two-thread cycle and recite why circular wait is the cheap one to break, you can reconstruct prevention, explain why databases chose detection instead, and answer the design question — without memorizing anything else.

If you're asked this

In one line: Deadlock is four conditions holding simultaneously — mutual exclusion, hold and wait, no preemption, and circular wait — so breaking any one of them prevents it.

If pushed for detail, in order: (1) name the four and stress that they're simultaneous; (2) give the two-mutexes-opposite-order trace and point out it's timing dependent; (3) say which condition you'd break and why circular wait is cheapest.

The follow-up to expect: "Does a cycle always mean deadlock?" — no, only with one instance per resource type. Or: "How does this differ from starvation?" — deadlock has a cycle and never resolves; starvation is a fairness problem in a thread that could otherwise run.

The same material gets tested three different ways. An MCQ asks you to spot which condition is missing. A numerical gives you an allocation matrix and asks whether the state is safe. An interview asks you to design around it — and that one is answered with lock ordering, not with Banker's algorithm.

Quick recall

• Four conditions, all simultaneous: mutual exclusion, hold and wait, no preemption, circular wait. Break any one and deadlock is impossible.
• The first three are true of nearly every mutex; circular wait is the one that's optional, which is why lock ordering is the standard fix.
• Cycle in the resource-allocation graph ⇒ deadlock only with one instance per resource type. Multiple instances: a cycle is necessary, not sufficient.
• Deadlock (cycle, permanent) ≠ starvation (no cycle, fairness, fixable by aging) ≠ livelock (not blocked at all, burning CPU).
• Linux largely ignores deadlock, databases detect and roll back a victim, application code prevents with lock ordering — three defensible answers to the same problem.