Mutual Exclusion

Load-Linked / Store-Conditional

LL/SC is a MIPS/ARM/PowerPC pair of instructions that generalize atomic read-modify-write. LL reads from memory and sets a hardware reservation on that cache line; SC stores back — but only succeeds if no interrupt, exception, or other write has touched the reservation since LL. Failure is indicated by SC zeroing the value register.

Why have LL/SC when CAS exists?

Because LL/SC doesn’t suffer from the ABA problem. CAS compares values — if a location goes A → B → A, CAS can’t tell. LL/SC tracks the memory cell via a hardware reservation; any intervening write to that address invalidates the reservation, even if the value ended up the same. Trade-off: the reservation can be lost to a context switch, cache eviction, or unrelated coherence traffic ⇒ SC fails spuriously. Requires a retry loop regardless.

Atomic pseudocode

LL Rdst, addr    // read *addr into Rdst; set reservation on addr
...              // computation in registers
SC Rsrc, addr    // if reservation intact, write Rsrc to *addr, set Rsrc=1
                 // else set Rsrc=0, no write

Implementing test-and-set via LL/SC

int testSet( int &lock ) {     // atomic
    int temp = lock;            // read
    lock = 1;                   // write
    return temp;
}

testSet:
    ll    $2, ($4)              # read and lock $4 (= addr)
    or    $8, $2, 1             # set $8 to 1
    sc    $8, ($4)              # attempt store
    beq   $8, $0, testSet       # SC failed ⇒ retry
    j     $31                   # return old value in $2

Lock-free pop — no ABA worry

Node *pop( Header &h ) {
    Node *t, *next;
    for ( ;; ) {
        t = LL( top );
        if ( t == nullptr ) break;   // empty
        next = t->next;
        if ( SC( top, next ) ) break;   // succeeds only if top untouched
    }
    return t;
}

Between LL and SC, if anyone else modifies top — even if they eventually restore the same pointer — SC fails and we retry. No counter needed.

Caveats

• Reservation granularity is the cache line, so unrelated writes to neighbours can spuriously fail SC ⇒ false contention.
• Context switches lose the reservation ⇒ always loop SC on failure.
• On x86 there’s no LL/SC — x86 uses LOCK CMPXCHG (CAS) and accepts the ABA cost.

Related

• Compare-and-Swap Instruction
• ABA Problem
• Test-and-Set Instruction