Dijkstra's Banker's algorithm: a detailed explanation with example and C++ code
Dijkstra's Banker's algorithm is a resource allocation and deadlock avoidance algorithm that tests whether granting a resource request will leave the system in a safe state. Developed by Edsger Dijkstra, it simulates each allocation in advance and only approves requests that keep every process able to finish. This guide walks through the algorithm with a worked example, the formal safety check, and a C++ implementation.
What is Banker's algorithm?
The Banker's algorithm sometimes referred to as avoidance algorithm or Deadlock algorithm was developed by Edsger Dijkstra (not to be confused with Dijkstra's shortest path algorithm — the two share an author but solve entirely different problems).
It tests the safety of allocating predetermined maximum resources by performing an s-state check for possible deadlock conditions. Only if that check passes is the allocation allowed to proceed. (Wikipedia: Banker's algorithm)
Banker's algorithm explained
Let's say you've got three friends (A, B, and C) who need a loan to tide them over for a bit.
You have $24 with you.
A needs $8, B needs $13, and C needs $10.
You already lent $6 to A, $8 to B, and $7 to C.
So you are left with $24 – $21 (6+8+7) = $3
Even after giving $6 to A, he still needs $2.Similarly, B needs $5 more and C $3.
Until they get the amount they need, they can neither do whatever tasks they have to nor return the amount they borrowed. (Like a true friend!)
You can pay $2 to A, and wait for him to get his work done and then get back the entire $8.
Or, you can pay $3 to C and wait for him to pay you back after his task is done.
Figure 1: Safe-state allocation across three borrowers with the lender's remaining balance. Source: HackerEarth.
You can't pay B because he needs $5 and you don't have enough.
You can pay him once A or C returns the borrowed amount after their work is done.
This state is termed as the safe state, where everyone's task is completed and, eventually, you get all your money back.
The second scenario — deadlock explained
Knowing B needs $10 urgently, instead of giving $8, you end up giving him $10.
And you are left with only $1.
In this state, A still needs $2 more, B needs $3 more, and C still needs $3 more, but now you don't have enough money to give them and until they complete the tasks they need the money for, no money will be transferred back to you.
This kind of situation is called an unsafe state — a state from which deadlock may occur (though it is not guaranteed). The Banker's algorithm avoids ever entering such a state.
Let's get back to the previous safe state.
You give $2 to A and let him complete his work.
He returns your $8 which leaves you with $9. Out of this $9, you can give $5 to B and let him finish his task with total $13 and then return the amount to you, which can be forwarded to C to eventually let him complete his task.
The goal of the Banker's algorithm is to handle all requests without entering an unsafe state — a state from which deadlock may become unavoidable.
It's called the Banker's algorithm because it could be used in the banking system so that banks never run out of resources and always stay in a safe state. If you want a broader primer on how such procedures underpin modern systems, see what an algorithm is and how it shapes our world.
Formal definitions and notation
To translate the analogy into operating-system terms: each borrower is a process, each dollar is a unit of a resource, and the lender's remaining balance is the pool of available resources. With that mapping in mind, the algorithm needs the following inputs.
For the banker's algorithm to work, it should know three things:
- How much of each resource each person could maximum request [Max]
- How much of each resource each person currently holds [Allocation]
- How much of each resource is available in the system for each person [Available]
So we need Max and Request.
If Request is given, Max = Allocation + Request
Need = Max − Allocation
A resource can be allocated only for a condition.
Request ≤ Available, or else the process waits until resources are available.
Let 'n' be the number of processes in the system and 'm' be the number of resource types.
- Available – It is a 1D array of size'm'. Available [j] = k means there are k occurrences of resource type Rj.
- Maximum – It is a 2D array of size 'm*n' which represents maximum demand of a section. Max[i,j] = k means that a process i can maximum demand 'k' amount of resources.
- Allocated – It is a 2D array of size 'm*n' which represents the number of resources allocated to each process. Allocation [i,j] =k means that a process is allocated 'k' amount of resources.
- Need – 2D array of size 'm*n'. Need[i,j] = k means process i still needs k more instances of resource type j to complete its task.
- Need [i,j] = Max [i,j] – Allocation[i,j]
The safety algorithm
1. Let Work = Available and Finish[i] = false for all i.
2. Find an index i such that Finish[i] == false AND Need_i ≤ Work.
If no such i exists, go to step 4.
3. Work = Work + Allocation_i; Finish[i] = true; go to step 2.
4. If Finish[i] == true for all i, the system is in a safe state.
Otherwise it is unsafe.
Worked example: four processes, three resource types
Suppose there are 4 processes and 3 resource types (A, B, C) to be allocated.
Available = (3, 3, 2).
| Process | Alloc A | Alloc B | Alloc C | Max A | Max B | Max C | Need A | Need B | Need C |
|---|---|---|---|---|---|---|---|---|---|
| P1 | 0 | 1 | 0 | 7 | 5 | 3 | 7 | 4 | 3 |
| P2 | 2 | 0 | 0 | 3 | 2 | 2 | 1 | 2 | 2 |
| P3 | 4 | 0 | 1 | 9 | 0 | 4 | 5 | 0 | 3 |
| P4 | 2 | 1 | 1 | 2 | 2 | 2 | 0 | 1 | 1 |
Need P2<Available, so we allocate resources to P2 first.
After P2 completion the table would look as follows. Available = (5, 3, 2).
| Process | Alloc A | Alloc B | Alloc C | Max A | Max B | Max C | Need A | Need B | Need C |
|---|---|---|---|---|---|---|---|---|---|
| P1 | 0 | 1 | 0 | 7 | 5 | 3 | 7 | 4 | 3 |
| P3 | 4 | 0 | 1 | 9 | 0 | 4 | 5 | 0 | 3 |
| P4 | 2 | 1 | 1 | 2 | 2 | 2 | 0 | 1 | 1 |
Need P4<Available, so we allocate resources to P4.
After P4 completion. Available = (7, 4, 3).
| Process | Alloc A | Alloc B | Alloc C | Max A | Max B | Max C | Need A | Need B | Need C |
|---|---|---|---|---|---|---|---|---|---|
| P1 | 0 | 1 | 0 | 7 | 5 | 3 | 7 | 4 | 3 |
| P3 | 4 | 0 | 1 | 9 | 0 | 4 | 5 | 0 | 3 |
And P3 will be allocated before P1, which gives us the sequence P2, P4, P3, and P1 without getting into deadlock.
Trace the safety check step by step. Start with Work = (3,3,2) and all Finish[i] = false.
- P2's Need (1,2,2) ≤ Work. Work becomes (5,3,2); Finish[P2] = true.
- P4's Need (0,1,1) ≤ (5,3,2). Work becomes (7,4,3); Finish[P4] = true.
- P3's Need (5,0,3) ≤ (7,4,3). Work becomes (11,4,4); Finish[P3] = true.
- P1's Need (7,4,3) ≤ (11,4,4). Work becomes (11,5,4); Finish[P1] = true.
All Finish[i] are true, so the state is safe.
A state is considered safe if it is able to finish all processing tasks.
Time complexity and limitations
The safety check itself runs in O(m·n²) time, where n is the number of processes and m is the number of resource types. The full Banker's algorithm, in which the resource-request procedure invokes the safety check once per request, is therefore also O(m·n²), though some references cite O(m·n³). The algorithm requires each process to declare its maximum resource needs in advance, assumes a fixed number of processes, and assumes resources cannot be lost — assumptions that limit its use in general-purpose operating systems. The algorithm was first described by Dijkstra in EWD-108, Een algorithme ter voorkoming van de dodelijke omarming (1964, in Dutch); the widely cited English formulation appears in Cooperating Sequential Processes (EWD-123, Technological University Eindhoven, 1965; reprinted in F. Genuys, Ed., Programming Languages, Academic Press, New York, 1968, pp. 43–112). See also the treatment in Silberschatz, Galvin, and Gagne's Operating System Concepts.
The resource request algorithm
When a process Pi makes a request vector Request_i, the system performs the following steps:
- Check that Request_i ≤ Need_i; otherwise raise an error.
- Check that Request_i ≤ Available; otherwise Pi waits.
- Tentatively allocate by setting Available = Available − Request_i, Allocation_i = Allocation_i + Request_i, and Need_i = Need_i − Request_i.
- Run the safety algorithm. If the resulting state is safe, confirm the allocation; if unsafe, roll back the tentative allocation and Pi waits.
C++ implementation
The implementation below takes three inputs from the user: the number of processes, the number of resource types, and the Allocation, Maximum, and Available matrices. It then prints a safe execution sequence (if one exists) and reports whether the system is in a safe state. It applies the safety algorithm described above. For readers who want to strengthen the underlying fundamentals, here is why studying data structures and algorithms matters and a related walkthrough of the top algorithms and data structures every programmer should know.
Note: the C++ below is illustrative rather than a strict reference implementation. Its main loop in method() terminates when the avail vector stops changing between passes rather than by explicitly verifying that every Finish[i] is true. This works for the typical textbook inputs but is not a strict implementation of the safety algorithm shown above — do not use it in production without replacing the termination check with an explicit scan over finish[].
// NOTE: This implementation is illustrative, not a strict reference.
// Its main loop terminates when `avail` stops changing between passes
// rather than by verifying every Finish[i] is true. Do not use in
// production without replacing the termination check with an explicit
// scan over finish[].
#include <iostream>
#define MAX 20
using namespace std;
class bankers
{
private:
int al[MAX][MAX],m[MAX][MAX],n[MAX][MAX],avail[MAX];
int nop,nor,k,result[MAX],pnum,work[MAX],finish[MAX];
public:
bankers();
void input();
void method();
int search(int);
void display();
};
bankers::bankers()
{
k=0;
for(int i=0;i<MAX;i++)
{
for(int j=0;j<MAX;j++)
{
al[i][j]=0;
m[i][j]=0;
n[i][j]=0;
}
avail[i]=0;
result[i]=0;
finish[i]=0;
}
}
void bankers::input()
{
int i,j;
cout << "Enter the number of processes:";
cin >> nop;
cout << "Enter the number of resources:";
cin >> nor;
cout << "Enter the allocated resources for each process: " << endl;
for(i=0;i<nop;i++)
{
cout<<"\nProcess "<<i;
for(j=0;j<nor;j++)
{
cout<<"\nResource "<<j<<":";
cin>>al[i][j];
}
}
cout<<"Enter the maximum resources that are needed for each process: "<<endl;
for(i=0;i<nop;i++)
{
cout<<"\nProcess "<<i;
for(j=0;j<nor;j++)
{
cout<<"\nResource "<<j<<":";
cin>>m[i][j];
n[i][j]=m[i][j]-al[i][j];
}
}
cout << "Enter the currently available resources in the system: ";
for(j=0;j<nor;j++)
{
cout<<"Resource "<<j<<":";
cin>>avail[j];
work[j]=-1;
}
for(i=0;i<nop;i++)
finish[i]=0;
}
void bankers::method()
{
int i=0,j,flag;
while(1)
{
if(finish[i]==0)
{
pnum =search(i);
if(pnum!=-1)
{
result[k++]=i;
finish[i]=1;
for(j=0;j<nor;j++)
{
avail[j]=avail[j]+al[i][j];
}
}
}
i++;
if(i==nop)
{
flag=0;
for(j=0;j<nor;j++)
{
if(avail[j]!=work[j])
flag=1;
}
for(j=0;j<nor;j++)
work[j]=avail[j];
if(flag==0)
break;
else
i=0;
}
}
}
int bankers::search(int i)
{
int j;
for(j=0;j<nor;j++)
if(n[i][j]>avail[j])
return -1;
return 0;
}
void bankers::display()
{
int i,j;
cout<<endl<<"OUTPUT:";
cout<<endl<<"========";
cout<<endl<<"PROCESS\t ALLOTED\t MAXIMUM\t NEED";
for(i=0;i<nop;i++)
{
cout<<"\nP"<<i+1<<"\t ";
for(j=0;j<nor;j++)
{
cout<<al[i][j]<<" ";
}
cout<<"\t ";
for (j=0;j<nor;j++)
{
cout<<m[i][j]<<" ";
}
cout<<"\t ";
for(j=0;j<nor;j++ )
{
cout<<n[i][j]<<" ";
}
}
cout<<"\nThe sequence of the safe processes are: \n";
for(i=0;i<k;i++)
{
int temp = result[i]+1 ;
cout<<"P"<<temp<<" ";
}
cout<<"\nThe sequence of unsafe processes are: \n";
int flg=0;
for (i=0;i<nop;i++)
{
if(finish[i]==0)
{
flg=1;
cout<<"P"<<i+1<<" ";
}
}
cout<<endl<<"RESULT:";
cout<<endl<<"=======";
if(flg==1)
cout<<endl<<"The system is not in safe state and deadlock may occur!!";
else
cout<<endl<<"The system is in safe state and deadlock will not occur!!";
}
int main()
{
cout<<" DEADLOCK BANKER'S ALGORITHM "<<endl;
bankers B;
B.input ( );
B.method ( );
B.display ( );
}
Frequently asked questions
What problem does Dijkstra's Banker's algorithm solve?
It solves the deadlock avoidance problem: given processes that will each request up to a declared maximum of shared resources, decide which resource requests to grant now so the system never enters a state where some set of processes can no longer finish.
What is Dijkstra's Banker's algorithm and how does it work?
It is a deadlock avoidance algorithm that checks, before each resource allocation, whether granting the request would leave the system in a safe state — meaning every process can still finish in some order. If the simulated allocation is unsafe, the request is denied and the process waits.
Is Dijkstra's Banker's algorithm the same as Dijkstra's shortest path algorithm?
No. They share an author (Edsger Dijkstra) but solve different problems. The Banker's algorithm is a deadlock avoidance algorithm for operating systems. The shortest path algorithm is a graph algorithm most commonly classified as greedy, and it is neither BFS nor DFS — it uses a priority queue ordered by shortest known distance.
Is Dijkstra's algorithm DP or greedy?
Dijkstra's shortest path algorithm is most commonly classified as greedy: at each step it selects the unvisited node with the smallest known distance. It is not usually taught as dynamic programming, though it shares the optimal-substructure property with DP and some references classify it under both.
Is Dijkstra's algorithm BFS or DFS?
Neither. It is a best-first search that uses a priority queue ordered by distance, whereas BFS uses a FIFO queue and DFS uses a stack.
What is a safe state in the Banker's algorithm?
A safe state is one in which there exists at least one ordering of all processes such that each process can obtain its maximum resource need using currently available resources plus resources held by earlier-finishing processes.
Next steps
That covers the Banker's algorithm end to end — the safety check, the resource-request procedure, a worked example, and a runnable C++ implementation. If you hire for systems-heavy roles, HackerEarth Assessments includes operating-systems and data-structures question categories you can use to build role-based coding tests.
