DEADLOCK DETECTION

• If deadlocks are not avoided, then another approach is to detect when they have occurred and recover somehow.
• In addition to the performance hit of constantly checking for deadlocks, a policy / algorithm must be in place for recovering from deadlocks, and there is potential for lost work when processes must be aborted or have their resources preempted.
SINGLE INSTANCE OF 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.
• 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.

• As before, cycles in the wait-for graph indicate deadlocks.

• This algorithm must maintain the wait-for graph, and periodically search it for cycles.

SEVERAL INSTANCES OF A RESOURCE TYPE:

The wait for graph scheme is not applicable to a resource allocation system with multiple instances of each resource type.

The deadlock detection algorithm described here is applicable to such a system and it uses several time varying data structures that are used in Bankers algorithm

They are

• 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 of each process. If Request[i, j]=k, then process Pi is requesting k more instances of resource type Rj

The detection algorithm outlined here is essentially the same as the Banker's algorithm, with two subtle differences:

• In step 1, the Banker's Algorithm sets Finish[ i ] to false for all i. The algorithm presented here sets Finish[ i ] to false only if Allocation[ i ] is not zero. If the currently allocated resources for this process are zero, the algorithm sets Finish[ i ] to true. This is essentially assuming that IF all of the other processes can finish, then this process can finish also. Furthermore, this algorithm is specifically looking for which processes are involved in a deadlock situation, and a process that does not have any resources allocated cannot be involved in a deadlock, and so can be removed from any further consideration.

• Steps 2 and 3 are unchanged

• Step 2:Find an i such that both (A) Finish[ i ] == false, and (B) Need[ i ] < Work. This process has not finished, but could with the given available working set. If no such i exists, go to step 4.

• Step 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.

• In step 4, the basic Banker's Algorithm says that if Finish[ i ] == true for all i, that 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:

Consider a system with five processes P0 –P4

Three resource types A,B,C .Resource type A has 7 instances, Resource Type B has 2 instances, Resource type C has 6 instances.

At time T0 ,the resource allocation state is

Allocation request available

  A B C A B C A B C

P0 0 1 0 0  0 0    0 0 0

P1 2 0 0 2 0 2

P2 3 0 3 0 0 0

P3 2 1 1 1 0 0

P4 0 0 2 0 0 2

At this point the system is not in a deadlock state. By executing the algorithm the sequence<P0,P2,P3,P1,P4> will result in Finish[i]=true for all i.

Now if P2 makes one additional request for an instance of type C. the request matrix is modified as

Request

  A B C

P0 0 0 0 

P1 2 0 2

P2 0 0 1

P3 1 0 0

P4 0 0 2

Now the system is deadlocked. Although we can reclaim the resources held by process P0,the number of available resources is not sufficient to fulfill the requests of other processes. Thus deadlock exists consisting of processes P1,P2,P3 and P4.

DETECTION –ALGORITHM USAGE:

• When should the deadlock detection be done? Frequently, or infrequently?

• The answer may depend on how frequently deadlocks are expected to occur, as well as the possible consequences of not catching them immediately. ( If deadlocks are not removed immediately when they occur, then more and more processes can "back up" behind the deadlock, making the eventual task of unblocking the system more difficult and possibly damaging to more processes. )

• 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. ( One might consider that the process whose request triggered the deadlock condition is the "cause" of the deadlock, but realistically all of the processes in the cycle are equally responsible for the resulting 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.