Deadlock Prevention & Avoidance — Banker's Algorithm
Press Next → or use ← → arrow keys
The Story That Explains Both
Before handing it over, the manager asks: "If I grant this, can I still eventually repay every customer in full, in some order?" If yes, grant it. If no, make them wait — even though the cash is physically sitting in the vault. That caution is exactly the Banker's Algorithm.
Prevention is pessimistic — it forbids patterns that could deadlock, even when they wouldn't. Avoidance is optimistic — it grants a request whenever the result is provably safe, postponing only the truly risky ones.
Prevention — Break One Coffman Condition
| Break… | How | Problem |
|---|---|---|
| 🔒 Mutual Exclusion | Make resources sharable (read-only files, spooling) | Impossible for intrinsically non-sharable things like locks |
| ✋ Hold and Wait | Protocol A: request everything up front · Protocol B: release all before requesting more | Low utilisation; possible starvation |
| 🚫 No Preemption | Let the OS forcibly take resources back | Only works for state-saveable resources (CPU, memory) |
| 🔄 Circular Wait | Number resource types; always request in increasing order | Most practical — used in real kernels |
Give every resource type a number and require processes to lock in strictly increasing order. A cycle needs someone to wait "backwards" — which the ordering forbids. Cheap, simple, and the technique real kernels and databases actually use.
Ordered Locking — No Cycle, No Deadlock
Both P1 and P2 grab R1 before R2. Since no process ever holds a higher-numbered resource while waiting for a lower-numbered one, the wait-for edges can never form a loop. Circular wait is structurally impossible.
Avoidance — Stay in the Safe State
A state is safe if there is an order ⟨P₁, P₂, …⟩ — a safe sequence — in which
each process's remaining Need can be met by the current Available plus the
resources held by processes earlier in the sequence: Needᵢ ≤ Available + Σ Allocationⱼ (j < i).
Avoidance simply refuses any request that would leave the safe zone.
Banker's Algorithm — The Data Structures
The fourth matrix, Need, is derived: what a process might still request. The algorithm has two
parts — the Safety Algorithm (is the current state safe?) and the Resource-Request
Algorithm (can I grant this specific request and stay safe?). Cost is O(m·n²) per request.
The Two Algorithms
# SAFETY ALGORITHM — is the state safe? Work = Available; Finish[i] = false for all i while ∃ i : Finish[i]==false and Need[i] <= Work: Work = Work + Allocation[i]; Finish[i] = true return "SAFE" if all Finish else "UNSAFE"
# RESOURCE-REQUEST ALGORITHM — can I grant Request from Pi? if Request > Need[i]: error # exceeds declared Max if Request > Available: return "WAIT" # pretend-grant, then test Available -= Request; Allocation[i] += Request; Need[i] -= Request if is_safe(): return "GRANTED" else: rollback(); return "DENIED — unsafe"
The request algorithm tentatively grants the request, runs the safety check, and only keeps the change if the result is safe — otherwise it rolls back and makes the process wait. It never risks an unsafe state.
Classic 5-Process Example — The Matrices
5 processes (P0–P4), 3 resources A/B/C. Total A=10, B=5, C=7; allocated A=7, B=2, C=5 → Available = [3, 3, 2].
| A | B | C | |
|---|---|---|---|
| P0 | 0 | 1 | 0 |
| P1 | 2 | 0 | 0 |
| P2 | 3 | 0 | 2 |
| P3 | 2 | 1 | 1 |
| P4 | 0 | 0 | 2 |
| A | B | C | |
|---|---|---|---|
| P0 | 7 | 5 | 3 |
| P1 | 3 | 2 | 2 |
| P2 | 9 | 0 | 2 |
| P3 | 2 | 2 | 2 |
| P4 | 4 | 3 | 3 |
| A | B | C | |
|---|---|---|---|
| P0 | 7 | 4 | 3 |
| P1 | 1 | 2 | 2 |
| P2 | 6 | 0 | 0 |
| P3 | 0 | 1 | 1 |
| P4 | 4 | 3 | 1 |
Start with Work = Available = [3,3,2] and find any process whose Need ≤ Work. Grant
it hypothetically, add its allocation back to Work, and repeat. The next slide traces it.
The Safety Trace — Building a Safe Sequence
| Pick | Need ≤ Work? | Work before | Work after (+Alloc) |
|---|---|---|---|
| P1 | [1,2,2] ≤ [3,3,2] ✓ | [3,3,2] | [6,4,3] |
| P3 | [0,1,1] ≤ [6,4,3] ✓ | [6,4,3] | [8,5,4] |
| P4 | [4,3,1] ≤ [8,5,4] ✓ | [8,5,4] | [8,5,6] |
| P0 | [7,4,3] ≤ [8,5,6] ✓ | [8,5,6] | [8,6,6] |
| P2 | [6,0,0] ≤ [8,6,6] ✓ | [8,6,6] | [10,5,7] — all free |
Worked Example — 4 Processes, Compute Available
4 processes (P0–P3), 3 resources A/B/C. Total A=8, B=5, C=6. Allocated = [7, 2, 4] → Available = [1, 3, 2].
| A | B | C | |
|---|---|---|---|
| P0 | 1 | 0 | 2 |
| P1 | 3 | 1 | 1 |
| P2 | 2 | 1 | 0 |
| P3 | 1 | 0 | 1 |
| A | B | C | |
|---|---|---|---|
| P0 | 4 | 3 | 3 |
| P1 | 4 | 2 | 3 |
| P2 | 5 | 2 | 2 |
| P3 | 5 | 3 | 3 |
| A | B | C | |
|---|---|---|---|
| P0 | 3 | 3 | 1 |
| P1 | 1 | 1 | 2 |
| P2 | 3 | 1 | 2 |
| P3 | 4 | 3 | 2 |
P0 fails first ([3,3,1] > [1,3,2] on A). But P1 fits → Work becomes [4,4,3]; now P0 fits → [5,4,5]; then P2 → [7,5,5]; then P3 → [8,5,6]. All finish, so the state is SAFE. Lesson: if the first process fails, try the next — don't stop.
Practice — 4 Processes, Resources X/Y/Z
4 processes (P0–P3), 3 resources X/Y/Z. Total X=9, Y=3, Z=6. Available = [1, 1, 2].
| X | Y | Z | |
|---|---|---|---|
| P0 | 2 | 1 | 1 |
| P1 | 1 | 0 | 1 |
| P2 | 4 | 1 | 2 |
| P3 | 1 | 0 | 0 |
| X | Y | Z | |
|---|---|---|---|
| P0 | 3 | 0 | 2 |
| P1 | 1 | 1 | 1 |
| P2 | 3 | 1 | 1 |
| P3 | 1 | 1 | 1 |
Starting from [1,1,2], P1 (need [1,1,1]) and P3 (need [1,1,1]) both fit — pick one, add its
allocation, and keep going. If you can order all four so every Need is met in turn, the state is safe. Try it
before checking your answer against the safety algorithm.
Prevention vs Avoidance
| Prevention | Avoidance (Banker's) | |
|---|---|---|
| Philosophy | Pessimistic — forbid risky patterns | Optimistic — allow if provably safe |
| When decided | Design time (structural) | Runtime (per request) |
| Needs max claims? | No | Yes — Max must be known in advance |
| Resource utilisation | Lower (over-restrictive) | Higher |
| Overhead | Low | O(m·n²) safety check per request |
| Best for | Simple, safety-critical systems | Known, bounded workloads |
Seven Rules for Prevention & Avoidance
Keeping Deadlock From Ever Happening
From breaking Coffman conditions to computing Need, running the safety algorithm, finding a safe sequence, and deciding whether to grant a resource request — you can solve any prevention or avoidance problem, by hand or in code.
You've completed the deadlock arc. Next in most courses come memory management — contiguous allocation, paging and segmentation — followed by virtual memory and page-replacement algorithms.
🏦 End of tutorial · Press ← to review, or click Restart