02. Hardware Primitives & Spinlocks

In Module 01, we established that software flags fail to enforce mutual exclusion because the flag check and flag set operations are inherently non-atomic. A preemptive context switch occurring between the test and the store destroys the synchronization barrier.

To build bulletproof mutual exclusion, operating systems rely on specialized architectural features provided directly by CPU silicon: hardware interrupt controls, formal algorithmic coordination, and atomic read-modify-write instructions.

1. Disabling Interrupts (Hardware Masking)

The earliest and most straightforward technique devised to guarantee mutual exclusion on single-core computer systems was to eliminate the source of preemption at the hardware level: masking the CPU's interrupt mechanism.

An operating system's scheduler cannot preempt a thread on its own initiative. The CPU is purely an instruction-execution engine; it switches control to the operating system dispatcher only when an external hardware interrupt (such as the periodic timer interrupt) or a software trap (such as a system call or page fault) forces the processor into privileged supervisor mode. If hardware interrupts are disabled, the scheduler cannot gain control of the CPU.

Microarchitectural Mechanics: The EFLAGS Register

On x86 and x86-64 architectures, maskable hardware interrupts are gated by a single bit within the CPU's architectural status register: the Interrupt Flag (IF), located at bit position 9 of the EFLAGS / RFLAGS register.

• cli (Clear Interrupts): Clears bit 9 (IF = 0). The core's execution unit ignores all signals arriving on the external INTR pin or from the Local Advanced Programmable Interrupt Controller (APIC).
• sti (Set Interrupts): Sets bit 9 (IF = 1). Re-enables maskable hardware interrupts (with an architectural shadow delay of one subsequent instruction).

The Reentrancy & Nesting Defect (pushf / popf)

In production operating system kernels, synchronization functions are frequently nested. A naive implementation that simply executes cli on entry and sti on exit introduces a severe bug:

/* BROKEN: Naive CLI/STI Fails Under Nesting */
void update_queue() {
    asm volatile("cli");     /* Interrupts disabled */
    log_event();             /* Calls helper function */
    /* BUG: Interrupts are now ENABLED here prematurely! */
    queue_head = queue_head->next; /* Vulnerable to preemption! */
    asm volatile("sti");
}

void log_event() {
    asm volatile("cli");     /* Disables interrupts */
    write_log_buffer();
    asm volatile("sti");     /* Blindly re-enables interrupts! */
}

When log_event() returns, it blindly executes sti, enabling interrupts before update_queue() has completed its critical queue manipulation.

To support safe nesting, the kernel must save the previous interrupt flag state onto the stack before disabling interrupts, and restore the saved state upon exit:

/* CORRECT: Nested Interrupt Preservation (x86 pushf / popf) */
static inline unsigned long save_flags_and_cli() {
    unsigned long flags;
    asm volatile(
        "pushf\n\t"           /* Push EFLAGS onto architectural stack */
        "pop %0\n\t"          /* Pop EFLAGS value into C variable 'flags' */
        "cli"                 /* Clear IF bit: mask interrupts */
        : "=r"(flags)
        :
        : "memory"
    );
    return flags;
}

static inline void restore_flags(unsigned long flags) {
    asm volatile(
        "push %0\n\t"         /* Push saved flags onto architectural stack */
        "popf"                /* Restore previous IF state to EFLAGS */
        :
        : "r"(flags)
        : "memory"
    );
}

This matches the canonical Linux kernel pattern: local_irq_save(flags) and local_irq_restore(flags).

The Two Fatal Architectural Flaws

Despite its elegance on simple hardware, disabling interrupts is fundamentally inadequate as a general-purpose synchronization mechanism:

2. Peterson's Algorithm (Software-Only Coordination)

In the early decades of computing, hardware designers did not provide atomic instructions like Test-and-Set or Compare-and-Swap. Computer scientists were faced with a profound theoretical and engineering challenge: Can provably correct mutual exclusion be achieved using only ordinary reads and writes to shared memory?

The Evolution of Software Synchronization

Before Gary Peterson published his breakthrough in 1981, researchers explored several flawed software approaches:

