Deadlock Avoidance

Deadlock avoidance is achieved through Banker’s Algorithm. It cannot be implemented in real life.

What is a Banker Algorithm?

Banker’s Algorithm is also known as the deadlock avoidance algorithm. It looks at all requests made by processes to get resources, and 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 the requested is granted otherwise it is an unsafe state, a 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 following conditions:

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 also say 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 lead to a deadlock.

Why Banker’s algorithm is called banker?

The Banker’s Algorithm derives its name from the bank; in a banking system, it ensures that the bank does not run out of resources because the bank would never allocate all its money in such a way that it can no longer satisfy the needs of all its customers.

Explain with Question

banker algorithms question

Find the safe sequence.

banker algorithms question solution

In the above question, there are 5 processes (P1…..P5) are requesting for 3 resources (A, B, C).

P1 gives me 7 instances of A, 5 instances of B, and 3 instances of C to execute itself successfully. In the same way, P2, P3….P5 request for some instances given in the question.

In the end, the banker algorithm tells us whether the deadlock happens or not. That’s why it’s called the deadlock deduction algorithm

Solution:

To find whether the deadlock is happening or not through the 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 resources.

Step 3:  Find Current Available?

Current available Resource of A = Total Resources of A – Total Allocation Resources of A. In the same way, we can calculate the current available resources for B and C resources.

Step 4: Compare the current available resources with the remaining needs of all resources. If Current availability is greater or equal to the 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 requires more resources than currently available resources. Process P2 will get executed because the Remaining need of P2 for resources A=1, B=2, C=2 is less than the current available resources A=3, B=3, C=2 resources. So P2 gets 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) 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

Let’s check now the next remaining Process, which is P3, because P2 is already executed. P3 also gets 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 more than one safe sequence may be possible.

banker algorithms question to solution

If all processes are executed successfully, then no deadlocks occur. If one process executes and others do not, then first come in a safe sequence, and the 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?

Solution:

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 the same resource type. Each process can request a max of “K” instances. 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 formula                   

Resources + 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 the same resource type. Each process can request a max of “K” instances. 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 formula                   

Resources + 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