GATE CS 2026 Set 1 Q25 — Deadlock

To ensure the system is deadlock-free, we analyze the worst-case resource allocation where a deadlock can potentially occur.

Let:

• Number of processes, $N = 5$
• Maximum resource requirement of each process, $Max(P_i) = 2$

A process can be blocked only if it has acquired $1$ resource and is waiting for its $2^{\text{nd}}$ resource. The worst-case allocation where a deadlock occurs is when every process is allocated $1$ resource less than its maximum requirement, and no resources are left free in the system.

$$\text{Worst-case allocated resources} = \sum_{i=1}^{N} (Max(P_i) - 1) = 5 \times (2 - 1) = 5$$

If the total number of resources $k = 5$, each of the $5$ processes can hold $1$ resource and wait indefinitely for another, resulting in a deadlock.

To guarantee that the system is deadlock-free, we must have at least one additional resource so that at least one process can satisfy its maximum demand, complete its execution, and release its allocated resources:

$$k \ge \sum_{i=1}^{N} (Max(P_i) - 1) + 1$$

$$k \ge 5 + 1 = 6$$

Thus, the minimum value of $k$ for the system to be deadlock-free is 6.