Deadlock Avoidance and the Banker's Algorithm

Prevention makes deadlock impossible by restricting how processes request resources. Avoidance is gentler: processes request resources freely, but each process declares in advance the maximum it may ever need, and the OS grants a request only if the system stays in a safe state, one from which every process can still finish. Dijkstra's Banker's algorithm is the classic avoidance method; the name comes from a banker who never lends so much that he could not satisfy all his customers' credit limits in some order.

The price is advance knowledge of maximum claims, a fixed number of processes and resources, and an $O(m n^2)$ check on every request. The benefit is that resources are not wasted the way they are under hold-and-wait prevention.

For $n$ processes and $m$ resource types:

Vectors are compared component-wise: $X \le Y$ means $X[j] \le Y[j]$ for every $j$.

A state is safe if there is a safe sequence $\langle P_{i_1}, \dots, P_{i_n} \rangle$: each $P_{i_k}$ can obtain its remaining Need from the currently available resources plus everything held by the processes before it in the sequence, finish, and release.

Safe, unsafe, deadlocked. Every safe state is deadlock-free. An unsafe state is not necessarily deadlocked: it only means the OS can no longer guarantee completion if processes demand their maxima. Deadlocked states are a subset of unsafe states.

Time upper bound $O(mn^2)$. Auxiliary workspace is $O(n+m)$, excluding the $O(nm)$ input matrices; an average time requires a distribution over inputs and scan orders. Any order that picks an eligible process works: picking one never hurts, because finishing only adds to Work. The scan convention scans $i = 0, 1, \dots, n - 1$ from the start after each choice and takes the first eligible process; other scan orders find other safe sequences, all equally valid.

When $P_i$ requests the vector Request:

Avoidance versus detection. Both algorithms look alike. Safety uses Need (worst-case future demand); detection uses Request (current outstanding requests). Avoidance runs before granting; detection runs after the fact.

Why a greedy scan suffices. If some safe sequence exists and the algorithm picks an eligible process $P_k$ that is not first in it, finishing $P_k$ only increases Work. Every process in the original sequence remains eligible at its turn, with $P_k$ removed. So the greedy choice never closes a safe path, and the algorithm declares the state unsafe only when no safe sequence exists.

Counting safe sequences. The number is not determined by the safety algorithm; it requires enumerating orders (a depth-first search over eligible choices). In the example, P2 and P1 are forced, then all $3! = 6$ orders of P0, P3, P4 work because Work $(4, 3, 2)$ already covers all three remaining needs.

Total resources $(A, B, C) = (7, 5, 5)$.

Allocated: $(6, 4, 4)$, so Available $= (1, 1, 1)$.

Safe sequence $\langle P2, P1, P0, P3, P4 \rangle$. Enumerating all orders, there are exactly 6 safe sequences, and every one starts with P2, P1: at the start only P2 fits, and after P2 only P1 does; the last three can then go in any order ($3! = 6$). Work ends at the total $(7, 5, 5)$, as it must.

From the state above:

Unsafe does not mean deadlocked. After pretending to give P1 the unit of A, nobody is actually blocked yet (no outstanding requests), so the detection algorithm finds no deadlock. The state is still refused, because a deadlock could follow if processes claim their maxima.

Ten units; P0, P1, P2 have maxima 8, 3, 6 and hold 4, 1, 2, so 3 units are free and the needs are 4, 2, 4. Safe: P1 (needs 2) finishes and frees 3 units, giving 4 free; then P0 (needs 4) finishes, giving 8; then P2. If P2 is given one more unit, the state is still safe, but only in the order P1, P2, P0 (after P1 finishes, 3 units are free: enough for P2, not for P0). If P2 is given two more, only 1 unit is free and every need exceeds it: unsafe.

When more than one process is eligible at several steps, the safe sequences do not reduce to one forced prefix and a factorial. Take this five-process state, with Available $(3, 3, 2)$:

Count by building the tree of choices, adding the Allocation of each process that finishes to Work:

Total: $12 + 2 + 2 = 16$ safe sequences, confirmed by enumerating all $5! = 120$ orders. That scan finds $\langle P1, P3, P0, P2, P4 \rangle$.

Testing a given sequence. Run the sequence and check each Need against Work at its turn.

A sequence that fails says nothing about the state as a whole: this state is safe, because some other order works.

Common misconceptions.