GATE 2010 CS (CS1) – Question 56
There are n resources R0,…,R(n−1), each with one instance, and k processes P0,…,P(k−1). Process Pi requests resources as below, then uses and releases them. Which n,k can lead to deadlock?
if (i % 2 == 0) {
if (i < n) request(R[i]);
if (i+2 < n) request(R[i+2]);
} else {
if (i < n) request(R[n-i]);
if (i+2 < n) request(R[n-i-2]);
}Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) n=21,k=12
Explanation
For n=21,k=12, P10 may acquire R10 and wait for R12, while P9 acquires R12 and waits for R10: a circular wait. With even n, even processes request even resources and odd processes request odd resources, with a consistent order within each group. For n=41,k=19, the increasing and decreasing request ranges do not overlap. Thus B.