Page 147 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes 4.6.18 Detection-Algorithm Usage
When should we invoke the detection algorithm? The answer 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?
If deadlocks occur frequently, then the detection-algorithm should be invoked frequently.
Resources allocated to deadlocked processes will be idle until the deadlock can be broken. In
addition, the number of processes involved in the deadlock cycle may grow.

Deadlocks occur only when some process makes a request that cannot be granted immediately.
This request may be the final request that completes a chain of waiting processes. In the
extreme, we could invoke the deadlock detection algorithm every time a request for allocation
cannot be granted immediately. In this case, we can identify not only the set of processes that
is deadlocked, but also the specific process that “caused” the deadlock. (In reality, each of the
deadlocked processes is a link in the cycle in the resource graph, so all of them, jointly, caused
the deadlock.) If there are many different resource types, one request may cause many cycles in
the resource graph, each cycle completed by the most recent request and “caused” by the one
identifiable process. Of course, invoking the deadlock-detection algorithm for every request may
incur a considerable overhead in computation time. A less expensive alternative is simply to
invoke the algorithm at less frequent intervals—for example, once per hour, or whenever CPU
utilization drops below 40 per cent. (A deadlock eventually cripples system throughput and
will cause CPU utilization to drop.) If the detection algorithm is invoked at arbitrary points in
time, there may be many cycles in the resource graph. We would generally not be able to tell
which of the many deadlocked processes caused the deadlock.
4.6.19 Recovery from Deadlock

When a detection algorithm determines that a deadlock exists, several alternatives exist. One
possibility is to inform the operator that a deadlock has occurred, and to let the operator deal
with the deadlock manually. The other possibility is to let the system recover from the deadlock
automatically. There are two options for breaking a deadlock. One solution is simply to abort one
or more processes to break the circular wait. The second option is to preempt some resources
from one or more of the deadlocked processes.
4.6.20 Process Termination

To eliminate deadlocks by aborting a process, we use one of two methods. In both methods,
the system reclaims all resources allocated to the terminated processes.

4.6.21 Abort All Deadlocked Processes
This method clearly will break the deadlock cycle, but at a great expense; these processes may
have computed for a long time, and the results of these partial computations must be discarded
and probably recomputed later.

4.6.22 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.
Aborting a process may not be easy. If the process was in the midst of updating a file, terminating
it will leave that file in an incorrect state. Similarly, if the process was in the midst of printing
data on the printer, the system must reset the printer to a correct state before printing the next
job. If the partial termination method is used, then, given a set of deadlocked processes, we
must determine which process (or processes) should be terminated in an attempt to break the

140 LOVELY PROFESSIONAL UNIVERSITY