Mutual Exclusion

Swap Instruction

Swap is a hardware instruction that performs an atomic interchange of two values — conceptually the same strength as test-and-set, just presented as a 2-word swap.

Why have both test/set and swap?

Different CPUs expose different primitives. Swap (XCHG on x86) was historically common; test/set is a simpler read-modify-write. Both give you the atomic building block for a spinlock; the software above them is identical in shape.

Atomic pseudocode

void Swap( int & a, int & b ) {
    // begin atomic
    int temp = a;
    a = b;
    b = temp;
    // end atomic
}

Using Swap for a spinlock

int Lock = OPEN;
void Task::main() {
    int dummy = CLOSED;
    do {
        Swap( Lock, dummy );    // swap my CLOSED with shared Lock
    } while ( dummy == CLOSED );  // loop until I swapped in against an OPEN
    CriticalSection();
    Lock = OPEN;
}

• If dummy returns OPEN ⇒ I acquired the lock (the lock was open; I closed it).
• If dummy returns CLOSED ⇒ lock was already closed; try again.

Multiprocessor note

On multiple CPUs, the hardware bus must guarantee these instructions can’t interleave on the same memory location — same constraint as test-and-set.

Related

• Set Instruction
• Fetch-and-Increment
• Spinlock
• Compare-and-Swap Instruction