Mutual exclusion primitives

Alternation---taking turns

Another solution, though it doesn't have all the desired properties listed above, is strict alternation. In this scheme, the processes take turns for the right to enter their critical region. Essentially there is a shared variable, which is initially 0:

int turn = 0;

This means that only process #0 is allowed to enter its critical region. If process #2, for example, wishes to enter its critical region, it must busywait for the variable to change to 2.

void enterCriticalSection(int myProcessNumber){
    while(turn != myProcessNumber){ // While it's not my turn,
        // ...busywait.
    }
}

Eventually, process #0 enters its critical region, and when it exits, it sets the shared variable to 1.

void leaveCriticalSection(){
turn = (turn + 1) % NUMBER_OF_PROCESSES; // Let the next process have a turn.
}

When process #1 enters its critical region, it sets the variable to 2 when it leaves. Process #2 would still be waiting by this time, and would enter its critical region as soon as the variable goes to 2. If it were the last of the cooperating processes, it would set the variable back to 0 again when it left its critical region.

A few problems with this solution:

requires you know in advance how many processes will want to share the memory
a process may be held up indefinitely waiting for its turn, even if no other process is in its critical section (which violates one of the requirements).

Alternation is a 'correct' solution (in that it stops races), but it is not terribly practical.

last updated 13 February 1998