Lecture 9: Deadlocks: prevention, avoidance, detection & recovery

Deadlock Avoidance, Detection and Recovery

1) Where This Lecture Fits

Once deadlock has been characterized and its necessary conditions are understood, the next question is practical: what should the operating system do about it? There are three major approaches:

• Prevention: break one of the necessary conditions.
• Avoidance: allow resource requests only if the system remains safe.
• Detection and Recovery: allow deadlocks to occur, detect them, then recover.

This lecture focuses on the last two: avoidance and detection with recovery.

2) Deadlock Avoidance

Deadlock avoidance is less rigid than prevention. It does not stop resource sharing completely. Instead, it checks each resource request carefully and grants it only if the system will remain in a safe state.

2.1 Safe State

A system is in a safe state if there exists at least one safe sequence of all processes such that each process can obtain its remaining resources, finish, and release its resources for the next process.

So the key idea is: avoidance refuses requests that would move the system from safe to unsafe.

2.2 Avoidance with Single Instance per Resource Type

If each resource type has only one instance, the Resource Allocation Graph can be extended using a claim edge. A claim edge shows that a process may request that resource in the future.

When a request is made, the operating system checks whether granting the request would create a cycle. If granting it creates a cycle, the request is delayed.

3) Banker’s Algorithm

For systems with multiple instances of each resource type, the classical avoidance method is the Banker’s Algorithm. The OS behaves like a cautious banker: it grants a request only if the resulting state remains safe.

3.1 Data Structures Used

The basic formula is:

Need = Max - Allocation

3.2 Safety Algorithm

The safety algorithm checks whether the current state is safe.

1. Set Work = Available
2. Set Finish[i] = false for all processes
3. Find a process Pi such that:
   • Finish[i] == false
   • Need[i] <= Work
4. If found, pretend that process finishes:

   Work = Work + Allocation[i]
   Finish[i] = true

5. Repeat until all processes finish or no suitable process can be found

If all Finish[i] values become true, the system is safe. Otherwise, the state is unsafe.

3.3 Resource Request Algorithm

When process Pi requests Request[i], the OS performs these checks:

1. If Request[i] <= Need[i], continue. Otherwise, the process has exceeded its maximum claim.
2. If Request[i] <= Available, continue. Otherwise, the process must wait.
3. Pretend to allocate:

   Available = Available - Request[i]
   Allocation[i] = Allocation[i] + Request[i]
   Need[i] = Need[i] - Request[i]

4. Run the safety algorithm.
5. If the state is safe, grant the request permanently. If unsafe, roll back the pretend allocation and make the process wait.

3.4 Merits and Limitations of Avoidance

4) Deadlock Detection

In deadlock detection, the operating system does not try to prevent or avoid deadlocks during normal execution. It simply allows the system to operate, then checks periodically whether a deadlock has occurred.

This approach is useful when:

• deadlock is expected to be rare, and
• the overhead of prevention or avoidance is considered too high.

4.1 Detection with Single Instance of Each Resource Type

For single-instance resources, a Wait-For Graph is used.

• Nodes represent processes only.
• An edge Pi → Pj means Pi is waiting for a resource held by Pj.

Rule: If the wait-for graph contains a cycle, then a deadlock exists.

4.2 Detection with Several Instances of Resource Types

For multiple instances, the OS uses a matrix-based detection algorithm. The main data structures are:

• Available
• Allocation
• Request

Detection steps:

1. Set Work = Available
2. If Allocation[i] == 0, set Finish[i] = true, else false
3. Find a process Pi such that:
   • Finish[i] == false
   • Request[i] <= Work
4. If found:

   Work = Work + Allocation[i]
   Finish[i] = true

5. Repeat
6. If some Finish[i] values remain false, those processes are deadlocked.

4.3 When Should Detection Run?

Detection may be run:

• whenever a request cannot be granted immediately,
• periodically after a fixed interval,
• when CPU utilization drops suspiciously, or
• on demand by an administrator.

Frequent detection finds deadlocks earlier but adds overhead. Infrequent detection reduces overhead but may allow the deadlock to affect more processes.

5) Recovery from Deadlock

Once deadlock is detected, the system must recover. The two standard recovery strategies are:

• process termination
• resource preemption

5.1 Process Termination

There are two main approaches:

1. Abort all deadlocked processes — simple, but very costly.
2. Abort one process at a time until the cycle is broken.

When aborting one process at a time, the OS must choose a victim carefully. Victim-selection factors include:

• process priority
• amount of computation already done
• amount of computation still needed
• number and type of resources held
• number of other processes that may also need to be aborted
• whether the process is interactive or batch

5.2 Resource Preemption

Instead of killing processes, the OS may take resources away from one process and give them to another. This sounds elegant, but it is not easy in practice.

Three main issues arise:

• Selecting a victim: choose which process will lose its resources.
• Rollback: the victim process may need to return to a safe checkpoint and restart later.
• Starvation: the same process may be selected again and again as victim.

Resource preemption is difficult because many resources are not safely preemptable. Taking away a printer or an in-progress I/O device is not the same as taking away CPU time.

6) Quick Comparison

7) Key Exam Points

• Avoidance is based on safe-state checking.
• Banker’s Algorithm is the standard avoidance method for multiple resource instances.
• Detection does not stop deadlock in advance; it finds it later.
• Wait-for graph is used for single-instance detection.
• Matrix-based detection is used for multiple-instance detection.
• Recovery is done by process termination or resource preemption.