Page 120 - DCAP403_Operating System

Unit 6: Process Synchronization

6.7.3 Deadlock Detection and Recovery Notes

Often neither deadlock avoidance nor deadlock prevention may be used. Instead deadlock
detection and recovery are used by employing an algorithm that tracks resource allocation and
process states, and rolls back and restarts one or more of the processes in order to remove the
deadlock. Detecting a deadlock that has already occurred is easily possible since the resources
that each process has locked and/or currently requested are known to the resource scheduler
or OS.

Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact,
generally undecidable, because the halting problem can be rephrased as a deadlock scenario.

However, in specific environments, using specific means of locking resources, deadlock detection
may be decidable. In the general case, it is not possible to distinguish between algorithms that are
merely waiting for a very unlikely set of circumstances to occur and algorithms that will never
finish because of deadlock.

6.7.4 Ignore Deadlock

In the Ostrich Algorithm it is hoped that deadlock doesn’t happen. In general, this is a reasonable
strategy. Deadlock is unlikely to occur very often; a system can run for years without deadlock
occurring. If the operating system has a deadlock prevention or detection system in place, this
will have a negative impact on performance (slow the system down) because whenever a process
or thread requests a resource, the system will have to check whether granting this request could
cause a potential deadlock situation.
If deadlock does occur, it may be necessary to bring the system down, or at least manually kill a
number of processes, but even that is not an extreme solution in most situations.

6.7.5 The Banker’s Algorithm for Detecting/Preventing Deadlocks

Banker’s Algorithm for Single Resource

This is modeled on the way a small town banker might deal with customers’ lines of credit. In the
course of conducting business, our banker would naturally observe that customers rarely draw
their credit lines to their limits. This, of course, suggests the idea of extending more credit than
the amount the banker actually has in her coffers.
Suppose we start with the following situation

Customer Credit Used Credit Line
Andy 0 6
Barb 0 5
Marv 0 4
Sue 0 7
Funds Available 10
Max Commitment 22
Our banker has 10 credits to lend, but a possible liability of 22. Her job is to keep enough in
reserve so that ultimately each customer can be satisfi ed over time: That is, that each customer
will be able to access his full credit line, just not all at the same time. Suppose, after a while, the
bank’s credit line book shows.

LOVELY PROFESSIONAL UNIVERSITY 113