Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the…
2012
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 shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.
This implementation
- A.
fails as L can overflow
- B.
fails as L can take on a non-zero value when the lock is actually available
- C.
works correctly but may starve some processes
- D.
works correctly without starvation
Attempted by 136 students.
Show answer & explanation
Correct answer: B
Key idea: A waiting process can overwrite the released 0 with 1, leaving the lock non-zero though no process holds it.
Concrete interleaving that demonstrates the failure:
Initially, L = 0.
Process P1 calls Fetch_And_Add(L,1). It sees the old value 0, so Fetch_And_Add returns 0 and L becomes 1. P1 enters the critical section.
Process P2 calls Fetch_And_Add(L,1). It sees a nonzero old value (1), so Fetch_And_Add returns nonzero and increments L (for example to 2). Because the returned value was nonzero, P2 executes the loop body and sets L = 1, and continues spinning.
P1 exits the critical section and executes ReleaseLock, which sets L = 0.
A waiting process such as P2 then performs (or already performed) the assignment L = 1 in its loop body after P1's release, overwriting the 0 with 1. From that point on, L remains non-zero while no process holds the critical section, and other processes cannot acquire the lock because the loop condition never observes a zero return from Fetch_And_Add.
Result: This is a correctness failure (the lock can appear held with no owner), not merely potential starvation.
How to fix or implement correctly (brief):
Use an atomic test-and-set (atomic exchange) that returns the previous value and sets the lock in one atomic step; only the process that observes the previous value 0 succeeds.
Alternatively, implement a ticket lock using Fetch_And_Add as a ticket allocator plus a separate serving variable so that Fetch_And_Add is not used to overwrite the shared availability flag.