Deadlock Avoidance in OS

Introduction

Deadlock Avoidance is a process used by the Operating System to avoid Deadlock. Let's first understand what is Deadlock in an Operating System is. Deadlock is a situation that occurs in the Operating System when any Process enters a waiting state because another waiting process is holding the demanded resource. Deadlock is a common problem in multi-processing where several processes share a specific type of mutually exclusive resource known as a soft lock or software.

But how can an Operating System avoid Deadlock?

The operating system avoids Deadlock by knowing the maximum resource requirements of the processes initially, and also, the Operating System knows the free resources available at that time. The operating system tries to allocate the resources according to the process requirements and checks if the allocation can lead to a safe state or an unsafe state. If the resource allocation leads to an unsafe state, then the Operating System does not proceed further with the allocation sequence.

How does this happen? How does the Operating System allocate resources to the processes? We will try to understand the process of allocation of resources with an intuitive example further in this article.

How does Deadlock Avoidance Work?

Let's understand the working of Deadlock Avoidance with the help of an intuitive example.

Let's consider three processes P1, P2, P3. Some more information on which the processes tell the Operating System are :

• P1 process needs a maximum of 9 resources (Resources can be any software or hardware Resources like tape drive or printer etc..) to complete its execution. P1 is currently allocated with 5 Resources and needs 4 more to complete its execution.
• P2 process needs a maximum of 5 resources and is currently allocated with 2 resources. So it needs 3 more resources to complete its execution.
• P3 process needs a maximum of 3 resources and is currently allocated with 1 resource. So it needs 2 more resources to complete its execution.
• The Operating System knows that only 2 resources out of the total available resources are currently free.

But only 2 resources are free now. Can P1, P2, and P3 satisfy their requirements? Let's try to find out.

As only 2 resources are free for now, only P3 can satisfy its need for 2 resources. If P3 takes 2 resources and completes its execution, then P3 can release its 3 (1+2) resources. Now the three free resources that P3 released can satisfy the need of P2. Now, P2 after taking the three free resources, can complete its execution and then release 5 (2+3) resources. Now five resources are free. P1 can now take 4 out of the 5 free resources and complete its execution. So, with 2 free resources available initially, all the processes were able to complete their execution leading to a Safe State. The order of execution of the processes was <P3, P2, P1>.

What if initially there was only 1 free resource available? None of the processes would be able to complete its execution. Thus leading to an unsafe state.

We use two words, safe and unsafe states. What are those states? Let's understand these concepts.

Safe State and Unsafe State

Safe State - In the above example, we saw that the Operating System was able to satisfy the needs of all three processes, P1, P2, and P3, with their resource requirements. So all the processes were able to complete their execution in a certain order like P3->P2->P1.

So, If the Operating System is able to allocate or satisfy the maximum resource requirements of all the processes in any order then the system is said to be in Safe State.

So safe state does not lead to Deadlock.

Unsafe State - If the Operating System is not able to prevent Processes from requesting resources which can also lead to a Deadlock, then the System is said to be in an Unsafe State.

Unsafe State does not necessarily cause deadlock it may or may not cause deadlock.

So, in the above diagram shows the three states of the System. An unsafe state does not always cause a Deadlock. Some unsafe states can lead to a Deadlock, as shown in the diagram.

Deadlock Avoidance Example

Let's take an example that has multiple resource requirements for every Process. Let there be three Processes P1, P2, P3, and 4 resources R1, R2, R3, R4. The maximum resource requirements of the Processes are shown in the below table.

A number of currently allocated resources to the processes are:

The total number of resources in the System are :

We can find out the no of available resources for each of P1, P2, P3, P4 by subtracting the currently allocated resources from total resources.

Available Resources are :

Now, The need for the resources for the processes can be calculated by :

Need = Maximum Resources Requirement - Currently Allocated Resources.

The need for the Resources is shown below:

The available free resources are <2,1,1,1> of resources of R1, R2, R3, and R4 respectively, which can be used to satisfy only the requirements of process P1 only initially as process P2 requires 2 R2 resources which are not available. The same is the case with Process P3, which requires 4 R3 resources which is not available initially.

The Steps for resources allotment is explained below:

1. Firstly, Process P1 will take the available resources and satisfy its resource need, complete its execution and then release all its allocated resources. Process P1 is initially allocated <1,2,3,1> resources of R1, R2, R3, and R4 respectively. Process P1 needs <2,1,0,1> resources of R1, R2, R3 and R4 respectively to complete its execution. So, process P1 takes the available free resources <2,1,1,1> resources of R1, R2, R3, R4 respectively and can complete its execution and then release its current allocated resources and also the free resources it used to complete its execution. Thus P1 releases <1+2,2+1,3+1,1+1> = <3,3,4,2> resources of R1, R2, R3, and R4 respectively.

2. After step 1 now, available resources are now <3,3,4,2>, which can satisfy the need of Process P2 as well as process P3. After process P2 uses the available Resources and completes its execution, the available resources are now <5,4,4,4>.

3. Now, the available resources are <5,4,4,4>, and the only Process left for execution is Process P3, which requires <1,1,4,0> resources each of R1, R2, R3, and R4. So it can easily use the available resources and complete its execution. After P3 is executed, the resources available are <7,4,5,4>, which is equal to the maximum resources or total resources available in the System.

So, the process execution sequence in the above example was <P1, P2, P3>. But it could also have been <P1, P3, P2> if process P3 would have been executed before process P2, which was possible as there were sufficient resources available to satisfy the need of both Process P2 and P3 after step 1 above.

Deadlock Avoidance Solution

Deadlock Avoidance can be solved by two different algorithms:

• Resource allocation Graph
• Banker's Algorithm

We will discuss both algorithms in detail in their separate article.

Resource Allocation Graph

Resource Allocation Graph (RAG) is used to represent the state of the System in the form of a Graph. The Graph contains all processes and resources which are allocated to them and also the requesting resources of every Process. Sometimes if the number of processes is less, We can easily identify a deadlock in the System just by observing the Graph, which can not be done easily by using tables that we use in Banker's algorithm.

Resource Allocation Graph has a process vertex represented by a circle and a resource vertex represented by a box. The instance of the resources is represented by a dot inside the box. The instance can be single or multiple instances of the resource. An example of RAG is shown below.

Banker's Algorithm

Banker's algorithm does the same as we explained the Deadlock avoidance with the help of an example. The algorithm predetermines whether the System will be in a safe state or not by simulating the allocation of the resources to the processes according to the maximum available resources. It makes an "s-state" check before actually allocating the resources to the Processes.

When there are more number of Processes and many Resources, then Banker's Algorithm is useful.