GATE CS 1998 Q1.32 — Deadlock

To ensure the system is guaranteed to be deadlock-free, we analyze the worst-case resource allocation scenario.

Let:

• $R = 6$ (total number of tape drives available)
• $n$ = number of processes
• $Max_i = 2$ (maximum demand of each process $i$)

In the worst-case scenario, each process is allocated one less than its maximum requirement, meaning each process holds exactly $Max_i - 1 = 2 - 1 = 1$ tape drive and is waiting for one more.

The total number of allocated drives in this state is:

For a deadlock to be impossible, the total number of resources $R$ must be strictly greater than this worst-case allocation, ensuring at least one process can get its remaining required resource and run to completion:

Since $n$ must be an integer, the maximum value of $n$ for the system to remain deadlock-free is $5$.

Verification:

• If $n = 5$, each process holds $1$ drive (total $5$ allocated). The $1$ remaining free drive can be allocated to any process, allowing it to finish and release its resources.
• If $n = 6$, each process holds $1$ drive (total $6$ allocated). No free drives remain, resulting in a deadlock.