GATE CS 2014 Set 3 Q31 — Deadlock

To find the minimum number of tape units required to guarantee that a deadlock never occurs, we analyze the worst-case allocation scenario where a deadlock can exist.

Let:

• $N = 3$ (number of programs/processes)
• $R = 3$ (maximum tape units required by each program)

Worst-case Deadlock Scenario:

A deadlock occurs when each of the $N$ programs is allocated exactly one unit less than its maximum requirement, and no more free resources are available to satisfy any program's request.

In this state, each program holds:

$$R - 1 = 3 - 1 = 2 \text{ tape units}$$

The total number of tape units allocated in this deadlocked state is:

$$N \times (R - 1) = 3 \times 2 = 6 \text{ tape units}$$

Preventing Deadlock:

If we have even one additional tape unit, at least one program will be able to acquire its required $3$ units, complete its execution, and release all its allocated resources back to the system.

Therefore, the minimum number of tape units $M$ required to ensure deadlock-free operation is:

$$M = N \times (R - 1) + 1$$

$$M = 3 \times (3 - 1) + 1 = 6 + 1 = 7$$

Thus, the system must have at least 7 tape units to guarantee that deadlocks never arise.