GATE CS 2018 Q.34 (CS Q.24): Deadlock Prevention, Avoidance and Detection

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 ____.

Your answer

Official answer and solution

Official answer: 2
From: Official GATE 2018 answer key

Solution

Apply the pigeonhole principle to find the maximum demand per process that guarantees deadlock freedom.

Let $P = 3$ be the number of processes and $R = 4$ be the total number of resource instances. Each process has maximum claim $K$ .

In the worst-case allocation just before deadlock, each process holds $K - 1$ instances without completing. Deadlock is guaranteed to be avoided if the total resources $R$ strictly exceeds the sum of these worst-case allocations:

P(K - 1) + 1 \le R

3(K - 1) + 1 \le 4

3(K - 1) \le 3 \implies K - 1 \le 1 \implies K \le 2

If $K = 2$ , the maximum total held by 3 processes without finishing is $3 \times 1 = 3$ . With 4 resources available, at least 1 resource remains free, allowing at least one process to acquire its maximum and terminate.
If $K = 3$ , each process can hold 1 resource (3 held) with 1 free; giving that free resource to any process leaves it with 2, still short of 3, leading to deadlock.

Thus, the largest value of $K$ that avoids deadlock is 2.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 34 of 65, printed as CS Q.24
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source