Question
The following solution is alleged to be a solution to the
critical section problem. Argue for its correctness or
show a case in which it fails.
shared int turn;
shared boolean flag[2];
proc (int i) {
while (TRUE) {
compute;
// Attempt to enter the critical section
try: flag[i] = TRUE; // An atomic operation
while (flag[(i+1) mod 2]) { // An atomic operation
if (turn == i)
continue;
flag[i] = FALSE;
while (turn != i);
goto try;
}
// Okay to enter the critical section
<critical section>;
// Leaving the critical section
turn = (i+1) mod 2; // Set turn to other process
flag[i] = FALSE; // Indicate no desire to enter my c.s.
}
}
turn = 0; // Process 0 wins tie for 1st turn
flag[0] = flag[1] = FALSE; // Initialize flags before starting
fork (proc, 1, 0); // Create process to run proc(0)
fork (proc, 1, 1); // Create process to run proc(1)
Explanation / Answer
PS: Please rate The code is correct. The turn parameter is meant to break ties. It is easiest to follow what is going on if one focuses first on the code within the continuously iterating while(TRUE) loop, ignoring the code involved with turn. while (TRUE){ compute; try: flag[i]=TRUE; while (flag[(i+1) mod 2]) { if (turn == i) continue; flag[i] = FALSE; while (turn != i) ; goto try; } turn = (i+1) mod 2; flag[i] = FALSE; } /*end of while(TRUE)*/ The flag[] two element array acts like a shared lock variable. Each proc, just prior to entering the critical section, will set its flag to TRUE and then block if the other proc has its flag set to TRUE. (The "(i+1) mod 2" expression evaluates to 1 if i=0 and 0 if i=1. So the while loop just tests the other proc's flag.) This works fine to allow only one of them in the at a time, except if they both get to the blocking "while(flag[(i+1) mod 2]) {goto try;}" loop at the same time. If this happens, they both deadlock since both have flag[i] set to TRUE. They'll both just iterate forever through (ignoring the blue code) try: flag[i]=TRUE; while(flag[(i+1) mod 2]) { goto try; } since nothing can change either proc's flag[i]. The extra statements involving "turn" are meant to avoid that deadlock possibility. The key logic is seen in the while loop that tests the other process's flag: try: flag[i]=TRUE; while (flag[(i+1) mod 2]){ if (turn == i) continue; flag[i]=FALSE; while (turn != i); goto try; } In this while loop, the proc whose turn it isn't falls past (doesn't execute) the "if(turn==i) continue;" statement to set its flag=FALSE and blocks at "while (turn != i);" waiting its turn. (Note that the "while(turn != i) ;" is a while loop with no body to it. It just keeps repeating the (turn != i) test until the test fails.) The proc whose turn it is will execute the "continue" statement which causes it to ignore the remaining part of the while loop and immediately retest the (flag[(i+1) mod 2]) condition. This looping will fail as soon as the proc whose turn it isn't sets its flag=FALSE. When this happens the proc whose turn it is will proceed into the . Upon leaving the the proc whose turn it is will give the turn to the other process by executing "turn = (i+1) mod 2;" and set its flag to FALSE, releasing the other proc from the "while (turn != i);" statement and allowing it to bypass the "while (flag[(i+1) mod 2]){...}" loop and proceed into the .