Deadlock detection
- The detection mechanism of deadlocks for a single instance of the resource type and multiple instances of the resource type is different. We can detect the deadlocks using the wait-for graph for single instance resource type and detect using detection algorithm for multiple instances of the resource type.
- Single Instance of resource type: a single instance of resource type means, the system consisting of only one resource for one type. We can detect this type of deadlocks with the help of the wait-for graph. A wait-for graph is a graph, it is derived from “Resource-Allocation Graph”. It is consisting of only processes as vertices instead of, resources and processes in the resource-allocation graph.
 |
| Deadlock Detection and Recovery |
An edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj to release a resource that Pi needs. An edge Pi to Pj exists in a wait-for graph if and only if the corresponding resource allocation graph contains two edges Pi to Rq and Rq to Pj for some resource Rq.
For example, consider the previous figure. We represent a RAG and corresponding Wait-for graph. A system is in deadlock state, if and only if the wait for graph contains cycles. So we can detect the deadlocks with cycles. In the figure, there are 2 cycles one is P1 to P2 to P1. second one P2 to P3 to P2. so the system consisting of two deadlocks.
Deadlock detection –several instances of resource type:
- The wait-for graph method is not applicable to several instance of the resource type. So we need another method for this type that is the “Deadlock Detection Algorithm”. This algorithm looks like “Banker’s Algorithm” and its employee's several data structures that are similar to those used in the Bankers Algorithm.
Data Structures:
Available: A vector of length m indicates the number of available resources of each type.
Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process.
Request: An n x m matrix indicates the current request for each process. If Request [ij] = k, then process Pi is requesting k more instances of the resource type. Rj.
Detection Algorithm
Example of Detection Algorithm
Five processes P0 through P4; three resource types A (7 instances), B (2 instances), and C (6 instances).
Snapshot at time T0:
State of the system?
Can reclaim resources held by process P0, but insufficient resources to fulfill other processes; requests.
A deadlock exists, consisting of processes P1, P2, P3, and P4.
Recovery from Deadlock
There are two methods for breaking a deadlock. One solution is simply to abort one by one processes to break the circular wait. The second option is to preempt some resources from one or more of the deadlocked processes.
Process Termination:
It is one method to recover from deadlock. We use one of two methods for process termination, these are:
Abort all deadlocked processes: It means to release all processes in the deadlocked state, and start the allocation from the starting point. It is a great expensive method.
Abort one by one process until the deadlock cycle is eliminated: In this method first abort one of the processes in the deadlocked state, and allocated the resources ( resource from abort process) to some other process in the deadlocked state then check whether the deadlock is breaked or not. If not abort another process from the deadlock state. Continue this process until we recover from deadlock. This method is less expensive than first.
Resource Preemption:
There are three methods to eliminate deadlocks using resource preemption, these are:
Selecting a Victim: Select a victim resource from the deadlock state, and preempt that one. Minimize cost.
Rollback: Rollback the processes and resources unto some safe state, and restart it from that state. This method requires the system to keep more information about the state of all the running processes. Return to some safe state, restart the process for that state.
Starvation: A process (or) resources can be picked as a victim only a finite number of times, it is said to be starvation. The most common solution is to include the number of rollbacks in the cost factor. the same process may always be picked as the victim, include number of rollback in the cost factor
Resource Preemption:
There are three methods to eliminate deadlocks using resource preemption, these are:
Selecting a Victim: Select a victim resource from the deadlock state, and preempt that one. Minimize cost.
Rollback: Rollback the processes and resources unto some safe state, and restart it from that state. This method requires the system to keep more information about the state of all the running processes. Return to some safe state, restart the process for that state.
Starvation: A process (or) resources can be picked as a victim only a finite number of times, it is said to be starvation. The most common solution is to include the number of rollbacks in the cost factor. the same process may always be picked as the victim, include number of rollback in the cost factor
0 Comments