Deadlock Detection and Recovery
Deadlock Detection- In case if a system does not work either a deadlock avoidance algorithm or, a deadlock-prevention then a deadlock situation might occur. In this situation, the system must provide:
■ An algorithm that inspects the state of the system to define whether a deadlock has occurred.
■ An algorithm that recover from the deadlock.
Single Instance of Each Resource Type
If all resources consume only a single instance, then we can delimit a deadlock detection algorithm that uses a variant of the RAG, called as wait-for graph.
– Nodes that are processes
– Pi → Pj if Pi is waiting for Pj
■ An edge from Pi to Pj in a wait-for graph indicates that process Pi is waiting for process Pj to issue a resource that Pi needs
■ Sometimes invoke an algorithm that inspects for a cycle in the graph. If there exist a cycle then there exists a deadlock.
■ An edge Pi → Pj be existent in a wait-for graph if and only if the corresponding resource allocation graph contains two edges Rj—>Pj and P—>Rj for some resource Rj
■ An algorithm that detect a cycle in a graph needs an order of n2 operations, where n is the number of vertices in the graph.
Several Instances of a Resource Type
■ The wait-for-graph scheme is not valid to a resource-allocation system with multiple instances of every resource type.
■ Deadlock detection algorithm that is valid for such a system, works several time-varying data structures that are alike to those used in the banker’s algorithm
■ Available: A vector with length m specifies the number of available resources of each type
■ Allocation: An n x m matrix that defines the number of resources of each type which is currently allocated to each process
■ Request: An n x m matrix shows the current request of each process. If Request [i][j] = k, then the process Pi is requesting k more instances of resource type Rj.
Recovery from Deadlock
Two major approaches which are mostly used for recovery from deadlock given as:
■ Process termination
■ Resource Preemption
Process Termination
- Abort all deadlocked processes. This technique will break the deadlock cycle but at great cost; the deadlocked processes can be calculated for a long time, and the results of these partial computation must be rejected and perhaps will have to be re-computed later.
- Abort one process at a time till the deadlock cycle is eliminated. This methodacquires considerable overhead then, after individually process is aborted, a deadlock detection algorithm need to be invoked to determine whether any processes are still
- Aborting a process may not be easy. If the process was in the middle of updating afile, terminating it will leave that file in an inappropriate state.
- In the same way, if the process was in the middle of printing data on a printer, the system
should reset the printer to a proper state before printing the next job. - If the partial termination technique is used, then it must determine whichdeadlocked process or processes should be terminated.
- Those processes should abort whose termination will sustain the minimum cost.
Unfortunately, the term minimum-cost is not a accurate one, Many factors can affect which process is elected, including:
1. What the priority of the process is?
2. How long the process has computed and for how much longer the process will compute before finishing its elected task.
3. How many and for what type of resources the process has used for example, whether
the resources are simple to preempt.
4. How many additional resources the process requires in order to complete.
5. How many processes would need to be terminated
6. Whether the process is batch/ interactive.
Resource Preemption Approach
■ On the way to avoid deadlocks by means of resource-preemption then preempt, some resources from processes and make available these resources to other processes till the deadlock cycle is broken.
■ If preemption is mandatory to deal with deadlocks, then three issues required to be addressed:
1. Selecting a victim. Which processes and resources are to be preempted? Such as in process termination, it must be determined the order of preemption to minimize cost. Cost factors may contain such parameters as the number of resources a deadlocked process is holding and the amount of time the process has up till now consumed during its execution.
2. Rollback. If a resource is preempted by a process, what have to be done with that process? Obviously, it cannot carry on with its normal execution; it is missing some required resource. The process must roll back to some safe state and restart it from that state.
3. Starvation. How to ensure that starvation will not occur? and how can have guarantee that resources will not always be preempted from the same process?
