Mutual exclusion primitives

in software

We saw that there is a potential race condition when processes share a lock variable. To use a shared lock variable correctly, we need hardware assistance. Taking turns provides a way in software to arbitrate for access to the critical region, but it needlessly restricts a process from entering its critical region when there are no other conflicting processes.

The solution is a combined approach. Each process gets its own lock variable, and a variable 'turn' is used to arbitrate in case of conflicts. The procedure for entering a critical region now becomes:

set your own lock variable to indicate that you wish to enter your critical section
then check all the other lock variables and see whose turn it is.

Peterson's solution

One algorithm, which works with two processes, is G.L. Peterson's solution (figure 2.8). Here it is rendered in Java:

public class Mutex {
    boolean interested[2]; // Whether each process wants to enter its critical region.
    int turn; // In case of conflict, whose turn is it?
    void enterCriticalSection(int thisProcess){
        int otherProcess = 1 - thisProcess;
        interested[thisProcess] = true;
        turn = otherProcess;    // No, please, after you.
        while(interested[otherProcess] && turn != thisProcess){
            /* busywait */
        }
    }
    void leaveCriticalSection(int thisProcess){
        interested[thisProcess] = false;
    }
}

(I've rewritten it a bit, to make it clearer what is going on, but the logic is exactly the same as that shown in the book.)

Note that the 'enterCriticalSection' procedure sets turn to 'otherProcess' before busywaiting. Isn't that a bit silly? Well, no. It's to ensure fairness. It is not silly, because if process #1 comes along while process #0 is in its critical section, process #1 sets 'turn' to 0 and waits politely. It is fair because it means that if two processes call 'enterCriticalSection' at about the same time, the last one to set 'turn' is the one which waits. Think about it.

last updated 15 February 1998