The Gateway to Computer Science Excellence
+65 votes

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.

   while (Fetch_And_Add(L,1)) 
      L = 1;

   L = 0;

This implementation

  1. fails as $L$ can overflow
  2. fails as $L$ can take on a non-zero value when the lock is actually available
  3. works correctly but may starve some processes
  4. works correctly without starvation
in Operating System by Boss
edited by | 11.6k views
@Bikram Sir As there is starvation possible why C is not considered in the answer?
Because , condition given in option B have stronger possibility ...


Acquire Lock gets success only when Fetch_And_Add gets executed with L = 0

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

7 Answers

+133 votes
Best answer

A process acquires a lock only when $L = 0$. When $L$ is $1$, the process repeats in the while loop- there is no overflow because after each increment to $L$, $L$ is again made equal to $1$. So, the only chance of overflow is if a large number of processes (larger than sizeof(int)) execute the check condition of while loop but not $L = 1$, which is  highly improbable.   

Acquire Lock gets success only when Fetch_And_Add gets executed with L = 0. Now suppose $P1$ acquires lock and make $L = 1$. $P2$ waits for a lock iterating the value of L between $1$ and $2$ (assume no other process waiting for lock). Suppose when $P1$ releases lock by making $L = 0$, the next statement $P2$ executes is $L = 1$. So, value of $L$ becomes $1$ and no process is in critical section ensuring $L$ can never be $0$ again. Thus, (B) choice. 

To correct the implementation we have to replace Fetch_And_Add with Fetch_And_Make_Equal_1 and remove $L=1$ in $AcquireLock(L)$.

by Veteran
edited by


Since Initial value of lock is 0. when first process come and execute AcquireLock(L) then it will execute

while (Fetch_And_Add(L,1)) then Lock will be set to 1 (Lock=1)by process and reads old value 
( which is here inital value = 0 ) and then again execute Lock = 1 then 
it will go Critical Section..means it will execute L=1 and then go to critical section..according to me 
if there would be a option which ask about whether it is deadlock solution or not then answer will be yess it is test lock solution .


verify me ?

See it is not deadlock for processes, but starvation

the main part is " P2 waits for a lock iterating the value of L between 1 and 2 (assume no other process waiting for lock). Suppose when P1 releases lock by making L = 0, the next statement P2 executes is L = 1. "

though here lock available L=1, still P2 cannot acquire it , as P2 already make value of L is 2

The max storage size of unsigned integer is 4bytes that is its range is 0 to 4,294,967,295. So unless 4,294,967,295 process comes and all got preempted just after while statement (seems highly unlikely), L can't be overflow.

The min storage size is 2bytes that its range is range is 0 to 65,535. So,unless 65,535 process comes and all got preempted just after while statement (seems highly unlikely), L can't be overflow.

So the correct answer is B.

@arjun sir

Suppose P1 acquires the lock and make L=1. P2 waits for a lock incrementing the value of L from 1 to 2 and before L is initialized to 1 again, P2 preempts and now another process P3 waits for a lock incrementing the value of L from 2 to 3 and before L could be made 1 again P3 also preempts and another process waits for the lock and this continues.

This way the value of L will keep on increasing and since L is unsigned integer L will overflow after sometime. Thus option (a) is also correct.

Option (c) can also be correct as we do not use a queue so the process won't follow a FIFO order and thus some processes might starve as well.



If "while" is implemented as spin lock,

will the Option A a good competitor ?
Suppose P0 is in CS, P1 just executed line L=1. If P0 released the lock making L=0. Then P1 executes while(fetch_and_add(L,1)) then this will return 0 and P1 can go to CS and so on.

NOTE: from fetch_and_add(L,1), i understand that at first value of L i.e. 0 will be returned then L+1 will be performed.

Where am I going wrong please tell?
No it will not. While(0) is a false condition so it will perform L=L+1(0+1=1) and then enter the CS

@sushmita exactly then why is option B true. Option c should be true.


In while loop if process get preempted after fetch and Add, still the value of L will be getting incremented right?

@Shaik Masthan @Ayush Upadhyaya plz help. I know this is peak time and no one has time to solve doubts. But please revert back if you guys or anyone get time.

Thank you.


In while loop if process get preempted after fetch and Add, still the value of L will be getting incremented right?

yes !

But the problem is, P$_1$ in CS, L=1, and Now P$_2$ executing the while loop