• Attempt 1 (The Turn Variable / Strict Alternation): A single shared variable turn dictated who could enter. While this guaranteed mutual exclusion (Condition 1), it failed Condition 3 (Progress): if Process 0 was idle in its remainder section, Process 1 was blocked from entering even though the critical section was completely empty.
• Attempt 2 (State Flags Without a Turn Variable): An array bool flag[2] recorded intent.
  If processes checked the flag before setting their own ("If you're not in, I will go in"), a context switch between the check and the set allowed both processes to enter simultaneously, violating mutual exclusion.
  If processes set their own flag before checking their competitor's ("I want in; are you in?"), both could set flag[0] = true and flag[1] = true simultaneously. When both reached the while loop, each waited for the other to drop their flag, creating a permanent deadlock (or an infinite polite dance known as livelock).
• Dekker's Algorithm (1965): The Dutch mathematician Theodorus Dekker designed the first provably correct two-process solution. However, Dekker's algorithm was notoriously complex, requiring nested conditional loops and dynamic priority back-off logic.

Peterson's Insight (1981)

Gary L. Peterson published a remarkably compact two-process mutual exclusion algorithm that united the intent array (from Attempt 2) with a polite tie-breaker scalar (from Attempt 1):

/* Peterson's Two-Process Mutual Exclusion Algorithm */
#include <stdbool.h>

static volatile bool flag[2] = {false, false}; /* flag[i] == true: Process i wants to enter */
static volatile int turn = 0;                  /* Whose turn is it to yield in a tie? */

void enter_region(int process) {
    int other = 1 - process;     /* The competing process ID (0 or 1) */
    flag[process] = true;        /* 1. Declare intent to enter */
    turn = other;                /* 2. Politely yield tie-breaker priority to peer */

    /* 3. Wait while peer wants to enter AND peer holds the priority */
    while (flag[other] == true && turn == other) {
        /* Busy wait (spin) */
    }
}

void leave_region(int process) {
    flag[process] = false;       /* Withdraw intent upon exit */
}

The genius of Peterson's algorithm lies in line 2: turn = other;. Rather than selfishly claiming "It is my turn!", each process politely declares "I grant you the turn!". The process that executes this assignment last overwrites the turn variable, effectively surrendering priority and forcing itself to wait while the earlier process proceeds into the critical region.

Formal Mathematical Proof of Correctness

We prove that Peterson's algorithm satisfies all criteria for mutual exclusion:

1. Proof of Mutual Exclusion (Safety)

We prove Condition 1 by contradiction. Assume both Process 0 and Process 1 are simultaneously inside their critical sections at time t:

• For Process 0 to enter, its while condition must have evaluated to false:
  flag[1] == false  ||  turn == 0
• For Process 1 to enter, its while condition must have evaluated to false:
  flag[0] == false  ||  turn == 1
• Both processes are inside the critical section, which requires that both set their intent flags: flag[0] == true and flag[1] == true. Therefore, the false conditions depend entirely on turn:
  Process 0 required: turn == 0
  Process 1 required: turn == 1
• However, turn is an atomic scalar in physical RAM. At any discrete instant t, turn can be either 0 or 1; it cannot be both.
• Whichever process wrote to turn last overwrote the previous write. If Process 1 wrote turn = 0 last, then turn == 0. This satisfied Process 0's entry condition while keeping Process 1 spinning in its while loop.
• Contradiction: It is mathematically impossible for both processes to observe their exit condition simultaneously. Mutual exclusion is preserved.

2. Proof of Progress (Non-Interference)

Suppose Process 1 is in its remainder section and has no desire to enter. By definition, flag[1] == false.

When Process 0 arrives at enter_region(0), it sets flag[0] = true and turn = 1. It evaluates:

while (flag[1] == true && turn == 1)

Because flag[1] is false, the compound expression evaluates to false immediately. Process 0 enters the critical region with zero delay. Process 1 running outside its critical section cannot block Process 0. Condition 3 is satisfied.

3. Proof of Bounded Waiting (Starvation Immunity)

Suppose Process 0 is waiting in its while loop while Process 1 is inside the critical region.

When Process 1 exits, it sets flag[1] = false in leave_region(1). This immediately unblocks Process 0, allowing it to enter.

Even if Process 1 immediately loops around and attempts to re-enter, its entry protocol executes:

flag[1] = true;
turn = 0; /* Process 1 yields turn to Process 0! */

By setting turn = 0, Process 1 surrenders priority. Because flag[0] is still true, Process 1 blocks on its own while loop, guaranteeing that Process 0 enters next. Process 0 can be bypassed at most once. Starvation is impossible. Condition 4 is satisfied.

The Modern Silicon Reality: Store Buffers & Memory Fences

