Deadlock Detection and Recovery

Deadlock Detection

·         Use an algorithm to detect deadlock (if any)

·         Recover from the deadlock

·         Single instance of each resource – wait-for graph

·         Multiple instance of a resource 

Wait-for Graph

·         Obtained from resource allocation graph

·         Remove the resource nodes

·         Collapse the corresponding edges

·         Edge from Pi to Pj means Pi is waiting for resource held by Pj

·         Deadlock - if there is a cycle in wait-for graph.

·         Invoke an algorithm to detect for cycles periodically.

·         Complexity of such an algorithm will be n2, where n is the number of vertices.

Example:

                            Resource Allocation Graph                       wait-for graph 

Multiple Instance - the working is similar to the working of Banker's algorithm. From the given information try to find out safe sequence. If safe sequence exists then there is no deadlock else there is deadlock.
Data structures required are:

·         Available

·         Allocation

·         Request (Request corresponds to Need in Banker's Algorithm)

When to invoke Deadlock Detection Algorithm?

·         Every time a process requests for a resource

Advantage

·         Processes involved in deadlock are identified

·         The process that caused the deadlock is identified

Disadvantage

·         Overhead in computation time

After fixed interval of time

Disadvantage

·         Can not tell which process caused the deadlock

Deadlock Recovery - there are two methods to recover from deadlock

1.      Process Termination

2.      Resource Preemption

The question is which process should be selected to terminate or from which process should the resources be preempted. The following points can influence the selection:

·         What is the priority of the process?

·         How long the process has computed?

·         How much the process has finished its working?

·         How many resources are being used by the process?

·         How many total processes will be required to be terminated?

In resource pre-emption we should also consider that a process never starves for resources i.e. always one of the process is selected as a victim for resource pre-emption.