OS Notes

Deadlock Recovery

Methods for recovering from deadlocks including process termination strategies, resource preemption, rollback mechanisms, and selecting victim processes for minimum cost recovery.

Introduction

Once a deadlock is detected, the system must break it. This is like untangling a traffic gridlock — someone has to back up, even if it inconveniences them. In operating systems, deadlock recovery means either killing processes or taking resources away from them. Neither option is pleasant, but a deadlocked system making zero progress is worse.

Recovery is the action taken after deadlock detection identifies the problem. The goal is to break the circular wait with minimum cost to the system. We want to disrupt as few processes as possible while resolving the deadlock completely.

Recovery Method 1: Process Termination

The most straightforward approach is to kill one or more processes involved in the deadlock. This releases their resources, potentially breaking the circular wait.

Option A: Abort ALL Deadlocked Processes

Kill every process involved in the deadlock cycle. This guarantees the deadlock is broken immediately.

Before	P1 ↔ P2 ↔ P3 (deadlocked cycle)
Action	Kill P1, P2, P3
After	All resources freed, deadlock broken
Advantage	Definitely works
Disadvantage	Maximum disruption — all work lost

When to use: When the cost of continued deadlock (e.g., in a real-time system) exceeds the cost of restarting all processes.

Option B: Abort ONE Process at a Time

Kill one process, check if deadlock is resolved. If not, kill another. Repeat until deadlock breaks.

Deadlocked	{P1, P2, P3, P4}
Step 1	Kill P2 (lowest cost victim)
Still deadlocked?	Step 2
Step 2	Kill P4 (next lowest cost)
Deadlock broken?	Done!
Result	Only P2 and P4 lost (P1 and P3 survived)

Advantage: Minimizes damage — only as many processes killed as necessary Disadvantage: High overhead — run detection algorithm after each termination (O(n² × m) per iteration)

Selecting the Victim Process

When we must choose which process to kill, we select the one with minimum cost. Cost factors include:

Factor	Lower Cost If...
Priority	Process has low priority
Computation done	Process just started (little work lost)
Resources held	Process holds few resources (less disruption to others)
Resources needed to finish	Process needs many more (far from completion)
Number of processes to terminate	Killing this one breaks the deadlock alone
Interactive vs batch	Batch processes are less urgent

Example

// Victim selection scoring (lower score = better victim) int calculate_victim_cost(Process *p) { int cost = 0; cost += p->priority * 10; // Higher priority → higher cost to kill cost += p->cpu_time_used * 5; // More work done → higher cost cost += p->resources_held * 3; // More resources → more disruption cost -= p->resources_needed * 2; // Needs a lot more → cheaper to kill (far from done) return cost; } Process* select_victim(Process *deadlocked[], int count) { Process *victim = deadlocked[0]; int min_cost = calculate_victim_cost(victim); for (int i = 1; i < count; i++) { int cost = calculate_victim_cost(deadlocked[i]); if (cost < min_cost) { min_cost = cost; victim = deadlocked[i]; } } return victim; }

Recovery Method 2: Resource Preemption

Instead of killing processes entirely, we can forcibly take resources from one process and give them to another to break the deadlock.

Steps in Resource Preemption

Select a victim: Choose which process will have resources preempted (similar cost factors as above)
Rollback: The victim process must be rolled back to a safe state before it acquired the preempted resource
Ensure no starvation: The same process should not always be the victim

The Rollback Problem

When we preempt a resource from process P, we must restore P to a consistent state. There are two options:

Total rollback: Abort P completely and restart from the beginning. Simple but wasteful.

Partial rollback (checkpointing): Roll back P to a checkpoint state just before it acquired the preempted resource. This requires the system to periodically save process state (checkpoints).

Example

Process P execution timeline: [Start] ──→ [Checkpoint 1] ──→ [Got R1] ──→ [Checkpoint 2] ──→ [Got R2] ──→ [DEADLOCKED] ↑ Rollback to here, release R2

Checkpointing

Example

