🔒 OS 05: Deadlocks & Banker's Algorithm

Targeted for: Juspay Elimination Round & Systems Architecture Interviews
Key Focus: The 4 Coffman Conditions, Resource Allocation Graphs, Deadlock Prevention vs Avoidance, Complete Numerical Banker's Algorithm derivation, and Lock Ordering.

🛑 1. What is a Deadlock?

A Deadlock is a permanent system state where a set of concurrent processes are blocked because every process holds at least one resource and is waiting for another resource held by another process in the same set.

       Holds Lock 1 ┌─────────────┐ Wants Lock 2
    ┌──────────────>│  Process A  ├──────────────┐
    │               └─────────────┘              │
    ▼                                            ▼
┌────────┐                                  ┌────────┐
│ Lock 1 │                                  │ Lock 2 │
└────────┘                                  └────────┘
    ▲               ┌─────────────┐              │
    │  Wants Lock 1 │  Process B  │<─────────────┘
    └───────────────┤             │ Holds Lock 2
                    └─────────────┘

🔑 2. The 4 Coffman Conditions

A deadlock cannot occur unless all 4 of the following conditions hold simultaneously:

#	Coffman Condition	Formal Definition	Real-World Hardware/Software Example
1	Mutual Exclusion	At least one resource must be held in a non-shareable mode (only one process can use it at an instant).	A Mutex lock, a physical tape drive, or a dedicated database write lock.
2	Hold and Wait	A process must be currently holding at least one resource while waiting to acquire additional resources held by other processes.	Process $P_1$ holds Mutex $A$ and calls `lock(B)` without releasing $A$.
3	No Preemption	Resources cannot be forcibly confiscated from a process; they can only be released voluntarily by the holding process after it completes its task.	The OS kernel cannot forcibly snatch a held Mutex from a running thread without causing state corruption.
4	Circular Wait	A closed chain of processes ${P_0, P_1, \dots, P_n}$ exists such that $P_0$ waits for a resource held by $P_1$, $P_1$ waits for $P_2$, $\dots$, and $P_n$ waits for $P_0$.	$P_0 \to R_1 \to P_1 \to R_2 \to P_0$.

🕸️ 3. Resource Allocation Graph (RAG)

A directed graph $G = (V, E)$ where:

Vertices ($V$): Partitioned into Processes $P = {P_1, P_2, \dots, P_n}$ (circles) and Resource Types $R = {R_1, R_2, \dots, R_m}$ (rectangles with dots representing resource instances).
Edges ($E$):
- Request Edge ($P_i \to R_j$): Directed edge from Process to Resource (Process is waiting).
- Assignment Edge ($R_j \to P_i$): Directed edge from Resource instance dot to Process (Process holds resource).

Single-Instance RAG (Cycle = Deadlock)     Multi-Instance RAG (Cycle != Deadlock guaranteed)

   ( P1 ) ───> [ R1 (•) ]                    ( P1 ) ───> [ R1 (••) ] ───> ( P2 )
     ▲             │                            ▲            │
     │             ▼                            │            ▼
   [ R2 (•) ] <─── ( P2 )                     ( P3 ) <─── [ R2 (•) ]
   
   Cycle: P1 -> R1 -> P2 -> R2 -> P1         If P2 finishes and releases its instance of R1,
   DEADLOCK GUARANTEED!                      the cycle is broken. NO DEADLOCK!

[!IMPORTANT] RAG Cycle Rules:

If the graph contains no cycles $\implies$ No Deadlock.

If the graph contains a cycle AND every resource type has only 1 instance $\implies$ Deadlock is guaranteed.

