Recovery from Deadlock

Once a deadlock detection algorithm finds that a deadlock exists, the system must break the deadlock.

There are two broad choices:

1️⃣ Manual recovery – Inform the system operator to fix it
2️⃣ Automatic recovery – OS resolves the deadlock itself

Automatic recovery uses two main techniques:

• Process/Thread Termination

• Resource Preemption

---

1️⃣ Process and Thread Termination

The system breaks the circular wait by aborting processes (or threads) and reclaiming their resources.

There are two methods:

---

✔ Abort All Deadlocked Processes

• Terminate every process involved in the deadlock.

• Resources are immediately freed.

• Deadlock cycle is removed at once.

❌ Disadvantages

• Very expensive.

• Processes may have run for a long time.

• All partial work is lost and must be recomputed.

---

✔ Abort One Process at a Time

• Terminate processes one by one.

• After each termination:

  • Run the detection algorithm again.

  • Check if deadlock still exists.

❌ Disadvantages

• High overhead due to repeated detection checks.

---

⚠ Practical Issues When Aborting

Termination may leave the system inconsistent:

• If updating a file → file may become corrupted.

• If holding a mutex while updating shared data:

  • Lock must be released

  • But shared data integrity is not guaranteed.

---

✔ Choosing Which Process to Abort

This is a policy decision, similar to CPU scheduling.

Goal:

Abort the process with minimum cost

Cost factors include:

1. Process priority

2. How long it has already executed

3. How much longer it needs to finish

4. Resources currently held (and their type)

5. Additional resources needed to complete

6. Number of processes that must be terminated

---

2️⃣ Resource Preemption

Instead of killing processes, the system may:

Temporarily take resources away from some deadlocked processes and give them to others until the cycle breaks.

This approach requires solving three problems:

---

✔ (1) Selecting a Victim

Decide:

• Which process loses resources?

• Which resources are taken?

Goal: Minimize cost

Cost may depend on:

• Number of resources held

• Time already consumed by the process

---

✔ (2) Rollback

After losing resources, the process cannot continue normally.

So it must be:

• Rolled back to a safe previous state, then restarted.

Two rollback options:

Total rollback

• Abort and restart process completely

• Simple but wasteful

Partial rollback

• Go back only far enough to avoid deadlock

• More efficient but requires storing detailed state info

---

✔ (3) Preventing Starvation

Problem:

• The same process might always be chosen as victim.

• That process may never finish → starvation

Solution:

• Include the number of times a process was rolled back in the cost factor.

• Ensure a process can be selected only a finite number of times.

---

Final Summary

After detecting a deadlock, recovery can be done by:

🔴 Termination

• Abort all processes (fast but costly), OR

• Abort one at a time (cheaper but slower)

🟢 Resource Preemption

• Take resources from selected victims

• Roll back affected processes

• Ensure starvation does not occur