Abstract 

Banker’s algorithm helps to prevent deadlock conditions. The concept of a banker’s algorithm is the same as the concept of allocation of money in a bank. The banker never allocates more than the available.

Scope

This article explains the banker’s algorithm.

Definition

Deadlock avoidance means whenever a process requests some resources, the operating system checks whether granting these resources would lead to deadlock or not, if it might lead to deadlock, the operating system would not grant resources. This is the basic idea of deadlock avoidance.

Let us have a scenario where we have two resources and processes P0 to P4 are running.

	Allocated        R0                    R1	Maximum        R0                   R1
P0	0                        1	7                     5
P1	2                        0	3                     2
P2	3                        0	9                     0
P3	1                        1	2                     2
P4	0                        0	4                     3

TOTAL <10,5>

P0 is holding 0 instances of R0 and 1 instance of R1. P1 is holding 2 instances of R0 and 0 instances of R1 and so on. The maximum need for each process has also been declared. P0 has declared that it will never take more than 7 instances of R0 and 5 instances of R1. P1 has declared that it will never take more than 3 instances of R0 and 2 instances of R1. Here, we are making an assumption that every process declares its maximum need. It might not be possible but this is the assumption on which deadlock avoidance and banker’s algorithm work. 

There are a total of 10 instances of R0 and 5 instances of R1. If P3 requests for 1 instance of R0 and 0 instances of R1, should the operating system grant the request or not? This is the problem that we are going to solve.

So we have a scenario where some resources are allocated and we know the maximum need of every process. We have request <1,0> coming for the operating system. The operating system needs to run some algorithm on whether it should grant the request or should ask this process to wait. The problem is that P3 is requesting <1,0>, should P3 be allocated the request or not? 

The operating system performs the basic checks. It checks whether <1,0> is not more than the maximum. <1,1> is already taken and it is asking for <1,0>. The total allocation is going to be <2,1>. <2,1> is less than <2,2> so there is no problem. If the problem occurs an error is generated. 

After this second check is performed by the operating system. It checks the availability of resources. Total resources are <10,5>. 4 instances of R0 and 3 instances of R1 are allocated to P4. So no problem appears because the process is requesting  <1,0> and available is <4,3>. It would not generate any error. Suppose it was requesting for something which was within the maximum limit but greater than available then also the operating system would not allocate resources and will ask the process to wait.

The first two checks are passed for the request now comes the main part of the algorithm. The operating system assumes that it has allocated the resource then it checks whether the resources allocated are in a safe state or not. New allocation becomes <2,1> and available resources becomes <3,3>. This is the new state. The operating system assumes the resources are granted. It runs an algorithm to find out if allocation would lead to a safe state or not. If it does not lead to a safe state then the request is not granted.

The algorithm generates a safe sequence. If the sequence can be generated then it is in a safe state else not in a safe state. The safe sequence is a permutation to these processes. Consider P2 P3 P4 P0 P1 a safe sequence. If serial execution of the processes which happen to be one after another is possible, then it is a safe sequence. 

To find out if a safe sequence exists or not we first build a need matrix. Need matrix is built simply by subtracting allocated from the maximum. Once we have completed the need matrix then we run the algorithm. 

Algorithm

Safe seq = {}
while (All Ps are not added to the seq)
  Find a Pi such that
need i <= available
If(no such i exists)
return false
else(We found an i) {
  available += allocated i
  Add Pi to safe sequence
}
return true
}

	Allocated   R0                 R1	Maximum  R0                 R1	Need   R0                R1
P0	0                   1	7                  5	7                4
P1	2                   0	3                   2	1                 2
P2	3                   0	9                    0	6                0
P3	1                   1	2                    2	0               1
P4	0                   0	4                     3	4               3

TOTAL <10,5>
INITIAL AVAILABLE <3,3>
available = <5,3>
    P1
available = <7,4>
    P1 P3
available = <7,4>
    P1 P3 P4
available = <7,5>
    P1 P3 P4 P0
available = <10,5>
    P1 P3 P4 P0 P2

Let’s run the algorithm one by one. We need to find a process whose need is more than available.

Let’s check if P0 is satisfying the criteria. P0 need is <7,4> and available is <3,3>, it’s not satisfying the criteria because its need is more than available.

P1’s need is <1,2> and available is <3,3>. This satisfies the criteria so we update available as current available + allocated of P1. So available now becomes <5,3>.P1 is added to the safe sequence. 

We again iterate the loop and find a process whose need is smaller than available. P2 need is <6,0> and available is <5,3>. P2 is not such a process.

P3 need is  <0,1> and available is <5,3> so P3 follows the condition and is added to the safe sequence. Available now becomes <7,4>.

Now process P4 whose need is <4,3> and available is <7,4> follows the criteria. Now the safe sequence becomes P1 P3 P4. 

Now the search for the process continues. We check P0 again. Its need is <7,4> and available is <7,4> so P0 is added to the safe sequence and available becomes <7,5>.

Now only P2 is left. P2 need is <6,0> and available is <7,5>. It also follows the criteria and thus is added to the safe sequence. And available becomes <10,5>.

We have a safe sequence as P1 P3 P4 P0 P2. Since we have a safe sequence request is granted to P3.

Summary

In deadlock avoidance whenever the process requests whenever process requests for some resources we check whether the process is making the legitimate request or not. We check if it is not asking for more than the maximum. If it is fine then we check if it is not greater than the current available. Then we run an algorithm to check if allocating resources would lead to deadlock or not. The algorithm runs assuming that the resource is granted to the process and checks whether after allocation deadlock will happen or not. 

Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article