§28.9–28.11Compare-And-Swap … Fetch-And-Add

Test-and-set is one citizen of a larger family. Three more atomic instructions — each a different superpower, one of which finally buys fairness.

28.9 Compare-And-Swap

Compare-and-swap compare-and-swap Atomic: if *ptr equals expected, store new; either way return the original (x86 compare-and-exchange). Builds the same spin lock as test-and-set but is strictly more powerful — the foundation of lock-free synchronization. defined in ch. 28 — open in glossary (SPARC) or compare-and-exchange (x86), as C pseudocode (Figure 28.4):

int CompareAndSwap(int *ptr, int expected, int new) {
    int original = *ptr;
    if (original == expected)
        *ptr = new;
    return original;
}

Update only if the current value matches your expectation; either way, learn what was there. A spin lock needs just:

void lock(lock_t *lock) {
    while (CompareAndSwap(&lock->flag, 0, 1) == 1)
        ; // spin
}

Used this way it behaves identically to test-and-set. But CAS is the more powerful instruction — a power the book cashes in later, with a peek at lock-free synchronization.

28.10 Load-Linked And Store-Conditional

MIPS (and Alpha, PowerPC, ARM) split the atom differently — a pair of instructions working in concert load-linked/store-conditional The paired primitives (MIPS, ARM, PowerPC, Alpha): load-linked reads; store-conditional succeeds ONLY if no intervening store touched the address since the LL — returning 1/0. Race between LL and SC? Exactly one contender's SC succeeds; the rest retry. defined in ch. 28 — open in glossary (Figure 28.5):

int LoadLinked(int *ptr) {
    return *ptr;
}

int StoreConditional(int *ptr, int value) {
    if (no update to *ptr since LoadLinked to this address) {
        *ptr = value;
        return 1; // success!
    } else {
        return 0; // failed to update
    }
}

Load-linked is an ordinary load; store-conditional succeeds only if nothing stored to that address in between — returning 1 on success, 0 on failure. The lock (Figure 28.6 — try building it yourself first!):

void lock(lock_t *lock) {
    while (1) {
        while (LoadLinked(&lock->flag) == 1)
            ; // spin until it's zero
        if (StoreConditional(&lock->flag, 1) == 1)
            return; // if set-it-to-1 was a success: all done
                    // otherwise: try it all over again
    }
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

The failure case is the instructive one: two threads both LL a flag of 0, both race to SC — and exactly one succeeds; the other’s SC fails (a store intervened since its LL) and it loops back to try again. Undergraduate David Capel’s short-circuit version, for connoisseurs of concision:

void lock(lock_t *lock) {
    while (LoadLinked(&lock->flag) ||
          !StoreConditional(&lock->flag, 1))
        ; // spin
}

28.11 Fetch-And-Add

One last primitive: fetch-and-add fetch-and-add Atomically increment a memory value and return the OLD value — the ticket dispenser primitive. defined in ch. 28 — open in glossary — atomically increment, return the old value:

int FetchAndAdd(int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

From it, Mellor-Crummey and Scott built the ticket lock ticket lock Mellor-Crummey/Scott: myturn = FetchAndAdd(&ticket); spin until turn == myturn; unlock increments turn. The ticket guarantees eventual progress for EVERY thread — the fairness that plain spin locks lack. defined in ch. 28 — open in glossary (Figure 28.7):

typedef struct __lock_t {
    int ticket;
    int turn;
} lock_t;

void lock(lock_t *lock) {
    int myturn = FetchAndAdd(&lock->ticket);
    while (lock->turn != myturn)
        ; // spin
}

void unlock(lock_t *lock) {
    lock->turn = lock->turn + 1;
}

The deli counter, in silicon — and the first design on the fairness axis’s good side. But every lock so far still spins, and spinning has a price the next section finally refuses to pay.