Published by: Zaya
Published date: 22 Jun 2021
The Banker’s algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra. Resource allocation state is defined by the number of available and allocated resources and the maximum demand of the processes. When a process requests an available resource, the system must decide if immediate allocation leaves the system in a safe state.
Algorithm
1) Find a row in the Need matrix which is less than the Available vector. If such a row exists, then the process represented by that row may complete with those additional resources. If no such row exists, eventual deadlock is possible.
2) Double check that granting these resources to the process for the chosen row will result in a safe state. Looking ahead, pretend that that process has acquired all its needed resources, executed, terminated, and returned resources to the Available vector. Now the value of the
The available vector should be greater than or equal to the value it was previously.
3) Repeat steps 1 and 2 until
a) all the processes have successfully reached pretended termination (this implies that the initial state was safe); or
b) deadlock is reached (this implies the initial state was unsafe)
Basic Facts:
Some terminologies
a) Available
It represents the number of available resources of each type.
b) Max
It represents the maximum number of instances of each resource that a process can request.
c) Allocation
It represents the number of resources of each type currently allocated to each process.
d) Need
It indicates the remaining resource needs of each process.
Example 1: State whether the given processes are in deadlock or not. Given that resource, instance is 10.
Process | Allocated | Maximum |
A | 3 | 9 |
B | 2 | 4 |
C | 2 | 7 |
Solution;
Calculating need resources, using
Need = Maximum - Allocated we get,
process | Allocated | Maximum | Need |
A | 3 | 9 | 6 |
B | 2 | 4 | 2 |
C | 2 | 7 | 5 |
Here currently total allocation = 3+2+2 = 7
So free = total available – current allocation = 10 – 7 = 3
Example 2: State whether the given processes are in deadlock or not. Given that resource instance is 10.
Process | Allocated | Maximum |
A | 4 | 9 |
B | 2 | 4 |
C | 2 | 7 |
Solution,
Calculating need resources, using
Need = Maximum - Allocated we get,
process | Allocated | Maximum | Need |
A | 4 | 9 | 5 |
B | 2 | 4 | 2 |
C | 2 | 7 | 5 |
Here currently total allocation = 4+2+2 = 8
So free = total available – current allocation = 10 – 8 = 2
Example 1: A system has four processes P1, P2, P3, and P4 and three resources R1, R2, and R3 with existing resources E = (15, 9, 5). After allocating resources to all the processes available resources becomes A = ( 3, 2, 0). State whether the process is safe or not using the banker’s algorithm. If safe,
write the safe sequence.
Note: If Need is not given, it can be calculated using Need = Maximum – Allocation
Solution:
We have A = ( 3, 2, 0)
Step 1: With current available resources A = ( 3, 2, 0) P4 can be executed.
Since need of P4 ≤ A i.e. (2,1,0) ≤ (3,2,0) so P4 executes
After complete execution of P4 it releases the resources which is allocated by it. Now total current available resources A becomes, A = previous free + Allocation by P4
A = (3,2,0) + (2,1,3) = (5,3,3)
Step 2: With current available resources A = ( 5, 3, 3) P1 can be executed.
Since need of P1 ≤ A i.e. (0,2,1) ≤ (5,3,3) so P1 executes
After complete execution of P1 it releases the resources which is allocated by it. Now total current available resources A becomes, A = previous free + Allocation by P1
A = (5,3,3) + (3,0,1) = (8,3,4)
Step 3: With current available resources A = ( 8, 3, 4) P3 can be executed.
Since need of P3 ≤ A i.e. (1,0,4) ≤ (8,3,4) so P3 executes
After complete execution of P3 it releases the resources which is allocated by it. Now total current available resources A becomes, A = previous free + Allocation by P3
A = (8,3,4) + (2,2,0) = (10,5,4)
Step 4: With current available resources A = ( 10, 5, 4) P2 can be executed.
Since need of P2 ≤ A i.e. (1,4,1) ≤ (10,5,4) so P2 executes
After complete execution of P2 it releases the resources which is allocated by it. Now total current available resources A becomes, A = previous free + Allocation by P2
A = (10,5,4) + (5,4,1) = (15,9,5)
Here all the process runs hence they are in a safe state and occurs no deadlock.
The safe sequence is: P4→P1→P3→P2
Example 2:
Assume we have the following resources:
We can create a vector representing our total resources: Total = (5, 2, 4, 3).
Consider we have already allocated these resources among four processes as demonstrated by the following matrix named Allocation.
Process Name | Tape Drives | Graphics | Printers | Disk Drives |
Process A | 2 | 0 | 1 | 1 |
Process B | 0 | 1 | 0 | 0 |
Process C | 1 | 0 | 1 | 1 |
Process D | 1 | 1 | 0 | 1 |
The vector representing the allocated resources is the sum of these columns:
Allocated = (4, 2, 2, 3).
We also need a matrix to show the number of each resource still needed for each process; we call this matrix Need.
Process Name | Tape Drives | Graphics | Printers | Disk Drives |
Process A | 1 | 1 | 0 | 0 |
Process B | 0 | 1 | 1 | 2 |
Process C | 3 | 1 | 0 | 0 |
Process D | 0 | 0 | 1 | 0 |
The vector representing the available resources will be the sum of these columns subtracted from the Allocated vector: Available = (1, 0, 2, 0).
Following the algorithm sketched above,
Iteration 1:
Examine the Need matrix. The only row that is less than the Available vector is the one for Process D.
Need(Process D) = (0, 0, 1, 0) < (1, 0, 2, 0) = Available
If we assume that Process D completes, it will turn over its currently allocated resources, incrementing the Available vector.
(1, 0, 2, 0) Current value of Available
+ (1, 1, 0, 1) Allocation (Process D)
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `
(2, 1, 2, 1) Updated value of Available
Iteration 2:Examine the Need matrix, ignoring the row for Process D. The only row that is less than the Available vector is the one for Process A.
Need(Process A) = (1, 1, 0, 0) < (2, 1, 2, 1) = Available
If we assume that Process A completes, it will turn over its currently allocated resources, incrementing the Available vector.
(2, 1, 2, 1) Current value of Available
+ (2, 0, 1, 1) Allocation (Process A)
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `
(4, 1, 3, 2) The updated value of Available
Iteration 3:
Examine the Need matrix without the row for Process D and Process A. The only row that is less than the Available vector is the one for Process B.
Need(Process B) = (0, 1, 1, 2) < (4, 1, 3, 2) = Available
If we assume that Process B completes, it will turn over its currently allocated resources, incrementing the Available vector.
(4, 1, 3, 2) Current value of Available
+ (0, 1, 0, 0) Allocation (Process B)
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `
(4, 2, 3, 2) The updated value of Available
Iteration 4:
Examine the Need matrix without the rows for Process A, Process B, and Process D. The only row left is the one for Process C, and it is less than the Available vector.
Need(Process C) = (3, 1, 0, 0) < (4, 2, 3, 2) = Available
If we assume that Process C completes, it will turn over its currently allocated resources, incrementing the Available vector.
(4, 2, 3, 3) Current value of Available
+ (1, 0, 1, 1) Allocation (Process C)
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `
(5, 2, 4, 3) The updated value of Available
Notice that the final value of the Available vector is the same as the original Total vector, showing the total number of all resources:
Total = (5, 2, 4, 2) < (5, 2, 4, 2) = Available
This means that the initial state represented by the Allocation and Need matrices is a safe state.
The safe sequence that assures this safe state is .
Note: The Banker's algorithm can also be used in the detection of deadlock.