// Simplified checkpoint mechanism typedef struct { int registers[32]; void *memory_snapshot; int memory_size; int resources_held[MAX_RESOURCES]; int num_resources; } Checkpoint; void save_checkpoint(Process *p) { Checkpoint *cp = create_checkpoint(); save_registers(cp->registers); cp->memory_snapshot = snapshot_memory(p); cp->num_resources = p->num_resources; memcpy(cp->resources_held, p->resources, ...); push_checkpoint_stack(p, cp); } void rollback_to_checkpoint(Process *p, Checkpoint *cp) { // Release resources acquired after checkpoint release_resources_after(p, cp); // Restore process state restore_registers(cp->registers); restore_memory(p, cp->memory_snapshot); }

Preventing Starvation in Recovery

If we always choose the same process as the victim (perhaps because it has the lowest priority), it will be repeatedly rolled back and never complete. This is starvation.

Solution: Include the number of rollbacks in the cost function. Each time a process is rolled back, increase its "immunity" so it becomes a less attractive victim next time.

c example

int calculate_victim_cost_with_starvation_prevention(Process *p) {
    int base_cost = calculate_victim_cost(p);
    // Each rollback adds significant cost, eventually making
    // this process too expensive to victimize
    base_cost += p->rollback_count * 100;
    return base_cost;
}

Recovery in Real Systems

Database Systems

Databases are the best example of deadlock recovery in practice. When MySQL detects a deadlock (via wait-for graph cycle), it:

Selects the transaction with the least work done as the victim
Rolls back that transaction (UNDO log makes this possible)
Returns a "deadlock detected" error to the application
The application typically retries the transaction

Operating Systems

Most general-purpose OS (Windows, Linux) simply kill the deadlocked process. There is no sophisticated rollback — the process is terminated and its resources are freed. The user sees a crash.

Distributed Systems

Distributed deadlock recovery is particularly challenging because no single node has complete information. Techniques include centralized coordinators, distributed cycle detection, and timeout-based approaches (assume deadlock if waiting too long).

Real-World Analogy

Deadlock recovery is like resolving a traffic gridlock at a blocked intersection. Option 1 (process termination) is like having a tow truck remove cars — disruptive but effective. Option 2 (resource preemption with rollback) is like asking a driver to reverse back to a previous intersection and take an alternate route. You want to minimize disruption (pick the car that is easiest to move) and avoid always picking on the same driver (starvation prevention).

Key Takeaways

Deadlock recovery breaks detected deadlocks by either terminating processes or preempting resources
Process termination can be all-at-once (guaranteed) or one-at-a-time (minimizes damage)
Victim selection minimizes recovery cost based on priority, work done, and resources held
Resource preemption requires rolling back the victim to a consistent state (checkpointing)
Starvation must be prevented by tracking and limiting repeated victimization
Database systems are the primary real-world users of sophisticated deadlock recovery
General-purpose OS typically just kill deadlocked processes without rollback

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Deadlock Recovery.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, deadlocks, deadlock, recovery, deadlock recovery

Continue learning this concept

DeadlocksDeadlock AvoidanceUnderstanding deadlock avoidance through safe state analysis, safe sequences, and the concept of unsafe states that may lead to deadlock. Foundation for the Banker\DeadlocksDeadlock DetectionAlgorithms for detecting deadlocks in operating systems including single-instance detection using wait-for graphs, multi-instance detection algorithm, and when to invoke detection.DeadlocksIntroduction to DeadlocksUnderstanding deadlocks in operating systems — what they are, why they occur, real-world examples, system model, and overview of handling strategies including prevention, avoidance, and detection.DeadlocksDeadlock PreventionStrategies for deadlock prevention by eliminating each of the four necessary conditions: mutual exclusion, hold and wait, no preemption, and circular wait with practical implementation approaches.DeadlocksNecessary Conditions for DeadlockThe four necessary conditions for deadlock: mutual exclusion, hold and wait, no preemption, and circular wait. Detailed explanation with examples of each condition.DeadlocksBanker\Complete explanation of the Banker\

PreviousDeadlock Prevention NextNecessary Conditions for Deadlock

OS Notes

Deadlock Recovery

Methods for recovering from deadlocks including process termination strategies, resource preemption, rollback mechanisms, and selecting victim processes for minimum cost recovery.

Introduction

Recovery Method 1: Process Termination

The most straightforward approach is to kill one or more processes involved in the deadlock. This releases their resources, potentially breaking the circular wait.

Option A: Abort ALL Deadlocked Processes