Despite its mathematical elegance, Peterson's algorithm fails completely on modern processors (x86, ARM, Apple Silicon, RISC-V) if implemented naively in C or C++.

Why does a mathematically proven algorithm fail in practice? Because Peterson assumed Sequential Consistency (SC): the hardware assumption that all reads and writes across all cores execute in the exact linear order specified by the programmer.

The Hardware Reordering Hazard

Modern CPUs achieve extraordinary performance by utilizing Store Buffers and Out-of-Order (OOO) execution:

• When Core 0 executes flag[0] = true, the write does not immediately update DRAM or even the L1 cache. It sits in Core 0's private FIFO Store Buffer to avoid stalling the CPU execution pipeline.
• When Core 0 proceeds to evaluate the while loop, it must read flag[1] from memory.
• To hide memory latency, the processor pipeline allows subsequent reads (Load) to bypass pending writes (Store). This hardware optimization is known as Store-Load Reordering.
• As a result, Core 0 reads flag[1] (which is still false in DRAM) before its own write to flag[0] has drained to the cache!
• Simultaneously, Core 1 does the exact same thing: it reads flag[0] as false before its write to flag[1] drains.
• The Crash: Both cores observe their competitor's flag as false, exit their while loops, and simultaneously enter the Critical Section, causing data corruption!

The Solution: Explicit Memory Barriers (Fences)

To restore correctness on modern hardware, we must insert architectural Memory Barriers (or compile with strict atomic acquire-release semantics) to force the CPU store buffer to drain before the load executes:

/* Correct Peterson's Algorithm on Modern Out-of-Order Silicon */
#include <stdatomic.h>

atomic_bool flag[2];
atomic_int turn;

void enter_region(int process) {
    int other = 1 - process;
    atomic_store_explicit(&flag[process], true, memory_order_relaxed);
    atomic_store_explicit(&turn, other, memory_order_relaxed);

    /* Full hardware memory barrier (x86 'mfence', ARM 'dmb ish') */
    atomic_thread_fence(memory_order_seq_cst);

    while (atomic_load_explicit(&flag[other], memory_order_relaxed) &&
           atomic_load_explicit(&turn, memory_order_relaxed) == other) {
        /* Busy wait */
    }
}

void leave_region(int process) {
    atomic_store_explicit(&flag[process], false, memory_order_release);
}

The memory_order_seq_cst fence emits an architectural fence instruction (such as mfence on x86 or dmb ish on ARM) that stalls the core until all pending stores in the store buffer have been committed to cache and made visible to all other cores.

3. Hardware-Assisted Atomic Instructions

Rather than relying on intricate multi-variable software proofs, hardware architects introduced instructions that execute the entire Load-Modify-Store sequence as a single, indivisible hardware transaction.

1. Test-and-Set-Lock (TSL / XCHG)

The classic instruction proposed for mutual exclusion is TSL (or XCHG on x86):

; Conceptual Operation of TSL:
TSL REG, LOCK_VAR
; 1. Reads the value of LOCK_VAR from memory into register REG.
; 2. Stores a non-zero value (typically 1) into LOCK_VAR.
; 3. Operations 1 and 2 occur ATOMICALLY without interruption.

In hardware, the CPU core executing TSL locks the memory bus or enforces exclusive cache ownership (via the MESI cache coherency protocol) so that no other CPU core can read or write the memory word during the instruction's execution.

2. Compare-and-Swap (CAS / CMPXCHG)

The dominant primitive in modern systems (x86 cmpxchg, ARM64 cas) is Compare-and-Swap (CAS). It takes three operands: a memory address (V), an expected old value (A), and a desired new value (B):

bool CAS(int *addr, int expected, int new_val) {
    /* Executes atomically in CPU silicon */
    if (*addr == expected) {
        *addr = new_val;
        return true;  /* Swap succeeded */
    }
    return false;     /* Memory did not match expected value */
}

If the memory contents equal expected, CAS stores new_val and returns success. If another thread intervened and changed the value, CAS leaves memory untouched and returns failure, signaling the caller to retry.

3. The ABA Hazard in Lock-Free Data Structures

While Compare-and-Swap (CAS) enables lock-free queues, stacks, and hash tables, it introduces a subtle vulnerability: The ABA Problem:

1. Thread 1 reads memory location V, observing value A.
2. Thread 1 is preempted while preparing to execute CAS(&V, A, C).
3. Thread 2 runs and modifies V from A to B.
4. Thread 3 runs and modifies V from B back to A (e.g., freeing a node and reallocating it to the same heap address).
5. Thread 1 resumes and executes CAS(&V, A, C). The memory contains A, exactly matching expected! CAS succeeds and writes C.

