1
$\begingroup$

I have seen two different Peterson’s Solution to mutual exclusion, one is from Modern Operating Systems:

#define FALSE 0
#define TRUE 1
#define N 2

int turn;
int interested[N];

void enter_region(int process)
{
    int other;
    other = 1 - process;
    intersted[process] = TRUE;
    turn = process;
    while(turn == process && interested[other] == TRUE);
}

void leave_region(int process)
{
    interested[process] = FALSE;
}

The other is from Operating System Concepts:

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

But they are different. The first one set turn to itself, while the second one set turn to the other. The following while condition also has the same difference. After googling around, I think the second one is right, but not sure.

$\endgroup$
2
$\begingroup$

Both versions of Peterson's algorithm are correct.

The version at Operating System Concepts (OSC) is slightly better if you would believe the natural meaning of turn as whose turn it is to enter the critical section or who has the priority to enter the critical section. The version at Modern Operating Systems (MOS) is slightly better for its better variable name interested.

Let us verify that the two versions are equivalent to each other. Let us rename the variable turn in the version at MOS to wait, (which should be a better name for that variable), meaning who should be waiting or who should yield to the other process regarding entering the critical section. Now you can see two versions are similar. The version at MOS say that the current process intends to wait behind the other process when it sets the wait to be itself and checks its value later. The version at OSC says the other process should have the turn to enter the critical section when it sets the turn variable to the other process and checks its value later. Now you can feel that those two versions seems doing the same thing.

To go a step further, after we have renamed turn to wait in the version at MOS, let us further imagine that the way the computer for MOS implements wait=0 is actually set some memory location to 1 and will name that location as turn'. It will implements wait=1 as setting that location turn' to 0. Also when it checks wait == 0 it actually checks turn' == 1. When it checks wait == 1, it actually checks turn' == 0. Other than this particular implementation for the wait variable, this computer is completely the same as another computer that runs the version at OSC. Now if you skip the intermediate syntactic step that set or check wait and view turn' at the computer for MOS as equivalent to turn at the computer for OSC, (and rename several other variables), you can see they are actually executing the same code.

(In short, if you imagine that, only for the original wait variable at MOS version, 1 means 0 and 1 means 0, then you can see both version are executing same kind of code.)

Another way to see the equivalence of the two versions is to notice, as the questioner has noted, each version sets some variable to some value and then checks whether that variable is still that value. This variable is only used in these two places. There are only two values for that variable. It does not matter what is name of the variable or what are those two values. As long as the code sets some variable to some value and then checks whether that variable is still that value, that part of code has same behavior. Of course, this reasoning here is somewhat shady. It can certainly to help your understanding, though.


Every time we refer to Peterson's algorithm, it is obligatory to praise what a simple and great distributed algorithm it is. How deceptively simple it is and how smart it deals with the intricacy of concurrency!

For a much more complete understanding of the Peterson's algorithm and why it is indeed correct, please check The assertional versus Tarskian methods.

$\endgroup$

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.