GATE CS 2021 Set 1 Q46 — Concurrency and Synchronization

Let us analyze each option by tracing the concurrent execution of the 5 threads:

• Option D is possible (Deadlock): Initially, $S = 5$. Suppose all 5 threads execute their first wait(S) statement (line 5) concurrently. Each thread successfully decrements $S$ by 1, making $S = 0$. Now, all 5 threads reach line 6 and attempt to execute the second wait(S). Since $S = 0$, all of them block indefinitely, resulting in a deadlock.
• Option A is possible (Value of 5): If the threads execute sequentially one after another without any interleaved context switches during the non-atomic counter++ operation, each thread successfully increments the counter by 1. The final value of counter will be $5$.
• Option B is possible (Value of 1): Since the counter++ operation is non-atomic, it consists of three steps: Read, Increment, and Write.
  1. Thread $T_1$ enters the critical section, reads counter = 0 into its local register, and is preempted before writing.
  2. Since $T_1$ holds 2 units of the semaphore, $S = 3$. The remaining threads $T_2, T_3, T_4, T_5$ can still execute sequentially. They run to completion, updating counter to $4$.
  3. Thread $T_1$ resumes, increments its local register value from $0$ to $1$, and writes $1$ back to counter.
  Thus, the final value of counter becomes $1$.
• Option C is impossible (Value of 0): If all threads successfully complete their execution, at least one write operation to counter must occur. Since counter starts at $0$ and any write operation writes a value of at least $\text{read\_value} + 1 \ge 1$, the final value of counter can never be $0$.