Deadlock Avoidance in OS
Overview
Deadlock Avoidance is used by the Operating System to Avoid Deadlock in the System. Deadlock avoidance is crucial for maintaining the stability and performance of computer systems.
The processes need to specify the maximum resources needed by 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. OS deadlock avoidance techniques are used to manage shared resources and avoid deadlocks in system resources, ensuring efficient and reliable operation.
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.
Deadlock Prevention
Deadlock prevention is a proactive strategy used by the operating system to ensure that deadlocks never occur in the first place. This is achieved by making sure that at least one of the four necessary conditions for deadlock—mutual exclusion, hold and wait, no preemption, and circular wait—is never allowed to exist in the system. By carefully managing how resources are allocated, the operating system can prevent deadlocks before they start.
For example, the operating system might prevent the hold and wait condition by requiring processes to request all the resources they will need at once, or it might prevent circular wait by enforcing a strict order in which resources can be requested. While these deadlock prevention techniques can be effective, they often require the operating system to use additional processing power and can make resource allocation more complex. Therefore, it is important to strike a balance between system efficiency and the need to prevent deadlocks. Efficiently allocating resources while ensuring that deadlock prevention measures are in place is a key challenge for modern operating systems.
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. When processes process requests for resources, the Operating System evaluates these requests to determine if granting the requested resources will keep the system in a safe state. 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 system state, then the Operating System does not proceed further with the allocation sequence. If the system cannot safely grant a process's request, the process must wait, and the system state is carefully monitored to avoid deadlocks.
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.
| Process | Maximum Required | current Available | Need |
|---|---|---|---|
| P1 | 9 | 5 | 4 |
| P2 | 5 | 2 | 3 |
| P3 | 3 | 1 | 2 |
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 (resources allocated), and its remaining resource requirement is 4. This means P1 needs 4 more resources to complete its execution (how many more resources).
-
P2 process needs a maximum of 5 resources and is currently allocated with 2 resources.Its remaining resource requirement is 3, so it needs 3 more resources to complete its execution (how many more resources).
-
P3 process needs a maximum of 3 resources and is currently allocated with 1 resource. Its remaining resource requirement is 2, so it needs 2 more resources to complete its execution (how many more resources).
The Operating System knows that only 2 resources out of the total available resources are currently free. The system checks if there are enough resources to proceed with the next process.
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 (enough resources). If P3 takes 2 resources and completes its execution, then P3 will release resources (release resources) and return its 3 (1+2) resources to the system. 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 resources (release resources) and return 5 (2+3) resources. Now five resources are free. P1 can now take 4 out of the 5 free resources (enough resources) and complete its execution. After completion, P1 will also release resources (release resources) back to the system. 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>. In this scenario, there was at least one sequence of resource allocation that allowed all processes to complete without deadlock.
What if initially there was only 1 free resource available? None of the processes would be able to complete its execution, as there would not be enough resources to satisfy any remaining resource requirement. Thus leading to an unsafe state.
We use two words, safe and unsafe states. What are those states?
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.
Hold and Wait
The hold and wait condition is a common scenario in resource allocation where a process holds at least one resource and is waiting to acquire additional resources that are currently held by other processes. This situation is one of the four necessary conditions for a deadlock to occur in an operating system.
To prevent deadlocks caused by hold and wait, the operating system can implement a resource allocation protocol that requires processes to request all the resources they will need before they begin execution. If all the resources are not available at the time of the request, the process must wait until it can acquire all the resources simultaneously. By ensuring that processes do not hold onto some resources while waiting for others, the operating system can effectively prevent deadlocks related to the hold and wait condition. This approach, while sometimes leading to lower resource utilization, is a straightforward way to enhance system stability and prevent deadlocks.
Circular Wait
Circular wait is another critical condition that can lead to deadlocks in an operating system. This condition arises when two or more processes are each waiting for a resource held by the next process in a circular chain, creating a cycle of dependencies that prevents any of the processes from proceeding.
To prevent deadlocks caused by circular wait, the operating system can enforce a resource allocation protocol where all resources are assigned a unique numerical order. Processes are required to request resources in a strictly increasing order of resource IDs. By following this predefined order, the system ensures that circular wait cannot occur, as it is impossible for two or more processes to form a cycle in their resource requests. This method is a practical way for the operating system to prevent deadlocks and maintain smooth resource allocation among multiple processes.
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.
| Process | R1 | R2 | R3 | R4 |
|---|---|---|---|---|
| P1 | 3 | 2 | 3 | 2 |
| P2 | 2 | 3 | 1 | 4 |
| P3 | 3 | 1 | 5 | 0 |
A number of currently allocated resources to the processes are:
| Process | R1 | R2 | R3 | R4 |
|---|---|---|---|---|
| P1 | 1 | 2 | 3 | 1 |
| P2 | 2 | 1 | 0 | 2 |
| P3 | 2 | 0 | 1 | 0 |
The total number of resources in the System are :
| R1 | R2 | R3 | R4 |
|---|---|---|---|
| 7 | 4 | 5 | 4 |
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 :
| R1 | R2 | R3 | R4 |
|---|---|---|---|
| 2 | 1 | 1 | 1 |
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:
| Process | R1 | R2 | R3 | R4 |
|---|---|---|---|---|
| P1 | 2 | 1 | 0 | 1 |
| P2 | 0 | 2 | 1 | 2 |
| P3 | 1 | 1 | 4 | 0 |
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:
-
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.
-
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>.
-
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
The choice between these algorithms depends on the resource categories in the system. The Resource Allocation Graph is typically used when resource categories have only single instances, while the Banker's Algorithm is suitable for multiple instances of resources. In the Resource Allocation Graph, a request edge is used to represent a process requesting a resource.
We will discuss both algorithms in detail in their separate article.Common deadlock avoidance techniques include the Banker's Algorithm and requiring processes to acquire resources in a predefined order to prevent circular waits.
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.In the Resource Allocation Graph, a cycle indicates that the system is in an unsafe state and could lead to a deadlock.
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. In the RAG, processes are represented as nodes, and resource requests and allocations are represented as edges. An example of RAG is shown below.
Allocation Matrix
The allocation matrix is a fundamental data structure used in deadlock avoidance algorithms, particularly the Banker’s algorithm, to manage and monitor resource allocation in an operating system. This matrix provides a clear overview of how many resources of each type are currently allocated to each process, as well as the total number of resources available in the system.
In the allocation matrix, each row represents a process, and each column corresponds to a specific resource type. The value at the intersection of a row and column indicates the number of resources of that type allocated to the process. By maintaining this matrix, the operating system can efficiently track resource usage and respond to resource requests from processes.
When a process makes a resource request, the deadlock avoidance algorithm uses the allocation matrix to simulate the allocation and determine if granting the request will keep the system in a safe state. If the system remains safe, the resources are allocated; otherwise, the request is denied or delayed. The allocation matrix is essential for ensuring that resources are allocated in a way that avoids deadlocks and maintains overall system stability.
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 uses a request matrix to track the resources requested by each process, and checks the resources allocated as well as the remaining resource needs for every process. The algorithm also determines how many more resources each process may need to finish execution. It ensures there is at least one sequence in which all processes can complete without causing a deadlock. 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.
- Deadlock avoidance helps to prevent the system from halting, which would necessitate manual intervention and degrade performance.