after increment the value, while(non-zero) ==> while(true) ==> enter into the body of while loop.

But if you make preempt here, i mean on resumed, P$_2$ have to execute the line L=1 ;

Now, P$_1$ exit ==> Lock = 0

Now  P$_2$ resumed and executed the line L=1 ;  ===> L=1 even CS is FREE


So lock is simply aquired by P2 after P1 finished, and P2 would enter the critical section now. How CS is free? @Shaik Masthan Please explain?


Sir, there is small flaw in answer as value of L is never modified. It is given in question, READ VALUE OF MEMORY X, INCREMENT IT BY i, RETURN OLD VALUE OF X.





p2 is still in while loop, not exit from while loop.. But it makes L =1 ... So no process can enter into cs




By increment, L set to 1... For the first process
Sir but if preemption occurs after every increment of L without letting L set to 1 everytime, then there could be a chance of L overflow?

Though it seems highly unlikely to overflow L but it is a viable possibility if all processes comes and preempted just after while loop. Remember Murphy's law: 

"things will go wrong in any given situation, if you give them a chance," or more commonly, "whatever can go wrongwill go wrong."

Thank you for the answer.

If it was asked in some exams like PGEE where multiple options are correct, then should we write A, and B options both?
+58 votes


$P_1$ $P_2$ $P_3$ $P_4$ $P_5$ $\dots$
L=0 L=1 L=2 L=3 L=4  
L=1 L=2 L=3 L=4 L=5  
CS $\dots$ $\dots$ $\dots$ $\dots$  
        00 $\dots$ 0  


L is a unsigned integer it has limited memory

Have a look at the image 

let say initial value of L =0  

Let say process P1 entered and it will read  L=0 (it will fatch it and add L=1) and enter CS .

Let say next process P2 entered it will read L=1 and when it execute the while loop it will fetch and add  L=1 and add 1 to it and make it 2

But in case if p2 preempt after reading while loop and before reading L=1  

if p3 comes after it then it will fetch l value which 2 and add 1 to it and make it 3 and preempt at this point before executing next line after while loop which is L=1.

same with P4, P5, P6,.........Pn 

in this way after some times L overflow because it is a unsigned Integer .

it makes L Overflow ans ANSWER A  as correct.

Consider the situation. when first process P1 Acquired Lock it has
lock value = 0. so it will automatically increment the L value to 1
and return 0. Now returning a value 0 means => While(0) hence loop breaks.
And breaking of while loop implies process has entered the critical section
and has not executed line (L=1;)inside while loop but still currently L=1 since Fetch_And_Add(0,1) has increased the value to 1(L'=L+i //1=0+1) first time P1 executed it.

Now a process P2 comes it reads value of L as 1.It execute statement Fetch_And_Add(L,i)
returning value as 1(i.e old value) but increasing the value of L to 2(L'=L+i //2=1+1)
Now since value returned to while loop is 1 =>(implies) while(1) and process will enter
the while loop and will set the value of L back to 1 by statement (L=1;)
This process P2 or any other process say P3,P4... will read value of L as 1
it will increment to 2, enter the while loop, set it back to 1 hence other process falling in infinite loop.
(L values will be like 1->2->1->2->1->2.... so on)
till P1 doesn't release the Lock(i.e come out of critical section ) and set value of L=0;(Release Lock)

now consider the situation of overflow
P1 has already entered the critical section. P2 comes and read the Value of L as 1.
It executes Fetch_And_Add(L,i). In this case Fetch_And_Add(1,1) changing value of 
L to 2 //L=L+i;Now before executing the the statement L=1; P3 comes read value of L as 2
and execute Fetch_And_Add(L,i) increasing the value to 3.Again before it could execute the line
L=1;P4 comes read value as 3 and execute Fetch_And_Add(L,i) making value of L as 4.
If same thing happens with rest of the coming process L value will be so large
that variable would be unable to hold and hence there would be overflow.
B is also true as explained in solution.
C is false since there is starvation.consider the case P1 is in critical section P2 is waiting in while loop.As P1 release the lock P3 acquires,P3 release lock P4 acquires.Hence P2 will be in starvation

by Boss
edited by
function is atomic
Yes, function is atomic but not the while loop.
I am agree with Shekhar Chauhan ,

As there is less possibility of A) option but it can occur ,

And according to Murphy's law -"Anything that can go wrong will go wrong"

So we are suppose to handle it so according to me both a) and b) option are possible
yes overflow is also occuring .

