Deadlock Detection And Recovery in OS
Deadlock Detection and Recovery in Operating System
Deadlock Detection is an important task of OS. As the OS doesn’t take many precautionary means to avoid it. The OS periodically checks if there is any existing deadlock in the system and take measures to remove the deadlocks.
There are 2 different cases in case of Deadlock detection –
- If resource has single Instance
- We make a Wait- For graph.
- If resources have multiple instances
- We make a different algorithm. (We will discuss these algorithm in future posts)
If Resources has Single Instance
A wait-for graph is made. A Wait-for graph vertex denotes process. The edge implies process waiting for Process 2 to release resource. A deadlock is detected if one wait-for graph contains a cycle.
Wait-for graph is made by looking at resource allocation graph. An edge between P1 to P2 exists if P1 needs some resource which P2 has.
In the above wait-for graph P1 is waiting for resource currently in use by P2 and P2 is waiting for resource currently in use by P3 and so on… P5 is waiting for resource currently in use by P1. Which creates a cycle thus deadlock is confirmed.
To detect cycle, system maintains the wait state of graph and periodically invoke an algorithm to detect cycle in graph.
If there are multiple instances of resources –
By multiple instance we mean one resource may allow 2 or more accesses concurrently, in such cases –
- Wait for graph is not applicable.
- In this, a new algorithm is used. It’s a bit similar to Banker’s Algorithm, but Bankers Algorithm is different.
- It too uses 3 data structures –
- Vector of length m
- Indicates number of available resources of each type.
- Matrix of size n*m
- A[i,j] indicates the number of j th resource type allocated to i th process.
- Matrix of size n*m
- Indicates request of each process.
- Request[i,j] tells number of instance Pi process is request of jth resource type.
The Algorithm for detection is –
Check this page here to learn how to solve Deadlock Detection Algorithm.
Time Complexity is O(m*n*n).
Deadlock can be recovered by
- Kill the Process – One way is to kill all the process in deadlock or the second way kill the process one by one, and check after each if still deadlock exists and do the same till the deadlock is removed.
- Preemption – The resources that are allocated to the processes involved in deadlock are taken away(preempted) and are transferred to other processes. In this way, system may recover from deadlock as we may change system state.
- Rollback – The OS maintains a database of all different states of system, a state when the system is not in deadlock is called safe state. A rollback to previous ‘n’ number of safe states in iterations can help in the recover.