Deadlocks: Prevention, Avoidance, Detection and Recovery

A deadlock at EdgeCampus

Two distributed training jobs, JA and JB, each need 6 GPUs (one per worker pod) on an 8-GPU edge cluster. Pods are created one by one and each pod grabs a GPU as soon as it is scheduled. After eight pods: JA holds 4 GPUs, JB holds 4, free GPUs = 0. Neither job can start (each needs 6), neither releases its GPUs (the pods are waiting for their siblings). The cluster is full and nothing runs — forever. With all-or-nothing allocation (gang scheduling), JA gets 6 GPUs, runs 10 minutes, releases them, and then JB runs: makespan 20 minutes.

The four necessary conditions (Coffman, 1971)

A deadlock can occur only if all four hold at the same time:

1. Mutual exclusion — a resource can be used by only one process at a time.
2. Hold and wait — a process holds resources while waiting for others.
3. No preemption — resources cannot be taken away; they are released voluntarily.
4. Circular wait — there is a cycle P1 → P2 → … → Pn → P1 where each waits for a resource held by the next.

Break any one and deadlock is impossible.

Resource-allocation graphs

Processes are circles, resource types are boxes with dots (instances). A request edge P → R means P waits for R; an assignment edge R → P means an instance of R is held by P.

• No cycle ⇒ no deadlock.
• Cycle and every resource has one instance ⇒ deadlock.
• Cycle with multi-instance resources ⇒ possibly deadlock — another process outside the cycle may release an instance and break it.

For single-instance resources, we can remove the resource nodes: a wait-for graph has an edge Pi → Pj when Pi waits for a resource held by Pj. Deadlock ⇔ the wait-for graph has a cycle, which can be found with a depth-first search in O(V + E).

Strategy 0: ignore it (the ostrich approach)

Linux and Windows do not prevent or detect deadlocks among user processes: deadlocks are rare, and prevention would be expensive and restrictive. Programmers are responsible (and use timeouts, watchdogs, restarts). Databases, by contrast, do detect deadlocks, because transactions deadlock frequently.

Strategy 1: prevention — break a condition

Resource ordering is the most practical: Linux kernel developers document lock orders, and the lockdep tool checks them at run time. In Java, "always lock the account with the smaller ID first" prevents transfer deadlocks (Lab 7.4).

Gang scheduling breaks hold-and-wait for distributed jobs: a job's pods are admitted together or not at all (Kubernetes schedulers such as Volcano, Kueue and YARN's gang scheduling do this for AI training).

Strategy 2: avoidance — the Banker's algorithm

Each process declares its maximum demand in advance. The system grants a request only if the resulting state is safe: there exists an order (a safe sequence) in which every process can obtain its remaining need, finish, and release everything.

• Safe ⇒ no deadlock can occur (the system can always follow the safe sequence).
• Unsafe ≠ deadlock, but the system might reach one if processes ask for their maximums.

Data for n processes and m resource types: Available[m], Max[n][m], Allocation[n][m], and Need = Max − Allocation.

Safety algorithm: Work = Available; repeatedly find an unfinished process with Need ≤ Work, pretend it finishes (Work += Allocation), mark it finished. Safe if all processes finish. (In this course, we scan P0…Pn−1 in passes and take every process that fits, in index order.)

Request algorithm for process Pi requesting Req:

1. If Req > Need[i] → error (exceeds its declared maximum).
2. If Req > Available → Pi must wait.
3. Pretend to allocate; if the new state is safe → grant, otherwise roll back and make Pi wait.

Worked example — EdgeCampus. Three resource types (GPU slots, CPU blocks, memory blocks), totals (5, 7, 10). Four jobs:

Available = (2, 3, 4). Safety: P1's need (1 3 4) ≤ (2 3 4) → Work = (3 3 6); P2 (2 1 6) → (4 4 8); P3 (2 3 4) → (4 6 8); P0 (3 3 6) → (5 7 10). Safe sequence P1, P2, P3, P0.

• P0 requests (1 1 2). It is available, but afterwards Available = (1 2 2) and no process's need fits (P1 needs 3 CPU blocks, P2 and P3 need too much memory): unsafe → P0 waits, even though the resources are free!
• P3 requests (1 1 2). Afterwards Available = (1 2 2), P3's need becomes (1 2 2) — it fits: P3, P1, P2, P0 → safe → granted.

The Banker's algorithm costs O(m·n²) per request and requires maximum demands in advance, which general-purpose OSs do not know. Its ideas survive in admission control: cloud schedulers and Kubernetes admit a pod only if its requested resources fit, and quota systems reserve capacity for the worst case.

Strategy 3: detection and recovery

Let deadlocks happen, check periodically, and recover.

Detection with multiple instances (like the safety algorithm, but with current Request instead of Need): Work = Available; processes holding nothing are marked finished; repeatedly find an unfinished process whose Request ≤ Work, assume it completes and releases its allocation. Processes that can never be marked finished are deadlocked.

When to run it? After every blocked request (expensive but immediate), every few minutes, or when CPU utilization drops suspiciously — a common trigger.

Recovery:

• Abort all deadlocked processes — simple, lots of lost work.
• Abort one at a time until the cycle disappears, choosing the victim with the lowest cost (priority, work done, resources held, how many more it needs, interactive or batch).
• Preempt resources and roll back the victim to a checkpoint (databases roll back a transaction; ML training restarts from the last checkpoint).
• Avoid starvation: do not always pick the same victim (include the number of past rollbacks in the cost).

MySQL/InnoDB and PostgreSQL build a wait-for graph among transactions; when a cycle appears, they abort the cheapest transaction with the error "Deadlock found when trying to get lock; try restarting transaction". Applications must be ready to retry.

Deadlock, livelock, starvation

• Deadlock — processes blocked forever, no one runs.
• Livelock — processes keep running but make no progress (two people in a corridor stepping aside in the same direction again and again; two threads that release and retry at the same rhythm). Fix: randomized back-off.
• Starvation — one process waits indefinitely while others progress (low priority, always chosen as victim). Fix: aging, fairness.

Priority inversion (Chapter 5) is not a deadlock: the high-priority task waits, but the system keeps making progress.

Deadlocks in distributed and edge–cloud systems

Without a global view, detection is hard: each node sees only part of the wait-for graph, messages are delayed, and a naive detector reports phantom deadlocks. Practical systems therefore prefer timeouts and leases (a lock expires if not renewed), ordering (acquire locks in a global key order), all-or-nothing allocation (gang scheduling, two-phase commit's prepare phase) and idempotent retries.

Key takeaways

• Four necessary conditions: mutual exclusion, hold and wait, no preemption, circular wait — break one to prevent deadlock.
• RAG: no cycle ⇒ no deadlock; cycle + single instances ⇒ deadlock; cycle + multiple instances ⇒ maybe. Wait-for graph cycle ⇔ deadlock (single instances).
• Strategies: ignore (general-purpose OS), prevent (resource ordering, all-or-nothing), avoid (Banker: grant only if the state stays safe; Need = Max − Allocation), detect & recover (databases: abort the cheapest victim and retry).
• Safe ⇒ no deadlock; unsafe ⇒ deadlock possible, not certain.
• Livelock = busy without progress; starvation = one waits forever; priority inversion ≠ deadlock.
• Distributed systems use timeouts, leases, lock ordering and gang scheduling for multi-GPU jobs.