If the graph contains a cycle BUT resource types have multiple instances $\implies$ Deadlock may or may not exist (must use Banker's / reduction algorithm).

🛡️ 4. Deadlock Handling Strategies

                                Deadlock Handling Strategies
                                            │
        ┌───────────────────┬───────────────┴───────────────┬───────────────────┐
        ▼                   ▼                               ▼                   ▼
1. Ignorance        2. Prevention                   3. Avoidance        4. Detection & Recovery
(Ostrich Algorithm) (Eliminate 1 of 4 conditions)   (Banker's Algo)     (Wait-For Graph + Kill)

Strategy 1: Deadlock Ignorance (Ostrich Algorithm)

Assume deadlocks occur so rarely that the performance cost of prevention/detection is not justified.
Used by: General-purpose OSs (Windows, Linux, macOS) for user-space application deadlocks. If a deadlock occurs, the user manually kills the process via Task Manager or kill -9.

Strategy 2: Deadlock Prevention (Breaking the 4 Conditions)

Eliminate Mutual Exclusion: Make resources shareable (e.g., Read-Only files, Read-Write Locks where multiple readers share access). Limitation: Write operations fundamentally require exclusivity.
Eliminate Hold and Wait: Require a process to request and receive all needed resources before starting execution, or force it to release all currently held resources before requesting new ones. Limitation: Extreme resource underutilization and starvation.
Eliminate No Preemption: If a process holding resources is denied an additional request, all its current resources are preempted (forcibly released). Limitation: Cannot be applied to stateful resources (database writes, printer streams).
Eliminate Circular Wait (🔥 Most Practical Strategy):
- Impose a Strict Global Linear Ordering on all resources (Assign integer ID to each lock $F: R \to \mathbb{N}$).
- Rule: A process can only request resource $R_j$ if $F(R_j) > F(R_i)$ for all resources $R_i$ it currently holds.
- Juspay Tree-of-Space Application: Always acquire node locks in Leaf-to-Root order (increasing depth or topological order). This guarantees no two threads can wait in a circle.

🏦 5. Deadlock Avoidance: Banker's Algorithm (Worked Example)

The Banker's Algorithm (Dijkstra) ensures the system never enters an Unsafe State (a state from which deadlock is possible).

┌────────────────────────────────────────────────────────────┐
│                    STATE TAXONOMY                          │
│                                                            │
│   ┌────────────────────────────────────────────────────┐   │
│   │ Safe State (Deadlock Impossible)                   │   │
│   │                                                    │   │
│   │   ┌────────────────────────────────────────────┐   │   │
│   │   │ Unsafe State                               │   │   │
│   │   │                                            │   │   │
│   │   │   ┌────────────────────────────────────┐   │   │   │
│   │   │   │ Deadlock State                     │   │   │   │
│   │   │   └────────────────────────────────────┘   │   │   │
│   │   └────────────────────────────────────────────┘   │   │
│   └────────────────────────────────────────────────────┘   │
└────────────────────────────────────────────────────────────┘

Problem Setup:

5 Processes: $P_0, P_1, P_2, P_3, P_4$
3 Resource Types: $A$ (10 instances), $B$ (5 instances), $C$ (7 instances)
Need Formula: $\text{Need}[i][j] = \text{Max}[i][j] - \text{Allocation}[i][j]$

Initial State Snapshot at Time $t_0$:

Process	Allocation ($A, B, C$)	Max Demand ($A, B, C$)	Need ($A, B, C$) [$\text{Max} - \text{Alloc}$]
$P_0$	$(0, 1, 0)$	$(7, 5, 3)$	$(7, 4, 3)$
$P_1$	$(2, 0, 0)$	$(3, 2, 2)$	$(1, 2, 2)$
$P_2$	$(3, 0, 2)$	$(9, 0, 2)$	$(6, 0, 0)$
$P_3$	$(2, 1, 1)$	$(2, 2, 2)$	$(0, 1, 1)$
$P_4$	$(0, 0, 2)$	$(4, 3, 3)$	$(4, 3, 1)$

Total Allocated: $A = 0+2+3+2+0 = 7,; B = 1+0+0+1+0 = 2,; C = 0+0+2+1+2 = 5$
Available Vector: $$\text{Available} = \text{Total Instances} - \text{Total Allocated} = (10-7,; 5-2,; 7-5) = \mathbf{(3, 3, 2)}$$

Step-by-Step Safety Algorithm Execution:

Let $\text{Work} = \text{Available} = (3, 3, 2)$ and $\text{Finish}[0..4] = [\text{false}, \dots, \text{false}]$.

Check $P_0$: $\text{Need}_0 = (7, 4, 3) \le \text{Work} (3, 3, 2)$? NO ($7 > 3$). Cannot satisfy $P_0$.
Check $P_1$: $\text{Need}_1 = (1, 2, 2) \le \text{Work} (3, 3, 2)$? YES!
- $P_1$ executes to completion and releases its allocated resources: $$\text{Work} = \text{Work} + \text{Alloc}_1 = (3, 3, 2) + (2, 0, 0) = \mathbf{(5, 3, 2)}$$
- $\text{Finish}[1] = \text{true}$. Safe sequence: $\langle P_1 \rangle$.
Check $P_3$: $\text{Need}_3 = (0, 1, 1) \le \text{Work} (5, 3, 2)$? YES!
- $P_3$ executes to completion and releases: $$\text{Work} = \text{Work} + \text{Alloc}_3 = (5, 3, 2) + (2, 1, 1) = \mathbf{(7, 4, 3)}$$
- $\text{Finish}[3] = \text{true}$. Safe sequence: $\langle P_1, P_3 \rangle$.
Check $P_4$: $\text{Need}_4 = (4, 3, 1) \le \text{Work} (7, 4, 3)$? YES!
- $P_4$ executes and releases: $$\text{Work} = \text{Work} + \text{Alloc}_4 = (7, 4, 3) + (0, 0, 2) = \mathbf{(7, 4, 5)}$$
- $\text{Finish}[4] = \text{true}$. Safe sequence: $\langle P_1, P_3, P_4 \rangle$.
Check $P_0$: $\text{Need}_0 = (7, 4, 3) \le \text{Work} (7, 4, 5)$? YES!
- $P_0$ executes and releases: $$\text{Work} = \text{Work} + \text{Alloc}_0 = (7, 4, 5) + (0, 1, 0) = \mathbf{(7, 5, 5)}$$
- $\text{Finish}[0] = \text{true}$. Safe sequence: $\langle P_1, P_3, P_4, P_0 \rangle$.
Check $P_2$: $\text{Need}_2 = (6, 0, 0) \le \text{Work} (7, 5, 5)$? YES!
- $P_2$ executes and releases: $$\text{Work} = \text{Work} + \text{Alloc}_2 = (7, 5, 5) + (3, 0, 2) = \mathbf{(10, 5, 7)}$$
- $\text{Finish}[2] = \text{true}$.

Conclusion:

Every process completed. The system is in a Safe State with safe execution sequence: $$\mathbf{\langle P_1, P_3, P_4, P_0, P_2 \rangle}$$

Resource-Request Evaluation Example:

Suppose process $P_1$ requests $(1, 0, 2)$:

Check $\text{Request}_1 \le \text{Need}_1$: $(1, 0, 2) \le (1, 2, 2)$ $\implies$ True.
Check $\text{Request}_1 \le \text{Available}$: $(1, 0, 2) \le (3, 3, 2)$ $\implies$ True.
Pretend to allocate:
- $\text{Available} = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)$
- $\text{Alloc}_1 = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)$
- $\text{Need}_1 = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)$
Run Safety Algorithm on modified state. If a safe sequence exists $\implies$ Grant request immediately. Otherwise $\implies$ Reject and force $P_1$ to wait.

💬 6. Verbatim Interview Scripts (Say This Out Loud)

Q: "How does strict lock hierarchy prevent deadlocks in distributed or multi-threaded systems?"

Verbatim Answer:
"A deadlock requires four conditions to hold simultaneously: Mutual Exclusion, Hold & Wait, No Preemption, and Circular Wait.

Strict Lock Ordering prevents deadlocks by mathematically eliminating the Circular Wait condition. We assign a unique numeric rank to every lock in the system. The protocol mandates that any thread needing multiple locks must acquire them in monotonically increasing rank order.

Because every thread acquires locks in the exact same direction, a cycle of dependency $(T_1 \to L_2 \to T_2 \to L_1)$ is impossible. For instance, in our M-ary Tree locking implementation, all threads acquire ancestor locks strictly from Leaf to Root (increasing depth/index). This guarantees that two threads operating on overlapping paths can never deadlock."

05-deadlocks-and-bankers-algorithm.md