GATE CS 2006 Q61 — Concurrency and Synchronization

To determine which statement is true, let us analyze the behavior of the fetch-and-set instruction and the implementation of the $P$ and $V$ functions.

1. Analysis of the Implementation

• fetch-and-set x, y: This atomic instruction sets the memory location $x$ (which points to s->value) to $1$ and stores its old value in $y$.
• Function $P(s)$ (Locking):
  • If s->value is initially $0$ (semaphore is free), fetch-and-set sets it to $1$ and returns $y = 0$. The loop condition while (y) becomes false, and the process successfully enters the critical section.
  • If s->value is initially $1$ (semaphore is locked), fetch-and-set sets it to $1$ (no change) and returns $y = 1$. The loop condition while (y) remains true, causing the process to busy-wait (spin-lock).
• Function $V(s)$ (Unlocking): It unconditionally resets s->value to $0$, allowing another waiting process to acquire the lock.

2. Evaluating the Options

• Option A: If context switching is disabled while a process is executing $P$, and the semaphore is already locked (s->value == 1), the process will enter the do-while loop and spin indefinitely. Since context switching is disabled, the CPU cannot switch to the process holding the lock to let it execute $V$ and release it. This leads to a permanent deadlock. Thus, the implementation may not work if context switching is disabled in $P$. This statement is true.
• Option B: Normal load/store operations are non-atomic. Using them instead of fetch-and-set would lead to race conditions, failing to guarantee mutual exclusion. Thus, this statement is false.
• Option C & D: The code correctly implements a binary semaphore using a spin-lock mechanism, and the $V$ implementation is correct. Thus, these statements are false.