7.9k 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){
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
edited | 7.9k 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

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

edited by
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

+5
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.
0

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

0
@MiNiPanda

If "while" is implemented as spin lock,

will the Option A a good competitor ?
0
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?
0
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
0

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

0

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.

+2

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

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

edited by
0
function is atomic
+1
Yes, function is atomic but not the while loop.
+3
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
0
yes overflow is also occuring .
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
+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?
+3
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

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

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){
2. L = 1;
3(critical section)
}4

5.ReleaseLock(L){
6. L = 0;
}
+8
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 :

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?

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

right , but it is not returning 0 again.

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

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

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
sir i think both A and B options are possible but  GATE key had B only.

verify plz

1
2