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