Bankers Algorithm in OS

Last Updated on March 2, 2023 by Prepbytes

The Bankers Algorithm is named after the fact that it is widely used in the banking system to avoid deadlock. The bank ensures that when consumers request money, the bank never exits a safe state by implementing the Bankers algorithm. If the customer’s request does not cause the bank to leave a safe state, the cash will be allocated; otherwise, the consumer will have to wait until another customer deposits sufficient money. Bankers algorithm in OS is also known as the deadlock avoidance algorithm.

What is Bankers Algorithm in Operating System?

The Bankers Algorithm in OS is an algorithm used to manage and allocate resources in a multi-task environment. It is used to prevent deadlocks and ensure the system remains in a safe state. The algorithm works by keeping track of the available resources in the system and allocating them to processes in a way that ensures that the system will not run out of resources and enter a deadlock state. The Banker’s Algorithm in OS uses a combination of resource allocation and deadlock detection to ensure efficient resource usage and prevent system failures.

Let us look at a real-world case to better comprehend this algorithm. Assume there are ‘n’ account holders in a certain bank, and the total amount of their money is ‘x’. Now, if a person applies for a loan (say, to buy a house), the loan amount reduced from the total amount available in the bank gives us the residual amount, which must be more than ‘x’ in order for the loan to be sanctioned by the bank. It is done with the worst-case scenario in mind, in which all account holders arrive at the bank at the same moment to withdraw their money. As a result, the bank is always in a secure position.

Bankers algorithm in operating system works similarly. Each process within the system must send all important necessary details to the operating system, such as impending processes, resource requirements, delays, and so on. Based on these details, the operating system determines whether to execute the process or hold it in the waiting state to avoid system deadlocks. As a result, the Bankers algorithm is often referred to as the Deadlock Detection Algorithm.

Data structures Required in the Bankers Algorithm Implementation

The following data structures are needed to implement the Bankers Algorithm in OS:

1. Available Resources Array: An array that stores the current number of available resources of each type.
2. Maximum Need Matrix: A matrix that stores the maximum number of resources of each type required by each process.
3. Allocation Matrix: A matrix that stores the number of resources of each type currently allocated to each process.
4. Need Matrix: A matrix that stores the remaining resources of each type required by each process (calculated as the difference between the Maximum Need and Allocation matrices).
5. Completed Processes Set: A set that stores the IDs of processes that have completed and released their resources.

These data structures are used to represent the state of the system and the resources being requested and allocated by the processes. The Bankers Algorithm in OS uses this information to determine if a resource request can be granted without resulting in a deadlock.
When implementing or dealing with the Bankers algorithm in OS, three factors must be kept in mind:

1. The [MAX] array indicates how many resources of each type a process can request.
2. The [ALLOCATION] array indicates how many resources of each type a process currently holds or allocates.
3. The [AVAILABLE] array indicates how many resources of each type are currently available in the system.

The Bankers Algorithm is made up of two algorithms which are:

1. Safety Algorithm
2. Resource Request Algorithm

Safety Algorithm
The Safety Algorithm is a part of the Bankers Algorithm in OS, which is used to determine if a system is in a safe state and if a resource request can be granted without resulting in a deadlock. The algorithm operates as follows:

The following are the steps in the Safety Algorithm:

• Step 1 – Consider two vectors, Work and Finish, with lengths m and n, respectively. The Work array represents the total available resources of each kind (R0,R1,R2,…Rm), while the Finish array represents whether or not the specific process Pi has done execution. It can be true or false.

  Initialize : Work = Available
  Finish[i] = false , where i=0,1,2,3,....n

• Step 2 – Need is an array of size m for each process.We can iterate over each process from i=0,1,2,3… to n and find if any process Pi exist for which –

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

  If no such process exists and finish[i]= false for all processes, the system is not in a safe condition since no such process can complete its execution using the available resources. As a result, the system may enter a deadlock state. If Finish[i] = true for all processes, go to step 4.

• Step 3 - If there is a process for which Need<=Available as described in step 2, then assign those resources to that process and increase the allocated array for that process by Allocated[i].

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

  Once this process is completed, move to step 2 and repeat for the other processes until all processes have completed their execution and Finish[i]= true for all i=0,1,2,3,...n.

• Step 4 - If finish[i]=true for all i=0,1,2,3..n, the system is determined to be in a safe state.

In the worst-case situation, the number of operations required by the safety algorithm is equal to n2 * m.

Resource Request Algorithm
A resource request algorithm is a process used in operating systems to manage resource allocation. When a process requests additional resources, the resource request algorithm determines if the request can be granted without compromising the safety of the system. The algorithm checks if the request can be granted by ensuring that the request does not cause a process to exceed its maximum resource needs and that there are enough resources available to grant the request.

Request[i,j] = x represents a process Pi request for x instances of a resource of type j.

The following are the steps in the resource request algorithm:

• Step-1: If Request[i,j] <= Need[i,j], the process is requesting resources that are less than or equal to the resources required for execution.If Request[i,j]>Need[i,j], an error can be thrown indicating that the process is seeking resources that are beyond its need.If Request[i,j] = Need[i,j], go to step 2.