Kill every process involved in the deadlock cycle. This guarantees the deadlock is broken immediately.

Before	P1 ↔ P2 ↔ P3 (deadlocked cycle)
Action	Kill P1, P2, P3
After	All resources freed, deadlock broken
Advantage	Definitely works
Disadvantage	Maximum disruption — all work lost

When to use: When the cost of continued deadlock (e.g., in a real-time system) exceeds the cost of restarting all processes.

Option B: Abort ONE Process at a Time

Kill one process, check if deadlock is resolved. If not, kill another. Repeat until deadlock breaks.

Deadlocked	{P1, P2, P3, P4}
Step 1	Kill P2 (lowest cost victim)
Still deadlocked?	Step 2
Step 2	Kill P4 (next lowest cost)
Deadlock broken?	Done!
Result	Only P2 and P4 lost (P1 and P3 survived)

Advantage: Minimizes damage — only as many processes killed as necessary Disadvantage: High overhead — run detection algorithm after each termination (O(n² × m) per iteration)

Selecting the Victim Process

When we must choose which process to kill, we select the one with minimum cost. Cost factors include:

Factor	Lower Cost If...
Priority	Process has low priority
Computation done	Process just started (little work lost)
Resources held	Process holds few resources (less disruption to others)
Resources needed to finish	Process needs many more (far from completion)
Number of processes to terminate	Killing this one breaks the deadlock alone
Interactive vs batch	Batch processes are less urgent

Example

Recovery Method 2: Resource Preemption

Instead of killing processes entirely, we can forcibly take resources from one process and give them to another to break the deadlock.

Steps in Resource Preemption

Select a victim: Choose which process will have resources preempted (similar cost factors as above)
Rollback: The victim process must be rolled back to a safe state before it acquired the preempted resource
Ensure no starvation: The same process should not always be the victim

The Rollback Problem

When we preempt a resource from process P, we must restore P to a consistent state. There are two options:

Total rollback: Abort P completely and restart from the beginning. Simple but wasteful.

Partial rollback (checkpointing): Roll back P to a checkpoint state just before it acquired the preempted resource. This requires the system to periodically save process state (checkpoints).

Example

Process P execution timeline: [Start] ──→ [Checkpoint 1] ──→ [Got R1] ──→ [Checkpoint 2] ──→ [Got R2] ──→ [DEADLOCKED] ↑ Rollback to here, release R2

Checkpointing

Example

Preventing Starvation in Recovery

If we always choose the same process as the victim (perhaps because it has the lowest priority), it will be repeatedly rolled back and never complete. This is starvation.

Solution: Include the number of rollbacks in the cost function. Each time a process is rolled back, increase its "immunity" so it becomes a less attractive victim next time.

c example

int calculate_victim_cost_with_starvation_prevention(Process *p) {
    int base_cost = calculate_victim_cost(p);
    // Each rollback adds significant cost, eventually making
    // this process too expensive to victimize
    base_cost += p->rollback_count * 100;
    return base_cost;
}

Recovery in Real Systems

Database Systems

Databases are the best example of deadlock recovery in practice. When MySQL detects a deadlock (via wait-for graph cycle), it:

Selects the transaction with the least work done as the victim
Rolls back that transaction (UNDO log makes this possible)
Returns a "deadlock detected" error to the application
The application typically retries the transaction

Operating Systems

Most general-purpose OS (Windows, Linux) simply kill the deadlocked process. There is no sophisticated rollback — the process is terminated and its resources are freed. The user sees a crash.

Distributed Systems

Real-World Analogy

Key Takeaways

Deadlock recovery breaks detected deadlocks by either terminating processes or preempting resources
Process termination can be all-at-once (guaranteed) or one-at-a-time (minimizes damage)
Victim selection minimizes recovery cost based on priority, work done, and resources held
Resource preemption requires rolling back the victim to a consistent state (checkpointing)
Starvation must be prevented by tracking and limiting repeated victimization
Database systems are the primary real-world users of sophisticated deadlock recovery
General-purpose OS typically just kill deadlocked processes without rollback

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Deadlock Recovery.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, deadlocks, deadlock, recovery, deadlock recovery

Continue learning this concept

PreviousDeadlock Prevention NextNecessary Conditions for Deadlock