Imagine you have deposited some money, and then it turns out the bank doesn't have the amount with them since they have given out loans. To avoid this situation, the banking system often uses the banker's algorithm to prevent bankruptcy.

This article will discuss the banker's algorithm, a combination of the safety algorithm and the resource request algorithm.

What is Banker's Algorithm?

The Banker's Algorithm is an operating system and computer science technique used for resource allocation and deadlock avoidance. In systems where several processes compete for constrained resources, such as CPU time, memory, and devices, it is intended to prevent deadlock. Operating systems use the Banker's algorithm, a resource management and deadlock avoidance technique, to allocate resources (such as memory or CPU time) to processes to avoid deadlocks. Deadlocks occur when several processes are unable to move forward because they are each waiting for resources that the others have.

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.

Process

Allocation

Max

Available

Need

A, B, C

A, B, C

A, B, C

A, B, C

PO

0, 1, 0

7, 5, 3

3, 3, 2

P1

2, 0, 0

3, 2, 2

P2

3, 0, 2

7, 0, 2

P3

2, 1, 0

2, 2, 2

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.

Process

Allocation

Max

Available

Need

A, B, C

A, B, C

A, B, C

A, B, C

PO

0, 1, 0

7, 5, 3

3, 3, 2

7, 4, 3

P1

2, 0, 0

3, 2, 2

1, 2, 2

P2

3, 0, 2

7, 0, 2

4, 0, 0

P3

2, 1, 0

2, 2, 2

0, 1, 2

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:

Process

Allotment

A B C D

Maximum

A B C D

Available

A B C D

P0

0 0 1 2

0 0 1 2

P1

1 0 0 0

1 7 5 0

P2

1 3 5 4

2 3 5 6

P3

0 6 3 2

0 6 5 2

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.

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 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]); }

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.