Deadlock detection and recovery is the method used to find and resolve deadlocks in an operating system. Deadlocks happen when processes are stuck, waiting for each other to release resources they need.
Let us see how we can detect a deadlock.
What is deadlock detection in OS?
A deadlock is a condition in an operating system where two or more processes want some event to happen, but it is not happening, and thus, all the processes are stuck. The necessary conditions for a deadlock to occur are Mutual Exclusion, No Preemption, Hold and Wait, and Circular Wait.
Steps for Detection and Recovery
Allow entering a deadlock: In a system, a deadlock can occur when processes compete for resources, leading to a situation where none of the processes can proceed. Allowing the system to potentially enter a deadlock means that there is a possibility that such situations may arise due to resource allocation policies.
Detection algorithm: Deadlock detection involves periodically examining the state of the system to determine if a deadlock has occurred. Common detection algorithms include the Resource Allocation Graph (RAG) and the Banker's algorithm. These algorithms analyze resource allocation and process states to identify circular waits, a characteristic of deadlock.
Recovery scheme: Once deadlock is detected, a recovery scheme is initiated to resolve the deadlock and restore system functionality. Recovery schemes can include approaches like process termination, resource preemption, and rollback. Process termination involves terminating one or more processes involved in the deadlock to break the circular wait. Resource preemption involves preempting resources from one or more processes to allow others to proceed. Rollback involves rolling back the state of certain processes to a point where deadlock is not present.
Approaches for Deadlock Detection and Recovery
Mainly, there are two broad approaches for deadlock detection and recovery. These are discussed below:-
Prevention
It is the approach that does not let a deadlock happen. The operating system ensures that the system is always in a safe state so there is no deadlock. The operating system uses algorithms for it, like the Banker's Algorithm.
Detection and Recovery
If, in any case, a deadlock occurs, then the operating system should be able to detect and recover from it. The operating system uses various detection algorithms, like the Wait-For Graph. And there are recovery algorithms, too, like RollBack and Abort algorithm. Basically, in recovery, the operating system frees the resources allowing the system to make progress.
We will look deep into the Deadlock Detection and Recovery methods below.
Algorithms Used for Deadlock Detection
The two algorithms that you can use for detecting Deadlock:
If the system has a cycle, it's experiencing Deadlock, and if there is no cycle, then there is no deadlock in the system.
Consider this RAG(Resource Allocation Graph):
To convert this into a Wait-for graph:
First, remove all resource nodes and join the edges, i.e., the edge from P1 to R1, and the edge from R1 to P2, similarly doing this with all edges.
After this, check if the wait-for graph has a cycle and if it's in a deadlock state.
P1 => P2 => P3 => P4, It is forming a cycle; hence it is in a deadlock state.
Some points to remember:
Invoke an algorithm to detect cycles periodically.
The complexity of such an algorithm is n^2, n=number of vertices.
Multiple Instance
The resource allocation graph is converted into the request matrix and the resource distribution matrix by using some safety algorithms on the system.
A similar algorithm to the banker's Algorithm is used for this.
We can accomplish this by using the following three data structures.
Available[m]: A vector of length m indicates the number of available resources of each type. Suppose Available[j]=k, then k instances of resource type Rj are available.
Allocation[n][m]: This matrix indicates each process’s n X m allocated resources. Suppose Allocation[i,j]=k; then Pi is allocated k instances of Rj.
Request[n][m]: This matrix indicates the current Request of each process. If Request [i, j] = k, then process Pi requests k more instances of resource type Rj.
Before starting with the Algorithm, first, Let's know about the safe state.
Safe state: In this process, when requesting an available resource, the system must decide if allocation leaves the system in a safe state or not. It is in a safe state if a safe sequence of all processes exists.
In this, we need to convert it into a safe sequence so that the system can be deadlock-free.
Let's check if the system is in a deadlock state or not.
First, find out the process whose Request (R1) <= Available P1. (P1)
Update the availability with the previous allocation.
Step 1:
Suppose Work and Finish be vectors of length m and n respectively.
a) Initialize Work = Available
b) For i=0,1,2…..... n
if Allocation(i) != 0
then
Finish[i] = false;
else
Finish[i] = true;
Step 2:
Find an index(i) such that both
a) Finish[i] = false
b) Request(i) <= Work.
If no such I exist, go to step 4.
Step 3:
Set:
Work = Work + Allocation(i)
Finish[i] = true
Go to step 2.
Step 4:
If Finish[i] = false for some i where 0 < i < n, then the system is in a deadlock state
The Algorithm requires an order of O(m x n2) operations to detect whether the system is in a deadlocked state.
When to invoke a Detection Algorithm?
The detection algorithm must be invoked in the following two situations:
Situation 1: Every time a process requests a resource, we call the detection algorithm. Using this algorithm, you will identify → a set of deadlocked processes and → the specific process causing the Deadlock.
Situation 2: The deadlock algorithm must execute in periodic intervals. → You can do that once in an hour or whatever preferred time duration you want. → Whenever CPU utilization drops below a certain threshold.
In this Algorithm, you will not identify which process is involved in the Deadlock.
Once you can detect the Deadlock now, you will need to recover from it.
Kill a Process In this process, the process responsible for the Deadlock is terminated. However, selecting which process to kill can be difficult. As a result, the operating system primarily kills the process that no longer works.
Kill all Processes
It is not appropriate to kill all the processes. However, when a critical situation arises, this approach may be suitable.
Killing all processes reduces the system's efficiency, so we must start all the processes again.
Resource Preemption
Preemption
Here, we transfer resources from one process to the process that needs them to finish its execution, and once that process is done, the resource is released.
The selection of resources is complex, and grabbing the resources is also challenging. Several states are necessary for the system to reach the Deadlock.
RollBack
A rollback of the system to the earlier safe state is possible using the operating system. This requires the implementation of checkpoints in every state.
When we identify Deadlock, we must roll back all allocations and return to the previous safe state.
Advantages of Deadlock Detection and Recovery in OS
Here are some advantages of deadlock detention and recovery in OS.
System Stability: Deadlock detection and recovery techniques help to keep operating systems stable by finding and resolving deadlocks as soon as possible.
Resource Optimisation: By detecting and resolving deadlocks, system resources can be used more efficiently, reducing wastage.
Process Continuity: Deadlock detection guarantees that processes do not become stuck indefinitely, allowing them to continue execution and finish their job.
Improved System Performance: By identifying and recovering from deadlocks, overall system performance is improved because processes can continue uninterrupted.
Disadvantages of Deadlock Detection and Recovery in OS
Here are some disadvantages of deadlock detention and recovery in OS.
Increased Complexity: Applying deadlock detection and recovery features to the operating system increases its complexity, making it more difficult to design, implement, and maintain.
Resource Utilisation: Recovery measures such as process termination or resource preemption can result in inefficient resource utilization, which may affect system efficiency.
Delay in Process Execution: Deadlock detection and recovery operations may cause delays in process execution, possibly affecting time-sensitive applications or real-time systems.
Limited Scalability: When working with large-scale systems or a large number of parallel processes, deadlock detection methods can encounter scalability issues, resulting in increased detection time or resource usage.
Frequently Asked Questions
What is deadlock detection in OS?
Deadlock detection in OS involves periodically checking system state to identify if processes are stuck in a deadlock, where none can progress due to resource contention.
What are the 4 types of deadlock?
The four types of deadlock are mutual exclusion, hold and wait, no preemption, and circular wait.
What is deadlock prevention in OS?
Deadlock prevention in OS involves implementing strategies like resource allocation policies and ordering resources to prevent the occurrence of deadlock situations.
What is deadlock in OS diagram?
A deadlock in an OS diagram typically depicts a scenario where processes are blocked, unable to proceed due to circular waiting for resources, forming a closed loop.
Conclusion
In this blog, we have discussed Deadlock Detection in OS. Deadlock detection in operating systems serves as a crucial mechanism for maintaining system stability and preventing gridlock scenarios. By periodically assessing process states and resource allocations, deadlock detection algorithms offer insights into system health and enable timely interventions.
Once you've uncovered the Deadlock, you'll have to determine how to resolve the Deadlock.
306+ registered