GATE CS 2013 Q16 — Deadlock

To ensure a system is deadlock-free, we must prevent a circular wait condition. Let us analyze the options by checking if a circular wait can be formed when processes execute concurrently.

Consider Option B:

• $X: P(b)P(a)P(c)$
• $Y: P(b)P(c)P(d)$
• $Z: P(a)P(c)P(d)$

Let's trace the execution of the first $P$ operations:

1. Both $X$ and $Y$ compete for semaphore $b$ as their first operation. Since $b$ is a binary semaphore initialized to $1$, only one of them can acquire it.
2. Case 1: $X$ acquires $b$ first. $Y$ is blocked on $P(b)$. Now, $X$ and $Z$ compete for semaphore $a$.
   • If $X$ acquires $a$, $X$ holds both $a$ and $b$. It can then easily acquire $c$, complete its execution, and release all semaphores, allowing $Y$ and $Z$ to proceed.
   • If $Z$ acquires $a$, $X$ blocks on $P(a)$. $Z$ holds $a$ and can successfully acquire $c$ and $d$ (since they are free), complete its execution, and release them. This unblocks $X$, which then completes, followed by $Y$.
3. Case 2: $Y$ acquires $b$ first. $X$ is blocked on $P(b)$. Now, $Y$ (holding $b$) and $Z$ (holding $a$) compete for $c$.
   • If $Y$ acquires $c$, $Y$ holds $b$ and $c$. It then acquires $d$, completes, and releases them.
   • If $Z$ acquires $c$, $Z$ holds $a$ and $c$. It then acquires $d$, completes, and releases them.

In all possible execution sequences of Option B, no circular wait is formed, making it completely deadlock-free.

For other options, we can easily find a deadlocked state. For example, in Option A, if $X$ acquires $a$, $Y$ acquires $b$, and $Z$ acquires $c$, a circular wait occurs ($X \to b \to Y \to c \to Z \to a \to X$), resulting in a deadlock.