GATE 2018 CS Q.24: solution and answer

GATE 2018 · CSQ.24 · 1 mark · NAT

Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of $K$ instances. Resource instances can be requested and released only one at a time. The largest value of $K$ that will always avoid deadlock is ____.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The largest value of K that always avoids deadlock is 2.

Official answer: 2Source: Official answer key, GATE 2018 CS (IIT Guwahati)

Deadlock needs every process to hold some instances while waiting for one more, with no free instance left.
The worst case is that each of the 3 processes holds $K - 1$ instances, one short of its maximum $K$ . The total held is then $3 (K - 1)$ .
Deadlock is impossible if at least one instance is still free in that worst case. So we need $3 (K - 1) + 1 \leq 4$ , which is $3 (K - 1) \leq 3$ .
This gives $K - 1 \leq 1$ , so $K \leq 2$ .
Check $K = 2$ : each process holds at most 1 instance while it still needs another, so at most 3 are held. The 4th instance is free. Some process gets its second instance, finishes and releases. The others can then finish too, so there is no deadlock.
Check $K = 3$ : take the split 2, 1, 1 with 0 free. Each process needs one more instance to reach its maximum of 3, and none is available. Deadlock is possible, so $K = 3$ does not always avoid deadlock.
The largest $K$ that always avoids deadlock is $2$ .

KEY IDEA

With $n$ processes, $m$ instances and a maximum need of $K$ each, deadlock is impossible when $n (K - 1) + 1 \leq m$ . Here $3 (K - 1) + 1 \leq 4$ gives $K \leq 2$ .

WATCH OUT FOR

Setting $3 K \leq 4$ and getting $K = 1$ , which wrongly requires every process to be able to finish at once. The right test is that the worst case, each process holding $K - 1$ , still leaves one instance free.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 6 Deadlock questions, with notes

GATE 2018 CS Q.24: solution and answer

Answer and solution

More Deadlock questions