Mutual exclusion primitives

Lock variables (don't quite work)

Consider using a boolean 'in critical section' flag,

boolean lockVariable = false;

The code to enter and leave the critical section would become:

void enterCriticalSection(){
    while(lockVariable == true){ // While another process is in its critical region...
        // ...do nothing. (Busywait.)
    }
    lockVariable = true; // Signal that we are entering our critical region.
}
void leaveCriticalSection(){
    lockVariable = false; // Let another process in.
}

Before it enters its critical section, it waits for the flag to become false. (If the flag were true, the process would wait (busywait) in the while loop until it were false.) Then, just before it enters its critical section, it sets the flag to true, preventing any other processes from entering their critical sections. After it exits the critical section, it sets the flag to false again, allowing other processes to enter.

Good idea?

No.

It doesn't work because the mutual exclusion mechanism itself contains a race condition: the process of testing the flag to see if it is false, then setting the flag to true is not atomic. This means that the following sequence of events is possible:

The flag is false (or the process busywaits until it becomes false---same difference)
It exits the busywaiting while loop
But! Before it gets a chance to set the flag to 'true', another process comes along, examines the flag, sees that it is 'false' and thinks that it is safe to enter its critical section, so it sets the flag to 'true'
Our original process sets the flag to 'true' too (not that that makes any difference now)
Both processes enter their critical sections
Havoc ensues

Test And Set instruction (or: making lock variables work)

(section 2.2.3) This involves a special hardware instruction called Test And Set Lock ('TAS' on the Motorola 680x0). This instruction has the special property that it is indivisible (atomic), even across processors. It basically allows you to correctly perform the trick described above, with the lock variable.

works on multiple processor machines (unlike disabling interrupts)
it also doesn't require supervisor mode (but user processes typically wouldn't use it)
requires hardware support (but most modern processors implement it)---uses special memory access mode.

Here's how one would use the instruction on an imaginary processor---the code is straight out of the book:

enter_critical_section:
        TSL    register,flag    ; Copy flag to register & set flag to 1. (Atomic operation.)
        CMP    register,#0    ; If flag was already 1...
        JNZ    enter_critical_section    ; ...busywait until it becomes zero.
        RET        ; (Return from subroutine.)
leave_critical_section:
        MOV    flag,#0    ; Set flag to zero: let another process enter.
        RET

last updated 13 February 1998