GATE CS 1997 Q6.7 — Deadlock

To find the minimum number of units of resource $R$ required to guarantee that a deadlock will never occur, we can analyze the worst-case allocation scenario where a deadlock is just about to happen.

Let:

• Number of processes, $N = 3$
• Maximum resource requirement for each process, $Max_i = 2$

Worst-case allocation without progress:
Each process is allocated one unit less than its maximum requirement. In this state, every process is blocked waiting for its final resource, resulting in a deadlock if no more resources are available.

$$\text{Resources allocated in worst-case} = \sum_{i=1}^{N} (Max_i - 1) = 3 \times (2 - 1) = 3\text{ units}$$

Deadlock Prevention:
If we add just $1$ more resource to this state, at least one process will get its maximum requirement, complete its execution, and release all its allocated resources back to the pool. This prevents any deadlock from occurring.

$$\text{Minimum resources } (R) \ge \sum_{i=1}^{N} (Max_i - 1) + 1$$ $$R \ge 3 + 1 = 4$$

Thus, the minimum number of units of $R$ to ensure no deadlocks ever arise is 4.