Deadlock: Conditions, Prevention, Detection and Recovery: short notes (Operating Systems)

Introduction

A set of processes is deadlocked when every process in the set is waiting for an event that only another process in the set can cause. Typically the event is the release of a resource: P1 holds a printer and waits for a scanner, P2 holds the scanner and waits for the printer, and neither will ever give way. Nothing inside the system will break the wait.

Deadlock can be handled in four ways: prevent it by making one necessary condition impossible, avoid it by refusing requests that could lead to it (the Banker's algorithm, in Deadlock Avoidance and the Banker's Algorithm), detect and recover after it happens, or ignore it (the "ostrich" approach many general-purpose systems take for application-level locks). The model, the four conditions, resource-allocation graphs, prevention, detection and recovery are the standard parts of the subject.

Prerequisites

Semaphores, Mutexes and Monitors: locks acquired in opposite orders, blocking wait.

Core concepts

System model

There are resource types $R_1, \dots, R_m$ (CPU cycles, memory pages, files, locks, devices), with $W_j$ identical instances of type $R_j$ . A process uses a resource by request, use, release. A request that cannot be granted makes the process wait.

The four necessary conditions (Coffman conditions)

Deadlock can arise only if all four hold at once:

Mutual exclusion: at least one resource is non-shareable.
Hold and wait: a process holds at least one resource while waiting for another.
No preemption: a resource is released only voluntarily by its holder.
Circular wait: there is a cycle $P_0 \to P_1 \to \dots \to P_k \to P_0$ in which each waits for a resource held by the next.

The conditions are necessary, not sufficient: all four can hold without a deadlock existing yet. Circular wait in fact implies hold and wait, but the four are listed separately because each suggests a different prevention method.

Deadlock, starvation and livelock. Deadlocked processes wait forever and do nothing. A starving process could proceed but keeps losing to others. In livelock, processes keep changing state in response to each other without progress.

Resource-allocation graphs

A resource-allocation graph (RAG) has process nodes (circles) and resource nodes (rectangles, with a dot per instance). A request edge $P_i \to R_j$ means $P_i$ waits for $R_j$ ; an assignment edge $R_j \to P_i$ means an instance of $R_j$ is held by $P_i$ .

No cycle: no deadlock.
Cycle, every resource single-instance: deadlock, and the processes on the cycle are deadlocked.
Cycle with multi-instance resources: deadlock is possible but not certain.

Resource-allocation graphs with and without deadlock — Figure 1. Left: P1 holds R1 and requests R2 while P2 holds R2 and requests R1, a cycle of single-instance resources and a deadlock. Right: the same cycle, but R1 has two instances and the second is held by P3, which needs nothing more; P3 can finish and release it, so there is no deadlock.

For single-instance resources, the wait-for graph drops the resource nodes: draw $P_i \to P_k$ when $P_i$ waits for a resource that $P_k$ holds. Deadlock exists if and only if the wait-for graph has a cycle, which cycle detection finds in $O(n^2)$ time for $n$ processes (adjacency matrix) or $O(n + e)$ with adjacency lists.

A process off the cycle can still be stuck. In Figure 2, P4 is not on the cycle, but waits for P1, which will never release its resource. P4 is permanently blocked behind the cycle. The WFG does not specify whether P4 holds any uncontested resources: DETECT in Detection and recovery initializes zero-allocation processes as finished, so it excludes a zero-allocation P4, but reports P4 as unable to finish if P4 also holds a resource. Distinguish cycle/deadlock participants from all permanently blocked processes, and follow the question's exact definition.

Prevention: break one condition

Condition	How to break it	Cost
Mutual exclusion	Make resources shareable (read-only files; spooling a printer)	Impossible for locks and most devices
Hold and wait	Request all resources at once before starting, or release everything before requesting more	Low utilization; starvation of processes needing many popular resources
No preemption	If a request fails, release what you hold (or let the OS take resources from waiting processes)	Works only for resources whose state can be saved and restored (CPU, memory), not printers or locks mid-update
Circular wait	Number resource types; request only in increasing order	Programmers must follow the order; the most practical method

Why resource ordering works. Suppose there is a cycle $P_0 \to P_1 \to \dots \to P_k \to P_0$ where $P_i$ holds $R_{(i)}$ and waits for $R_{(i+1)}$ held by $P_{i+1}$ . Increasing order means the number of $R_{(i+1)}$ is larger than that of $R_{(i)}$ for every $i$ , so going round the cycle the numbers strictly increase and return to the start, a contradiction.

Detection and recovery

Detection with multiple instances

The algorithm resembles the Banker's safety check, but uses current requests instead of maximum needs:

Text

DETECT(Available, Allocation, Request):      -- n processes, m resource types
    Work <- Available
    for i <- 1 to n: Finish[i] <- (Allocation[i] = 0)
    repeat
        find i with Finish[i] = false and Request[i] <= Work
        if found then Work <- Work + Allocation[i]; Finish[i] <- true
    until no such i
    return { i : Finish[i] = false }          -- the deadlocked processes

It runs in $O(m n^2)$ time. "Request $\le$ Work" is optimistic: it assumes a process that gets what it asks for now will finish and release everything.

When to run it. On every failed request (expensive, but identifies the culprit), periodically, or when CPU utilization drops sharply.

Recovery

