Search code examples
operating-systemsynchronizationsystem

Bounded waiting in Peterson's solution


Considering two processes:

Process 0

do{
flag[0] = TRUE;
turn = 1; 
while (flag[1] && turn == 1);
    critical section
flag[0] = FALSE;
remainder
}while(1)

Process 1

do{
flag[1] = TRUE;
turn = 0; 
while (flag[0] && turn == 0);
    critical section
flag[1] = FALSE;
remainder
}while(1)

Where flag[] and turn are shared variables. Suppose process 0 starts executing first and it stops looping at while. Then process 1 goes and stops as well at while. Then process 0 resumes executing, while condition breaks and it executes its critical section. Fine.
My question is how is bounded waiting guaranteed? In this scenario I can't seem to work it out:
Process 0 exits the critical section sets flag[0] = FALSE; but then Process 1 does not resume executing rather Process 0 starts all over again, sets flag[0] = TRUE; and can reenter critical section code. What am I missing?


Solution

  • Process 0 exits the critical section sets flag[0] = FALSE; but then Process 1 does not resume executing rather Process 0 starts all over again, sets flag[0] = TRUE;

    Yes you are right till here but when Process 0 starts all over again and tries to re-enter critical section , it will execute the following two statements again:

    flag[0] = TRUE;
    turn = 1;
    

    so turn will be 1 and as we know Process 1 has not yet entered critical section due to which the flag[1] is still true and therefore the loop condition

     while (flag[1] && turn == 1);
    

    will be true,This means that process 0 will not be able to enter critical section twice. This satisfies the condition of Bounded Waiting. Also whenever Process 1 will resume its execution the condition

    while (flag[0] && turn == 0);
    

    will become false as turn is 1 and it will indeed enter critical section.