edited by
29,636 views
105 votes
105 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.

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

8 Answers

Best answer
207 votes
207 votes

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
69 votes
69 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

edited by
32 votes
32 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
10 votes
10 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;
}
Answer:

Related questions

47 votes
47 votes
6 answers
4
Arjun asked Sep 26, 2014
19,406 views
Consider the $3$ processes, $P1, P2$ and $P3$ shown in the table. $$\small \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time} & \textbf{Time Units Req...