# Banker’s Algorithm in OS

by

### What is Banker’s Algorithm?

Bankers algorithm is an algorithm which is used for deadlock avoidance and resource allocation. It was established by Edsger Dijkstra. The reason behind the name ‘banker’s algorithm’ is that it is mostly used in banking systems. Banker’s algorithm helps to identify whether a loan should be provided or not.

### Characteristics of Banker’s Algorithm

The characteristics of Banker’s algorithm are:

The disadvantages of banker’s algorithm are:

Data Structures used to implement the Banker’s Algorithm

There are four types of data structures used to implement Banker’s algorithm:

Available

Max

Allocation

Need

[i, j]

= k indicates that for the execution of ‘Pi’ process, presently ‘k’ instances of resource type ‘Rj’ are required.

Banker’s algorithm comprises of two algorithms:

Safety algorithm

The safety algorithm is used to check the system state means whether the system is in a safe state or not.

The safety algorithm contains the following steps:

Resource Request Algorithm

Let Requesti is the request array for the process ‘Pi’. Requesti [j] = k means ‘Pi’ process needs k instances of Rj resource type. At the time   when a process Pi demands  resources, then we follow the below steps.

Example of Banker’s Algorithm

Consider the following snapshot of a system:

 Processes Allocation A   B    C Max  A   B   C Available A   B   C P0 1     1     2 4    3    3 2    1    0 P1 2     1     2 3    2    2 P2 4     0     1 9    0    2 P3 0     2     0 7    5    3 P4 1     1     2 1    1    2

Solution:

1. Content of the need matrix can be calculated by using the below formula

Need = Max – Allocation

 Process Need A B C P0 3 2 1 P1 1 1 0 P2 5 0 1 P3 7 3 3 P4 0 0 0

⸫⸫

2. Now, we check for a safe state

Safe sequence:

Available = (2, 1, 0)

Need ≤ Available = False

So, the system will move for the next process.

Available = (2, 1, 0)

Need ≤ Available = True

Request of P1 is granted.

⸫                          Available = Available +Allocation

= (2, 1, 0) + (2, 1, 2)

= (4, 2, 2) (New Available)

Available = (4, 2, 2)

Need ≤ Available = False

So, the system will move to the next process.

Available = (4, 2, 2)

Need ≤ Available = False

So, the system will move to the next process.

Available = (4, 2, 2)

Need ≤ Available = True

Request of P4 is granted.

⸫                          Available = Available +Allocation

= (4, 2, 2) + (1, 1, 2)

= (5, 3, 4) now, (New Available)

Available = (5, 3, 4)

Need ≤ Available = True

Request of P2 is granted.

⸫                          Available = Available +Allocation

= (5, 3, 4) + (4, 0, 1)

= (9, 3, 5) now, (New Available)

Available = (9, 3, 5)

Need ≤ Available = True

Request of P3 is granted.

⸫                          Available = Available +Allocation

= (9, 3, 5) + (0, 2, 0) = (9, 5, 5)

= Available (9, 5, 5)

Need ≤ Available = True

So, the request will be granted to P0.

Safe sequence: < P1, P4, P2, P3, P0>

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

3. The total amount of resources = sum of columns of allocation + Available

= [8 5 7] + [2 1 0] = [10 6 7]

by