Banker's Algorithm in Operating System

Example of Banker's Algorithm

Let's consider an example below where the Allocation, Max, and Available fields are given to us. This example shows four P0, P1, P2, and P3 processes and three resources, Type A, B, and C. There is also an Available field that shows the currently available resource.

First we will calculate the Need. The Need field can be calculated using the formula:

Need[i] = Max[i] - Allocation[i]

After applying the formula, we found the following result.

Now, let's check the safe sequence.
 

For Process P0, Need is (7,4,3), and Available is (3,3,2). It shows that the resource needed is more than the available so the system will move to the subsequent process request.
 

For Process P1, Need is (1,2,2), and the Available is (3,3,2). It shows that the resource needed is less than the Available. So the system will move forward with the request of P1. 
 

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

Now New Available is (5,3,2)
 

For Process P2, Need is (4,0,0), and the Available is (5,3,2). It shows that the resource needed is less than the Available. So the system will move forward with the request of P2.

Available = Available + Allocation =(5,3,2) + (3,0,2) = (8,3,4)

Now the New Available is (8,3,4)

For Process P3, Need is (0,1,2), and the Available is (8,3,4). It shows that the resource needed is less than the Available. So the system will move forward with the request of P3.

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

Now the New Available is (10,4,4)

For Process P0, Need is (7,4,3), and the Available is (10,4,4). It shows that the resource needed is less than the Available. So the system will move forward with the request of P0.

Available = Available + Allocation =(10,4,4) + (0,1,0) = (10,5,4)

Therefore the Safe Sequence <P1,P2,P3,P0>.

Why Banker's Algorithm is named so?

The Banker's algorithm gets its name based on how the banks work. 

Consider that a bank has "m" depositors who have each deposited some amount. Let's call it the total deposit "t." The job of the banks is to provide loans. Loans are given to the borrower by subtracting the amount requested from the total amount deposited ‘t’.

Banks must ensure that they have the total deposit in their reserves at all times. As a result, even if all customers want to withdraw their deposits, the bank can easily accommodate them. Otherwise, the customers and the bank would get into a "deadlock,” where the bank doesn't have the money, and the depositor can’t withdraw his amount.

It is a resource allotment and deadlock avoidance algorithm. It tests for safety by simulating the maximum possible allocation scenario and determining whether the final state is safe. If it's unsafe, we can't allocate the resources, as it will lead to a deadlock.

A deadlock-avoiding method is the Banker's Algorithm. Through the banker's algorithm, we can determine the safe sequence of the processes. We can determine whether allocating resources to a process will be "safe" or not. 

Consider the table below:         

The table shows four different processes. The allotment column represents the instances of the resources A, B, C, and D allocated to the four processes. The maximum column represents the maximum instance of resource a process can request for execution. In the last column, we have an available vector representing the number of resources available.

Characteristics of Banker's Algorithm

The characteristics of Banker's Algorithm are as follows:

• When a process makes a resource request, it must endure a period of waiting
• The algorithm encompasses sophisticated elements to optimize the allocation of resources
• This algorithm necessitates the timely return of resources once all the necessary ones have been acquired
• It possesses an advanced feature for resource allocation
• It can handle resource request and releases dynamically

Working of Banker's Algorithm

Take into account the scenario when there are a set number of students and a classroom with a finite amount of books. Each student need a particular amount of books to complete their assignments. The Banker's algorithm can handle the distribution of books to ensure equitable and effective resource allocation. 

This algorithm does a safety check to make sure every student completes the work before approving the request. The allotted books are deducted from the available books if the safety check is successful, which means the allocation was made in a secure manner. When the homework is finished, the students bring the books back to the classroom, where they are restocked with them. Up until all of the student assignments are still outstanding, this process is continued.

Read about: Free Space Management in OS

Data Structures used to implement Banker’s Algorithm

The Banker's algorithm operates several data structures to organize and track the allocation of resources. Suppose there are 'n' number of processes and 'm' many resource types. Here are the fundamental data structures used in the Banker's algorithm:

1. Available

• This data structure keeps track of the system's available instances of each resource type 
   
• Available[i] = k where k is the R[j] resource type instance

2. Max

• This data structure keeps track of the maximum resource needs of each process. It records the maximum number of instances a process needs in the execution
   
• Max[P1][R1] = k where P1 can request at most k instances of the resource type

3. Allocation

• This data structure keeps track of the number of instances of each resource type assigned to the process
   
• Allocation[P1][R1] = k where k is the instance of resource type R1 allocated to process to P1

4. Need

• This data structure determines the identifies the additional resource instances needed by each process to finish its execution. 
   
• It is calculated by subtracting the maximum resource demands from the provided resources for each process
   
• Need[P1][R1] = k where P1 process requires K more instance of resource type R1 for execution

5. Finish

• This data structure  indicates a Boolean value that shows that the process has been allocated and all resources are been released after completion
   
• Need[P1][R1] = k
  For P1 to execute, K additional instances of resource type R1 are required

Types of Algorithm in Banker's Algorithm

Safety Algorithm

The safety algorithm analyzes the system's state to decide its safety. 

Step1

Start by initializing two vectors, Work and Finish, which have lengths of a and b, respectively. The Work vector has resources of each type, and the finished vector indicates whether the process has finished execution or not. Now set the Work = Available and Finish[i] = false. Assume that all processes are unfinished.

Step 2

