Understanding Banker's Algorithm in Operating System

Introduction

The banker’s algorithm in the operating system is especially used to avoid deadlock and resource allocation problems that basically use the predefined simulation for all the resources.

Why this algorithm is named Banker’s algorithm?

This algorithm is internally used in the banking system to check whether a loan can be allotted to a particular person or not.

For example, consider a scenario in which there is x number of people who holds an account in a bank and all of them have T amount of money in total. Now suppose a person wants to take a loan of a particular amount then the loan will be sanctioned only if the total amount left after deducing that loan amount is equal to or greater than T. This is done in order to ensure that if all people having account in the bank come to withdraw their deposited amount then they can withdraw easily.

In simple words, we can say that the bank should never sanction loan amounts in such a way that it cannot allocate money to the depositors.

Algorithm

Let there exist ‘N’ number of processes in a system and ‘M’ be the number of available resources.

Available resources

• The number of available resources are represented in an 1- d array of size ‘M’.
• Available_Resources[i] = R represents there are R number of resource of i type.

Max

• The maximum demand of each process is represented in a 2-d array of dimensions M x N.
• Maximum_Demand[i, j] = L represents the process of type i may request k instances resource type j.

Allocation

• The number of resources of each type allocated to each process is defined in a 2-D array of size N x M.
• Allocation[i, j] = S represents that the process of ith type is currently allocated S instances of the resource of type j.

Need

• The remaining resource need of each process is represented in a 2-D array of size N x M.
• Need[i, j] = Q represents the process of ith type requires Q instances of resource of jth type.
• Need[i, j] = Maximum_Demand[i, j] - Allocation[i, j]

The banker’s algorithm is itself composed of a safety algorithm and a resource request algorithm:

Safety Algorithm

The safety algorithm determines whether a system exists in a safe state or not and can be described using the following:

• Let us consider that Work and Finish be arrays of lengths M and N respectively. Let us initialize the Work as Available, Finish[i] = false; for i = 1, 2, 3,….n.
• Find an i such that both, Finish[i] = false and Need[i] <= Work if there doesn’t exists any such i then go to step 4.
• Work = Work + Allocation[i]

Then mark, Finish[i] = true, and then go to step 2.

• If the value of Finish [i] is equal to true for all i then the system is in a safe state.

Resource request algorithm

Let us consider that Request[i] represents the request array for the process of ith type (Pi). Then, Requesti [j] = R signifies that the process of ith type (i.e, Pi ) requires R resources of type Rj. Generally, the following actions are taken when a process Pi resquest some resources:

1. If the ith need is greater than ith request, i.e, Request <= Needi then go to the step 2 otherwise, raise an error condition as the process has reached to its maximum claim.

2. If the ith request is lesser than or equal to ith available resource i.e, If Requesti <= Availablei the go to the step 3. Otherwise, the ith process (i.e, Pi) must due to the non-availability of the resources.

3. Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:

Availablei = Available – Requesti

Allocationi = Allocationi + Requesti

Needi = Needi – Requesti

Conclusion

In this article, we discussed in detail regarding the Banker’s algorithm in operating system.