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:
Disadvantages of Banker’s Algorithm
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 Request_{i} is the request array for the process ‘P_{i}’. Request_{i }[j] = k means ‘P_{i}’ process needs k instances of R_{j }resource type. At the time when a process P_{i }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 |
P_{0} | 1 1 2 | 4 3 3 | 2 1 0 |
P_{1} | 2 1 2 | 3 2 2 | |
P_{2} | 4 0 1 | 9 0 2 | |
P_{3} | 0 2 0 | 7 5 3 | |
P_{4} | 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 | |
P_{0} | 3 | 2 | 1 |
P_{1} | 1 | 1 | 0 |
P_{2} | 5 | 0 | 1 |
P_{3} | 7 | 3 | 3 |
P_{4} | 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 P_{1 }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 P_{4 }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 P_{2 }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 P_{3 }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 P_{0}.
Safe sequence: < P_{1,} P_{4,} P_{2,} P_{3,} P_{0>}
_{ }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]