The Defect: Although the memory word matched A, the underlying semantic state of the data structure changed completely during the intervening steps.

Solution: Tagged Pointers. Modern systems pair pointers with a monotonic version counter (e.g., 64-bit pointer + 64-bit counter using 128-bit double-word CAS: CMPXCHG16B on x86-64). Every mutation increments the version counter, transforming A-0 → B-1 → A-2 so that A-0 != A-2, causing CAS to fail safely.

4. Spinlocks & Microarchitectural Costs

Equipped with hardware atomic primitives like TSL, XCHG, and CMPXCHG, we can construct the simplest and most fundamental locking primitive in computer systems: the Spinlock.

A spinlock operates on a straightforward principle: when a thread attempts to enter a critical region and discovers that the lock is already held, it does not yield the CPU or enter a sleep state. Instead, it executes an active, tight polling loop (it spins) repeatedly testing the lock variable until it becomes free.

/* Fundamental Spinlock Implementation (Test-and-Set) */
typedef struct {
    volatile int lock; /* 0 = Unlocked, 1 = Locked */
} spinlock_t;

void spin_lock(spinlock_t *sl) {
    /* Atomically swap 1 into sl->lock; spin while previous value was 1 */
    while (__atomic_test_and_set(&sl->lock, __ATOMIC_ACQUIRE)) {
        /* Active busy-wait loop */
        asm volatile("pause"); /* Architectural spin-wait hint */
    }
}

void spin_unlock(spinlock_t *sl) {
    /* Release lock with release memory ordering */
    __atomic_clear(&sl->lock, __ATOMIC_RELEASE);
}

The Fundamental Trade-Off: Spinning vs. Blocking

Why would an operating system designer intentionally choose busy waiting over putting a thread to sleep? The answer lies in the microsecond latency cost of context switches:

• The Cost of Sleeping: When a thread calls a blocking synchronization primitive (like a POSIX mutex or semaphore) and goes to sleep, the kernel must execute an involuntary context switch: save CPU registers to the thread's PCB, flush hardware queues, invoke the scheduler, switch the page table base pointer (CR3), and warm up the cold cache on the new thread. On modern x86 hardware, a context switch consumes 1,000 to 3,000 CPU cycles (∼1 to 3 μs).
• The Efficiency Threshold: Let T_cs represent the expected duration of the critical section, and let T_switch represent the round-trip latency of suspending and rescheduling a thread:
  Spinning vs. Blocking Decision Invariant:

  If Tcs < 2 × Tswitch → Spinning burns fewer CPU cycles than sleeping.
  If Tcs > 2 × Tswitch → Sleeping conserves cycles and frees the core.

• The Uniprocessor Disaster: On a single-core computer, spinning is always irrational. If Thread 0 holds the lock and Thread 1 spins on the only available CPU core, Thread 0 cannot execute to make progress or release the lock! Thread 1 burns 100% of its time slice in complete futility until the timer interrupt forces a context switch. Consequently, production OS kernels strictly disable local preemption or prohibit spinlocks on uniprocessors.

Microarchitectural Contention: Cacheline Bouncing

On modern multi-core processors, CPU cores communicate over a shared high-speed interconnect bus or mesh network using a cache coherency protocol (such as MESI or MOESI).

When a thread uses a basic Test-and-Set spinlock:

• Every execution of xchg or test_and_set is an atomic write operation.
• To perform an atomic write, the core must obtain exclusive ownership of the cache line containing sl->lock. The hardware sends an Invalidate Broadcast to all other cores.
• If 16 cores are spinning on the same lock, Core 1 claims the line and invalidates Cores 2–16. An instant later, Core 2 issues an atomic write, snatching the line and invalidating Cores 1 and 3–16.
• The Resulting Storm: The 64-byte cache line bounces perpetually back and forth between core caches. This phenomenon—Cacheline Bouncing—completely saturates the inter-socket interconnect, creating memory bus congestion that degrades the performance of unrelated threads across the entire computer.

Algorithmic Optimization 1: Test-and-Test-and-Set (TTAS)

To eliminate the cacheline bouncing storm, computer scientists developed the Test-and-Test-and-Set (TTAS) optimization.

The core insight is simple: reading memory does not invalidate other cores' caches. Under the MESI protocol, multiple cores can simultaneously hold a cache line in the Shared (S) state without issuing any bus transactions.

