Question

Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the OLD value of X. It is used in the pseudocode below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0 (0 = lock available, non-zero = lock unavailable).

AcquireLock(L) {
  while (Fetch_And_Add(L,1))
    L = 1;
}

ReleaseLock(L) {
  L = 0;
}

This implementation

AcquireLock(L) {
  while (Fetch_And_Add(L,1))
    L = 1;
}

ReleaseLock(L) {
  L = 0;
}

This implementation

Accepted Answer

The correct answer is (B) fails as L can take on a non-zero value when the lock is actually available. The loop body's plain write 'L = 1' is NOT part of the same atomic operation as Fetch_And_Add, so it can race with a concurrent ReleaseLock's 'L = 0' (or another process's Fetch_And_Add). A waiting process's non-atomic reset to 1 can stomp on the shared counter's true state after the lock has actually become free, leaving L stuck at a non-zero value even though no process holds the lock — causing later acquirers to spin forever on an available lock. This is a genuine correctness bug, not just a fairness/starvation issue.

Explanation