Critical section problem

Question

repeat 

     flag[i]=true;

     turn =j;

     while(flag[j] and turn=j ) do no op;

      critical section;

      flag[i]= false;

       remainder section;

 until false;

 

Above algorithm is the correct soln of the critical section problem which satisfies all the three codition-1.>mutual exclusion 2.>progress 3.>bounded waiting

my question is how this algorithm satisfies bounded waiting ??let say both the process pi and pj want to enter its critical section then they will turn flag[i] and flag[j] to 1 then pi while change the value of turn to j and and pj to i but turn can contain only one value so any one of the process will enter its cs let say it is pi.later the process pi on completion again want to enter its cs then is it will be executed indefinetly and pj will never be executed if this phenomenon is repeated  .so,please tell me where i m wrong .

Answer 1

yes. you are right but that is starvation .Notice here Pj  is  sure that it is bounded to enter cs by only one process. there will not be infinite number of process before it that could enter cs.hence bounded waiting is satisfied as only one process could enter cs before it i.e P_i  and the number of bound is known or limited.

since you felt about  starvation then if you notice ,it  is even prone to deadlock if both process are preempted after each of them  executes till "turn = j "  later when any of them come to WHILE .. it would be TRUE always and hence they continue doing no operation waiting indefinitely for an action which could be done by one another  . BUT, anyway we are interested only to handle critical section here.

Comments

..k  k i found my mistake........thank u for ur support

---

@ani there is a mistake u have done here and @saurav just look and understand . peterson algorithm is never in deadlock or starvation . now see how. starvation will be if a will be going again and again if b want to enter . when process 1 will be in cs then the turn will be cahnged by the second process as it should have changed the value of turn.. it can be noted that the process which execute tunn=process first always enters first . if 1 have executed it first then he will be going and while he will be in critical section process 2 will change the turn to himself ,means 2 so when the process 1 suppose again want to enter cannot enter as the flag[j] will be set and when it will again execute turn =1.. so the while loop become true for 1 nd will break for 2nd . hence no starvation.

---

ya. sorry .i made a mistake thanks for correcting me

.actualy i forgot that even if prempted the process will remeber  what it had read hence accordingly i would execute.i mistakenly assumed that process  read the new turn and hence always while loop would be true for each.

Answer 2

what u got wrong here is again when the p1 come after executing it will change the turn varaible to himself and then the older process while condition will break so after one another will go in . so aftre every 1 step second is getting a change to enter so .

Comments

yes yes after pi completes it sets its flag to false so the other process waiting in the while loop will enter the cs so no chances of starvation and ateast one of the 2 process will always be in the cs if they want to enter due to the turn variable....so no deadlock