Fetch_And_Add(X, i) is an atomic read-modify-write instruction that reads…
2012
Fetch_And_Add(X, i) is an atomic read-modify-write instruction that reads memory location X, increments it by i, and returns the old value of X.
Context: The instruction is used below to implement a busy-wait lock. L is an unsigned shared integer initialized to 0. A value of 0 means the lock is available; any non-zero value means it is unavailable.
AcquireLock(L) | ReleaseLock(L) |
|
|
|
|
|
|
Which of the following best describes this lock implementation?
Answer: B. fails as L can take on a non-zero value when the lock is actually available — CONCEPT A busy-wait lock must preserve a faithful state invariant: the shared state represents available when no process owns the lock and unavailable while a…
- 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 131 students.
Show answer & explanation
Correct answer: B
CONCEPT
A busy-wait lock must preserve a faithful state invariant: the shared state represents available when no process owns the lock and unavailable while a process owns it. Atomicity protects only the read-modify-write instruction; ordinary stores around it can still race with release.
APPLICATION
Let P1 execute Fetch_And_Add when L = 0. The instruction writes 1 and returns 0, so the while condition is false and P1 acquires the lock.
While P1 holds the lock, let P2 execute Fetch_And_Add. It changes L from 1 to 2, returns 1, enters the loop body, and is paused before executing L = 1.
P1 now releases the lock by writing L = 0. At this instant no process owns the lock.
P2 resumes and performs its delayed loop-body store L = 1. The shared value is now non-zero even though the lock is available.
On its next iteration P2 sees a non-zero old value and keeps waiting; another process can be delayed for the same reason.
CROSS-CHECK
Store order Observed state | Meaning Check |
Waiter stores L = 1, then owner stores L = 0 Final value is 0 | Release is visible Availability is represented |
Owner stores L = 0, then waiter stores L = 1 Final value is 1 | No process owns the lock Availability is hidden |
Integer overflow is not needed to exhibit the second ordering.
RESULT: The implementation fails because L can take a non-zero value when the lock is actually available.
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Iocl Engineers Officers Grade A Paper 2