Deadlock Avoidance or Bankler's Algorithm

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:

• If a system is in the safe state ⇒ no deadlocks.
• If a system is in an unsafe state ⇒ possibility of deadlock.
• Avoidance ⇒ ensures that a system will never enter an unsafe state.

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.

Bankers Algorithms for a single resource

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

• Step 1
  With the current free resources process, B can be executed, since the need of B ≤ Free i.e 2 ≤ 3 So B executes. After execution of B, it releases the resources allocated by it.
  Total free resource becomes, free = current free + Allocation by B = (1+2+2) = 5
• Step 2
  Now, with the current free resources process C can be executed, since the need for C ≤ Free i.e 5 ≤ 5 So C executes. After execution of C, it releases the resources allocated by it.
  Total free resource becomes, free = current free + Allocation by C = (5+2) = 7
• Step 3
  With the current free resources process, A can be executed, since the need of A ≤ Free i.e 6 ≤ 7 So A executes. After execution of A, it releases the resources allocated by it.
  Total free resource becomes, free = current free + Allocation by A = (1+6+3) = 10
  Here all the process runs successfully hence they are in a safe state and occurs no deadlock.
  The safe sequence is: B→C→A

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

• Step 1
  With the current free resources process, B can be executed, since the need for B ≤ Free i.e 2 ≤ 2 So B executes. After execution of B, it releases the resources allocated by it.
  Total free resource becomes, free = current free + Allocation by B = (2+2) = 4
  With current free resources, none of the processes can be further be executed hence processes are unsafe and occurs deadlock.

Bankers Algorithm for multiple resources

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:

• 5 tape drives
• 2 graphic displays
• 4 printers
• 3 disks

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.

Disadvantages of the Banker's Algorithm

• It requires the number of processes to be fixed; no additional processes can start while it is
  executing.
• It requires that the number of resources remains fixed; no resource may go down for any reason
  without the possibility of deadlock occurring.
• It allows all requests to be granted infinite time, but one year is a finite amount of time.
• Similarly, all of the processes guarantee that the resources loaned to them will be repaid in a
  finite amount of time. While this prevents absolute starvation, some pretty hungry processes
  might develop.
• All processes must know and state their maximum resource need in advance.