GATE CSE 2012 | Question: 32

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

• 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

Comments

because its not working properly then chaecking starvation is useless, any-way test-set(l) is starvation solution

---

Option c will be right if i am not wrong .

firstly:when first process acquire lock (AT L=0) AND it execute while loop condition, in this condition itself L will become 1.and return 0 to while. so while(0) will be false and then first process will enter into CS,AND now prempt it .now another process came and it want to acquire lock (but now L=1 hai) SO it will not be able to acquire lock and fall in BUSY WAIT.now onwards if any further process will come all will fall in BUSY WAIT and will not be able to acquire lock till the first process came out from CS.

now if first process came out from CS then it will make L=0,now the lock is available .so now any busy waiting process can schedule in any order since here queue is not used here .so starvation possible here

---

Good Read 

Option A : Here when we execute the L (shared variable ) value will change 0 or 1                    or 2  so that here overflow will not occur 

Option B ; first process P1 set L=0  now in this time the another process P2 is in wailting it doing L= 1 and 2 again and again ,, now assume  that p1  released lock L=0 when P2 just checked while condition but p2 not did L=1 before doing L=2 process p1 did L=0 now Process p2 will do L=1 ,,, then in next iteration again process p2 will do  check while loop then it will again fall under busy wait so that 

here the lock is actually available bcoz there is no process present in critical section but L= 1 shared varible contains non zero value 

Answer 1

AcquireLock(L){
   while (Fetch_And_Add(L,1)) /*preempt every process right here*/
      L = 1;
}

ReleaseLock(L){ 
   L = 0;
}

Then overflow can occur. The range of unsigned int in C is $2^{16}$. This means 65536 processes have to run simultaneously and have to preempt in increasing order of process IDs right at the same point.
The chances of you dying of a bear attack while taking the GATE exam are higher

 

Option A is correct, but is highly, highly, highly unrealistic.

---

AcquireLock(L){
   while (Fetch_And_Add(L,1)) /* a */
      L = 1;                  /* b */
}

ReleaseLock(L){ 
   L = 0;                    /* c */
}

 

Let there be two processes P1 and P2. P1 executes a. Preempt. P2 executes c. Preempt. P1 executes b.
Now, Lock is available, but since the while loop isn't atomic, P1 put L = 1, when actually it should've been 0.

 

So, B is correct.

---

Starvation is also clearly possible, depending on which process happens to get the chance to run. But C is wrong because it says "works correctly".

---

 

Answer 2

Answer (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 }
   }

 

Source: https://www.geeksforgeeks.org/operating-systems-set-17/

Answer 3

B.

When initially L=0....So when P1 perform AcquireLock function and Lock value is 1.The P2 perform AcquireLock function but L=1....So P2 wait for P1 release lock.

After Some time P1 perform ReleaseLock function but when P1 store the value L=0,it preempted.So CS is free but value of L=1 and also lock is available but P1 is preempted and L=1 so no process can enter in CS.

So,We can say that solution is fail as L can take on a non-zero value when the lock is actually available.

Comments

can we preempt the process after (L=1) AND before the fetch_And_Add(L,1)) instruction execute?

Answer 4

Consider the below scenario for option B

P1	P2
Acquire lock = 0 and execute   while loop, while loop breaks and process goes to Critical Section Preempts--->
	Process P2 comes to action and sees the value of Lock as 1.  Executes while loop setting value of L to 2. Since while condition is true and there is no semicolon after it, it will now execute next statement. As it is about to move value 1 to Lock, before moving the value <<<-------Preempts
Process P1 comes out of critical section and makes value of Lock = 0 , now lock is available. Preempts------>>>>
	Now lock is available, but now process P2 executes L=1 and sets lock to 1. Now this while loop is stuck.  Now no other process can set the value of lock to 0 and it will go in Infinite loop