Fetch_And_Add (X, i) is an atomic Read-Modify-Write instruction

Home » Operating Systems » Operating systems miscellaneous » 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

1. fails as L can overflow
2. fails as L can take on a non-zero value that lock is actually available
3. works correctly but may starve some processes
4. works correctly without starvation

Correct Option: B

Take closer look the below while loop.
while (Fetch_And_Add(L,1))
L = 1;// A waiting process can be here just after
// the lock is released, and can make L = 1.
Consider a situation where a process has just released the lock and made L = 0. Let there be one more process waiting for the lock, means executing the AcquireLock() function. Just after the L was made 0, let the waiting processes executed the line L = 1. Now, the lock is available and L = 1. Since L is 1, the waiting process (and any other future coming processes) can not come out of the while loop.
The above problem can be resolved by changing the AcuireLock() to following.
AcquireLock(L){
while (Fetch_And_Add(L,1))
{// Do Nothing}
}