The Banker's Algorithm

A system state is described by four structures over `n` processes and `m` resource types. `Available[j]` is the number of instances of resource type `j` currently free. `Max[i][j]` is the maximum number of instances of resource `j` that process `i` will ever request during its lifetime, declared before the process starts. `Allocation[i][j]` is the number of instances of `j` currently held by process `i`. The derived quantity `Need[i][j] = Max[i][j] − Allocation[i][j]` is the number of additional instances of `j` that process `i` may still request. These satisfy the invariant `Need[i][j] ≥ 0` and `Allocation[i][j] ≤ Max[i][j]` for every process and resource, and the total allocated of any resource never exceeds the number of instances that exist. A state is safe if there exists a safe sequence — an ordering `⟨P₁, P₂, …, Pₙ⟩` of all processes — such that for every `Pᵢ`, the resources `Pᵢ` might still need can be satisfied by the currently available resources plus the resources held by all processes `P₁ … Pᵢ₋₁` (which, having gone first in the sequence, are assumed to run to completion and release everything). Intuitively: even in the absolute worst case where every process immediately asks for its full declared maximum, the banker can still satisfy everyone, one at a time, by waiting for each to finish and reclaim its resources before serving the next. A state that is not safe is called unsafe — note carefully that unsafe does not mean deadlocked; it means a deadlock is merely possible if processes behave adversarially. Avoidance is conservative: it forbids even the risk. The algorithm has two moving parts that are often confused. The Safety Algorithm is a pure query: given a snapshot of `Available`, `Allocation`, and `Need`, does a safe sequence exist? The Resource-Request Algorithm is the decision procedure invoked whenever a process asks for resources: it tentatively applies the request, calls the Safety Algorithm on the resulting hypothetical state, and either commits the request (if safe) or blocks the requesting process and rolls back (if unsafe). This separation — a checkable safety predicate plus a request handler that never commits an unsafe transition — is the conceptual core of every avoidance algorithm, including the single-resource variant known as the Resource Allocation Graph algorithm.

Setup. Before any process runs, it declares its maximum claim vector `Max[i][·]` for all `m` resource types, subject to `Max[i][j] ≤` total instances of `j`. The OS initializes `Allocation[i][·] = 0`, `Need[i][·] = Max[i][·]`, and `Available[·]` to the total instance counts (nothing allocated yet).

Step 1 — Safety Algorithm. This is invoked (a) once at startup with the initial all-zero allocation (trivially safe), and (b) hypothetically inside every resource request, on a copy of the state with the request tentatively applied. ``` function IS_SAFE(Available, Allocation, Need, n, m): Work ← copy of Available # length m Finish ← array of n booleans, all false changed ← true while changed: changed ← false for i in 0 .. n-1: if not Finish[i] and Need[i] ≤ Work (componentwise): Work ← Work + Allocation[i] # simulate Pi finishing, reclaim its resources Finish[i] ← true changed ← true if all Finish[i] are true: return (true, sequence of i in the order they were marked Finish) else: return (false, ∅) ```

Step 2 — Resource-Request Algorithm. When process `Pᵢ` issues a request vector `Request[·]`: ``` function REQUEST_RESOURCES(i, Request, Available, Allocation, Need, n, m):

# 1. Sanity checks against declared bounds if Request > Need[i] (any component exceeds): error("process exceeded its declared maximum claim")

# 2. Must wait if resources simply aren't free yet if Request > Available (any component exceeds): block process i until Available is updated, then retry return PENDING

# 3. Tentatively grant: pretend the request succeeded Available ← Available − Request Allocation[i] ← Allocation[i] + Request Need[i] ← Need[i] − Request

# 4. Check safety of the resulting hypothetical state (safe, seq) ← IS_SAFE(Available, Allocation, Need, n, m) if safe: return GRANTED # commit — state above is now real else:

# 5. Roll back completely; request is denied for now Available ← Available + Request Allocation[i] ← Allocation[i] − Request Need[i] ← Need[i] + Request block process i, request remains pending return DENIED ``` When any process later releases resources (normal completion or partial release), `Available` increases and every blocked, previously-denied request should be re-tried against the new `Available` — a released resource may turn a previously unsafe hypothetical state into a safe one.

