Deadlock avoidance is achieved through Banker’s Algorithm. It cannot implement in real-life.
What is Banker Algorithm?
Banker’s Algorithm is also known as deadlock avoidance algorithm. It looks at all request made by processes to get resources, it checks for the safe state, If the request given by the process is less than equal to (<=) freely available resource in the system, then it is a safe state and requested is granted otherwise it is a unsafe state, deadlock will be there.
Inputs to Banker’s Algorithm:
- Currently allocated resources by each process.
- Max need of resources by each process.
- Max free available resources in the system.
The request will only be granted under the below condition:
If the request made by the process is less than equal to the freely available resource in the system.
Safe State: A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock.
We can say also a system is in a safe state only if there exists a safe sequence.
Unsafe State: If there is no safe sequence, then the system will be in an unsafe state, which may leads toward deadlock.
Why Banker’s algorithm is called banker?
The Banker’s Algorithm derives its name from bank, in a banking system it is ensure that the bank does not run out of resources, because the bank would never allocate its all money in such a way that it can no longer satisfy the needs of all its customers.
Explain with Question
Find the safe sequence?
In the above question, there are 5 processes (P1…..P5) are requesting for 3 resources (A, B, C).
P1 says gives me a 7 instance of A, 5 instances of B and 3 instances of C to execute itself successfully. In the same way P2, P3….P5 requesting for some instances given in the question.
In the end, banker algorithm tells us whether the deadlock happens or not, that’s why it’s called deadlock deduction algorithm
To find whether the deadlock is happen or not through Banker Algorithm, we have to follow the four basic steps.
Step 1: Find the Total Allocation Resources of A, B and C?
Step 2: Find the Remaining Need?
Remaining need Of A = MAX Need of A – Allocation of A. and the same for B and C resource.
Step3: Find Current Available?
Current available Resource of A = Total Resources of A – Total Allocation Resources of A. In the same way we can calculate Current available Resource for B and C resource.
Step 4: Compare the current available resources with remaining need of all resources. If Current availability is greater or equal to remaining need then that process will get executed and our safe state will start from that process and that process will release its Allocation resources after execution for other processes.
Process Execution Explain Under
As through step 4, P1 cannot execute because it’s require more resources as compare to current available resources. Process P2 will get executed because Remaining need of P2 for resources A=1, B=2, C=2 is less than current available resources A=3, B=3, C=2 resources. So P2 get executed.
When P2 is executed it will release allocation resources A=2, B=0,C=0 these resources are added in Current available resources. So current available resources will be A= 5, B=3, C=2
Now we check the remaining process first (but not mandatory) and resume for P2 and check for P3. P3 cannot execute and we check P4 which will execute easily. At this position Safe sequence will be p2àp4 and current available resources will be A= 7, B=4, C=3
Now, we will check for P5 which will also executed then Safe sequence will be P2 → P4 → P5 and current available resources will be A= 7, B=4, C=5
Recheck again now, for P1 which will also execute then Safe sequence will be P2 → P4 → P5 → P1 and current available resources will be A= 7, B=5, C=5
Lets check now, the next remaining Process which is P3 because P2 is already executed. P3 also get executed here because available resources are greater than required. Then Safe sequence will be P2 → P4 → P5 → P1 → P3 and current available resources will be A= 10, B=5, C=7.
Here we can also verify that if current available resources = total given resources after execution of all resources then there is a correct sequence.
Note that there may be more than one safe sequences can be possible.
If all process is executed successfully then no deadlocks occur. If one process execute and others not then first come in safe sequence and other goes to deadlock?
Now Look at Deadlock Avoidance Questions.
Question No 1:
A system is having 3 processes each require 2 units of resources “R” The minimum no of units of “R” such that no deadlock will occur
Case 01: Manual Calculations
If we have only 1 resource then that one resource may allocate to any process like P1 and still P1 require 1 more resource and we have no more resource and P2 and P3 are waiting for 2, 2 resources which will execute after P1 execution but P1 never execute because P1 require 1 more resource which is not available. So deadlock will occur.
Processes P1 P2 P3 Resource 1
If we have 2 resources then resources are given to P1 (as the need of p1 is also 2) so it will execute successfully after P1, p2 also required 2 process and p2 also execute and same for p3.
Processes P1 P2 P3 Resource 2
But we have to check all possibilities of resources allocation
Like, if we have 2 resources and one resource may allocate to P1 and other may allocated to P2 and still p1 and p2 require 1 more resource to execute but we have no more resource and p3 is waiting for 2 resources which will execute after the execution of p1 or p2. But both p1 and p2 will never execute so deadlock will occur.
Processes P1 P2 P3 Resource 1 1
Now check that if we have 3 resources and three process and we allocate one resource to each process the 3 resources are used but still all process require one more resource but we have no more resource so deadlock will occur.
Processes P1 P2 P3 Resource 1 1 1
Now if we have 4 resources and we allocate 1 resource to each process then 3 resources are used and still need of each process is 1 resource and we have 1 resource available. Any process can get this resource and can execute. We answer is 4.
Processes P1 P2 P3 Resource 2 1 1
Answer: So Answer is 4.
Case 02: Through Formula
Give the less 1 resource from the demand of every process and add 1 in previous total of resources. Explained Under
A process required Resource=2, Minimum Resource required = 2-1=1
B process required Resource=2, Minimum Resource required = 2-1=1
C process required Resource=2, Minimum Resource required = 2-1=1
Add 1 in total minimum resource required = 3+1=4
So, 4 are minimum resource for deadlock avoidance when there are 3 processes and every process required 2 processes.
Max resource for deadlock is 3 where it is minimum resources required-1.
Question No: 02
P1 required 3 resources, P2 required 4 resources, and P3 required 5 resources. How much minimum resources are required to remove deadlock?
Minimum need of resources to avoid deadlock= (P1 resources -1) + (P2 resources -1) + (P3 resources -1) +1 = (3-1) + (4-1) + (5-1) +1= 10
Maximum of resources which can be in deadlock
= Minimum need of resources to avoid deadlock -1= 10-1=9
Note: If we have three resources A,B and C. Suppose A has 5 instances, B has 1 instance and C contains 10 instance than it means we have total 16 resources. Where 5 are the type of A, 1 is type of B and 10 are type of C.
Question No 03:
Consider a system with 3 processes that share 4 instances of same resource type. Each process can request a max of “K” instance. Find the largest value of “K” which will always avoid deadlock _ ?
Case 01: Manual calculations
If a process is request for 3 resources and there are only 4 resources.
If the case is, there is an allocation of 2 resources to P1, 1 resource to P2 and 1 resource to P3 then deadlock will occur because P1 require one more resource to execute but we have nothing more to allocate.
Case 02: Through formulaResources + Processes > Total Demand Resources + Processes > (process) * (K value) 4+3>3*2 (condition true) 4+3>3*3(condition false)
So, the largest value of K will be 2 When the system is deadlock free.
If condition is true then no deadlock when condition is false then deadlock occurs. Because requesting for resource is greater than available resources. So value of K is much important
Question No: 04
Consider a system with 4 processes that share 4 instances of same resource type. Each process can request a max of “K” instance. Find the largest value of “K” which will always avoid deadlock __ ?
Case 01: Manual calculations
If every process is request (k=1) for one resource and 4 resources are available. Then there will be no deadlock. But if every process is requesting for 2 resources and there are only 4 resources then deadlock will occur. Because at the time, every process is holding one resource and waiting for second resource.
Case 02: Through formulaResources + Processes > Total Demand Resources + Processes > (process) * (K value) 4+4>4*1 (condition true) 4+4>4*2(condition false)
So, the largest value of K will be 1 When the system is deadlock free.
It was all about deadlock avoidance, next lecture we will see deadlock detection
If It Is Useful, Help Other’s By Sharing…