Deadlock Detection

Deadlock Detection

If a system does not employ either deadlock prevention or a deadlock avoidance algorithm, then a deadlock situation may occur. If deadlocks are not avoided, then another approach is to detect when they have occurred and recover somehow.

The system may provide:

1. An algorithm that examines the state of the system to determine whether a deadlock has occurred.

2. An algorithm to recover from the deadlock.

Single Instance of Each Resource Type

If each resource category has a single instance, then we can use a variation of the resource-allocation graph known as a wait-for graph.

A wait-for graph can be constructed from a resource-allocation graph by eliminating the resources and collapsing the associated edges, as shown in the figure below.An arc from Pi to Pj in a wait-for graph indicates that process Pi is waiting for a resource that process Pj is currently holding.

Several Instances of a Resource Type

Wait for graph is not applicable to a system with multiple instances of each resource type. The detection algorithm outlined here is essentially the same as the Banker's algorithm, with two subtle differences:

1. Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively. Initialize Work=Available. For i=0,1,2,…..,n-1, if Allocation ≠ 0 then Finish[i] = false otherwise, Finish [i] = true.

2. Find an index i such that

            a. Finish[i] = = false

            b. Request­_i ≤ Work

If no such i exists, go to step 4

3. Set Work = Work + Allocation[ i ], and set Finish[ i ] to true. This corresponds to process i finishing up and releasing its resources back into the work pool. Then loop back to step 2.

4. If Finish[ i ] == true for all i, then there is no deadlock. This algorithm is more specific, by stating that if Finish[ i ] == false for any process Pi, then that process is specifically involved in the deadlock which has been detected.

Example:

Detection-Algorithm Usage

The answer to the question, when should detection algorithm must be invoked depends on two factors:

1. How often is a deadlock likely to occur?

2. How many processes will be affected by deadlock when it happens?

There are two obvious approaches, each with trade-offs:

1. Do deadlock detection after every resource allocation which cannot be immediately granted. This has the advantage of detecting the deadlock right away, while the minimum numbers of processes are involved in the deadlock. The down side of this approach is the extensive overhead and performance hit caused by checking for deadlocks so frequently.

2. Do deadlock detection only when there is some clue that a deadlock may have occurred, such as when CPU utilization reduces to 40% or some other magic number. The advantage is that deadlock detection is done much less frequently, but the down side is that it becomes impossible to detect the processes involved in the original deadlock, and so deadlock recovery can be more complicated and damaging to more processes.