§28.6–28.8A Failed Attempt: Just Using Loads/Stores … Evaluating Spin Locks

Interrupt control is out. Time to build from ordinary memory — and discover why ordinary memory isn’t enough.

28.6 A Failed Attempt: Just Using Loads/Stores

The obvious design (Figure 28.1): a flag, tested then set:

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *mutex) {
    // 0 -> lock is available, 1 -> held
    mutex->flag = 0;
}

void lock(lock_t *mutex) {
    while (mutex->flag == 1) // TEST the flag
        ; // spin-wait (do nothing)
    mutex->flag = 1;          // now SET it!
}

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

Two problems, one of correctness and one of performance. The correctness failure takes exactly one untimely interrupt:

The performance problem is the waiting style itself: spin-waiting — endlessly checking the flag, burning cycles; exceptionally wasteful on a uniprocessor, where the thread being waited for can’t even run.

28.7 Building Working Spin Locks With Test-And-Set

Since plain loads and stores can’t fuse the test with the set, hardware does it for us — support dating to the earliest multiprocessors (Burroughs B5000, early 1960s), present everywhere today. The test-and-set test-and-set The atomic exchange instruction: return the old value at an address while storing a new one — test and set as ONE atomic act (x86 xchg, SPARC ldstub). Enough to build a working spin lock, which pure loads/stores provably are not. defined in ch. 28 — open in glossary (atomic exchange) instruction, described as C:

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr; // fetch old value at old_ptr
    *old_ptr = new;     // store 'new' into old_ptr
    return old;         // return the old value
}

— all of it atomic. Return the old value, install the new one, no seam in between. Which makes the lock almost embarrassingly short (Figure 28.3):

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        ; // spin-wait (do nothing)
}

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

Two cases prove it. Lock free (flag 0): TestAndSet returns 0 — the caller exits the loop having already set the flag to 1 in the same atomic act; acquired. Lock held (flag 1): TestAndSet returns 1 (and re-stores 1, harmlessly) — the caller spins, and spins, until some unlock stores 0; the next TestAndSet returns 0-and-sets-1, and the lock changes hands. One winner per release, guaranteed by atomicity.

This is the spin lock spin lock The simplest lock: spin-wait, burning CPU cycles, until the lock frees (built on test-and-set or kin). Correct; unfair (spinners can starve); painful on one CPU (whole slices wasted if the holder is preempted), reasonable on multiprocessors with short critical sections. defined in ch. 28 — open in glossary : the simplest lock there is, spinning CPU cycles until the lock frees. One requirement on a single CPU: a preemptive scheduler — without the timer, a spinner never relinquishes the processor and the holder never runs.

28.8 Evaluating Spin Locks

A correct lock, at last — with a fairness hole and a scheduler-shaped weak spot. Both get fixed; first, a tour of the other atomic instructions hardware offers.