Deadlock formulas

Deadlock: conditions, prevention, avoidance and detection. 4 formulas for GATE CS Operating Systems, each with when to use it. Each is explained in the topic notes.

All 4 Deadlock formulas

NEED MATRIX

Need [i] [j] = Max [i] [j] - Allocation [i] [j]

Remaining claim of process $P_{i}$ for resource type $R_{j}$ .

AVAILABLE VECTOR

Available [j] = Total [j] - i = 0 \sum n - 1 Allocation [i] [j]

Free instances of $R_{j}$ ; Total is the number of instances of $R_{j}$ in the system.

MINIMUM RESOURCES THAT GUARANTEE NO DEADLOCK

R_{m i n} = n (k - 1) + 1

Single resource type, $n$ processes, each needing at most $k$ units (and possibly asking for all $k$ ), units requested one at a time and held while waiting. Deadlock is impossible iff $R \geq n (k - 1) + 1$ ; with $R \leq n (k - 1)$ a deadlock can occur.

LARGEST NUMBER OF PROCESSES WITH NO POSSIBLE DEADLOCK

n_{m a x} = ⌊ \frac{R - 1}{k - 1} ⌋

Same assumptions, $k \geq 2$ . Follows from $n (k - 1) + 1 \leq R$ .

Where this was asked: 2018 (2), 2022 (1), 2025 (1), 2026 (2). See the 6 previous-year questions on Deadlock. This shows what was asked, not what will be asked.

KEEP GOING

Deadlock: the notes and 6 solved previous-year questions