Deadlock

A set of processes is deadlocked when every process in the set is waiting for an event (here, the release of a resource) that can be caused only by another process in the same set. Nobody can release anything, so nobody ever moves. Resources here are non-shareable units that a process requests, uses, and releases; a request for a unit that is not free makes the process wait.

Conventions used in these notes: processes are numbered $P_0,P_1,\dots$; when several processes could be picked next in an algorithm, the one with the smallest index is picked (any valid order gives the same yes/no answer for safety and detection). Resource types are written $R_1,R_2,\dots$ and a type may have several identical instances.

A system can handle deadlock in four ways: prevention (make one necessary condition impossible), avoidance (grant a request only if the system stays safe), detection and recovery (let deadlock happen, find it, break it), or ignoring the problem and relying on a restart.

Deadlock can occur only if all four of the following hold at the same time. They are necessary, not sufficient: all four can hold in a system that is not currently deadlocked.

A resource-allocation graph (RAG) is a directed graph with process nodes $P_i$ and resource-type nodes $R_j$. Each instance of $R_j$ is drawn as a dot inside its box.

• Request edge $P_i\to R_j$: $P_i$ is waiting for an instance of $R_j$.
• Assignment edge $R_j\to P_i$: an instance of $R_j$ is allocated to $P_i$.

With several instances, a cycle alone does not settle the question. If an instance of a resource that a process on the cycle is waiting for is held by a process that can eventually finish (for example one outside the cycle that is not waiting for anything), that process will release it and the cycle can break.

A reliable way to test a multi-instance RAG: repeatedly pick a process whose pending requests can all be satisfied from currently free instances, let it finish, and release its allocations. If every process can be removed this way there is no deadlock; the processes left over are deadlocked. This is exactly the detection algorithm described later.

Prevention designs the system so that at least one of the four necessary conditions can never hold. It needs no knowledge of future requests, but it often lowers resource utilisation and throughput.

Why resource ordering works. Suppose a circular wait $P_0\to P_1\to \cdots \to P_m\to P_0$ existed, where $P_i$ holds $R_i$ and waits for $R_{i+1}$ (indices mod $m+1$). Under the ordering rule, waiting for $R_{i+1}$ while holding $R_i$ means $\text{order}(R_i)<\text{order}(R_{i+1})$. Chaining around the cycle gives $\text{order}(R_0)<\text{order}(R_1)<\cdots <\text{order}(R_m)<\text{order}(R_0)$, which is impossible.

Avoidance lets all four conditions be possible but grants a request only if the resulting state is safe. It needs each process to declare in advance its maximum claim for each resource type.

A state is safe if there exists a safe sequence $⟨P_a,P_b,\dots ⟩$: an order in which each process can, in turn, get all it may still need from what is free plus what the earlier processes in the sequence will have released, then finish. Otherwise the state is unsafe.

• Safe state $\Rightarrow$ not deadlocked, and the system can keep it free of deadlock by granting only requests that leave the state safe.
• Deadlock $\Rightarrow$ unsafe state.
• Unsafe state does not mean deadlock; it only means deadlock may happen depending on the future requests.

Single instance of every type: the resource-allocation-graph algorithm. Besides request and assignment edges, draw a claim edge $P_i⇢R_j$ (dashed) for every resource $P_i$ may request in future; all claim edges are declared before $P_i$ starts. When $P_i$ requests $R_j$, the claim edge becomes a request edge. The request is granted only if turning it into an assignment edge $R_j\to P_i$ creates no cycle, with claim edges counted; otherwise $P_i$ waits. When some type has several instances, this test is not enough and the Banker's algorithm is used.

Banker's algorithm data for $n$ processes and $m$ resource types: the vector $\text{Available}$ (length $m$), and $n\times m$ matrices $\text{Max}$, $\text{Allocation}$ and $\text{Need}$. Vector comparison $X\le Y$ means $X[j]\le Y[j]$ for every $j$. The algorithm assumes a fixed number of processes and resource instances, maximum claims declared before a process starts, and that a process given all it needs finishes and releases everything in finite time.

If a system neither prevents nor avoids deadlock, it must detect it and then recover. Detection does not use maximum claims; it works on what processes are holding and currently requesting.

Single instance of every type: wait-for graph. Remove the resource nodes from the RAG and draw an edge $P_i\to P_j$ when $P_i$ waits for a resource held by $P_j$. There is a deadlock if and only if the wait-for graph has a cycle, and every process on a cycle is deadlocked. Cycle detection costs $O(n^2)$ for $n$ processes (adjacency-matrix search).

When to run detection. Running it at every request catches deadlock immediately but is expensive; running it at fixed intervals, or when CPU utilisation drops, costs less but several cycles may form and it becomes harder to say which request caused the deadlock.

How many instances guarantee no deadlock? Take a single resource type with $R$ identical instances, and $n$ processes. Each process needs at most $k$ instances (and may actually ask for all $k$), requests them one at a time, and holds what it has while waiting. Deadlock needs every process blocked with nothing free. The most that $n$ blocked processes can hold without any of them having its full need is $k-1$ each, giving $n(k-1)$ instances held. If one more instance exists, at least one process can obtain all $k$, finish and release, so deadlock is impossible.

For different maximum needs $k_1,k_2,\dots ,k_n$ the condition becomes $R\ge {\sum }_{i=1}^n(k_i-1)+1$.