The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+36 votes
5.7k views

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 when the lock is actually available
  3. works correctly but may starve some processes
  4. works correctly without starvation
asked in Operating System by Boss (18.1k points)
edited by | 5.7k views
0
@Bikram Sir As there is starvation possible why C is not considered in the answer?
+1
Because , condition given in option B have stronger possibility ...
0

Why

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

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

6 Answers

+73 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)$.

answered by Veteran (355k points)
edited by
0
@arjun Sir, Is it like this : There is a non-zero probability of getting preempted just after the while loop  (Line 1) execution.

So, $P_2$  may go into infinite loop based on above possibility.
0
here both A and B are correct....below explanation is right...
0
what about starvation?
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.

Shouldn't after wrapping up L is again made equal to 0 as L is an unsigned integer?

0
@ArjunSir

AmazingExplanation..it was tough for me but when i read 2 to 3 times ..then its easy..hatsoff 2 u..;-)
0
when lock =0, the process will execute L=1 and then goto critical section or it will not execute L=1, and directly goto critical section?
+1

@sushmita

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 
0
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 ?
0

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

+1
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.
+35 votes

L=0

$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

answered by Boss (45.1k points)
edited by
0
function is atomic
+1
Yes, function is atomic but not the while loop.
0
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
+10 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
answered by Loyal (8.2k points)
+2
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?
+2
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.
0
agree with keeriti
0

@kireeti mam

 

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

+6 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

AcquireLock(L){
  1. while (Fetch_And_Add(L,1)) 
     2. L = 1;
      3(critical section)
}4

5.ReleaseLock(L){ 
  6. L = 0;
}
answered by Boss (15.1k points)
+7
Theoretically A is possible, but B is a better answer and GATE key had B only.
+2
How can P3 preempt P2?

According to the question the operation is atomic right.
0

By observing the below bold codes :

while(Fetch_And_Add(L,1)

L=1;

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???!!!

0

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

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

@ 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

+2
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
0
"Now,P1 released and makes X value 1 again" How? ReleaseLock(L) will make L=0 right?
0 votes
The Answer is A - Fails as L can Overflow if N number of processes get preempted before executing L = 1 with N as sufficiently large values of N( Greater than the Range of Unsigned integer). Fetch_and_Add will continue to increment L
answered by
0 votes
sir i think both A and B options are possible but  GATE key had B only.

verify plz
answered by Active (4.3k points)
Answer:

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

38,053 questions
45,543 answers
131,856 comments
48,880 users