Abraham Silberasch Galvin operating system Book chapter 5 process synchronization

Question

The first known correct software solution to the critical-section problem
for two processes was developed by Dekker. The two processes, P0 and
P1, share the following variables:
boolean flag[2]; /* initially false */
int turn;
The structure of process Pi (i == 0 or 1) is shown in Figure 5.21. The
other process is Pj (j == 1 or 0). Prove that the algorithm satisfies all
three requirements for the critical-section problem. How it can satisfy bounded waiting condition?

do {
flag[i] = true;
while (flag[j]) {
if (turn == j) {
flag[i] = false;
while (turn == j)
; /* do nothing */
flag[i] = true;
}
}
/* critical section */
turn = j;
flag[i] = false;
/* remainder section */
} while (true);

Comments

this process suffers strict alternation

Answer 1

P1, P2 share these variable (took process names as (P1 and P2) rather than (P0 and P1))

boolean flag[2]; /* initially false */
int turn;

Code for P1:

1. do {
2. flag[i] = true;
3. while (flag[j]) {
4. if (turn == j) {
5. flag[i] = false;
6. while (turn == j)
7. ; /* do nothing */
8. flag[i] = true;
9. }
10. }
11. /* critical section */
12. turn = j;
13. flag[i] = false;
14. /* remainder section */
15. } while (true);

Code for P2:

1. do {
2. flag[j] = true;
3. while (flag[i]) {
4. if (turn == i) {
5. flag[j] = false;
6. while (turn == i)
7. ; /* do nothing */
8. flag[j] = true;
9. }
10. }
11. /* critical section */
12. turn = i;
13. flag[j] = false;
14. /* remainder section */
15. } while (true);

 

I believe you don't have any doubt in Mx and Progress. Say P1 got CS first (when P2 is also waiting for the CS-entry), while leaving P1 will make the turn to P2, see line 12 (I have turned it Bold.) If P1 wants to re-enter the CS, It will enter Loop (at line 3, will be struck at loop 2 at line 6) after spinning for a while, due to scheduling algorithm it has to be preempted out and P2 has to be given the Processor, P2 breaks Loop (as it has (turn==i) in line 6 of its respective code) whereby entering the CS. So none of the 2 processes is INFINITELY starving for the processor. Hence Bounded wait handled.