Banker's Algorithm
Scenario
A small-town bank has $10,000 in cash. Three local businesses have credit lines totaling $20,000. The banker must carefully approve loans so that there's always enough cash to let at least one business finish its project, pay back its entire loan, and fund the others.
Mental model
The OS acts like a banker, only lending out resources if it can guarantee a path for everyone to eventually finish and return what they borrowed.
The Banker's Algorithm is a deadlock avoidance strategy. It tracks the maximum possible resource needs of every process, what they currently hold, and what is currently available. Before granting a request, it simulates the allocation. If the system can find a 'safe sequence' where all processes can theoretically finish one by one, the request is approved.
Explanation
The Banker's Algorithm, developed by Edsger Dijkstra, is the most famous algorithm for Deadlock Avoidance. It gets its name from how a bank manages liquidity: a bank never lends out so much money that it can't satisfy the maximum credit limit of at least one of its customers. If it did, and all customers suddenly maxed out their credit, the bank would go bankrupt (deadlock).
To make this work, the OS requires three pieces of information upfront: the 'Maximum' resources each process might need, the 'Allocation' of resources each process currently has, and the 'Available' resources currently free in the system. By subtracting Allocation from Maximum, the OS calculates the 'Need' matrix—how many more resources each process might request to finish its job.
When a process requests a resource, the OS pretends to grant it. It updates the matrices and runs a safety check. The safety check looks for a process whose remaining 'Need' is less than or equal to the 'Available' pool. If it finds one, it assumes that process will finish and return all its resources, adding them back to the 'Available' pool.
The algorithm repeats this step, looking for the next process that can finish with the newly expanded 'Available' pool. If it can find a sequence that allows every single process to finish, this is called a 'Safe Sequence'. The simulated state is deemed a 'Safe State', and the original resource request is permanently granted.
However, if the simulation gets stuck—meaning no process can finish with the available resources—the state is 'Unsafe'. An unsafe state isn't a deadlock yet, but it means deadlock is possible if processes request their maximum needs. To avoid this, the OS denies the request, forcing the process to wait until more resources are freed up by others.
Key points
- Max Matrix: The maximum number of resources a process will ever request during its execution.
- Need Matrix: Calculated as Max minus Allocation. It represents what the process still requires to complete.
- Safe Sequence: An execution order of processes where each process can finish using currently available resources plus the resources released by previously finished processes.
Common mistakes
- Confusing an Unsafe State with Deadlock: An unsafe state means a deadlock COULD happen, not that it HAS happened. The algorithm prevents the system from ever entering an unsafe state.
- Assuming it is highly practical: In reality, it is very difficult to know the exact maximum resource needs of a process before it runs, making the Banker's Algorithm more of a theoretical cornerstone than a widely implemented OS feature.
Glossary
- Bankers Algorithm
- A resource allocation strategy used by operating systems to carefully grant resources to programs, ensuring the system never gets stuck in a deadlock where everyone is waiting.
- Safe Sequence
- A theoretical order of execution where all running programs can finish their tasks one by one using currently available resources without getting stuck.
- Unsafe state
- A vulnerable system condition where resources have been handed out in such a way that a deadlock could occur if every program simultaneously requested all the remaining resources they need.
Recall questions
- How is the 'Need' of a process calculated in the Banker's Algorithm?
- What happens if a resource request leads to an unsafe state?
- Why is the Banker's Algorithm rarely used in modern operating systems?
Questions & answers
A system has 10 tape drives. Process A needs max 9, currently holds 3. Process B needs max 4, holds 2. Process C needs max 7, holds 3. Is the system in a safe state?
Yes. Total held = 8. Available = 2. Process B needs 2, so it can finish. It releases 4. Available = 6. Process C needs 4, it finishes, releases 7. Available = 13. Process A finishes.
Approach: Calculate Need: A=6, B=2, C=4. Available = 10 - (3+2+3) = 2. Find a sequence where Need <= Available.
In the context of the Banker's Algorithm, define a 'safe state'.
A state is safe if there exists at least one sequence of all processes such that each process can be satisfied by the currently available resources plus the resources held by all previously finished processes in the sequence.
Approach: Focus on the existence of a guaranteed completion sequence without getting trapped.
Continue learning
Previous: Deadlock: Prevention vs Avoidance