Explain deadlock avoidance technique for a single instance of each resource type

Overview

Deadlock Avoidance is used by Operating System to Avoid Deadlock in the System. The processes need to specify the maximum resources needed to the Operating System so that the Operating System can simulate the allocation of available resources to the requesting processes and check if it is possible to satisfy the need of all the processes requirements.

Scope

This article explains :

• What is Deadlock avoidance
• How does Deadlock avoidance work
• Safe and Unsafe state
• Deadlock avoidance example
• Resource Allocation Graph
• Banker's Algorithm

Introduction

Deadlock Avoidance is a process used by the Operating System to avoid Deadlock. Let's first understand what is Deadlock in Operating System. Deadlock is a situation that occurs in 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 Operating System avoid Deadlock?

Operating System avoids Deadlock by knowing the maximum resources requirements of the processes initially, and also Operating System knows the free resources available at that time. 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 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 tells the Operating System are :

• P1 process needs a maximum of 9 resources (Resources can be any software or hardware Resource 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.
• 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, then 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 which 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 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 Operating System was able to satisfy the need 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 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 Operating System is not able to prevent Processes from requesting resources which can also lead to Deadlock, then the System is said to be in an Unsafe State.

Unsafe State does not necessarialy cause deadlock it may or maynot causes deadlock.

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

Deadlock Avoidance Example

Let's take an example that has multiple resources requirement for every Process. Let there be three Processes P1, P2, P3, and 4 resources R1, R2, R3, R4. The maximum resources 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.

Conclusion

• Deadlock Avoidance is used by Operating System to avoid Deadlock by using resource allocation Graph or by Banker's algorithm.
• Deadlock Avoidance work by letting the Operating System know the Process requirements of resources to complete their execution, and accordingly operating system checks if the requirements can be satisfied or not.
• If all the resources required of the Process are satisfied with the available resources, then the System is said to be in a Safe state.
• If all the resources requirements of the Process are not satisfied with the available resources in any possible way, then the System is said to be in an unsafe state.
• Safe state does not cause Deadlock.
• Unsafe state may or may not cause Deadlock.
• Resource Allocation Graph is used to represent all the Processes and resource states in the form of a graph.
• Banker's Algorithm checks for the s-state(safe state or unsafe state) before actually allocating the resources to the Processes.