Perfect explanation by @shekhar chauhan sir.Firstly I was stuck in CS where it is.And every time i consider it inside while loop and i was think there is no ME.So anyone  who face same problem like me =》CS is present at completely outside from while loop but obviously before release_lock ().

Awesome explanation
+20 votes
ans is B.

imagine the scenario when one process P1 was already in critical section by making L=1.

now another process P2 came and it stuck in busy waiting of Acquire lock. at some time this P2 execute the condition part and then preempted.

now P1 had completed its work and it made L=0 in release lock. now p1 is preempted.

then P2 again start its execution from where it left, so it execute the next step in Acquire lock which is L=1. currently no process is in critical section but value of L is 1. so no process can enter critical section.

hence we can say solution fails as L can take on a non-zero value when the lock is actually available
by Loyal
How P2 will execute the next step that is L=1? if it failed the while condition itself...? shouldn't it again execute the while statement?
Assume p0 is already in the CS and now P1 has executed " while (Fetch_And_Add(L,1)) " the next statement that it is yet to execute is " L = 1;". Now assume that before P1 executes " L = 1;" P0 has released the lock. Now when P1 executes its next statement " L = 1;" the cs is again locked. This scenario will lead to option B.
agree with keeriti

@kireeti mam


P1 executes its next statement " L = 1;  mean P1 is in critical Section  right ??
so lock is not available. ??

+8 votes

why not a is correct .. there may be chance of over flow .initial L=0 , p1 enter first execute line no 1 and increment Lby 1 now L=1 then execute line 2 again L=1 and go to cs . now p2 come and execute line 1 now L=2 suppose p2 is preempt and p3 enter then execute while loop now L=3 before go to line 2 it also preempted and so on .. and L is unsigned integer . so it may exceed the range or get into overflow . then it fails . so a is correct one

  1. while (Fetch_And_Add(L,1)) 
     2. L = 1;
      3(critical section)

  6. L = 0;
by Boss
Theoretically A is possible, but B is a better answer and GATE key had B only.
How can P3 preempt P2?

According to the question the operation is atomic right.

By observing the below bold codes :



Now, initially L is 0 and there comes p0 to execute...

p0 however making 1 but it's returning old value 0.

and also since while loop (0) , then why will the control will go to L=1; statement it will simply ignore L=1;

and L=1 already due to that atomic function Fetch_And_Add(X,i) where L is incremented by 1 and returns 0.

When p1 is accessing the while with L value 1. By the function L becomes 2 and return old value 1 so the while loop (1) and then now, the control will then go to L = 1 that means L which was 2 becomes 1 by overriding.

Then how come overflow is possible ma'am?! .. If so???!!!


@bikram sir, I too have the same doubt as mentioned in the comment above i.e. "since while loop (0) , then why will the control will go to L=1; statement it will simply ignore L=1; ".

Also, while() L=1; is a single line of code, so how is Context Switch possible after while and before L=1?

Please help out.

we are assuming that there are 2 process p1 and p2...

@ Untamed_one

right , but it is not returning 0 again.

@ shraddha priya

2 process can require CS at the same time. right? But context switch is not the case here. Here the process are in busy wait

Actually what is happening

P1 acquired lock and makes X=1

Now, P1 not released yet , but P2 comes and makes lock value X=1 to 2

but P1 not released yet , so P2 preempted.

Now,P1 released and makes X value 1 again

Now, P2 comes and want to acquire lock,  but as X is 1, it cannot acquire lock, though lock is available.

Same thing happen if next process comes

@srestha mam I think values can't be incremented by the process who is in C.S   assume p0 is in CS and L=1 then here p2 comes and make it 2 because of Fetch_And_Add(X,i) if  p0 is coming out of the critical section the value of L which is 2 will not be 1 it will be 0. yes if we have alot of processes like p2,p3,p4,p5... then the value of L can be 2,3,4,5...Am I right?

0 votes

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.

can we preempt the process after (L=1) AND before the fetch_And_Add(L,1)) instruction execute?
0 votes
   while (Fetch_And_Add(L,1)) /*preempt every process right here*/
      L = 1;

   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.

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

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


by Loyal
0 votes

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.

         while (Fetch_And_Add(L,1))
         { // Do Nothing }




Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,907 answers
118,145 users