BANKER’S ALGORITHM

In this blog, we will discuss a multiple instance deadlock avoidance algorithm in operating systems i.e. Banker’s Algorithm.

Banker’s Algorithm is a deadlock avoidance and detection algorithm that tells if any system can go into a deadlock or not by analyzing the currently allocated resources and the resources it requires for its execution in the future. The name was chosen because the algorithm could be used in a banking system to ensure that the bank never allocated its available cash in such a way that it could no longer satisfy the needs of all its customers. When a new process enters the system for execution, it must indicate how many instances of each resource type it will require. This amount must not exceed the system’s entire number of resources. When a user requests a set of resources, the system must decide if allocating these resources will put the system in a safe state. If it will, resources will be allocated; if not, the process will have to wait until another process releases sufficient resources. Also, when a process gets all its requested resources it must return them in a finite amount of time.

DATA STRUCTRES USED FOR BANKER’S ALGORITHM:

various data structures we need to maintain for performing Banker’s Algorithm

Let n = number of processes, and m = number of resource types.

Available :

· It is a 1-d array of size ‘m’ indicating the number of available resources of each type. It represents the number of instances presently available in the system after some of being already allocated to the processes. Using the ‘Available’ we check whether we can grant the request of resources by the processes.

Max :

· It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system. This has to be declared by each process at the the time of their arrival .

Allocation :

· It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently allocated to each process. The instances of each resource type the processes are currently holding.

Need :

· It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process after thy are already holding some of the instances, the remaining instances of each resource type they need for their completion.

· Need [ i , j ] = Max [ i , j ] — Allocation [ i , j ]

Allocation specifies the resources currently allocated to Process P and the Need matrix specifies the additional resources that process P may still request to complete its task.

BANKER’S RESOURCE ALLOCATION ALGORITHM

simple steps to apply Banker’s Algorithm.

Let us understand these steps through an example;

Example:

Suppose we have 3 processes(A, B, C) and 3 resource types(R1, R2, R3) each having 5 instances.

Scenario given in which we need to check for deadlock

Solution:

1. First, calculate the available vector.

Available= Total instances — Total Allocated = [0,1,2]

2. Then, the second step would be to be to calculate the Need matrix.

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

So, the resultant need matrix would be as follows:

Need Matrix of different processes.

Now, through the need matrix we will see that our system is free from deadlock or not. If the deadlock is not present than the system is said to be in ‘safe state’.

To check if there is deadlock in the system or not :

· First, we need to check whether Available >= Need[i].

In this example, Available= [0,1,2] which is equal to Need[B] ,so process B will be executed.

· After process B will get finished, it will return the resources which were already allocated to it.

· Available= Available+ Allocation[B]

· New Available= [0,1,2]+[2,0,1]=[2,1,3]

· Then again check for Available >= Need[i]

· For process A, Need=[1,0,3] which is less than Available ,so process A is granted access to resources, and it will execute and release the resources.

· New Available = [2,1,3] + [1,2,1]=[3,3,4]

· Similarly, process C will get executed and it will release the allocated resources and we will get all the instances of resources back.

The system allocates all the needed resources to each process. So, we can say that system is in a safe state.

DISADVANTAGES OF BANKER’S ALGORITHM :

· It does not permit a process to change its need in between processing.

· All the processes should know in advance about the maximum resource needs which is very hypothetical.