Process termination: abort all deadlocked processes, or abort one at a time and rerun detection. Choose victims by priority, work done, resources held, or resources still needed.
Resource preemption: take resources from a victim and roll back the victim to a safe state (checkpoint or restart). Avoid starvation by counting rollbacks in the victim-selection cost so the same process is not chosen forever.

Worked examples

Detection

Five processes and resource types A, B, C; all instances are allocated (Available $= (0, 0, 0)$ ).

Process	Allocation (A B C)	Request (A B C)
P0	0 1 0	0 0 0
P1	2 0 0	2 0 2
P2	3 0 3	0 0 0
P3	2 1 1	1 0 0
P4	0 0 2	0 0 2

P0 needs nothing: Work $= (0, 1, 0)$ . P1 cannot proceed yet. P2 needs nothing: Work $= (3, 1, 3)$ . Then P3: $(5, 2, 4)$ ; P4: $(5, 2, 6)$ ; finally P1: $(7, 2, 6)$ . The order P0, P2, P3, P4, P1 finishes everyone: no deadlock.

Now let P2 request one more C (Request $= (0, 0, 1)$ ). Only P0 can finish, giving Work $= (0, 1, 0)$ , and no other request fits. P1, P2, P3 and P4 are deadlocked.

Minimum resources that rule out deadlock

Three processes share $R$ identical units of one resource; each needs up to 4 at once and holds units while waiting for more. The worst case gives every process 3 units (one short of its maximum). With $R = 9$ that uses everything and all three wait forever. With $R = 10$ , one more unit lets some process reach 4, finish and release. So the minimum is 10.

In general, for maximum needs $k_1, \dots, k_n$ :

R_{\min} = \sum_{i=1}^{n} (k_i - 1) + 1 .

For needs 2, 3 and 4 this gives $1 + 2 + 3 + 1 = 7$ . For five processes needing 2 each, 6 units suffice.

Turning the formula around. The same inequality $\sum (k_i - 1) + 1 \le R$ answers the inverse questions.

How many processes can share 6 units if each needs 2? With $n$ processes the worst case holds $n \times 1$ units, so we need $n + 1 \le 6$ : at most 5 processes. With 6 processes each could hold one unit and all 6 would wait.
Four processes share 10 units, each needing $k$ . What is the largest $k$ that is deadlock-free? $4(k - 1) + 1 \le 10$ gives $k \le 3.25$ , so $k = 3$ . With $k = 4$ each process can hold 3 units, 12 in total, but only 10 exist; the state in which three processes hold 3 units and the fourth holds 1 uses all 10 with everyone short, a deadlock.
Three processes need 3, 4 and 5 units. $R_{\min} = 2 + 3 + 4 + 1 = 10$ ; with 9 units the state (2, 3, 4) leaves every process one short.

Ordering prevents the lock-order deadlock

The two-semaphore deadlock in Semaphores, Mutexes and Monitors disappears when both processes take S before Q: number S as 1 and Q as 2, and the cycle can no longer form.

Important properties and observations

A cycle is necessary for deadlock; it is sufficient only when every resource on the cycle has a single instance.
Detection reports processes that cannot finish, not the edges to break.
Prevention restricts how requests are made; avoidance (Banker's) examines each request at run time with advance knowledge of maximum needs; detection allows deadlock and cleans up.
A safe state cannot deadlock; an unsafe state may or may not.

Common misconceptions.

"A cycle always means deadlock." Not with multi-instance resources.
"Starvation and deadlock are the same." A starving process could run; a deadlocked one cannot.
"Preventing mutual exclusion is the usual method." Most resources are inherently exclusive; ordering is the practical method.

GATE examination perspective

RAG questions. Check instance counts before concluding deadlock from a cycle; with multiple instances, run detection.
Minimum resources. $\sum (k_i - 1) + 1$ for one resource type; maximum number of processes for a given $R$ solves $n(k - 1) + 1 \le R$ .
Which condition is broken? All-at-once allocation breaks hold and wait; ordering breaks circular wait; spooling breaks mutual exclusion; forcible release breaks no preemption.
Detection traces. Use Request, not Need; a process with zero allocation counts as finished from the start.
Recovery trade-offs. Abort all (simple, costly) versus abort one at a time (rerun detection each time).

Summary

Semaphores, Mutexes and Monitors: prerequisite. Locks taken in opposite orders.
Lock-Based Concurrency Control and Two-Phase Locking: dependent. Deadlocks among transactions and their detection with wait-for graphs.
Deadlock Avoidance and the Banker's Algorithm: dependent. Avoidance with maximum claims.
Classical Synchronization Problems: related. The dining philosophers deadlock and its fixes.

Deadlock: Conditions, Prevention, Detection and Recovery

Introduction

Prerequisites

Core concepts

System model

The four necessary conditions (Coffman conditions)

Resource-allocation graphs

Prevention: break one condition

Detection and recovery

Detection with multiple instances

Recovery

Worked examples

Detection

Minimum resources that rule out deadlock

Ordering prevents the lock-order deadlock

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

System model

The four necessary conditions (Coffman conditions)

Resource-allocation graphs

Prevention: break one condition

Detection and recovery

Detection with multiple instances

Recovery

Worked examples

Detection

Minimum resources that rule out deadlock

Ordering prevents the lock-order deadlock

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps