Prevention — Break a Coffman Condition
- Mutual exclusion — sometimes unavoidable (printers). Spooling avoids it for some devices.
- Hold and wait — require processes to request all resources upfront; or release everything before requesting more. Drawback: low utilization, possible starvation.
- No preemption — if a process holding resources requests more and is denied, force it to release everything; restart later.
- Circular wait — impose a total order on resource types; processes must request in increasing order. Effective and widely used in kernels.
Avoidance — Banker's Algorithm
Avoidance allows all four conditions but dynamically rejects any allocation that would put the system into an unsafe state. Requires advance knowledge of each process's maximum need.
State Variables
- n = number of processes, m = number of resource types.
- Available[m] — currently free instances of each type.
- Max[n][m] — maximum demand of each process.
- Allocation[n][m] — currently allocated.
- Need[n][m] = Max - Allocation.
Safe State
A state is safe if there exists a sequence ⟨P_{i1}, P_{i2}, ..., P_{in}⟩ such that for each P_{ik}, its remaining Need can be satisfied by Available + the allocations of all P_{ij} (j < k).
Safety Algorithm
- Work = Available, Finish = [false, ...].
- Find i with Finish[i] = false and Need[i] ≤ Work. If none, stop.
- Work += Allocation[i]; Finish[i] = true. Goto 2.
- If all Finish[i] = true, state is safe.
Resource-Request Algorithm
On request Request[i] from process Pi:
- If Request[i] > Need[i]: error.
- If Request[i] > Available: Pi waits.
- Pretend to allocate: Available -= Request; Allocation[i] += Request; Need[i] -= Request.
- Run safety algorithm.
- If safe → grant.
- Else → roll back the pretence and Pi waits.
Worked Example
Three resource types A=10, B=5, C=7. Five processes:
| Process | Allocation A,B,C | Max A,B,C | Need A,B,C |
|---|---|---|---|
| P0 | 0,1,0 | 7,5,3 | 7,4,3 |
| P1 | 2,0,0 | 3,2,2 | 1,2,2 |
| P2 | 3,0,2 | 9,0,2 | 6,0,0 |
| P3 | 2,1,1 | 2,2,2 | 0,1,1 |
| P4 | 0,0,2 | 4,3,3 | 4,3,1 |
Available = 10 - 7, 5 - 2, 7 - 5 = (3,3,2).
Run safety: Work = (3,3,2). Need P1 = (1,2,2) ≤ Work → finish P1, Work = (5,3,3). Need P3 = (0,1,1) ≤ Work → finish P3, Work = (7,4,4). Need P0, Need P2, Need P4 each fit in turn → safe sequence ⟨P1,P3,P4,P2,P0⟩.
Now P1 requests (1,0,2). Available becomes (2,3,0); Allocation P1 = (3,0,2); Need P1 = (0,2,0). Re-run safety → still safe → grant.
But if P0 then requests (0,2,0), Available (2,1,0) — re-run safety; if no sequence found, deny.
Summary
- Prevention is conservative; Banker's avoidance is dynamic but needs Max info upfront.
- Safety algorithm runs in O(m·n²) — feasible only for moderate workloads.
- Most general-purpose OSes prefer detection or "ignore".