Time complexity of `IS_SAFE`. The outer `while` loop makes at most `n` full passes in the worst case (each pass finds at least one new process to finish, or the loop terminates because nothing changed — the "changed" flag guarantees we stop the moment a pass finds no candidate). Each pass scans all `n` processes, and for each process compares `Need[i]` against `Work` component-wise, an `O(m)` operation, and if it finishes, adds `Allocation[i]` to `Work`, also `O(m)`. So a pass costs `O(n·m)`, and there are at most `n` passes, giving ``` T(IS_SAFE) = O(n² · m) ``` This is tight: consider processes ordered so that each one becomes satisfiable only after the previous one finishes (a "chain" dependency) — then exactly `n` passes are needed, each re-scanning all remaining processes, yielding genuine `Θ(n²m)` behavior on such inputs. A more careful implementation can maintain a worklist/queue of not-yet-finished processes and avoid re-scanning already-finished ones within a pass, but the `Θ(n²m)` worst case persists because the order of completion is not known in advance and, in the chain scenario, only one process can be confirmed finishable per full scan.

Time complexity of `REQUEST_RESOURCES`. Steps 1–3 and the rollback in step 5 are `O(m)`. The dominant cost is the call to `IS_SAFE`, so each request check costs `O(n²m)`, the same as one safety query.

Space complexity. Three `n × m` matrices (`Max`, `Allocation`, `Need`) plus one length-`m` vector (`Available`), plus the `O(n + m)` scratch space (`Work`, `Finish`) used transiently inside `IS_SAFE`. Total resident space is ``` O(n·m) ```

Correctness argument. The central claim is: > Invariant. The Resource-Request Algorithm only ever commits a transition from a safe state to > another safe state. Consequently, if the system starts safe (which it does, trivially, with zero > allocation), it remains safe forever, and a safe state can never deadlock. Proof that safe states cannot deadlock. Suppose the system is in a safe state with safe sequence `⟨P₁,…,Pₙ⟩`. By definition, `Need[P₁] ≤ Available`, so `P₁` can always obtain everything it might ever ask for; when it does (worst case) and finishes, it releases `Allocation[P₁]`, making `Available' = Available + Allocation[P₁] ≥ Need[P₂]` by the safe-sequence condition, so `P₂` can complete next, and so on inductively. Hence every process is guaranteed a path to completion — no process can be stuck forever waiting on resources held by others in a cycle, which is precisely the absence of deadlock. ∎ Proof that the algorithm preserves safety. `REQUEST_RESOURCES` tentatively applies a request and then literally re-invokes `IS_SAFE` on the resulting state before committing. If `IS_SAFE` returns false, the tentative change is rolled back exactly (all three vector updates are inverses of the tentative ones, restoring the prior — safe, by the invariant — state). If `IS_SAFE` returns true, the new state is safe by definition of what `IS_SAFE` verifies, and the algorithm commits it as the new real state. In either branch the resulting real state is safe. By induction on the sequence of requests, starting from the trivially safe zero-allocation state, every reachable real state is safe. ∎ Combining the two proofs: every state the system ever actually enters is safe, and safe states cannot deadlock, so the Banker's Algorithm guarantees deadlock never occurs — provided its structural assumptions hold: the number of instances of each resource type is fixed and known, every process declares an accurate maximum claim before running and never exceeds it, processes are not required to finish within bounded time (avoidance guarantees possibility of completion, not fairness or liveness), and the resources are reusable (not consumable, like message-queue slots that vanish on use). Violate the maximum-claim assumption — a process lies about its ceiling, or a new process joins mid-execution with an unforeseen maximum — and the safety guarantee is void. This is the central tradeoff: mathematically airtight deadlock immunity, purchased at the price of a strong, often unrealistic, prediction requirement imposed on user programs, plus a nontrivial `O(n²m)` cost paid on the critical path of every resource request.

Consider `n = 5` processes and `m = 3` resource types with instance counts `A:10, B:5, C:7`. This is the canonical trace used to illustrate every step of the algorithm, extended with a rejected request.

Initial state (already safe):

Total allocated: `A=7, B=2, C=5`. Available = `(10-7, 5-2, 7-5) = (3, 3, 2)`.

Run `IS_SAFE` on the initial state. `Work = (3,3,2)`, all `Finish = false`.

• Pass 1: `Need[P0]=(7,4,3) ≤ Work`? No (7>3). `Need[P1]=(1,2,2) ≤ (3,3,2)`? Yes → finish P1,

`Work = (3,3,2)+(2,0,0) = (5,3,2)`. `Need[P2]=(6,0,0) ≤ (5,3,2)`? No (6>5). `Need[P3]=(0,1,1) ≤ (5,3,2)`? Yes → finish P3, `Work = (5,3,2)+(2,1,1) = (7,4,3)`. `Need[P4]=(4,3,1) ≤ (7,4,3)`? Yes → finish P4, `Work = (7,4,3)+(0,0,2) = (7,4,5)`.

• Pass 2: `Need[P0]=(7,4,3) ≤ (7,4,5)`? Yes → finish P0, `Work = (7,4,5)+(0,1,0) = (7,5,5)`.

