How to implement the banker's algorithm

When a new process starts in a computer system, it must provide the operating system with information such as upcoming processes, demands for their resources, counting them, and delays. Based on these factors, the operating system determines which process sequence should run or wait to avoid system deadlock.

The banker's algorithm provides the safe execution of processes in arbitrary order without the occurrence of a deadlockWhen processes need some resources that are held by other processes to complete the execution.. It checks whether the system can go into a deadlock in the future or not by analyzing all the available resources before allocation. It checks for the safe stateA state in which all system processes can be executed with the available resources so that deadlock doesn't occur. and requests if the system remains in the safe state after request approval. It denies the request if there is no safe state. As a result, it is also known as the operating system's deadlock avoidance algorithm or deadlock detection method. We'll learn how to implement the banker's algorithm in this Answer.

Note: Click here to learn more about the banker's algorithm.

Data structures

Some arrays that we use while implementing the banker's algorithm are given below:

The Availablearray

It is an array representing the number of resources with the length m. When Available[j]= k, it means k instances of resource type R[j] are available.

The Max array

It is an n×\timesm size matrix representing each process P[i] that can store the maximum number of resources R[j]. When Max[i][j] = k, it means the process P[i] can request instances k of resource type R[j].

The Allocationarray

It is a n×\timesm size matrix representing each type of resource currently allocated to the processes. When Allocation[i][j] = k, it means k instances of resource type R[j] are currently allocated to process P[i].

The Needarray

It is a n×\timesm size matrix representing the remaining need of resources for each process. When Need[i][j] = k, it means a process P[i] needs k more instances of resources type R[j].

Algorithms

The banker's algorithm is a combination of the following two algorithms:

  1. Safety algorithm

  2. Resource request algorithm

Let's see both algorithms in detail.

Safety algorithm

The safety algorithm used to check whether the system is in a safe state or not. The algorithm work as follows:

Step 1

Consider two vectors Work and Finish with the length m and n respectively.

Work = Available
Finish[i] =false for i = 0, 1, ... , n - 1.

This means none of the processes is finished and Available represents the number of available resources.

Step 2

Check the available status of the resource R[i] such that:

Finish[i] == false
Need[i] <= Work

This we have to find an unfinished process whose needs can be fulfilled by the resources R[i]. If i doesn't exist, just go to Step 4.

Step 3

Do the following:

Work = Work + Allocation[i]
Finish[i] = true

When we get an unfinished process, after allocating its resources we mark it as Finish. Go to Step 2 to check the resource availability status for the next process.

Then, we use a loop to check the same for all other processes.

Step 4

If Finish[i]==true , it means the system is in a safe state and deadlock will never occur.

Resource request algorithm

The resource request algorithm used to check whether the requests can be granted safely or not and how the system will behave when a process requests for resources. The resource request algorithm works as follows:

Let's say, for each process P[i], we create a resource request array R[i]. When Resource Request[i][j] = k, it means the process P[i] requires the k instances of resource type R[j].

Step 1

Initially, if the request is less or equal to the resource need, move to Step 2. Otherwise, we raise an error condition as the process has exceeded its maximum requirement of resources.

if (Request[i] <= Need[i])
    //then go to step 2;
else
    error

Step 2

If the request is less than or equal to available resources, then move to Step 3. Otherwise, the process needs to wait as resources are not available at the moment.

if (Request[i] <= Available[i]) 
    //then go to step 3; 
else
    //wait P[i]

Step 3

Now, we suppose that resources have been allocated to the process. We perform the following actions.

Available = Available - Request
Allocation[i] = Allocation[i] + Request [i]
Need[i] = Need[i] - Request[i]

When the resource allocation state comes out to be safe, its resources are allocated to the process P[i]. If the new state is unsafe, then P[i] has to wait for Request[i] and restore the old resource-allocation state.

Implementation

Let's see the step-by-step code implementation of the banker's algorithm in C++.

//C++ program for Banker's Algorithm 
#include <iostream>
using namespace std;
int main() 
{ 
	// P0, P1, P2, P3, P4 are the names of Process
	int no_of_processes, no_of_resources, i, j, k; 
	no_of_processes = 5; // Number of processes 
	no_of_resources = 3; //Number of resources 
	int allocate[5][3] = { { 0, 1, 0 }, // P0 // Allocation Matrix 
						{ 2, 0, 0 }, // P1 
						{ 3, 0, 2 }, // P2 
						{ 2, 1, 1 }, // P3 
						{ 0, 0, 2 } }; // P4 
	int max[5][3] = { { 7, 5, 3 }, // P0 // MAX matrix representing max need 
					{ 3, 2, 2 }, // P1 
					{ 9, 0, 2 }, // P2 
					{ 4, 2, 2 }, // P3 
					{ 5, 3, 3 } }; // P4 
	int available[3] = { 3, 3, 2 }; // Available Resources 
	int finish[no_of_processes]={0}, safe_seq[no_of_processes], index = 0; 
	 
	int need[no_of_processes][no_of_resources]; 
	
	for (i = 0; i < no_of_processes; i++) { 
		for (j = 0; j < no_of_resources; j++) 
			need[i][j] = max[i][j] - allocate[i][j]; //calculating need of resources
	} 
	int y = 0; 
	for (k = 0; k < 5; k++) { 
		for (i = 0; i < no_of_processes; i++) { 
			if (finish[i] == 0) {  //unfinished process
				bool flag = true; 
				for (j = 0; j < no_of_resources; j++) { 
					if (need[i][j] > available[j]){  //not enough resources
						flag = false; 
						break; 
					} 
				} 
				if (flag == true) {  //resources are available
					safe_seq[index++] = i; 
					for (y = 0; y < no_of_resources; y++) 
						available[y] += allocate[i][y]; //allocating resources
					finish[i] = 1; //process is finished 
				} 
			} 
		} 
	} 
	cout<<"Th SAFE Sequence is: \n"; 
	for (i = 0; i < no_of_processes - 1; i++) 
		cout<<" P->"<<safe_seq[i]; 
	cout<<" P->"<<safe_seq[no_of_processes - 1]; 
	return 0;
}

Explanation

  • Lines 28–31: We use two for loops to calculate the need of resources by subtracting max from the allocate.

  • Lines 33–43: In the for loop, we check if the process is not finish which means if the process needs some resources. By using if condition, we check whether the resources are available as per the need of process. If not, we mark the flag as false.

  • Lines 45–49: If resources are available, we allocate them to the process and add them in the safe_seq. Afterward, we assign 1 to the finish[], which means the process is finished now.

Time complexity

The time complexity of the banker's algorithm is O(n∗n∗m)O(n*n*m), where nn is the number of processes and mm is the number of resources.

Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
You TubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved