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.
Requesti ≤ 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:
- 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.
- 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.
No comments:
Post a Comment