Hardware Support: Test-and-Set and Atomic Instructions

A critical section is a code region that touches shared state and must not be executed by more than one thread at a time. A correct solution needs three properties: mutual exclusion (at most one thread in the critical section at once), progress (a thread not in its critical section cannot block others from entering), and bounded waiting (a thread requesting entry is not overtaken infinitely often). Peterson's algorithm achieves all three using only ordinary loads and stores to shared variables — but it relies on an assumption that real hardware routinely violates: that memory operations from different threads become visible to everyone in the exact order they were issued, with no reordering and no caching artifacts. On real multicore machines with per-core caches and out-of-order execution, a plain store followed by a plain load can appear, from another core's point of view, to happen in the opposite order unless the hardware is explicitly told otherwise. Peterson's algorithm silently breaks under this reordering. The hardware solves this by exposing a small number of atomic read-modify-write (RMW) instructions. An instruction is atomic if, from the point of view of every other core, it appears to execute as a single, uninterruptible step: no other core can observe an intermediate state, and no other core's competing RMW on the same memory location can interleave with it. The CPU implements this guarantee at the level of the cache-coherence protocol, typically by having the core that issues the instruction acquire exclusive ownership of the cache line before performing the read-modify-write, and holding that ownership until the write commits. Two atomic instructions dominate real systems:

• Test-and-Set (TAS): atomically writes 1 (or `true`) into a memory location and returns the location's previous value, in one indivisible step.
• Compare-And-Swap (CAS): atomically compares a memory location's current value to an expected value; if they match, it writes a new value into the location; either way it returns (or reports) whether the swap happened. CAS is strictly more powerful than TAS — it can simulate TAS and also implement arbitrary optimistic updates, which is why it underlies most modern lock and lock-free algorithms.

A related but weaker primitive, fetch-and-add, atomically adds a value to a memory location and returns the old value; it is useful for counters and ticket locks. All of these instructions share the same essential property: the hardware, not the compiler and not the programmer, guarantees indivisibility, and this is exactly the missing ingredient that made pure software solutions like Peterson's algorithm fragile.

Test-and-Set as a hardware primitive. Conceptually, TAS is a single CPU instruction with the following atomic semantics: ``` // TAS executes as ONE indivisible hardware step. // No other core can observe or interleave with it. function TestAndSet(lock: pointer to boolean) -> boolean: old := lock // read lock := true // write return old // to the caller, both steps are atomic ``` Building a spinlock from TAS is now straightforward: a thread spins, repeatedly calling TAS, until it observes that the lock was free (old value `false`) at the moment it grabbed it. ``` // Lock word, shared, initialized to false (unlocked) shared lock: boolean := false procedure acquire(lock): while TestAndSet(lock) == true: // someone else already held it; spin and retry continue procedure release(lock): lock := false // plain store is fine; releaser owns the lock ``` The key insight is that `TestAndSet` returning `false` can happen for at most one thread among all concurrent callers, because the hardware serializes the RMW on that memory location: whichever thread's TAS instruction executes "first" (in the hardware's total order for that location) is the only one that can see the old value `false`; every other concurrent caller is guaranteed to see `true`, either the pre-existing `true` or the `true` just written by the winner.

Compare-And-Swap as a hardware primitive. CAS generalizes this idea to arbitrary values, not just booleans: ``` // CAS executes as ONE indivisible hardware step. function CompareAndSwap(location: pointer, expected: value, new: value) -> value: old := location if old == expected: location := new return old // Caller checks: "old == expected" tells you whether the swap happened. ``` A CAS-based spinlock looks almost identical to the TAS version, but now the lock word distinguishes "free" (0) from "held" (1) using an explicit compare: ``` shared lock: integer := 0 // 0 = free, 1 = held procedure acquire(lock): while CompareAndSwap(lock, 0, 1) != 0: // CAS failed: lock was already 1 (held) — retry continue procedure release(lock): lock := 0 ``` CAS is strictly more powerful than TAS because it lets a thread implement an optimistic retry loop: read the current value, compute a new value based on it, and only commit if nothing changed in between. This pattern underlies non-blocking stacks, queues, and counters: ``` // Lock-free increment of a shared counter, no lock needed at all procedure atomicIncrement(counter: pointer to integer): repeat: old := counter new := old + 1 until CompareAndSwap(counter, old, new) == old // if CAS failed, another thread updated counter first — retry with fresh 'old' ``` Note the failure mode: CAS can fail spuriously in the sense that some other thread's write slipped in between the read and the CAS, but it can never* fail silently in a way that loses an update — the loop simply retries with a fresh read. This retry-until-success pattern is the essence of lock-free programming.

Why release does not need to be atomic. In both designs, `release` is a plain store. This is safe because only the thread currently holding the lock is permitted to call `release`, so there is no concurrent writer to race against — the "atomic" part of the protocol is entirely about acquiring the lock, where multiple threads truly race. ```pseudocode // Generalized spinlock built on either primitive (RMW is the abstraction) procedure acquire(lock): while RMW(lock) indicates "already held": pause_or_backoff() // yield / exponential backoff, see below // invariant restored: this thread now holds the lock exclusively procedure release(lock): store(lock, FREE) // ordinary atomic store, no RMW needed ```