• Step 2: If Request[i,j] < Available[i,j] indicates that the requested resources are available in the system and can be assigned to the process.If Request[i,j] < Available[i,j], then go to step 3, otherwise, the process must wait for the available resources to be more than the requested resources.

• Step 3: If Request[i,j] < Available[i,j], then resources are allocated to the process Pi, and the Available[i,j],Allocation[i,j], and Need[i,j] will be changed as follows:

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

Example of Bankers Algorithm in OS

In this example, we have a process table with a number of processes that has an allocation column (to show how many resources of type A, B, and C are allocated to each process in the table), a max field (to show how many resources of type A, B, and C can be allotted to each process), and an available field (for showing the currently available resources of each type in the table).

We need to compute the following two things using the above processing table

Q.1 construct the need matrix? Q.2 Is the system in safe state?
Ans 1 - We can easily construct the need matrix using the formula:

(Need)i = (Max)i - (Allocation)i

Ans 2 - Let us now check for a safe sequence:

1. In the case of Process P0, Need = (6, 5, 3) and Available = (4, 3, 2) Clearly, the resources required outnumber the ones available. As a result, the system will proceed to the next request.

2. In the case of Process P1, Need = (8, 2, 1) and Available = (4, 3, 2) Clearly, the resources required outnumber the ones available. As a result, the system will proceed to the next request.

3. In the case of Process P2, Need = (5, 1, 3) and Available = (4, 3, 2) Clearly, the resources required outnumber the ones available. As a result, the system will proceed to the next request.

4. In the case of Process P3, Need = (1, 2, 2) and Available = (4, 3, 2) Clearly, the resources required are less than the resources available in the system. As a result, P1's request is approved.

   Available=Available+Allocation = (4, 3, 2) + (3, 0, 1) = (7, 3, 3)

5. Now, Check again for Process P0, Need = (6, 5, 3) and Available = (7, 3, 3) Clearly, the resources required outnumber the ones available. As a result, the system will proceed to the next request.

6. Check again for Process P1, Need = (8, 2, 1) and Available = (7, 3, 3) Clearly, the resources required outnumber the ones available. As a result, the system will proceed to the next request.

7. Check again for Process P2, Need = (5, 1, 3) and Available = (7, 3, 3) Clearly, the resources required are less than equal the resources available in the system. As a result, P2's request is approved.

   Available=Available+Allocation = (7, 3, 3) + (0, 2, 0) = (7, 5, 3)

8. Now,only two processes are left, lets check again for Process P0, Need = (6, 5, 3) and Available = (7, 3, 3). Clearly, the resources required are less than equal the resources available in the system. As a result, P0's request is approved.

   Available=Available+Allocation = (7, 3, 3) + (2, 1, 0) = (9, 4, 3)

9. Now,only one process is left, lets check for Process P1, Need = (8, 2, 1) and Available = (9, 4, 3). Clearly, the resources required are less than equal the resources available in the system. As a result, P1's request is approved.

   Safe sequence: < P3,P2,P0,P1>

Code Implementation:

#include <bits/stdc++.h> 
using namespace std;

int main() { 
    int i, j, k; 
    int n = 4; //number of processes 
    int m = 3; //number of resources 
    int allocation[4][3] = {{2, 1, 0},   //Allocation Matrix 
                        {1, 2, 2},  
                        {0, 2, 0},  
                        {3, 0, 1}}; //Each row represents a process 
  
    int max[4][3] = {{8, 6, 3}, //MAX Matrix 
                      {9, 4, 3}, 
                      {5, 3, 3}, 
                      {4, 2, 3}}; //Maximum resources that can be allocated 
  
    int available[3] = {4, 3, 2}; //Available resources at start 
  
    int finish[n] = {0};
    int ans[n] = {0};
    int idx =  0; 
    
    int need[n][m];  //Calculating Need matrix
    for(int i=0;i<n;i++)
    { 
        for(int j=0;j<m; j++)
        {
            need[i][j] = max[i][j] - allocation[i][j];
        } 
    } 
    
    int y = 0; 
    for (int k=0;k<4;k++) 
    { 
        for(int i=0;i<n;i++)
        { 
            if(finish[i]==0)
            { 
                int flag = 0; 
                for(int j=0;j<m;j++)
                { 
                    if(need[i][j]>available[j])
                    { 
                        flag = 1; //if needed resources are more in number than the available ones, move to the next process
                        break; 
                    }
                } 
                
                if(flag==0)
                {  //if available resources fulfilled the need
                    ans[idx++] = i; //the index of process, that has been allocated the resources
                    for(int y=0;y<m;y++)
                    { 
                        available[y] += allocation[i][y]; 
                    }
                    finish[i] = 1; 
                } 
            } 
        } 
    } 
    
    bool flag = true;
    for(int i=0; i<n; i++)
    {
        if(finish[i] == 0)
        { 
            flag = false; 
            cout<<"System is in deadlock !!"; break; 
        }
    }
    
    if(flag==true)
    {
        cout<<"System is in safe state and following is the safe sequence: ";
        for(int i=0;i<n-1;i++)
        {
            cout<<"P"<<ans[i]<<" -> "; 
        }
        cout<<"P"<<ans[n-1]<<endl;
    }  
    return 0; 
}

