Deadlock Resolution

Section 1: Overview

A deadlock occurs when we have a set of processes [not necessarily all the processes in the system], each holding some resources, each requesting some resources, and none of them is able to obtain everything that it needs to continue.

Resources can be preemptable or non-preemptable. A resource is preemptable if it can be taken away from the process that is holding it. Memory is an example of a preemptable resource.

Section 2: Conditions

Necessary For Deadlock

All of these conditions are necessary for a deadlock to occur. If any condition is not satisfied, the system is not in a deadlocked state. If it is impossible to satisfy all four conditions concurrently, deadlock is impossible.

Mutual exclusion – at least one resource must be held in a non-sharable way; processes claim exclusive control of resources they need.
Hold-and-wait – at least one process is holding a resource and waiting for another resource that is currently in use.
No preemption (of holder) – Resources are only released voluntarily; no interruption is possible (i.e. resources cannot be forcefully withdrawn by another process).
Circular wait – there must exist a circular chain of processes, each waiting for a resource held by another.

While the four conditions must be present for a deadlock to occur, their presence does not necessarily guarantee a deadlock.

Given the first three conditions, a sequence of events may occur that leads to an unresolvable circular wait.
- The circular wait is unresolvable because of the first three conditions.
The first three conditions are policies, whereas circular wait is a circumstance that might occur depending on the sequencing of requests and releases.

Section 3: Deadlock Prevention

The goal of deadlock prevention is to prevent the necessary conditions from being satisfied.

Condition: Mutual Exclusion – Solution: make resources sharable.
- Example: read-only files
Condition: Hold-and-wait – Solution: if a requested resource is unavailable, release all currently allocated resources before waiting.
- But this allows livelocks.
- Another approach is to request all resources at once in a single request.
  - If processes request resources only once and are granted the requested resources at once, hold-and-wait is not satisfied and livelock is not possible.
Condition: No preemption – Solution: make resources preemptable.
Condition: Circular wait – Solution: allow processes to wait for resources, but ensure that the waiting can't be circular.
- One approach might be to assign a precedence to each resource and force processes to be allocated resources in the order of increasing precedence.
  - That is to say that if the highest precedence resource currently held by a process is X, the process cannot request any resource with precedence <= X.
  - This forces resource allocation to follow a particular and non-circular ordering, so a circular wait cannot occur.

Deadlock prevention disallows many different ways of using resources, because they could potentially lead to deadlock.

However, if the resources suffer reasonable low contention, deadlock could be unlikely, and the undesirable result would be that resources are left idle to prevent the infrequent or unlikely occurrence of deadlock, leading to low resource utilization.

Section 4: Deadlock Detection

Approach:

Permit the first three necessary conditions for deadlock (mutual exclusion, hold-and-wait, no preemption of holder).
For greater efficiency, tolerate the occasional deadlock.
Require early detection to avoid 'doing nothing'.
Take recovery action when needed.

What To Do When a Deadlock Is Detected?

We could recover from a deadlock by using process termination: killing all deadlocked processes, or killing processes one at a time until the deadlock-detection algorithm no longer detects a deadlock.
- Killing processes is undesirable, which is the advantage of killing processes one at a time; it kills fewer processes.
- However, the second solution incurs overhead.
Alternatively, we could recover from a deadlock by resource preemption: preempting resources from processes and giving the resources to other processes until the cycle is broken.
- We need to consider how to select a process to preempt, what to do with a process whose resource we preempt (how do we do rollback?), and how to prevent starvation.

More details here.

Section 5: Deadlock Avoidance

Deadlock avoidance is an alternative that can yield higher resource utilization.

Allow necessary conditions (mutual exclusion, hold-and- wait, no preemption of holder, and circular wait) to occur, but use algorithms to predict deadlock and refuse resource requests that could lead to deadlock.
However, the cost of deadlock avoidance is that we must know much more about how the various processes will request the resources.

The goal of deadlock avoidance is to ensure that the system is always in a safe state. When in a safe state, deadlock is not possible. But if we are in an unsafe state, deadlock could occur.

To ensure that the system remains in a safe state, we must know the following for each process:

The number of each type of resource that it currently holds.
The maximum number of each type of resource that it might need.
The number of each type of resource that exists in the system.