Two process critical section software solution

Question

// a software solution for critical section problem

bool flag[2];
int turn;

void process(int id) {
  while(true) {
    flag[id] = true;
    while(turn != id) {
      while(flag[1-id]);
      turn = id;
    }

    < Critical Section >

    flag[id] = false;
  }
}

int main(int argc, char const *argv[]) {
  
  flag[2]={0,0};
  turn = 0;
  
  parbegin
    process(0);
    process(1);
  parend	
  
  return 0;
}

Which of the following is false ?

1. Mutual exclusion is satisfied.
2. Progress is satisfied.
3. Bounded waiting is satisfied.
4. None.

Answer 1

i think its option B. here bounded waiting is not satisfied.
initially turn =0
process 0 can enter into CS any number of times even when process 1 made its flag as 1.
 

while(true) {
 1.   flag[id] = true;
 2.  while(turn != id) {
 3.     while(flag[1-id]);
 4.    turn = id;
    }
 5.   < Critical Section >
 6.   flag[id] = false;
  }
suppose process0 came, 
p0 : 1 (p0 made its flag as 1)
p1  : 1 (p1 made its flag as 1) 
p0 : 2,5,6 (turn!=0 is false so, it doesnt care if p1 is intrested in CS or not, without seeing the flag of p1, it executes CS) 
now again p0 tries to enter 
p0: 1,2,5,6 this continues..
p0 can enter CS any number of times
so bounded waiting is not satisfied

Comments

P1: 1..2..3..|| (about to go to 4) pre-empt

P0:1..2..<CS enter>

P1: 4..2..<CS enter>

---

Yes, ME not satisfied then no need to talk about progress and bounded waiting .

---

Good one Debashish.

@Anisha. Bounded waiting is satisfied as there is no bias against P1. Its not the thing that P1 will never enter CS since P0 upon exit sets the flag to false.

Answer 2

As per Dekker and Peterson , we can work with both with flag[] and turn both variables.

Now, 2 process wants to enter critical section. Initially turn=0.

Now, say process[0] wants to enter critical section first. It makes flag value=0. But it is only can go in critical section when turn=1 and flag=1. So ,flag[0] and flag[1] both are active at the same time. Means both process can enter critical section at the same time.

-----------------------------------------------------------------------------------------------------------------------------------

Now, here ME not not satisfied, as both process are active in single turn, means both can enter C.S. at the same time.

flag[id] = true;//here flag[0] can enter C.S.

while(turn != id) {
      while(flag[1-id]);//here flg[1] also actively go in C.S.
      turn = id;

Now,  it is not a strict alteration. And flag is not a bound for a process to enter into C.S. next. So, Progress will satisfy.

Bounded waiting- Here the process[0] and process[1] has no bound for entering C.S. next. Both are active at the same time. So, Bounded waiting not satisfied here.

So, option 1) and 3) are false

Comments

"Now, say process[0] wants to enter critical section first. It makes flag value=0. But it is only can go in critical section when turn=1 and flag=1. So ,flag[0] and flag[1] both are active at the same time. Means both process can enter critical section at the same time."

• "say process[0] wants to enter critical section first. It makes flag value=0" ??

• while(turn != id) // for the first time process0 finds turn = 0 and and id = 0 and first while loop breaks. 

 Seems contradictory with your answer!

And please show the sequence of steps for this line "as both process are active in single turn"

---

@Srestha,

ME not satisfied, then no need to talk about progress and bounded waiting .

---

Bounded waiting is satisfied as there is no bias against P1. Its not the thing that P1 will never enter CS since P0 upon exit sets the flag to false.

---

@sushant gokhale  . How bounded waiting is satisfied . P0 can enter in critical section infinite time without giving chance to p1 .

P0 enters in to CS . again wanted to enter in to CS so P0 sets the Flag[0]=true . and preepmt out now p1 got stuck at while(flag[1-id]); now p1 preempt out and  p0 got scheduled .

same scenario can continue for infinite time .

so no bounded waiting .

---

@Amit pal.

Consider these scenarios:

There is 500m race on a circular track.There are only 2 people viz. you and your friend competing.

1)  Sometimes you are kept on inner/smaller track and sometimes, your friend is kept on smaller track.

   So , there is equal chance for both to win th game.

2) You are always kept on the outer/longer track. So, probablity of you wining the game is less than 50%.

3) You are kept out of the competition so that your friend is always allowed to win.

Now, case 1 is fair competition.

Case 2 is just that both are competing but there is bias in favour of your friend.

Case 3 is meaning less.

Now, what you are talking of case 3. Process P1 is suitably preempted out at specific times.

When, you talk of bounded waiting, always consider 1st and 2nd case. If 1st comes true, bounded wait is satisfied. If there is bias as in case 2, bounded wait may not be satisfied.

So, I think your case is not appropriate.

---

@sushant 

the case about which i am talking is also a possibility . And if it is satisfying the condition of bounded waiting than it need to satisfy in all scenario . 

And according to murphy's law :
Murphy's law is an adage or epigram that is typically stated as: Anything that can go wrong, will go wrong.

So we cannot ignore this case also .

---

@AMit pal. One more thing. P1 is interrupted and in waiting queue for flag[0] to become false. So, once P0 leaves the CS, P1 would be immediately informed of that flag[0] has become false. So, P1 can enter CS.

---

@amit pal. I think you are right because scheduler is biased in granting the CPU to P0.

---

Thanks Amit for clearing my doubt in a better way :)

---

@sushant . When P1 is out . and CPU is handling P0 . then who will inform to P1 that flag[0] has become false . ? untill P1 gets the CPU time

---

its ok @sushant  ji :)

---

@AMit Pal. Its like the queue in monitor mechanism....queue for particular condition

---

say process[0] wants to enter critical section first. It makes flag value=0"  

then what does the next statement mean while(turn!=id)? i am thinking that this an waiting loop for p0  that means untill turn=p0 ,p0 can't enter the cs

then while(flag[1-id])// here lets say p0 has executed the while statement and found out that p1 does wants to enter cs eventually p0 enters by making turn=id

but at the same time if p1 also exeuting the while statement found out still turn!=p0  so  subsequently it also enters..so  ME does not satisfies here .is i am thinking right??

Answer 3

Answer is option C.

Actually bounded waiting is not satisfied. Process P0 or P1  can execute in the critical sections  with out any bound.

Let us assume process P0 is executing in its critical section. and process P1 is waiting in the while loop While (flag[1-id]).After completing the execution in the critical section,Po  can access the critical section for any number of times REPEATEDLY without letting process P1 to access the CS.