How Do Atomic Primitives Enable Lock-Free Synchronization?

Atomic hardware primitives such as compare-and-swap and load-link/store-conditional allow multiple processor cores to update shared memory safely without acquiring mutual exclusion locks. By executing a read-modify-write sequence as a single indivisible hardware operation, these instructions let threads detect concurrent modifications and retry when interference occurs. This mechanism forms the foundation of lock-free data structures that guarantee system-wide progress even if individual threads are delayed or preempted.

The Limits of Traditional Locking

In multithreaded classical computing, traditional synchronization relies on locks such as mutexes or spinlocks to protect critical sections. While locks are straightforward to reason about, they introduce several performance and reliability hazards:

  • Deadlock: Two or more threads wait indefinitely for locks held by each other.
  • Priority inversion: A low-priority thread holding a lock is preempted, stalling high-priority threads that need the same lock.
  • Convoying and contention: When a thread holding a lock is descheduled by the operating system, all other threads waiting on that lock stall.

Lock-free synchronization eliminates these failure modes by removing mutual exclusion. Instead of blocking, threads operate optimistically: they read shared state, compute a new state locally, and attempt to commit the change atomically. A synchronization algorithm is lock-free if, at any point in execution, at least one thread is guaranteed to make progress within a finite number of steps.

Compare-and-Swap (CAS)

Compare-and-swap is the most common atomic primitive in modern x86 and ARM architectures (for example, LOCK CMPXCHG on x86). A CAS instruction takes three operands: a memory address \(A\), an expected value \(E\), and a new value \(N\).

Hardware executes the following logic atomically:

  1. Read the current value \(V\) stored at address \(A\).
  2. If \(V = E\), write \(N\) to address \(A\) and return true (or the old value).
  3. If \(V \neq E\), leave \(A\) unchanged and return false.

Because the CPU guarantees that no other core can modify \(A\) between the read and the write, a thread can build a lock-free update using a retry loop:

do {
    old_val = *addr;
    new_val = compute(old_val);
} while (!CAS(addr, old_val, new_val));

If another thread modifies *addr while compute(old_val) is running, CAS fails, and the thread simply reads the updated value and tries again.

The ABA Problem

CAS only checks whether the current value equals the expected value; it cannot detect whether the memory location was modified and then restored to its original value. If Thread 1 reads value \(A\), gets preempted, and Thread 2 changes the value from \(A\) to \(B\) and back to \(A\), Thread 1's subsequent CAS will succeed even though the underlying state changed. In pointer-based structures like lock-free stacks, this can corrupt memory. Developers mitigate the ABA problem by pairing pointers with version counters (double-width CAS) or using memory reclamation schemes such as hazard pointers.

Load-Link / Store-Conditional (LL/SC)

Load-link and store-conditional are a pair of instructions used in architectures such as ARM, RISC-V, and PowerPC. Instead of comparing values, LL/SC tracks whether a memory location has been accessed by another core between two instructions:

  • Load-Link (LL): Reads the value at address \(A\) and sets a hardware reservation (typically on the cache line containing \(A\)) for the executing core.
  • Store-Conditional (SC): Attempts to write a new value \(N\) to address \(A\). The write succeeds only if the core's reservation is still valid—meaning no other core has written to that cache line since the LL instruction—and returns a status indicating success or failure.

A lock-free update with LL/SC follows a similar retry pattern:

do {
    old_val = LL(addr);
    new_val = compute(old_val);
} while (!SC(addr, new_val));

Because SC checks for any intervening write rather than comparing values, LL/SC naturally avoids the ABA problem. If another core writes \(B\) and then \(A\) back to the address, the reservation is cleared, and SC fails.

Hardware Implementation

At the microarchitectural level, atomic primitives rely on the CPU's cache coherence protocol (such as MESI or MOESI). When a core executes CAS or LL, it requests exclusive ownership of the target cache line. Other cores' copies of that cache line are invalidated.

For CAS, the core holds the cache line exclusively for the brief duration of the read-compare-write operation, delaying incoming coherence requests from other cores until the atomic instruction completes. For LL/SC, the core monitors coherence traffic (snooping) for invalidations to the reserved cache line; any external write invalidates the reservation, causing the subsequent SC to fail.

Practical Applications

Together, CAS and LL/SC serve as the building blocks for high-performance concurrent systems:

  • Lock-free counters and flags: Simple atomic increments and bitmask updates without mutex overhead.
  • Lock-free stacks and queues: Algorithms like Treiber's stack and the Michael-Scott queue use CAS on head and tail pointers to allow concurrent pushes and pops.
  • Operating system kernels: Schedulers, reference counting, and read-copy-update (RCU) mechanisms rely on atomic primitives to coordinate across cores with minimal latency.