Lesson 3 · Synchronization and deadlocks

Deadlocks

Deadlock is a cycle of waiting where every participant holds something another needs. It requires four conditions simultaneously, which is also the good news — break any single one and deadlock becomes impossible.

The Four Coffman Conditions

Deadlock in OS terms — deadlock in an operating system — occurs when a set of processes are each waiting for a resource held by another in the set, so none can ever proceed. Discussions of the types of deadlock in OS courses all reduce to this one definition, because Coffman showed in 1971 that four conditions must hold simultaneously — which is the key structural fact, because it means eliminating any one makes deadlock impossible.

Mutual exclusion: at least one resource is non-shareable. A read-only file causes no deadlock; an exclusive lock can. Hold and wait: a process holds one resource while waiting for another. Acquiring everything at once, or nothing, breaks this.

No preemption: a resource cannot be forcibly taken from its holder, only released voluntarily. Memory pages can be preempted by swapping them out, which is why memory rarely deadlocks; a mutex cannot be, which is why locks do.

Circular wait: a closed chain exists where each process waits for the next. The diagram on this page shows the minimal case — two processes, two locks, each holding what the other wants. This is the condition real systems attack, because the other three are usually inherent to the resources involved.

All four must hold at once — each row names the attack that removes it
Condition	Means	How to break it	Practical?
Mutual exclusion	A resource cannot be shared	Make resources shareable or read-only	Rarely — often inherent
Hold and wait	Holds one while requesting another	Acquire everything at once, or nothing	Hurts concurrency badly
No preemption	Cannot be taken from its holder	`trylock`, release and retry with backoff	Yes, needs backoff
Circular wait	A closed chain of waiting	Impose a global lock order	Yes — the standard fix

Mutual exclusion — the resource cannot be shared
Hold and wait — holding one while requesting another
No preemption — it cannot be taken away
Circular wait — a closed chain of waiting

Resource Allocation Graphs

A resource allocation graph makes the situation visible. Processes are circles, resources are squares, an assignment edge runs from resource to process (it holds this), and a request edge runs from process to resource (it wants this).

The rule is precise and worth stating carefully. If every resource type has exactly one instance, then a cycle in the graph means deadlock, full stop. If resource types have multiple instances, a cycle is necessary but not sufficient — the cycle may resolve when some other holder of that type releases its instance.

This is why detection is more expensive than drawing a picture suggests. With multiple instances you need an algorithm that repeatedly finds a process whose remaining requests can be satisfied from what is currently available, grants it, and reclaims everything it held — deadlock exists precisely when no such sequence completes.

The graph is also the fastest way to diagnose a hung system by hand. Dump the lock state, note who holds what and who waits on what, and look for the cycle. Java thread dumps and gdb's thread backtraces exist largely to let you do exactly this.

Assignment edge: resource → process. Request edge: process → resource
Single instance: a cycle is deadlock
Multiple instances: a cycle is necessary, not sufficient
Thread dumps exist so you can find the cycle by hand

Key reference

Terms, operations, and practical uses

Coffman conditions

Mutual exclusionAt least one resource cannot be shared.
Hold and waitHolding one resource while requesting another.
No preemptionThe resource cannot be taken away, only released.
Circular waitA closed chain of processes each waiting on the next.

Modelling

Assignment edgeResource to process — this one holds it.
Request edgeProcess to resource — this one wants it.
Single instanceA cycle in the graph is deadlock.
Multiple instancesA cycle is necessary but not sufficient.

Handling it

Lock orderingBreaks circular wait, costs nothing at runtime.
trylockBreaks hold-and-wait; needs backoff or it livelocks.
Banker's algorithmExact avoidance, needs maxima declared up front.
DetectionLet it happen, find the cycle, abort a victim.

Code example

The same two threads, two lock orders

