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 initialize

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 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.

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

ReleaseLock(L){
 L = 0;
}

This implementation

Accepted Answer

fails as L can take on a non-zero value when the lock is actually available. The implementation fails because the Fetch_And_Add operation increments L even when it is already non-zero, which means that the lock can appear to be held (non-zero) even when it is actually available (zero). This can lead to situations where a process believes the lock is not available when it is, causing incorrect behavior.

Solution

Related GATE Technical questions