4

From Operating System Concepts by Abraham Silberschatz, Peter B. Galvin, Greg Gagne, Peterson's solution to the critical-section problem has two processes Pi and Pj,

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);

    critical section

    flag[i] = false;
    remainder section
} while (true);

Figure 5.2 The structure of process Pi in Peterson’s solution.

Why does Pi set turn to j rather than i? I find it hard to understand intuitively. Thanks.

2

First, the way this algorithm is written, in particular using array references flag[i] and flag[j], instead of two single variables, e.g. flag_p0 and flag_p1, suggests to the reader that it would scale easily to three or more threads. However, that is simply not the case. The busy wait loop test condition has to enlarge to accommodate each new thread, or the data structures needed and tests change substantially) to generalize for N threads.

So, in the context of just this two process version as was originally developed: the actual value written to turn is unimportant as long as:

  1. for each thread, the same value is written as is tested for equality in the busy wait (or, the opposite value is tested for inequality), and,
  2. the other thread uses the opposite constant value

The point is that either the other thread is no longer interested in the protected resource (flag[j] fails), or, the other thread is interested but is still busy waiting (flag[j] is true, but the value written is now the other value).

These two tests together cover not only interest in accessing the protected resource, but problematic issues like race condition that would otherwise occur if the turn memory location weren't also involved. In short, it takes three words of state to accomplish this algorithm (and each word actually needs only 1 bit!).

The specific values used for the turn variable are not important, and do not have to be i for Pi and j for Pj; they just need to be different values used in the two different processes.

You could just as easily write i to turn if you like, e.g. for Pi

flag[i] = true;                  // register interest
turn = i;                        // write to the turn variable to detect busy condition
while (flag[j] && turn == i);    // test (lack of interest or busy wait) by Pj

as long as Pj is similarly adjusted.


Or we could dumb it down to the essence without the (arguably erroneous) allusion to the generalized N-thread version that uses arrays, as there are only two processes supported in the original algorithm. Here for P0

flag_p0 = true;                  // register interest
busy = 100;                      // write to the turn variable to detect busy condition
while (flag_p1 && busy == 100);  // test (lack of interest or busy wait) by p1

And for P1

flag_p1 = true;                  // register interest
busy = 200;                      // write to the turn variable to detect busy condition
while (flag_p0 && busy == 200);  // test (lack of interest or busy wait) by p0
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.