101
0/227
Loading content...
We've now learned all the components of the Banker's Algorithm:
This final page brings everything together in a comprehensive worked example. We'll walk through a realistic scenario with multiple processes making requests over time, seeing exactly how the algorithm grants some requests, denies others, and maintains system safety throughout.
This is the kind of detailed trace you might work through in an exam, a code review, or when debugging a real deadlock avoidance implementation.
By the end of this page, you will have traced through a complete multi-request scenario, seeing grant decisions, denial decisions, process completions, and resource releases. You'll understand exactly how the Banker's Algorithm maintains safety through a dynamic sequence of operations.
Scenario: We're managing resources in a file server with 5 client processes. Each process needs combinations of three resource types to complete its tasks.
Resource Types:
Processes:
| Process | Allocation (A,B,C) | Max (A,B,C) | Need (A,B,C) |
|---|---|---|---|
| P₀ | (0, 1, 0) | (7, 5, 3) | (7, 4, 3) |
| P₁ | (2, 0, 0) | (3, 2, 2) | (1, 2, 2) |
| P₂ | (3, 0, 2) | (9, 0, 2) | (6, 0, 0) |
| P₃ | (2, 1, 1) | (2, 2, 2) | (0, 1, 1) |
| P₄ | (0, 0, 2) | (4, 3, 3) | (4, 3, 1) |
| Total | (7, 2, 5) | — | — |
Available Resources:
Available = Total - Allocated
= (10, 5, 7) - (7, 2, 5)
= (3, 3, 2)
Initial Safety Check:
Before processing any requests, let's verify the initial state is safe.
We already traced through the safety algorithm for this state in earlier pages. The safe sequence is <P₁, P₃, P₀, P₂, P₄>. The system starts in a safe state, ready to accept requests.
We'll process the following sequence of events:
| Time | Event | Details |
|---|---|---|
| T₁ | P₁ requests | (1, 0, 2) — additional file handles and disk channels |
| T₂ | P₄ requests | (3, 3, 0) — file handles and network buffers |
| T₃ | P₀ requests | (0, 2, 0) — additional network buffers |
| T₄ | P₁ completes | Releases all resources |
| T₅ | P₃ requests | (0, 0, 1) — one more disk channel |
| T₆ | P₃ completes | Releases all resources |
| T₇ | P₄ re-requests | (3, 3, 0) — retry earlier denied request |
Let's trace through each event in detail.
Current State:
Request: P₁ requests (1, 0, 2)
Step 1 — Validate Request:
Is Request ≤ Need[1]?
(1, 0, 2) ≤ (1, 2, 2)?
1 ≤ 1 ✓
0 ≤ 2 ✓
2 ≤ 2 ✓
✓ Valid request
Step 2 — Check Availability:
Is Request ≤ Available?
(1, 0, 2) ≤ (3, 3, 2)?
1 ≤ 3 ✓
0 ≤ 3 ✓
2 ≤ 2 ✓
✓ Resources available
Step 3 — Tentative Allocation:
New Available = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)
New Allocation[1] = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)
New Need[1] = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)
Step 4 — Safety Check with New State:
| Process | New Allocation | New Need | Work | Need ≤ Work? |
|---|---|---|---|---|
| P₀ | (0, 1, 0) | (7, 4, 3) | (2, 3, 0) | 7>2 ✗ |
| P₁ | (3, 0, 2) | (0, 2, 0) | (2, 3, 0) | 0≤2, 2≤3, 0≤0 ✓ |
P₁ can complete. New Work = (2, 3, 0) + (3, 0, 2) = (5, 3, 2)
Continuing the safety check...
| Process | Need | Work=(5,3,2) | Need ≤ Work? | New Work if Complete |
|---|---|---|---|---|
| P₀ | (7, 4, 3) | 7>5 ✗ | — | — |
| P₂ | (6, 0, 0) | 6>5 ✗ | — | — |
| P₃ | (0, 1, 1) | 0≤5, 1≤3, 1≤2 ✓ | Complete | (5,3,2)+(2,1,1)=(7,4,3) |
Work = (7, 4, 3). Now:
All processes can complete. State is SAFE.
Safe sequence found: <P₁, P₃, P₀, P₂, P₄>
P₁'s request for (1, 0, 2) is granted. The allocation is committed.
| Process | Allocation | Need |
|---|---|---|
| P₀ | (0, 1, 0) | (7, 4, 3) |
| P₁ | (3, 0, 2) | (0, 2, 0) |
| P₂ | (3, 0, 2) | (6, 0, 0) |
| P₃ | (2, 1, 1) | (0, 1, 1) |
| P₄ | (0, 0, 2) | (4, 3, 1) |
Available after T₁: (2, 3, 0)
Current State:
Request: P₄ requests (3, 3, 0)
Step 1 — Validate Request:
Is Request ≤ Need[4]?
(3, 3, 0) ≤ (4, 3, 1)?
3 ≤ 4 ✓
3 ≤ 3 ✓
0 ≤ 1 ✓
✓ Valid request
Step 2 — Check Availability:
Is Request ≤ Available?
(3, 3, 0) ≤ (2, 3, 0)?
3 > 2 ✗
P₄ is requesting 3 instances of resource A, but only 2 are available. The request cannot be granted regardless of safety. P₄ must wait.
State unchanged. P₄ is blocked, waiting for type A resources.
Available after T₂: (2, 3, 0) (unchanged)
Current State:
Request: P₀ requests (0, 2, 0)
Step 1 — Validate Request:
(0, 2, 0) ≤ (7, 4, 3)? ✓ Valid
Step 2 — Check Availability:
(0, 2, 0) ≤ (2, 3, 0)? ✓ Available
Step 3 — Tentative Allocation:
New Available = (2, 3, 0) - (0, 2, 0) = (2, 1, 0)
New Allocation[0] = (0, 1, 0) + (0, 2, 0) = (0, 3, 0)
New Need[0] = (7, 4, 3) - (0, 2, 0) = (7, 2, 3)
Step 4 — Safety Check:
| Process | Allocation | Need | Work=(2,1,0) | Need ≤ Work? |
|---|---|---|---|---|
| P₀ | (0, 3, 0) | (7, 2, 3) | 7>2, 3>0 ✗ | No |
| P₁ | (3, 0, 2) | (0, 2, 0) | 2>1 ✗ | No |
| P₂ | (3, 0, 2) | (6, 0, 0) | 6>2 ✗ | No |
| P₃ | (2, 1, 1) | (0, 1, 1) | 1≤1, 1>0 ✗ | No |
| P₄ | (0, 0, 2) | (4, 3, 1) | 4>2, 3>1, 1>0 ✗ | No |
No process can complete with Work = (2, 1, 0).
With zero disk channels (type C) available and every process needing at least something, the system is deadlock-prone. The algorithm scans all processes and finds none that can satisfy their remaining needs.
Safety Algorithm returns: UNSAFE
Even though (0, 2, 0) ≤ Available, granting this request would leave the system in an unsafe state. The allocation is rolled back, and P₀ must wait.
This is the key insight of deadlock avoidance: P₀ asked for resources that were available, but granting them would have committed the system to a state where deadlock could occur.
State unchanged. P₀ is blocked.
Available after T₃: (2, 3, 0) (unchanged)
Event: P₁ finishes its work and releases all resources.
P₁'s current allocation: (3, 0, 2)
Resource Release:
New Available = (2, 3, 0) + (3, 0, 2) = (5, 3, 2)
Allocation[1] = (0, 0, 0) // P₁ finished
Need[1] = (0, 0, 0) // P₁ needs nothing more
Releasing resources only increases Available, which can only improve system safety. We don't need to run the safety algorithm on release—only on allocation.
Wake Up Blocked Processes:
With more resources now available, we should re-evaluate blocked processes:
Let's check if their requests can now be granted. Re-run their pending requests.
| Process | Allocation | Need | Status |
|---|---|---|---|
| P₀ | (0, 1, 0) | (7, 4, 3) | Blocked (was unsafe) |
| P₁ | (0, 0, 0) | (0, 0, 0) | Completed |
| P₂ | (3, 0, 2) | (6, 0, 0) | Active |
| P₃ | (2, 1, 1) | (0, 1, 1) | Active |
| P₄ | (0, 0, 2) | (4, 3, 1) | Blocked (insufficient) |
Available after T₄: (5, 3, 2)
Note: In a real system, the OS would now re-evaluate pending requests from blocked processes. For our walkthrough, we'll let P₃ and P₄ make their moves first.
Current State:
Request: P₃ requests (0, 0, 1) — its remaining disk channel need
Step 1 — Validate:
(0, 0, 1) ≤ (0, 1, 1)? ✓
Step 2 — Available:
(0, 0, 1) ≤ (5, 3, 2)? ✓
Step 3 — Tentative Allocation:
New Available = (5, 3, 2) - (0, 0, 1) = (5, 3, 1)
New Allocation[3] = (2, 1, 1) + (0, 0, 1) = (2, 1, 2)
New Need[3] = (0, 1, 1) - (0, 0, 1) = (0, 1, 0)
Step 4 — Safety Check:
| Process | Need | Work=(5,3,1) | Need ≤ Work? |
|---|---|---|---|
| P₀ | (7, 4, 3) | 7>5, 4>3, 3>1 ✗ | No |
| P₂ | (6, 0, 0) | 6>5 ✗ | No |
| P₃ | (0, 1, 0) | 0≤5, 1≤3, 0≤1 ✓ | Yes! Complete |
P₃ can complete. Work = (5,3,1) + (2,1,2) = (7, 4, 3)
Continuing:
All processes can complete. State is SAFE.
P₃'s request for (0, 0, 1) is granted.
State after T₅:
Event: P₃ finishes its work and releases all resources.
Note: P₃ completed without needing its full Max claim. Its remaining Need was (0, 1, 0), but it chose not to request that final network buffer.
P₃'s current allocation: (2, 1, 2)
Resource Release:
New Available = (5, 3, 1) + (2, 1, 2) = (7, 4, 3)
Allocation[3] = (0, 0, 0)
Need[3] = (0, 0, 0)
The Max claim is an upper bound, not an exact prediction. Processes often finish without reaching their maximum needs. This is why unsafe states don't always lead to deadlock—processes may be 'well-behaved' and not request all they could.
| Process | Allocation | Need | Status |
|---|---|---|---|
| P₀ | (0, 1, 0) | (7, 4, 3) | Blocked |
| P₁ | (0, 0, 0) | (0, 0, 0) | Completed |
| P₂ | (3, 0, 2) | (6, 0, 0) | Active |
| P₃ | (0, 0, 0) | (0, 0, 0) | Completed |
| P₄ | (0, 0, 2) | (4, 3, 1) | Blocked |
Available after T₆: (7, 4, 3)
With substantial resources now available, let's see if blocked requests can proceed.
Current State:
Request: P₄ requests (3, 3, 0) — same request that was blocked at T₂
Step 1 — Validate:
(3, 3, 0) ≤ (4, 3, 1)? ✓
Step 2 — Available:
(3, 3, 0) ≤ (7, 4, 3)? ✓ (Previously failed: 3 > 2)
Now resources are available!
Step 3 — Tentative Allocation:
New Available = (7, 4, 3) - (3, 3, 0) = (4, 1, 3)
New Allocation[4] = (0, 0, 2) + (3, 3, 0) = (3, 3, 2)
New Need[4] = (4, 3, 1) - (3, 3, 0) = (1, 0, 1)
Step 4 — Safety Check:
| Process | Allocation | Need | Work=(4,1,3) | Need ≤ Work? |
|---|---|---|---|---|
| P₀ | (0, 1, 0) | (7, 4, 3) | 7>4, 4>1, 3≤3 ✗ | No |
| P₂ | (3, 0, 2) | (6, 0, 0) | 6>4 ✗ | No |
| P₄ | (3, 3, 2) | (1, 0, 1) | 1≤4, 0≤1, 1≤3 ✓ | Yes! |
P₄ can complete. Work = (4,1,3) + (3,3,2) = (7, 4, 5)
Continuing:
All processes can complete. State is SAFE.
P₄'s request for (3, 3, 0) is now granted! The same request that was blocked at T₂ succeeds now that more resources are available.
Final State after T₇:
| Process | Allocation | Need | Status |
|---|---|---|---|
| P₀ | (0, 1, 0) | (7, 4, 3) | Blocked |
| P₁ | (0, 0, 0) | (0, 0, 0) | Completed |
| P₂ | (3, 0, 2) | (6, 0, 0) | Active |
| P₃ | (0, 0, 0) | (0, 0, 0) | Completed |
| P₄ | (3, 3, 2) | (1, 0, 1) | Active |
Available: (4, 1, 3)
Let's summarize what happened across our scenario:
| Time | Event | Request | Result | Reason |
|---|---|---|---|---|
| T₁ | P₁ requests | (1, 0, 2) | ✓ Granted | Safe sequence exists |
| T₂ | P₄ requests | (3, 3, 0) | ⏳ Blocked | Insufficient A (3 > 2) |
| T₃ | P₀ requests | (0, 2, 0) | ✗ Denied | Would create unsafe state |
| T₄ | P₁ completes | — | Released (3,0,2) | Available increased |
| T₅ | P₃ requests | (0, 0, 1) | ✓ Granted | Safe sequence exists |
| T₆ | P₃ completes | — | Released (2,1,2) | Available increased |
| T₇ | P₄ retries | (3, 3, 0) | ✓ Granted | Now sufficient and safe |
Notice that P₀ is still blocked at the end of our scenario. With Need = (7, 4, 3) and Available = (4, 1, 3), there's no way P₀ alone can complete. P₀ must wait for P₂ and/or P₄ to complete and release resources. This shows how processes with high resource needs can experience significant delays.
This concludes our comprehensive coverage of the Banker's Algorithm. Let's consolidate everything we've learned:
You've now mastered the Banker's Algorithm—from theoretical foundations to practical implementation. You can analyze system states, determine safety, process requests, and understand when and why the algorithm makes its decisions. This knowledge applies to database systems, resource managers, cloud platforms, and any system that must guarantee deadlock freedom.