Banker’s Algorithm
This algorithm is a deadlock avoidance algorithm.It means it will tell us if the processes are in deadlock or not and tell us what will be the safe sequence of processes .
Suppose,A=CPU=10,B=Memory=5,C=Printer=7
It means there are 10 instances of CPU,5 instances of memory and 7 instances of printer
Allocation columns denotes that how many instances of A,B,C are allocated to each process.
Max need columns denotes how many instances of A,B,C are required for a process to execute successfully.
For example- if p1 process gets 7 instances of A,5 instances of B,3 instances of C then p1 will get executed successfully.
Remaining need column denotes (Max need-allocation) column
Firstly,total 7 instances of A , 2 instances of B and 5 instances of C are already allocated.
So,available number of instance A=10–7=3
available number of instance B=5–2=3
available number of instance C=7–5=2
So,available list a list where number of free instances are stored.
Idea is to traverse through the Remaining Need and check which process fulfills the below condition.
safeSeq=[] //a list that holds the safe sequence of all process
If(Remaining needs of all instances are equal or less than available instances):
safeSeq.push(particular process)
Available_list += Allocation
Now we check Remaining Need from p1 to p5 and find that p2 process is the first process that fulfills the condition as
(1)process P2 fulfills the condition and so allocated instances are added with available list.
(1,2,2) < (3,3,2)
So, safeSeq=[p2]
Available list=[3+2,3+0,2+0]=[5,3,2]
(2) process P4 fulfills the condition and so allocated instances are added with available list.
(2,1,1) < (5,3,2)
Available list=[5+2 ,3+1 , 2+1 ]=[7, 4 , 3]
(3) process P5 fulfills the condition and so allocated instances are added with available list.
(5,3,1) < (7,4,3)
Available list= [7+0 , 4+0 , 3+2 ] = [ 7,4,5]
(4) process P1 fulfills the condition and so allocated instances are added with available list.
(7,4,3) < (7,4,5)
Available list= (7+0 , 4+1 , 5+0 )=(7,5 ,5)
(5) process P3 fulfills the condition and so allocated instances are added with available list.
(6,0,0) < (7,5,5)
Available list=[7+3,5+0,5+2]=[10 , 5, 7]
So,all process are executed successfully .For this reason ,there is no deadlock.
And the safe sequence is —
p2->p4->p5->p1->p3
[N.B]if a condition arises that no available process is fulfilling the above condition.Then it means there is a deadlock.
Below link has the implementation of it.
https://github.com/Sajid576/OS-Lab/blob/master/Bankers%20Algorithm/bankers.py