`Need[P2]=(6,0,0) ≤ (7,5,5)`? Yes → finish P2, `Work = (7,5,5)+(3,0,2) = (10,5,7)`. All five finished. Safe sequence: ⟨P1, P3, P4, P0, P2⟩. The system is safe.

Request A: P1 requests `(1,0,2)`. 1. Check against `Need[P1] = (1,2,2)`: `(1,0,2) ≤ (1,2,2)`. OK. 2. Check against `Available = (3,3,2)`: `(1,0,2) ≤ (3,3,2)`. OK. 3. Tentatively apply: `Available = (2,3,0)`, `Allocation[P1] = (3,0,2)`, `Need[P1] = (0,2,0)`. 4. Run `IS_SAFE`: `Work=(2,3,0)`.

• `Need[P1]=(0,2,0) ≤ (2,3,0)` ✓ → finish P1, `Work=(2,3,0)+(3,0,2)=(5,3,2)`.
• `Need[P3]=(0,1,1) ≤ (5,3,2)` ✓ → finish P3, `Work=(5,3,2)+(2,1,1)=(7,4,3)`.
• `Need[P4]=(4,3,1) ≤ (7,4,3)` ✓ → finish P4, `Work=(7,4,3)+(0,0,2)=(7,4,5)`.
• `Need[P0]=(7,4,3) ≤ (7,4,5)` ✓ → finish P0, `Work=(7,4,5)+(0,1,0)=(7,5,5)`.
• `Need[P2]=(6,0,0) ≤ (7,5,5)` ✓ → finish P2.

All finish → safe. Grant the request. New real state: `Available=(2,3,0)`.

Request B: P4 requests `(3,3,0)`. 1. Check against `Need[P4] = (4,3,1)`: `(3,3,0) ≤ (4,3,1)`. OK. 2. Check against current `Available = (2,3,0)`: `3 > 2` on resource A. Request exceeds Available. P4 must block immediately — no tentative grant is even attempted, since insufficient physical resources exist yet. Return `PENDING`.

Request C: P0 requests `(0,2,0)`. 1. Check against `Need[P0] = (7,4,3)`: OK. 2. Check against `Available = (2,3,0)`: `(0,2,0) ≤ (2,3,0)`. OK. 3. Tentatively apply: `Available = (2,1,0)`, `Allocation[P0] = (0,3,0)`, `Need[P0] = (7,2,3)`. 4. Run `IS_SAFE`: `Work=(2,1,0)`.

• `Need[P0]=(7,2,3) ≤ (2,1,0)`? No. `Need[P1]=(0,2,0) ≤ (2,1,0)`? No (2>1).

`Need[P2]=(6,0,0) ≤ (2,1,0)`? No. `Need[P3]=(0,1,1) ≤ (2,1,0)`? No (1>0 on C). `Need[P4]=(4,3,1) ≤ (2,1,0)`? No.

• No process can finish in this pass. `changed = false` → loop terminates. `Finish` has no true

entries beyond none. Unsafe. 5. Roll back: restore `Available=(2,1,0)+(0,2,0)=(2,3,0)`, `Allocation[P0]=(0,1,0)`, `Need[P0]=(7,4,3)`. Deny the request; P0 blocks, even though `Available` alone looked sufficient — this is exactly the scenario avoidance is designed to catch.

Pure, textbook Banker's Algorithm is rarely run unmodified inside general-purpose kernels like Linux or Windows, precisely because ordinary processes cannot reliably declare accurate maximum resource claims in advance — a compiler does not know beforehand how many file descriptors a user's arbitrary input will provoke it to open. Where the technique genuinely thrives is in domains where maximum claims are known or can be conservatively bounded by design: embedded and real-time systems with statically analyzed resource budgets, database systems reasoning about lock escalation limits per transaction class, cluster and job schedulers (Hadoop YARN-style capacity reasoning, HPC batch schedulers) that admit jobs only if their declared peak resource footprint keeps the cluster in a safe allocation state, and formal verification tooling that models resource-holding protocols to prove absence of deadlock before deployment. More broadly, the safe-state framework is the conceptual ancestor of admission-control policies throughout distributed systems: any component that says "I will only accept this request if the system, in the worst case, can still satisfy every outstanding commitment" is running a Banker's-style safety check, even when it does not call it by that name. Understanding this algorithm deeply also clarifies, by contrast, why Deadlock Detection and recovery — check periodically, kill or roll back a victim if a cycle is found — is the pragmatic choice in most production kernels and databases, since it needs no advance declarations at all.

Ask the tutor: How would the Banker's Algorithm need to change if a new process could join the system after it has already started running?