Time complexity. A single TAS or CAS instruction takes O(1) time — it is one hardware instruction, though its latency is higher than an ordinary load or store because it must acquire exclusive cache-line ownership across the coherence protocol (often tens of cycles under contention, versus a few cycles for a normal memory access). The `acquire` loop's running time is not O(1) in general: under contention, a thread may spin for an unbounded number of retries in the worst case if the scheduler is adversarial (e.g., other threads keep grabbing the lock first). In the uncontended case — no other thread wants the lock — `acquire` costs exactly one atomic instruction, O(1). Space overhead is O(1) per lock: a single word.

Correctness — mutual exclusion. The argument rests entirely on the hardware's atomicity guarantee, which we take as an axiom of the machine: for any single memory location, all RMW operations issued by different cores are totally ordered, and each one's read sees exactly the effect of all RMWs before it in that order, with no other operation interleaved inside it. Claim: at most one thread can be inside the critical section at any time. Proof sketch. Consider the sequence of TAS calls on `lock`, ordered by the hardware's serialization. The very first TAS call after `lock` was last `false` reads `false` and writes `true` — call this thread the winner; it proceeds into the critical section. Every other TAS call, until the winner calls `release` and sets `lock` back to `false`, must occur after the winner's TAS in the hardware's total order (because the winner's TAS already set the word to `true`, and by atomicity no call can "skip over" this write). Each of these later calls therefore reads `true` and loops. Hence exactly one thread can hold the lock between an `acquire` and its matching `release`, establishing mutual exclusion by induction on the sequence of acquire/release pairs. The identical argument applies to CAS, substituting "reads `expected` and writes `new`" for "reads `false` and writes `true`."

Progress. If no thread holds the lock (`lock == false`/`0`), some thread attempting `acquire` will succeed on its very next TAS/CAS call, because the RMW is unconditional — it does not depend on any other thread's future behavior. This satisfies the progress requirement: the decision of who enters next is made only among threads that are actually trying to enter, in bounded time (one instruction), not deferred indefinitely by a thread outside the critical section.

Bounded waiting — the honest tradeoff. Plain TAS/CAS spinlocks do not guarantee bounded waiting: with an adversarial scheduler, one thread could in principle keep re-losing races to other threads forever (spinlock starvation), since which of several simultaneously-spinning threads wins the next TAS is unspecified by the hardware — it depends on arbitration order in the coherence protocol, which is not required to be fair. This is fixed at a higher layer: a ticket lock (built from fetch-and-add) or an MCS/CLH queue lock (built from CAS) adds explicit FIFO ordering on top of the same atomic primitives, restoring bounded waiting. This is the natural next construction on the road to full Locks and Mutual Exclusion.

Why software alone cannot do this. Peterson's algorithm relies on the compiler and CPU preserving program order for ordinary loads/stores, and on writes becoming visible to other cores promptly and in order. Modern CPUs reorder instructions and buffer writes in per-core caches for performance; enforcing the necessary ordering purely in software would require the compiler and hardware to insert full memory fences around every shared access, which is exactly as expensive as — and strictly less general than — just providing atomic RMW instructions directly. Hardware support is not a convenience; it is the only way to get a genuine indivisibility guarantee at reasonable cost.

Trace three threads, T1, T2, T3, contending for a CAS-based lock (`lock` starts at 0 = free), with instructions interleaved by the hardware's arbitration in the order shown.

Two things this trace makes concrete. First, at every step at most one thread ever holds the lock — mutual exclusion visibly holds because every failed CAS reads exactly the value the current holder wrote. Second, T2 is repeatedly overtaken by T3 at step 5 purely because of arbitration order, not because of anything T2 did wrong — this is the concrete manifestation of the bounded-waiting gap discussed above. A ticket lock would prevent step 5 from happening out of arrival order by handing out sequence numbers atomically with fetch-and-add and only letting the thread whose ticket matches a "now serving" counter proceed.

Every operating system kernel uses spinlocks built on TAS or CAS to protect short, performance-critical data structures such as scheduler run queues, interrupt-handling state, and page tables, precisely because these sections are too short to justify the overhead of a full blocking lock. User-space threading libraries (pthreads mutexes, Java's `synchronized`, Go's `sync.Mutex`) implement their "fast path" — the uncontended, common case — with a single CAS instruction, only falling back to the operating system's blocking mechanism (futex on Linux) when contention is detected. Lock-free and wait-free data structures — concurrent queues, stacks, hash tables used in high-throughput databases and in-memory caches — are built almost entirely on CAS loops of the pattern shown above, because they avoid the possibility of one thread blocking all others even during a scheduler preemption. Garbage collectors in managed runtimes (JVM, Go runtime) use CAS to implement lock-free allocation paths and to coordinate concurrent marking. Modern instruction sets also provide load-linked/store-conditional (LL/SC) as an alternative to CAS on ARM and RISC-V, avoiding the ABA problem inherent to plain CAS, but the underlying design principle — an atomic hardware read-modify-write as the indivisible unit of synchronization — is identical, and it is the bedrock on which the entire discipline of Locks and Mutual Exclusion and concurrent programming is built.

Ask the tutor: How would you build a fair ticket lock using fetch-and-add, and why does it guarantee bounded waiting where a plain CAS spinlock does not?