GATE CS 2000 Q1.21 — Concurrency and Synchronization

This problem is a variation of the classic Dining Philosophers Problem, which can lead to a deadlock due to circular wait.

Let us analyze the resource acquisition sequence for the processes $P[0], P[1], P[2], P[3]$ and $P[4]$ using the mutexes $m[0], m[1], m[2], m[3], m[4]$.

Each process $P[i]$ attempts to acquire resources in the following order:

1. First, it locks $m[i]$.
2. Then, it attempts to lock $m[(i+1) \bmod 4]$.

Consider the following execution sequence for the first four processes $P[0]$ to $P[3]$:

• $P[0]$ executes wait(m[0]) and successfully acquires $m[0]$.
• $P[1]$ executes wait(m[1]) and successfully acquires $m[1]$.
• $P[2]$ executes wait(m[2]) and successfully acquires $m[2]$.
• $P[3]$ executes wait(m[3]) and successfully acquires $m[3]$.

Now, each process attempts to acquire its second mutex:

• $P[0]$ attempts wait(m[1]) and is blocked because $m[1]$ is held by $P[1]$.
• $P[1]$ attempts wait(m[2]) and is blocked because $m[2]$ is held by $P[2]$.
• $P[2]$ attempts wait(m[3]) and is blocked because $m[3]$ is held by $P[3]$.
• $P[3]$ attempts wait(m[0]) (since $(3+1) \bmod 4 = 0$) and is blocked because $m[0]$ is held by $P[0]$.

This creates a closed cycle of dependency:
$$\text{P}[0] \to \text{m}[1] \to \text{P}[1] \to \text{m}[2] \to \text{P}[2] \to \text{m}[3] \to \text{P}[3] \to \text{m}[0] \to \text{P}[0]$$

Since all four conditions for deadlock (Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait) are satisfied, this execution sequence results in a deadlock.