# Two threads, two locks. The only difference between the runs is the ORDER
# locks are requested in -- which is the whole fix for circular wait.
# Steps are interleaved one at a time, because a deadlock needs both threads
# to hold something before either asks for the second lock.
def run(order_a, order_b):
    held, wants = {}, {}
    threads = [("P1", order_a, 0), ("P2", order_b, 0)]
    progress = True
    while progress:
        progress = False
        for i, (who, order, at) in enumerate(threads):
            if at >= len(order) or who in wants:
                continue                       # finished, or already blocked
            lock = order[at]
            if held.get(lock) in (None, who):
                held[lock] = who               # acquired
                threads[i] = (who, order, at + 1)
                progress = True
            else:
                wants[who] = lock              # blocked: another thread holds it
    if len(wants) == 2:
        p1, p2 = wants["P1"], wants["P2"]
        if held[p1] == "P2" and held[p2] == "P1":
            return f"deadlock detected (cycle P1->{p1}->P2->{p2})"
    return "both finished"

bad = run(["A", "B"], ["B", "A"])    # opposite orders -- a cycle can form
good = run(["A", "B"], ["A", "B"])   # one global order -- no cycle possible
print(f"unordered: {bad} | ordered: {good}")

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
// Two threads, two locks. The only difference between the runs is the ORDER
// locks are requested in -- the whole fix for circular wait. Steps interleave
// one at a time, because deadlock needs both to hold something first.
string run(vector<string> orderA, vector<string> orderB) {
    map<string, string> held, wants;
    vector<string> names = {"P1", "P2"};
    vector<vector<string>> orders = {orderA, orderB};
    vector<size_t> at = {0, 0};
    bool progress = true;
    while (progress) {
        progress = false;
        for (int i = 0; i < 2; i++) {
            if (at[i] >= orders[i].size() || wants.count(names[i])) continue;
            string lock = orders[i][at[i]];
            if (!held.count(lock) || held[lock] == names[i]) {
                held[lock] = names[i]; // acquired
                at[i]++;
                progress = true;
            } else {
                wants[names[i]] = lock; // blocked: another holds it
            }
        }
    }
    if (wants.size() == 2) {
        string p1 = wants["P1"], p2 = wants["P2"];
        if (held[p1] == "P2" && held[p2] == "P1")
        return "deadlock detected (cycle P1->" + p1 + "->P2->" + p2 + ")";
    }
    return "both finished";
}
int main() {
    string bad = run({"A", "B"}, {"B", "A"}); // opposite orders
    string good = run({"A", "B"}, {"A", "B"}); // one global order
    cout << "unordered: " << bad << " | ordered: " << good << "\n";
}

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
class Main {
    // Two threads, two locks. The only difference between the runs is the
    // ORDER locks are requested in -- the whole fix for circular wait.
    // Steps interleave one at a time, because deadlock needs both threads
    // to hold something before either asks for its second lock.
    static String run(List<String> orderA, List<String> orderB) {
        Map<String, String> held = new LinkedHashMap<>();
        Map<String, String> wants = new LinkedHashMap<>();
        String[] names = {"P1", "P2"};
        List<List<String>> orders = List.of(orderA, orderB);
        int[] at = {0, 0};
        boolean progress = true;
        while (progress) {
            progress = false;
            for (int i = 0; i < 2; i++) {
                if (at[i] >= orders.get(i).size() || wants.containsKey(names[i])) continue;
                String lock = orders.get(i).get(at[i]);
                if (!held.containsKey(lock) || held.get(lock).equals(names[i])) {
                    held.put(lock, names[i]); // acquired
                    at[i]++;
                    progress = true;
                } else {
                    wants.put(names[i], lock); // blocked: another holds it
                }
            }
        }
        if (wants.size() == 2) {
            String p1 = wants.get("P1"), p2 = wants.get("P2");
            if (held.get(p1).equals("P2") && held.get(p2).equals("P1"))
            return "deadlock detected (cycle P1->" + p1 + "->P2->" + p2 + ")";
        }
        return "both finished";
    }
    public static void main(String[] args) {
        String bad = run(List.of("A", "B"), List.of("B", "A"));
        String good = run(List.of("A", "B"), List.of("A", "B"));
        System.out.println("unordered: " + bad + " | ordered: " + good);
    }
}

InputP1 and P2 each need locks A and B

Outputunordered: deadlock detected (cycle P1->B->P2->A) | ordered: both finished

Example

Run the example step by step

Output

Prevention: Break One Condition