/* Optimized Test-and-Test-and-Set (TTAS) Lock */
void spin_lock_ttas(spinlock_t *sl) {
    while (1) {
        /* Phase 1: Spin locally on shared read-only cache line (ZERO bus traffic!) */
        while (sl->lock == 1) {
            asm volatile("pause"); /* De-pipeline & reduce core power */
        }

        /* Phase 2: Attempt atomic acquisition ONLY when lock appears free */
        if (__atomic_test_and_set(&sl->lock, __ATOMIC_ACQUIRE) == 0) {
            break; /* Successfully acquired lock! */
        }
        /* If acquisition failed, loop back to read-only spinning */
    }
}

In TTAS, while the lock is held, all spinning cores read from their local L1/L2 caches in the Shared state. Bus traffic drops to zero. Only when the lock holder writes 0 (unlock) is an invalidation sent, signaling the waiting cores to attempt a single atomic acquisition.

Algorithmic Optimization 2: The x86 PAUSE Instruction

Inside modern spin loops, compilers emit the architectural pause instruction (or yield on ARM). The pause instruction solves two critical hardware problems:

1. Pipeline Flush Prevention on Loop Exit: Modern out-of-order processors aggressively speculate down the loop branch. When the lock is finally freed, the processor detects a memory order violation in its speculative load queue, forcing a massive pipeline flush that wastes ∼40 clock cycles. The pause instruction introduces a brief sub-nanosecond architectural delay that prevents speculative pipeline overrun.
2. SMT / Hyper-Threading Resource Sharing: On processors with Simultaneous Multithreading (Intel Hyper-Threading / AMD SMT), two logical threads share the execution units of a single physical core. A thread in a naked spin loop monopolizes the execution pipeline. The pause instruction yields core execution slots to the sibling hardware thread, allowing the thread doing real work to run faster.

Algorithmic Optimization 3: Exponential Backoff

When a TTAS lock is released, all spinning cores detect the free state simultaneously and rush to execute atomic_test_and_set. This creates a temporary Thundering Herd problem, where N cores flood the bus at the exact same instant.

To smooth out contention, algorithms incorporate Exponential Backoff: if a thread fails an atomic acquisition, it pauses for a delay that doubles on each successive failure:

/* Exponential Backoff Loop */
int delay = 1;
while (atomic_acquire(&lock) == FAILED) {
    for (int i = 0; i < delay; i++) {
        asm volatile("pause");
    }
    if (delay < MAX_BACKOFF) delay *= 2;
}

Scalable Queued Spinlocks (Ticket Locks and MCS Locks)

Basic spinlocks have no concept of fairness. A newly arrived core might snatch a released lock immediately, while another core has been spinning for millions of cycles. This lack of FIFO ordering violates Condition 4 (Bounded Waiting) and can lead to starvation.

• Ticket Spinlocks: Analogous to taking a numbered ticket at a deli. Two counters coordinate threads: next_ticket (incremented atomically via fetch_and_add) and now_serving. Threads spin until my_ticket == now_serving. While fair and starvation-free, releasing the lock requires writing to now_serving, which still invalidates the cache lines of all waiting cores (O(N) bus traffic).
• MCS Locks (Mellor-Crummey and Scott) & Linux qspinlocks: The ultimate evolution of the spinlock. Instead of all cores spinning on a single shared memory address, each thread allocates a node in a distributed linked list. Each core spins exclusively on its own private, local per-CPU cache line. When a thread unlocks, it modifies only the successor node's private variable. Bus traffic drops from O(N) to O(1), enabling spinlocks to scale cleanly across supercomputers with thousands of cores.

The Priority Inversion Disaster

Spinlocks introduce a notorious systems failure when combined with priority-based preemptive scheduling: Priority Inversion.

The Solution: Operating systems resolve this pathology through two strict design mandates:

1. Disabling Local Preemption During Spinlocks: In the Linux kernel, calling spin_lock() automatically increments the thread's preemption disable counter (preempt_disable()). The local CPU scheduler is forbidden from preempting the lock holder until spin_unlock() is executed.
2. Priority Inheritance Protocol (PIP): If a high-priority thread H blocks on a lock held by a low-priority thread L, the operating system temporarily elevates L's priority to match H's priority. This ensures that medium-priority threads cannot preempt L, allowing L to finish its critical section rapidly, release the lock, and drop back to its original priority.