What Is the Banker’s Algorithm?
Learn the Banker’s Algorithm — safe-state checking, Max/Allocation/Need matrices — with an OS interview question and code example.
Expected Interview Answer
The Banker’s Algorithm is a deadlock-avoidance algorithm that grants a resource request only if the resulting system state is provably safe, meaning there still exists some order in which every process can finish with the resources available.
Before granting any request, the OS pretends to allocate it and then runs the safety algorithm: it looks for a process whose remaining maximum need can be satisfied by the currently available resources, marks it as finishable, adds its resources back to the available pool, and repeats until either every process is marked finishable (safe state, so the request is granted) or no process can proceed (unsafe state, so the request is denied and the process waits). This requires the OS to know in advance each process’s maximum possible claim for every resource type, tracked in a Max matrix alongside Allocation and Need matrices. Because it checks every request against every possible future execution order, it guarantees the system never enters a state that could deadlock, at the cost of requiring upfront knowledge of maximum demands and repeated O(n*m) safety checks on every request.
- Guarantees the system never enters an unsafe, potentially deadlocking state
- Grants resources dynamically rather than reserving worst-case totals upfront
- Provides a formal, provable safety check before every allocation
- Foundational for understanding deadlock avoidance versus prevention
AI Mentor Explanation
The Banker’s Algorithm is like a groundstaff manager who only lends out extra practice nets to a team if, after lending them, there is still some order in which every team currently training can eventually finish using the nets they need. Before saying yes, the manager mentally simulates: can Team A finish with what is left, freeing its nets for Team B, and so on until everyone is done? If any lending leaves a point where no team can proceed with what remains, the manager refuses that request, even though nets are technically available. This upfront simulation is exactly what keeps the ground from ever reaching a stuck, no-one-can-train state.
Step-by-Step Explanation
Step 1
Track state
Maintain Max (maximum claim per process), Allocation (currently held), and Need = Max - Allocation matrices, plus an Available vector.
Step 2
Simulate the request
On a request, tentatively subtract it from Available and add it to that process’s Allocation.
Step 3
Run the safety algorithm
Repeatedly find a process whose Need fits within Available, mark it finishable, and add its Allocation back to Available.
Step 4
Grant or deny
If every process gets marked finishable, the state is safe and the request is granted; otherwise it is rolled back and the process waits.
What Interviewer Expects
- A clear definition tied to safe-state checking before granting a request
- Knowledge of the Max, Allocation, Need, and Available data structures
- Ability to walk through the safety algorithm at a high level
- Awareness of the practical limitation: requires knowing maximum claims in advance
Common Mistakes
- Confusing the Banker’s Algorithm with deadlock detection (it avoids, not detects after the fact)
- Forgetting it requires each process to declare its maximum resource claim upfront
- Thinking it prevents deadlock by denying all concurrent requests rather than checking safety
- Not knowing the difference between a safe state and an unsafe state
Best Answer (HR Friendly)
“The Banker’s Algorithm is a way for the operating system to act cautiously, like a careful banker who never lends out more than can be repaid. Before handing a process any extra resource, it mentally checks whether every currently running process could still finish in some order with what would be left, and only grants the request if that check passes. It trades a bit of upfront bookkeeping for a strong guarantee that the system never gets stuck.”
Code Example
#define N 4 /* processes */
#define M 3 /* resource types */
int available[M];
int max_claim[N][M];
int allocation[N][M];
int need[N][M]; /* need[i][j] = max_claim[i][j] - allocation[i][j] */
int is_safe_state(void) {
int work[M];
int finish[N] = {0};
for (int j = 0; j < M; j++) work[j] = available[j];
int progress = 1;
while (progress) {
progress = 0;
for (int i = 0; i < N; i++) {
if (finish[i]) continue;
int can_finish = 1;
for (int j = 0; j < M; j++) {
if (need[i][j] > work[j]) { can_finish = 0; break; }
}
if (can_finish) {
for (int j = 0; j < M; j++) work[j] += allocation[i][j];
finish[i] = 1;
progress = 1; /* found one, keep scanning */
}
}
}
for (int i = 0; i < N; i++) {
if (!finish[i]) return 0; /* some process can never finish: unsafe */
}
return 1; /* every process can finish in some order: safe */
}Follow-up Questions
- What is the difference between a safe state and an unsafe state?
- Why does the Banker’s Algorithm require processes to declare a maximum claim in advance?
- How does deadlock avoidance differ from deadlock prevention?
- What is the time complexity of the safety algorithm, and why does it matter for many processes?
MCQ Practice
1. What does the Banker’s Algorithm check before granting a resource request?
It tentatively grants the request and runs the safety algorithm to confirm a completion order still exists for all processes.
2. What must every process declare in advance for the Banker’s Algorithm to work?
The Max matrix, declared upfront by each process, is required to compute Need and run the safety check.
3. If the safety algorithm cannot mark every process finishable, what happens to the request?
An unsafe resulting state means the tentative allocation is rolled back and the requesting process waits.
Flash Cards
What is the Banker’s Algorithm? — A deadlock-avoidance algorithm that grants a request only if the resulting state is provably safe.
What three matrices does it track? — Max, Allocation, and Need (Need = Max - Allocation), plus an Available vector.
What is a safe state? — A state where some order exists in which every process can finish with available resources.
What is the algorithm’s main practical limitation? — It requires each process to declare its maximum resource claim in advance.