Prevention structurally eliminates a condition so deadlock cannot arise. Attacking mutual exclusion is rarely possible — some resources genuinely cannot be shared — though read-write locks and immutable data reduce the exposure.

Attacking hold and wait means acquiring every resource at once, before starting. This works and is used in database systems, but it hurts concurrency badly: a process holds everything for its whole run, and it must know its full requirements in advance. The variant is to release everything before requesting anything new, which risks livelock.

Attacking no preemption means taking resources back. pthread_mutex_trylock returns immediately rather than blocking, so a process that cannot get the second lock releases the first and retries. Effective, but needs backoff — otherwise two processes retry in lockstep forever, which is livelock rather than progress.

Attacking circular wait is the one everybody actually uses: impose a global lock ordering and require that locks are always acquired in that order. If every thread takes lock A before lock B, no cycle can form. It costs nothing at runtime, needs no bookkeeping, and is enforced by convention plus tooling — Linux's lockdep validates lock ordering at runtime and reports violations before they deadlock in production.

Hold-and-wait: acquire everything up front, at a concurrency cost
No-preemption: trylock and release, with backoff to avoid livelock
Circular wait: a global lock order — the practical answer
lockdep catches ordering violations before they bite

Avoidance, Detection, and What Real Systems Do

Avoidance allows the conditions but refuses any allocation that could lead to deadlock. Banker's algorithm does this by requiring each process to declare its maximum resource needs up front, then granting a request only if the resulting state is safe — meaning some ordering exists in which every process can still finish.

It is exact and almost never used. Declaring maximum needs in advance is unrealistic for general programs, the check is O(n²m) on every allocation, and the number of processes and resources must be known. It appears in exams far more often than in kernels.

Detection and recovery takes the opposite stance: let deadlock happen, notice it, and fix it. Recovery means killing a process, or rolling one back to a checkpoint and preempting its resources. Databases do this well — they detect wait-for cycles, pick a victim by cost, abort that transaction, and let the application retry. Because transactions are already atomic, the rollback is free.

General-purpose operating systems mostly do none of the above — the so-called ostrich algorithm. Deadlock is rare enough in practice, and the prevention machinery expensive enough, that Linux and Windows simply do not guard the general case, leaving it to lock ordering in kernel code and to the developer in user code. That is a deliberate engineering judgement, not an oversight.

The four strategies, and who actually uses each
Strategy	When it acts	Cost	Used by
Prevention	Before — by design	Concurrency, or ordering discipline	Kernel and application code
Avoidance	At each allocation	O(n²m) per request, needs declared maxima	Almost nobody
Detection and recovery	After it happens	A cycle search, then abort a victim	Databases
Ignore it	Never	Zero, until it happens	Linux, Windows

Banker's algorithm is exact, expensive, and needs declared maxima
Databases detect cycles and abort a victim transaction
Rollback is cheap when the work is already transactional
General OSes ignore it deliberately and rely on lock ordering

Livelock, Starvation, and What Deadlock Is Not

Livelock looks worse than deadlock because the system appears busy. Threads are actively executing, responding to each other, and making no progress — two people stepping aside in a corridor, repeatedly and symmetrically. It typically arises from naive deadlock recovery: both threads detect contention, both release, both retry, both collide again.

The fix is asymmetry. Randomised backoff breaks the symmetry that keeps them synchronised, which is the same reason Ethernet uses exponential backoff on collisions.

Starvation is a single process never getting a resource while others proceed. Unlike deadlock nothing is stuck — the system makes progress, just not for this one. Priority scheduling without aging causes it, and so does an unfair lock that keeps handing off to whichever thread happens to be running.

Distinguishing them matters diagnostically. Deadlocked threads are blocked and consume no CPU. Livelocked threads burn CPU at full rate. A starved thread is blocked while the system throughput looks fine. Seeing 100% CPU with no work completing points at livelock; seeing idle CPU with nothing completing points at deadlock.

Livelock: full CPU, zero progress — fix with randomised backoff
Starvation: one loser while the system progresses normally
Deadlocked threads use no CPU; livelocked threads use all of it
The CPU graph tells you which one you have