GATE CS 2012 Q32 — Concurrency and Synchronization

To analyze the behavior of the lock implementation, let us trace the execution with two processes, $P_1$ and $P_2$, where the shared variable $L$ is initially $0$ (lock is available):

1. $P_1$ attempts to acquire the lock:
   • $P_1$ executes Fetch_And_Add(L, 1). This atomically reads the old value $0$, increments $L$ to $1$, and returns $0$.
   • Since the returned value is $0$, the while loop condition is false. $P_1$ successfully acquires the lock and enters the Critical Section (CS).
2. $P_2$ attempts to acquire the lock while $P_1$ is in the CS:
   • $P_2$ executes Fetch_And_Add(L, 1). This reads the current value $1$, increments $L$ to $2$, and returns $1$.
   • Since the returned value is $1$ (non-zero), $P_2$ enters the loop body and is about to execute L = 1;.
3. $P_1$ releases the lock:
   • $P_1$ finishes its CS and calls ReleaseLock(L), which sets $L = 0$. The lock is now conceptually free.
4. $P_2$ resumes execution:
   • $P_2$ now executes its pending loop body statement: L = 1;.
   • This overwrites the value of $L$ back to $1$.

At this point, no process is in the Critical Section, meaning the lock is actually available. However, because $L = 1$, any subsequent call to AcquireLock(L) by any process will read a non-zero value and get stuck in the busy-wait loop. Thus, the implementation fails because $L$ can take on a non-zero value when the lock is actually available.