Now find values of i such that both Finish[i] = false and Need[i] <= Work. If such a process exists, then continue to step 3. Otherwise, If such a process does not exist, go to step 4.

Step 3

The process that give us Need[i] <= Work ,those processes will be added to Allocation[i]. It will continue until all the other processes have completed their execution, and Finish[i] = true for all 'i' values.

Step 4

If Finish[i] = true, then the system is safe.

Resource Request Algorithm

The resource request algorithm assesses whether the process demanding resources can safely fulfill its request.

Let's consider a request R1[i] for a process P1. when R1[j] == k then the process P1 is requesting k instance of resource R[j].

Step 1

if R1[i] <= Need, it will pass it to step 2 or show an error if it does not fulfill the condition.

Step 2

If R1 <= Available, it will pass it to step 3; else, P[i] will wait until resources are available.

Step 3

During step 3, we assign the resources to process P1 and undertake the following actions:

• Actively decrement the value of the Available resources by the amount specified in R1[i]
• Increment the Allocation for process P1 by the same value
• Reduce the Need for process P1 by R1[i]
   

If the current state becomes unsafe, Process P(i) must pause its execution until it receives all requested type R(i) resources, thereby restoring the previous resource-allocation state.

Implementation of Banker's Algorithm in C

An implementation of Banker's algorithm in C is:-

• C

C

#include <stdio.h>

int main() {
    int numProcesses = 5; // Number of processes
    int numResources = 3; // Number of resources

    int allocationMatrix[5][3] = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}}; // Allocation Matrix
    int maxMatrix[5][3] = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}};   // MAX Matrix
    int availableResources[3] = {3, 3, 2}; // Available Resources

    int isFinished[numProcesses], safeSequence[numProcesses], index = 0;
    for (int k = 0; k < numProcesses; k++) {
        isFinished[k] = 0;
    }

    int needMatrix[numProcesses][numResources];
    for (int i = 0; i < numProcesses; i++) {
        for (int j = 0; j < numResources; j++)
            needMatrix[i][j] = maxMatrix[i][j] - allocationMatrix[i][j];
    }

    for (int k = 0; k < numProcesses; k++) {
        for (int i = 0; i < numProcesses; i++) {
            if (isFinished[i] == 0) {
                int flag = 0;
                for (int j = 0; j < numResources; j++) {
                    if (needMatrix[i][j] > availableResources[j]) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0) {
                    safeSequence[index++] = i;
                    for (int y = 0; y < numResources; y++)
                        availableResources[y] += allocationMatrix[i][y];
                    isFinished[i] = 1;
                }
            }
        }
    }

    int flag = 1;
    for (int i = 0; i < numProcesses; i++) {
        if (isFinished[i] == 0) {
            flag = 0;
            printf("The system is not safe.\n");
            break;
        }
    }

    if (flag == 1) {
        printf("SAFE Sequence: ");
        for (int i = 0; i < numProcesses - 1; i++)
            printf("P%d -> ", safeSequence[i]);
        printf("P%d\n", safeSequence[numProcesses - 1]);
    }

    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Explanation

In order to avoid deadlock in a multi-process environment, this C code implements the Banker's Algorithm. It necessitates knowledge of the processes, resources, and their distribution. Then, if a safe order of processes exists to prevent deadlock, it is checked and printed. Otherwise, it denotes a hazardous situation.
 

Advantages of Banker's Algorithm

• Avoids Deadlock - 
  A deadlock is a situation in which two computer programs partaking the identical resource are effectively averting each other from accessing the resource, performing in both programs ending to perform
   
• Less Restrictive than deadlock prevention
   
• Helps OS manage and control process requests for different computing resources
   
• It contains a variety of resources that satisfy the needs of each procedure
   
• It has advanced features of max allocation
   

Disadvantages of Banker's Algorithm

• It only works with a fixed number of resources and processes
   
• It doesn't allow processes to exchange their maximum needs while processing
   
• Processes have to know their max requirements in advance
   
• It requires memory overhead to check safety check and also in organizing data structure
   
• It become complicated as the number of resources and process increases
   

Frequently Asked Questions

What is the time complexity of the banker's algorithm?

The time complexity of the Banker's algorithm is O(n^2 * m), where n is the number of processes and m is the number of resources. This complexity arises from the need to potentially check all processes for safety.

What is Banker's algorithm with example?

Consider a system with five instances for two resources, A and B. Now if the one process request for 1 A and 1 B, then this algorithm checks if the request can leave the system in a safe state. If the system is secure, then the resource is allocated safely.

What are the different types of bankers algorithm?

The Single Resource Type Banker's Algorithm, which is appropriate for systems with only one resource type, and the Multi-Resource Type Banker's Algorithm, which manages systems with many resource kinds, are two versions of the Banker's algorithm.

What is Banker's algorithm in real life?

There are many areas in which Banker's Algorithm can be used in real life, like Project Management, Classroom, Banking, or Financial Risk Management. In each domain, the Banker's Algorithm plays an important role. 

Conclusion

Banker's algorithm is a deadlock avoidance algorithm. The safety and resource request algorithms are two primary components of Banker's algorithm. Banker's algorithm ensures that the processes are allocated the resources without getting into any unsafe state. Banker's algorithm cannot be practically implemented as it is not feasible to determine the number of resources a process may need beforehand. 

Recommend Reading-

• Deadlock Prevention and Avoidance
• Deadlock Detection Algorithm
• Deadlock, Starvation, and Livelock

Happy Learning, Ninjas!