Banker's Algorithm
The Banker's Algorithm is the standard deadlock avoidance method, deciding whether to grant a resource request by simulating the grant and checking whether a safe completion order for every process still exists. Each process must declare its maximum need for each resource type in advance, and a request is granted only if the resulting state is safe.
The Banker's Algorithm is the standard method for deadlock avoidance. Its name comes from the analogy of a banker who will only lend money if, after the loan, there's still some guaranteed way for every customer to eventually be repaid in full, given the bank's cash on hand and the loans customers are expected to eventually repay.
The data it needs
Every process must declare its maximum possible need for each resource type in advance. From that, the algorithm tracks three things per resource type: total instances, currently available instances, and for each process, its maximum need and current allocation. The difference between max need and current allocation is that process's remaining need.
How a request is evaluated, step by step
- A process requests some number of additional instances of a resource.
- Check that the request doesn't exceed the process's declared remaining need, and doesn't exceed what's currently available. If either check fails, the process simply waits.
- Pretend to grant the request: temporarily reduce available resources and increase that process's allocation.
- Run the safety check: try to find an order in which every process (including the one that just got resources) can finish, using only what's available plus what gets released as each process completes.
- If a safe order exists, actually commit the grant. If no safe order exists, undo the pretend grant and make the process wait instead, even though the resources were physically available.
A worked example
Three processes, one resource type with 10 total instances.
| Process | Max Need | Currently Holding |
|---|---|---|
| P1 | 7 | 3 |
| P2 | 5 | 2 |
| P3 | 4 | 2 |
Currently allocated: 3 + 2 + 2 = 7. Available: 10 - 7 = 3.
Now P2 requests 1 more instance. Check: P2's remaining need was 5 - 2 = 3, requesting 1 is within that. Available is 3, so 1 is also physically available.
Pretend to grant: P2's allocation becomes 3, available drops to 2.
Safety check: can any process finish with 2 available? P2 now needs 5 - 3 = 2 more, exactly available, so P2 can finish, releasing 3, giving 2 + 3 = 5 available. P1 needs 7 - 3 = 4 more, available is 5, so P1 can finish, releasing 3, giving 5 + 3 = 8. P3 needs 4 - 2 = 2 more, available is 8, so P3 finishes too.
A safe order exists (P2, P1, P3), so the request is genuinely granted.
Where this matters in real systems
The Banker's Algorithm itself is rarely implemented literally in general-purpose operating systems, since it demands every process know and declare its maximum resource usage before it even starts, which most real software can't predict. Its real legacy is conceptual: the same safe-state reasoning underlies resource governors in some real-time operating systems and embedded control systems, where resource needs genuinely are known in advance and the cost of a deadlock (a stalled aircraft control system, for instance) is unacceptable.
What interviewers actually ask about the Banker's Algorithm
- "Walk me through how the Banker's Algorithm decides to grant or deny a request." Pretend to grant it, run the safety check for a completion order, commit if safe, roll back and make the process wait if not.
- "What must a process declare before the algorithm can be used?" Its maximum possible need for each resource type, in advance.
- "Why is a request sometimes denied even though the resources are physically available?" Because granting it, while physically possible, could lead to a state where no safe completion order exists for all processes.
- "What's the time complexity concern with running the Banker's Algorithm frequently?" The safety check needs to search over process/resource states, which scales with the number of processes and resource types, making it too expensive to run on every single resource request in a large, dynamic general-purpose system.
Key takeaways
- The Banker's Algorithm only grants a resource request if doing so leaves the system in a state where a safe completion order for all processes still exists.
- It requires every process to declare its maximum resource need upfront.
- A request can be denied even when resources are physically available, if granting it risks an unsafe state.
- Its practicality is mostly limited to systems where resource needs really are known in advance, like specialized real-time systems.
More in Deadlocks
Browse all Operating Systems topics
Log in to save which topics you've read across every subject.
Frequently asked questions
Walk me through how the Banker's Algorithm decides to grant or deny a request.
Pretend to grant it, run the safety check for a completion order, commit if safe, roll back and make the process wait if not.
What must a process declare before the algorithm can be used?
Its maximum possible need for each resource type, in advance.
Why is a request sometimes denied even though the resources are physically available?
Because granting it, while physically possible, could lead to a state where no safe completion order exists for all processes.
What's the time complexity concern with running the Banker's Algorithm frequently?
The safety check needs to search over process/resource states, which scales with the number of processes and resource types, making it too expensive to run on every single resource request in a large, dynamic general-purpose system.