Deadlock detection and Recovery

Deadlock detection

Deadlock detection with one resource of each type

• For a system with one instance of each resource, we can detect deadlock by constructing a resource-allocation graph.
• If the graph contains one or more cycles, a deadlock exists. Any process that is part of the cycle is deadlocked.
• If no cycle exists, the system is not deadlocked.

Example:

• Consider a complex system with 7 processes, A through G, and 6 resources, R through W.
• The state of which resources are currently owned and which ones are currently being requested is as follows:

1. Process A holds R and wants S.
2. Process B holds nothing but wants T.
3. Process C holds nothing but wants S.
4. Process D holds U and wants S and T.
5. Process E holds T and wants V.
6. Process F holds W and wants S.
7. Process G holds V and wants U.

From this, we can construct a resource graph as follows:

Processes D, E, and G are all deadlocked.
Processes A, C, and F are not deadlocked because S can be allocated to any one of them, which then finishes and taken by the other two processes in turn.

Deadlock Detection with multiple resources of each type
In this case, we use a matrix-based algorithm for detecting deadlocks among n processes (P1,…Pn)
E: Existing resource vector (E1, E2….Em); we have m different resource
For example: if class 1 is printer then E1=2 means we have 2 printers
A: Available resource vectors
For example: if A1=0, no printers are available, both printers have been assigned
C: Current Allocation matrix
Cij is the number of instances of resource j that are held by process i
R: Request matrix
Rij is the number of instances of resource j that process i wants.

1. Look for an unmarked process, Pi , for which the i-th row of R is less than or equal to A.
2. If such a process is found, add the i-th row of C to A, mark the process, and go back to step 1.
3. If no such process exists, the algorithm terminates.

Here, requests represented by 1st and 2nd rows of matrix R cannot be satisfied (Compare A with each Rs). But 3rd one can be satisfied.
• So process 3 runs and eventually returns A=(2 2 2 0).
• At this point process 2 can run and return A=(4 2 2 1).
• Now process 1 can run and there is no deadlock.
• What happens if process 2 needs 1 CD-ROM drive, 2 Tape drives, and 1 Plotter (i.e. 2nd row of R becomes (2 1 1 1))?
• Entire system gets deadlock or not???

Deadlock Recovery

Traditional operating system such as Windows doesn’t deal with deadlock recovery as it is time and space consuming process. Real-time operating systems use Deadlock recovery.

i. Recovery through preemption

To eliminate deadlocks using resource preemption, we successively preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken. Issues to be addressed:
a. Selecting a victim
b. Rollback

c. Starvation

ii. Recovery through rollback

• Processes are checkpoint periodically
• A checkpoint refers to save the state of a process by writing the state to a file
• Checkpoint contains not only the memory image but also the resource state (i.e. the resource allocated to the process)
• To be more effective, new checkpoints must not replace the old checkpoints but should be written to a different file
• When a deadlock is detected, we first determine the resource causing the deadlock and then rollback the process which currently holds that resource to a point in time before it acquired the resource by starting one of its earlier checkpoints

iii. Recovery through the killing process

The simplest way to recover from deadlock is to kill one or more processes.
Which process to kill?

a. Kill all the deadlocked processes
Sure to break the deadlock but can be expensive as some of the processes may have computed for a long time and killing the process makes the process to do all those computations once again after it has been started again

b. Abort one process at a time until the deadlock cycle is eliminated.
This method incurs considerable overhead, since, after each process is aborted, a deadlock detection algorithm must be invoked to determine whether any processes are still deadlocked.