GATE CS 2018 Q24 — Deadlock

To ensure that a system is always free from deadlock, the total number of resources allocated in the worst-case scenario (where every process is holding one less than its maximum requirement) must be strictly less than the total available resources.

Let:

• $N = 3$ (Number of processes)
• $R = 4$ (Total instances of the resource)
• $K =$ Maximum demand of each process

In the worst-case state, each of the $N$ processes holds $(K - 1)$ resources and is waiting for one more resource. For a deadlock to be avoided, the total resources allocated in this state must be less than the total available resources $R$:

Substituting the given values:

Since the maximum demand $K$ must be an integer, the largest integer value of $K$ that always avoids deadlock is $2$.

Verification:

• If $K = 2$: The worst-case allocation is when each of the $3$ processes holds $1$ resource (total $3$ allocated). Since $1$ resource remains free ($4 - 3 = 1$), any of the processes can acquire it, complete its execution, and release its resources. Thus, deadlock is impossible.
• If $K = 3$: The processes could hold $2$, $1$, and $1$ resources respectively (total $4$ allocated, $0$ free). Each process needs at least $1$ more resource to finish, resulting in a deadlock.