Deadlock Recovery

operating-systems concurrency

Definition

Deadlock Recovery

Deadlock recovery is the process of resolving a deadlock once it has been identified by a detection algorithm. The goal is to break the circular dependency and return the system to a safe state.

Recovery Strategies

The OS can employ several methods to resolve a deadlock, ranging from simple to complex:

Process Termination

• Abort all deadlocked processes: The simplest but most expensive method, as all progress is lost.
• Abort one process at a time: Abort processes sequentially and rerun the detection algorithm until the deadlock is cleared.
• Criteria for Selection:
  • Least amount of CPU time consumed.
  • Fewest resources held.
  • Lowest priority.

Resource Preemption

• Preempt resources: Gradually take resources away from deadlocked processes and give them to others until the cycle is broken.
• Rollback: To avoid inconsistent states, the process from which resources were taken must be rolled back to a previous checkpoint where it did not hold the resource.
• Starvation: The OS must ensure that the same process is not always chosen as the victim for preemption.

Integrated Strategy

Most modern operating systems use a combination of strategies tailored to specific resource classes (e.g., using preemption for memory and avoidance for complex I/O devices).