Deadlock: Detection & Recovery
Scenario
Instead of building a fortress to prevent a fire, or analyzing every wire to avoid one, you install smoke alarms. When the alarm sounds, you grab a fire extinguisher and put it out.
Mental model
Let deadlocks happen. Periodically check for them. When one is found, take drastic action to fix it.
Deadlock detection and recovery is an optimistic approach. The OS places no restrictions on resource requests and does no upfront simulation. Instead, it periodically runs an algorithm to search for circular wait cycles in the resource allocation graph. If a deadlock is detected, the OS recovers by preempting resources or killing processes.
Explanation
Preventing and avoiding deadlocks are costly. Prevention ruins resource utilization, and avoidance burns CPU cycles on continuous simulations. Modern operating systems (like Linux and Windows) often prefer a simpler, more optimistic approach: ignore the problem until it happens. This is the core philosophy behind Deadlock Detection and Recovery.
Under this approach, the OS grants resource requests freely, assuming deadlocks are rare. Behind the scenes, the OS maintains a Resource Allocation Graph—a map showing which processes hold which resources and who is waiting for what. Periodically (or when a process is blocked for too long), the OS runs a detection algorithm to look for cycles in this graph. If a closed loop is found, a deadlock has occurred.
Once a deadlock is detected, the system enters the Recovery phase. The OS must break the deadlock by forcibly taking away resources, but it has to be careful about how it does it. There are two main strategies: Process Termination and Resource Preemption.
Process Termination involves killing stuck processes. The OS could ruthlessly terminate all deadlocked processes, which is fast but wastes all their computed progress. Alternatively, it can terminate them one by one, rerunning the detection algorithm after each kill until the cycle is broken. The OS usually tries to kill a 'victim' with the least accumulated CPU time or the lowest priority.
Resource Preemption is a more surgical approach. The OS forcibly yanks a resource away from a process and gives it to another to break the cycle. However, the process that lost its resource cannot continue normally; it must be rolled back to a previous safe state and restarted. This requires the OS to maintain checkpoints of process states, adding complexity to the system.
Key points
- Resource Allocation Graph (RAG): A directed graph used by the OS to track resource assignment and requests. Cycles in this graph indicate a deadlock.
- Process Termination: Killing one or more processes to break the circular wait. The OS uses heuristics (like priority or progress) to choose the victim.
- Resource Preemption: Stealing a resource from a process and rolling that process back to a previous checkpoint to recover from deadlock.
Common mistakes
- Assuming all OSs use avoidance or prevention: Most general-purpose OSs (Windows, Linux) use the 'Ostrich Algorithm' (ignoring it entirely for user apps) or basic detection/recovery, because deadlocks are infrequent and prevention/avoidance overhead is too high.
- Believing preemption is cost-free: Preempting a resource requires state rollback. You can't just take a half-written file away from a process without cleaning up the corrupted data first.
Glossary
- Deadlock Detection and Recovery
- An optimistic strategy where the operating system lets programs run freely, occasionally checks to see if any are hopelessly stuck together, and then forces one to restart if they are.
- Resource Allocation Graph
- A visual or mathematical map used by the operating system to track which programs currently hold which resources, and which programs are waiting for them.
- resource utilization
- A measure of how efficiently the computer's hardware components (like CPU, memory, and disks) are being used by running programs.
Recall questions
- What data structure does the OS analyze to detect a deadlock?
- What are the two primary methods for recovering from a deadlock?
- Why might an OS choose detection over avoidance?
Questions & answers
An OS regularly runs a cycle-finding algorithm on its resource graph. If a cycle is found, it terminates the lowest-priority process. What strategy is this?
Deadlock detection and recovery (specifically, recovery via process termination).
Approach: Recognize that 'cycle-finding' happens after the fact, meaning it's detection. Terminating the process is the recovery step.
What is the primary drawback of using resource preemption to recover from a deadlock?
It requires the ability to roll processes back to a previous safe checkpoint, which is complex and difficult to implement for many types of resources.
Approach: Understand that taking a resource away mid-use leaves the process in an invalid state, requiring rollback.
Continue learning
Previous: Deadlock: Prevention vs Avoidance