Page 119 - DCAP403_Operating System

Operating System

Notes 6.7 Handling of Deadlocks

There are several ways to address the problem of deadlock in an operating system.

1. Prevent
2. Avoid
3. Detection and recovery
4. Ignore

6.7.1 Deadlock Prevention

Deadlocks can be prevented by ensuring that at least one of the following four conditions occur:
1. Mutual exclusion: Removing the mutual exclusion condition means that no process may
have exclusive access to a resource. This proves impossible for resources that cannot be
spooled, and even with spooled resources deadlock could still occur. Algorithms that
avoid mutual exclusion are called non-blocking synchronization algorithms.
2. Hold and wait: The “hold and wait” conditions may be removed by requiring processes
to request all the resources they will need before starting up (or before embarking upon

a particular set of operations); this advance knowledge is frequently difficult to satisfy

and, in any case, is an inefficient use of resources. Another way is to require processes to
release all their resources before requesting all the resources they will need. This too is
often impractical. (Such algorithms, such as serializing tokens, are known as the all-or-
none algorithms.)
3. No preemption: A “no preemption” (lockout) condition may also be difficult or impossible

to avoid as a process has to be able to have a resource for a certain amount of time, or the
processing outcome may be inconsistent or thrashing may occur. However, inability to
enforce preemption may interfere with a priority algorithm.

Note Preemption of a “locked out” resource generally implies a rollback, and is to be
avoided, since it is very costly in overhead.

Algorithms that allow preemption include lock-free and wait-free algorithms and optimistic
concurrency control.

4. Circular wait: The circular wait condition: Algorithms that avoid circular waits include
“disable interrupts during critical sections” , and “use a hierarchy to determine a partial
ordering of resources” (where no obvious hierarchy exists, even the memory address of
resources has been used to determine ordering) and Dijkstra’s solution.

6.7.2 Deadlock Avoidance

Deadlock Avoidance, assuming that you are in a safe state (i.e. a state from which there is a
sequence of allocations and releases of resources that allows all processes to terminate) and you
are requested certain resources, simulates the allocation of those resources and determines if the

resultant state is safe. If it is safe the request is satisfied, otherwise it is delayed until it becomes
safe.
The Banker’s Algorithm is used to determine if a request can be satisfied. It uses requires

knowledge of who are the competing transactions and what are their resource needs. Deadlock
avoidance is essentially not used in distributed systems.

112 LOVELY PROFESSIONAL UNIVERSITY