Deadlock Handling Approaches: Deadlock Prevention & Avoidance (Banker’s Algorithm)

1. Overview of the 4 Approaches to Handling Deadlocks

An Operating System can deal with the Deadlock problem in four ways:

2. Approach 1: Deadlock Prevention

We know that all 4 Coffman conditions (Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait) must hold simultaneously for a deadlock to occur.

Deadlock Prevention works by ensuring that at least ONE of these four necessary conditions can NEVER hold! Let us see how we can break (attack) each of the 4 conditions:

1. Eliminating Mutual Exclusion

• For Shareable Resources: Read-only files can be shared simultaneously by 100 processes without locks, so they never cause deadlocks.
• For Non-Shareable Resources: Hardware like a Printer or Mutex Lock is inherently non-shareable—we cannot eliminate Mutual Exclusion for such resources (though Spooling can help for printers).

2. Eliminating Hold and Wait

To ensure that a process never holds one resource while waiting for another, we enforce one of two protocols:

• Protocol A (All-at-Once Allocation): Every process must request and be allocated ALL of its required resources before it begins execution!
• Protocol B (Release Before Request): A process is allowed to request new resources only when it is currently holding ZERO resources (it must release all currently held resources first).
• Drawback: Low resource utilization and potential starvation.

3. Eliminating No Preemption (Allowing Preemption)

If a process that is already holding some resources requests another resource that cannot be immediately allocated to it, then all resources the process is currently holding are implicitly preempted (taken away)! The process will be restarted only when it can regain its old resources plus the new one it requested.

4. Eliminating Circular Wait (The Most Practical Method!)

• How it Works (Total Resource Ordering):
  1. Assign a unique increasing integer number to every resource type in the system: e.g., Tape Drive = 1, Scanner = 5, Printer = 12.
  2. Strict Rule: Every process must request resources in strictly increasing order of enumeration!
  • For example, a process can request the Scanner (5) first and then the Printer (12) (5 < 12), but a process holding the Printer (12) is forbidden from requesting the Scanner (5)!
  • This mathematically guarantees that a circular wait loop can never form!

3. Approach 2: Deadlock Avoidance

While Deadlock Prevention imposes strict static rules that reduce hardware utilization, Deadlock Avoidance is smarter and dynamic:

• Core Requirement: Each process must declare in advance the Maximum Number of resources of each type that it may ever need during its lifetime.
• Whenever a process requests a resource at runtime, the Deadlock Avoidance algorithm inspects the current allocation and future maximum needs to check whether granting the request will leave the system in a Safe State.
  • If Safe: The resource is granted immediately!
  • If Unsafe: The process must wait, even if the resource is currently free!

Safe State vs Unsafe State

• Safe State: A state is Safe if the OS can find at least one Safe Sequence of processes < P1, P2, …, Pn > such that every process can get its maximum needed resources, finish execution, and release all its resources for the next process in the sequence.
• Key Rule:
  • A Safe State has ZERO chance of Deadlock.
  • An Unsafe State does not mean it is already deadlocked, but an Unsafe State CAN lead to a Deadlock! Deadlock Avoidance ensures the system never enters an Unsafe State.

4. Dijkstra’s Banker’s Algorithm (For Multiple Resource Instances)

Why is it called the Banker’s Algorithm? Because it works just like a Bank Manager giving out loans—a bank never lends out its cash in such a way that it cannot satisfy the withdrawal needs of all its customers!

4 Data Structures Used in Banker’s Algorithm (n Processes, m Resources):

1. Available[m]: Number of currently free/available instances of each resource type.
2. Max[n][m]: Maximum demand of each process.
3. Allocation[n][m]: Number of resources currently allocated to each process.
4. Need[n][m]: Remaining resources each process might still need to finish!

Formula: Need[i] = Max[i] − Allocation[i]

Solved Numerical Example of Banker’s Algorithm (Exam Favorite!)

Suppose a system has 3 processes (P0, P1, P2) and 1 resource type with 10 total instances. Currently Available = 2 instances:

Step-by-Step Safety Check (Available = 2):

1. Check P0: Needs 4, but Available = 2 (4 > 2 → Cannot satisfy P0 yet).
2. Check P1: Needs 2, and Available = 2 (Need ≤ Available ✅)!
   • Allocate 2 to P1. P1 finishes execution and releases its allocated 2!
   • New Available = 2 + 2 = 4.
3. Check P0 again: Needs 4, and now Available = 4 (4 ≤ 4 ✅)!
   • Allocate 4 to P0. P0 finishes and releases its allocated 4!
   • New Available = 4 + 4 = 8.
4. Check P2: Needs 7, and now Available = 8 (7 ≤ 8 ✅)!
   • Allocate 7 to P2. P2 finishes and releases its allocated 2!
   • Final Available = 8 + 2 = 10.

• Result: The system is in a SAFE STATE, and the Safe Sequence is < P1, P0, P2 >!

💡 Exam Preparation Tips for DAVV BCA

• Always write the golden formula of Banker’s Algorithm in a box: Need = Max - Allocation and the condition to pick the next process: Need[i] ≤ Available.
• Differentiate clearly between Deadlock Prevention (breaks one of the 4 necessary conditions statically) and Deadlock Avoidance (uses Banker’s Algorithm dynamically to keep the system in a Safe State).