Deadlock avoidance — Banker's algorithm

WHY does this algorithm exist?

WHY "safe" matters: A state is safe if there exists at least one ordering of processes (a safe sequence) such that each process can get its remaining needs, run to completion, and release everything. Unsafe ≠ deadlocked — it just means deadlock might become unavoidable. The banker refuses to ever enter an unsafe state, so deadlock can never occur.

WHAT are the data structures?

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

HOW: the Safety Algorithm (derived from scratch)

We want to answer: "Given the current allocation, can everyone finish?"

Step 0 — set up bookkeeping.

• $Work = Available$ (the free pool we can hand out as we simulate).
• $Finish[i] = false$ for all $i$ (nobody has finished yet).

WHY $Work$ starts at $Available$: before anyone finishes, the only resources we can lend are the ones currently free.

Step 1 — find a process that can finish right now. Look for $i$ with $Finish[i] = false$ and $Need[i] \le Work$ (componentwise).

WHY: if a process's remaining need fits in the free pool, we can imagine giving it everything, letting it run, and getting it all back.

Step 2 — pretend it finishes and returns its resources. $Work = Work + Allocation[i], \qquad Finish[i] = true$

WHY add $Allocation[i]$, not $Max[i]$: when it finishes it releases everything it held, which is $Allocation$. Its $Need$ was already covered from $Work$ in step 1.

Step 3 — repeat until no such process exists.

Step 4 — decide. If $Finish[i] = true$ for all $i$ → state is safe; the order we picked is a safe sequence. Otherwise unsafe.

HOW: the Resource-Request Algorithm

Process $P_i$ makes request $Request_i$.

WHY pretend-then-check: the only way to know a grant is safe is to look at the resulting state and verify a safe sequence still exists.

Worked Example 1 — Is the state safe?

3 resource types $A, B, C$ with total $= (10,5,7)$.

Available $= Total - \sum Allocation = (10,5,7) - (7,2,5) = (3,3,2)$. Why this step? Free = total minus everything held.

Need = Max − Allocation: P0 (7 4 3), P1 (1 2 2), P2 (6 0 0), P3 (0 1 1), P4 (4 3 1).

Now run Safety with $Work=(3,3,2)$:

• $Need_{P1}=(1,2,2)\le(3,3,2)$ ✓ → finish P1, $Work=(3,3,2)+(2,0,0)=(5,3,2)$. Why add Alloc P1? It releases its held resources.
• $Need_{P3}=(0,1,1)\le(5,3,2)$ ✓ → $Work=(5,3,2)+(2,1,1)=(7,4,3)$.
• $Need_{P0}=(7,4,3)\le(7,4,3)$ ✓ → $Work=(7,4,3)+(0,1,0)=(7,5,3)$.
• $Need_{P2}=(6,0,0)\le(7,5,3)$ ✓ → $Work=(7,5,3)+(3,0,2)=(10,5,5)$.
• $Need_{P4}=(4,3,1)\le(10,5,5)$ ✓ → $Work=(10,5,7)$. All finished.

Safe sequence: $\langle P1, P3, P0, P2, P4\rangle$. State is SAFE. ✅

Worked Example 2 — Should we grant a request?

From Example 1's state, $P1$ requests $Request_1=(1,0,2)$.

1. $(1,0,2)\le Need_{P1}(1,2,2)$? ✓
2. $(1,0,2)\le Available(3,3,2)$? ✓
3. Pretend-grant:
   • $Available = (3,3,2)-(1,0,2)=(2,3,0)$
   • $Alloc_{P1}=(2,0,0)+(1,0,2)=(3,0,2)$
   • $Need_{P1}=(1,2,2)-(1,0,2)=(0,2,0)$

Run Safety with $Work=(2,3,0)$:

• P1 $Need(0,2,0)\le(2,3,0)$ ✓ → $Work=(2,3,0)+(3,0,2)=(5,3,2)$
• P3 $(0,1,1)\le(5,3,2)$ ✓ → $Work=(7,4,3)$
• P0 $(7,4,3)\le(7,4,3)$ ✓ → $Work=(7,5,3)$ ... P2, P4 follow.

Safe sequence $\langle P1,P3,P0,P2,P4\rangle$ exists → GRANT. ✅ Why we still verify after pretending? Because availability dropped; we must confirm everyone can still finish.

Worked Example 3 — A request that is refused

From Example 1, suppose $P4$ requests $(3,3,0)$.

• $\le Need_{P4}(4,3,1)$? ✓
• $\le Available(3,3,2)$? ✓ → pretend: $Available=(0,0,2)$.

Run Safety with $Work=(0,0,2)$: scan needs P0(7 4 3)✗, P1(1 2 2)✗, P2(6 0 0)✗, P3(0 1 1)✗ (B short), P4(1 0 1)✗. No process can proceed → UNSAFE → rollback, P4 waits. ❌ Why refuse a request that "fits"? Fitting in $Available$ isn't enough — the resulting state has no safe sequence.

Common mistakes

Flashcards

Connections

• Deadlock — Coffman conditions
• Deadlock detection and recovery
• Deadlock prevention
• Resource Allocation Graph
• Process scheduling
• Semaphores and mutual exclusion

Concept Map

Hinglish (regional understanding)