Subject: Operating System

Topic: Process Concurrency

Difficulty: Hard

Banker’s algorithm is a deadlock avoidance algorithm. It is named so because this algorithm is used in banking systems to determine whether a loan can be granted or not.

Consider there are n account holders in a bank and the sum of the money in all of their accounts is S. Every time a loan has to be granted by the bank, it subtracts the loan amount from the total money the bank has. Then it checks if that difference is greater than S. It is done because, only then, the bank would have enough money even if all the n account holders draw all their money at once.

Banker’s algorithm works in a similar way in computers. Whenever a new process is created, it must exactly specify the maximum instances of each resource type that it needs. The banker’s algorithm is a method used in deadlock avoidance technique in multiple instances of a resource type.

For the Banker's algorithm to work, it needs to know three things:

1. How much of each resource each process could possibly request[MAX]

2. How much of each resource each process is currently holding[ALLOCATED]

3. How much of each resource the system currently has available[AVAILABLE]

The various data structures used in it are:

Total_resource[ i ]: A 1-D matrix of size m .It stores the total number of resources in a system.

Max[i , j ]: A 2-D matrix where each process stores the maximum demand of resources (Rj) of process Pi.

Allocation [i , j]: A 2-D matrix which stores the current allocation status of all resource types to various process in the system.

Need [i , j]: A 2-D matrix which tells the current remaining resource need of each process. It is the maximum demand of a process and the current allocation status.

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

Avail[i]: A 1-D matrix which stores the current available instances of each resource type.

Resources may be allocated to a process only if it satisfies the following conditions:

request ≤ available, else process waits until resources are available

Let us assume that there are n processes and m resource types. Some data structures are used to implement the banker’s algorithm. They are:

Available: It is an array of length m. It represents the number of available resources of each type. If Available[j] = k, then there are k instances available, of resource type Rj.

Max: It is an n x m matrix which represents the maximum number of instances of each resource that a process can request. If Max[i][j] = k, then the process Pi can request atmost k instances of resource type Rj.

Allocation: It is an n x m matrix which represents the number of resources of each type currently allocated to each process. If Allocation[i][j] = k, then process Pi is currently allocated k instances of resource type Rj.

Need: It is an n x m matrix which indicates the remaining resource needs of each process. If Need[i][j] = k, then process Pi may need k more instances of resource type Rj to complete its task.

Need[i][j] = Max[i][j] – Allocation [i][j]