GATE CS 2010 Q46 — Deadlock

To determine if a deadlock is possible, let us analyze the resource request patterns of the processes:

1. Even-indexed processes ($P_i$ where $i$ is even):

• Request $R_i$ first, then $R_{i+2}$.
• They only request even-indexed resources in a strictly increasing order of indices ($R_0 \to R_2 \to R_4 \dots$).

2. Odd-indexed processes ($P_i$ where $i$ is odd):

• Request $R_{n-i}$ first, then $R_{n-i-2}$.
• They request resources in a strictly decreasing order of indices.
• If $n$ is even, $n-i$ and $n-i-2$ are odd. Thus, odd processes only request odd-indexed resources. Since even and odd processes access completely disjoint sets of resources, no interaction occurs, making deadlock impossible. This rules out options A and C.
• If $n$ is odd, $n-i$ and $n-i-2$ are even. Thus, both even and odd processes compete for even-indexed resources. Since one group requests them in increasing order and the other in decreasing order, a deadlock cycle can form.

Let us test the remaining options with odd $n$:

• Option B ($n=21, k=12$):
  Consider process $P_8$ (even) and $P_{11}$ (odd):
  • $P_8$ requests $R_8$ then $R_{10}$.
  • $P_{11}$ requests $R_{21-11} = R_{10}$ then $R_{21-11-2} = R_8$.
  If $P_8$ acquires $R_8$ and $P_{11}$ acquires $R_{10}$, they will wait for each other indefinitely, resulting in a deadlock.
• Option D ($n=41, k=19$):
  The maximum index requested by any even process is $18$ (requested by $P_{16}$). The minimum index requested by any odd process is $41 - 17 - 2 = 22$ (requested by $P_{17}$). Since the resource sets $[0, 18]$ and $[22, 40]$ are disjoint, no deadlock can occur.