Output

System is in safe state and following is the safe sequence: 
P3 -> P2 -> P0 -> P1

Characteristics of Bankers Algorithm in OS

The Bankers Algorithm in OS has the following characteristics:

• Deadlock avoidance: The Bankers algorithm uses resource allocation and release rules to prevent deadlocks from occurring.
• Safety state: The Bankers algorithm checks if the current state is a safe state, where no deadlock will occur even if all the processes keep running to completion.
• Dynamic nature: The Bankers algorithm is dynamic in nature, as it can handle resource requests and releases during the execution of processes.
• Non-preemptive: The Bankers algorithm does not preempt resources from processes, i.e., resources are only released voluntarily by the processes.
• Conservatism: The Bankers algorithm is conservative, as it only grants resource requests if the resulting state is a safe state.
• Resource utilization: The Bankers algorithm ensures that resources are efficiently utilized by processes.
• Optimality: The Bankers algorithm does not guarantee optimal resource utilization, but rather aims to prevent deadlocks from occurring.

Advantages of Bankers Algorithm in OS

Some advantages of Bankers Algorithm in OS are mentioned below:

• Deadlock avoidance: The Bankers algorithm in OS can detect and avoid deadlocks, ensuring the safe and efficient allocation of resources.
• Resource utilization: The Bankers algorithm helps to optimize resource utilization by ensuring that resources are only allocated to processes that need them.
• System stability: The Bankers algorithm helps to maintain system stability by ensuring that processes do not hold onto resources indefinitely.
• Safe state detection: The Bankers algorithm can detect when the system is in a safe state, allowing for the allocation of resources to be safely managed.
• Simplicity: The Bankers algorithm is relatively simple and straightforward to implement, making it a popular choice for resource allocation in operating systems.

Drawbacks of Bankers Algorithm in OS

Some drawbacks of Bankers Algorithm in OS are as follows:

• Overhead: The Bankers algorithm requires additional computation and memory overhead to maintain data structures and check for safe states, affecting system performance.
• Inflexible resource allocation: The Bankers algorithm follows a set of predetermined rules for resource allocation, which may not be flexible enough to handle complex or dynamic resource requirements.
• Limited applicability: The Bankers algorithm in OS is limited in its applicability to only those systems with a finite number of resources, and may not be suitable for systems with continuous or infinite resources.
• Blocking processes: The Bankers algorithm may lead to processes being blocked, waiting for resources to become available, causing decreased system performance.
• Static resource allocation: The Bankers algorithm in OS uses a static approach to resource allocation, and does not account for changes in resource requirements over time, leading to sub-optimal resource utilization.

Conclusion
The Bankers Algorithm in OS is a deadlock avoidance algorithm used to avoid deadlocks and to ensure safe execution of processes. The algorithm maintains a matrix of maximum and allocated resources for each process and checks if the system is in a safe state before allowing a process to request additional resources. The algorithm checks if the request can be granted by ensuring that the request does not cause a process to exceed its maximum resource needs and that there are enough resources available to grant the request. If the system is in a safe state, the algorithm grants the request and updates the allocation matrix. If the system is not in a safe state, the request is denied and the process is blocked until enough resources become available to grant the request. The Bankers Algorithm is a useful tool for managing resource allocation and avoiding deadlocks in operating systems.

Frequently Asked Questions(FAQs)

Below are some FAQs on Bankers Algorithm in OS

1. How does the Bankers Algorithm in OS work?
The Bankers Algorithm in OS works by maintaining a matrix of maximum and allocated resources for each process, and then checking if the system is in a safe state before allowing a process to request additional resources. The algorithm checks if the request can be granted without compromising the safety of the system, by ensuring that the request does not cause a process to exceed its maximum resource needs and that there are enough resources available to grant the request.

2. What are the key components of the Bankers Algorithm?
The key components of the Bankers Algorithm in OS include the allocation matrix, the maximum matrix, the need matrix, the available vector, and the work vector. The allocation matrix represents the resources that are currently allocated to each process, the maximum matrix represents the maximum resources required by each process, the need matrix represents the resources still needed by each process, the available vector represents the resources that are currently available, and the work vector is used to keep track of the available resources during the algorithm's execution.

3. What is a safe state in the context of the Bankers Algorithm?
A safe state in the context of the Bankers Algorithm in OS is a state in which there exists a sequence of processes such that each process can be completed without encountering deadlocks. In other words, it is a state in which all processes can be executed to completion without any deadlocks or resource starvation.

4. What is an unsafe state in the context of the Bankers Algorithm?
An unsafe state in the context of the Bankers Algorithm in OS is a state in which the execution of processes may result in deadlocks or resource starvation. In an unsafe state, processes may be blocked waiting for resources that will never become available, resulting in a deadlock.