Atomic Operations and Lock-Free Fundamentals

An atomic operation is a single step that no other thread can interrupt or observe half-done — like a turnstile that counts each person exactly once, however big the crowd.

Learning Objectives

Use atomic types, loads, stores, read-modify-write operations, fetch-add, exchange and compare-and-swap (weak and strong).

Write correct spin loops; choose memory orders (relaxed, acquire, release, acq_rel, seq_cst) and fences; reason with happens-before and synchronizes-with.

Publish data safely; distinguish lock-free, wait-free and obstruction-free; understand ABA, tagged pointers, false sharing and cache-line contention.

Know when mutexes are preferable, how to test lock-free code, and why to avoid premature lock-free programming.

Plain-Language Explanation

An atomic operation is a single step that no other thread can interrupt or observe half-done — like a turnstile that counts each person exactly once, however big the crowd. Atomics let threads coordinate without locks for simple things: counters, flags, pointers. But they come with a subtle second job: deciding what *other* memory writes become visible along with them. That is what memory orders control, and it is where most atomic code goes wrong.

Precise Technical Explanation

_Atomic T/atomic_int (C11), std::atomic<T> (C++11), AtomicInteger/AtomicReference/VarHandle (Java), Interlocked/Volatile (C#), sync/atomic (Go), AtomicUsize etc. (Rust), Atomics on SharedArrayBuffer (JavaScript). Lock-free for sizes the hardware supports (is_lock_free()); larger types may use hidden locks.

Atomic loads and stores An atomic load sees a complete value written by some store; an atomic store is never torn. Neither alone makes a read-modify-write safe.

Operations that read, modify and write as one indivisible step: fetch_add, fetch_sub, fetch_or, exchange, compare_exchange. On x86 they compile to lock-prefixed instructions; on Arm to LL/SC loops or LSE atomics.

Fetch-add and exchange fetch_add(n) adds and returns the *old* value — the basis of counters and ticket allocation. exchange(v) stores v and returns the old value — the basis of test-and-set spinlocks and "take ownership" hand-offs.

Compare-and-swap (CAS) compare_exchange(expected, desired): if the current value equals expected, replace it with desired and return true; otherwise copy the current value into expected and return false. Any atomic update x = f(x) can be built as a CAS loop.

Weak versus strong CAS compare_exchange_weak may fail *spuriously* (even when the value matched) on LL/SC architectures; it is cheaper and belongs in loops. compare_exchange_strong fails only on a real mismatch; use it when not looping.

Loops that repeatedly test an atomic. Good spin loops: test with a plain load before attempting an expensive RMW ("test-and-test-and-set"), use a pause/yield hint (_mm_pause, std::this_thread::yield), back off, and eventually block (C++20 atomic::wait/notify, futexes).

Every atomic operation takes a memory order that constrains how *other* memory operations around it may be reordered and when they become visible to other threads (Module 7 explains the full model).

memory_order_relaxed: atomicity and a single modification order per variable, nothing else. Correct for independent counters and statistics; wrong for flags that publish data.

Acquire and release A release store (or RMW) makes all earlier writes of the thread visible to any thread whose acquire load reads that store's value. The canonical message-passing pattern: write data; store ready = true (release). Reader: load ready (acquire); if true, read data — guaranteed complete.

memory_order_acq_rel for read-modify-write operations that both consume and publish (e.g. a lock-free queue's index update).

memory_order_seq_cst (the default): acquire/release plus one global total order of all seq_cst operations that every thread agrees on. Simplest to reason about; on x86 only seq_cst stores are more expensive; on Arm more operations need barriers.

std::atomic_thread_fence(order) orders memory operations without being attached to a specific atomic variable; used with relaxed atomics to build acquire/release patterns across several variables. atomic_signal_fence constrains only the compiler (for signal handlers).

If A happens-before B, B sees A's effects. Within one thread, program order gives happens-before; across threads it comes from synchronization (release → acquire, unlock → lock, thread start/join).

A release operation synchronizes-with an acquire operation that reads the value it wrote (or a later value in its release sequence). Synchronizes-with edges are how happens-before crosses threads.

Publication and visibility Publishing an object means making it reachable by other threads *and* making its construction visible to them. Publishing through a relaxed store (or a plain variable) can expose a half-constructed object. Publish through a release store, a lock, a thread-safe queue, or immutable final fields.

Lock-free versus wait-free versus obstruction-free Obstruction-free: a thread makes progress if it runs alone for long enough.

Lock-free: some thread always makes progress (CAS loops: one CAS always wins).

Wait-free: every thread completes in a bounded number of its own steps (fetch_add on hardware that implements it directly).

Lock-free does not mean fast, fair or simple — just that a suspended thread cannot block everyone.

A CAS checks that a value is *equal* to what was read, not that it is *unchanged*. If another thread changes A → B → A in between, the CAS succeeds wrongly — e.g. a lock-free stack pops node A, which was freed and reused for a new node with the same address (demonstrated below).

Tagged pointers and version counters Pair the pointer with a counter that increments on every update and CAS both together (double-width CAS, or tag bits in unused pointer bits). A→B→A then differs in its tag. Safe memory reclamation (hazard pointers, epochs — Module 19) addresses the reuse problem directly.

Independent atomics in the same cache line make cores fight over the line (Memory course, Module 13). Pad or align hot atomics to 64 bytes (alignas(std::hardware_destructive_interference_size)).

Even a single atomic updated by many cores serialises them: every RMW needs exclusive ownership of the line. Measured below — a shared atomic counter can be slower than per-thread counters by an order of magnitude.

Atomic performance caveats Atomic RMW instructions cost ~20–100 cycles even uncontended on some CPUs, and much more under contention; seq_cst stores on x86 need a full barrier (xchg/mfence). Lock-free algorithms often execute more atomics than a well-designed lock-based one.

When mutexes are preferable When the critical section touches several variables or must maintain an invariant across them; when operations are long; when correctness matters more than nanoseconds (almost always). A mutex is one atomic acquire and one release.

Testing lock-free algorithms Stress tests on many cores and on weakly ordered hardware (Arm); ThreadSanitizer; model checkers that explore interleavings and memory-model behaviors (CDSChecker, GenMC, Rust's loom, Java's JCStress); formal proofs for anything important.

Avoiding premature lock-free programming Use the standard library's concurrent containers and well-tested libraries. Custom lock-free code without proofs, reclamation and weak-memory testing is a source of rare, catastrophic bugs.

Why It Matters in Real Systems

Atomics are the foundation of every lock, reference count (shared_ptr, Arc), concurrent queue, metrics counter and lock-free cache. Misused memory orders produce bugs that appear only on Arm phones or new servers.

Key Terms

Visibility/ordering guarantee of an atomic operation Acquire / release Consume / publish prior writes

Release → acquire edge reading the released value Lock-free / wait-free

System-wide / per-thread progress guarantee Value changed and changed back between read and CAS Independent data on one cache line

Syntax and API Overview

The specification's relaxed counter (G++ 11.2):

Relaxed ordering is sufficient for this counter's numeric correctness: every fetch_add is indivisible and all increments land in one modification order. It does not publish or order *unrelated* data — and the final read is safe only because the join() calls synchronize with the threads' completion.

#include <atomic>
#include <iostream>
#include <thread>

std::atomic<int> count{0};

void increment() {
    for (int i = 0; i < 10000; ++i) {
        count.fetch_add(1, std::memory_order_relaxed);
    }
}

int main() {
    std::thread a(increment);
    std::thread b(increment);
    a.join();
    b.join();
    std::cout << count.load() << '\n'; // 20000
}

Complete Code Example

CAS loops, acquire/release publication, a spinlock, and a deterministic ABA demonstration (G++ 11.2):

#include <atomic>
#include <cstdint>
#include <iostream>
#include <string>
#include <thread>
#include <vector>

// 1. CAS loop: atomic maximum
void atomic_max(std::atomic<int>& target, int value) {
    int current = target.load(std::memory_order_relaxed);
    while (current < value &&
           !target.compare_exchange_weak(current, value, std::memory_order_relaxed)) {
        // on failure 'current' was refreshed with the latest value; loop re-checks
    }
}

// 2. publication with release/acquire
struct Config { std::string name; int retries; };
Config* shared_config = nullptr;              // plain data, published below
std::atomic<bool> ready{false};

// 3. test-and-test-and-set spinlock (educational)
class SpinLock {
    std::atomic<bool> locked{false};
public:
    void lock() {
        for (;;) {
            if (!locked.exchange(true, std::memory_order_acquire)) return;   // got it
            while (locked.load(std::memory_order_relaxed)) std::this_thread::yield();
        }
    }
    void unlock() { locked.store(false, std::memory_order_release); }
};

int main() {
    std::atomic<int> best{0};
    {
        std::vector<std::jthread> ts;
        for (int v : {17, 4, 99, 23
…

atomic max of {17,4,99,23,98,56}: 99
reader sees config 'payments' with 3 retries
spinlock-protected total: 400000
plain CAS after A->B->A: succeeded (ABA: the change went unnoticed)
tagged CAS after A->B->A: failed (tag 0 != 2: change detected)
16-byte tagged atomic is lock-free here: false

Line-by-Line Explanation

atomic_max: load, compare, and try to CAS in the new value; a failed CAS updates current, so the loop re-checks whether value is still larger. Lock-free: some thread's CAS always succeeds.

Publication: the writer initialises Config *then* release-stores ready; the reader's acquire load that sees true synchronizes-with that store, so the plain fields are fully visible. With relaxed orders the reader could see ready == true and a half-initialised object (on weakly ordered hardware or after compiler reordering).

The spinlock's exchange(true, acquire) takes the lock; while it is taken, waiters spin on a cheap relaxed load (no cache-line ping-pong from repeated RMWs); unlock is a release store, publishing the protected writes.

ABA: the plain pointer CAS cannot tell that top changed twice; the version tag can.

The last line reports whether a 16-byte atomic is lock-free on this platform: GCC typically answers false because it implements 16-byte atomics through libatomic rather than inline cmpxchg16b — a real-world caveat for tagged pointers.

Output

Shown above; it is deterministic (the concurrent parts are summarised after joins).

Interleaving or State Trace

Publication (one valid execution):

new Config{...} (plain writes) ready.load(acquire) → false, yield ready.store(true, release) ready.load(acquire) → true store synchronizes-with load reads shared_config->name sees "payments" (happens-after initialisation)

Correctness and Safety Analysis

Each atomic's role is explicit: best — RMW with relaxed order (only the final value matters, read after joins); ready — release/acquire publication; locked — acquire on lock, release on unlock (a mutex's semantics). total is a plain variable protected by the spinlock. The ABA section shows why CAS-based structures need versioning or safe reclamation.

Common Mistakes and Misconceptions

Using relaxed stores/loads for a "ready" flag that guards other data.

"Atomic variable = thread-safe class": two atomic operations in a row are not atomic together.

compare_exchange_weak outside a loop.

Spinning with RMWs (exchange in a tight loop) instead of test-and-test-and-set.

Hand-writing lock-free containers for production.

Failure Modes and Debugging Steps

Torn/half-initialised data on Arm but not x86: missing release/acquire.

Livelocks or very high CPU in spin loops: add back-off or block.

Crashes in lock-free structures under load: ABA or use-after-free — use tags plus safe reclamation; test with TSan, model checkers and Arm hardware.

Contention measured — one shared atomic counter versus per-thread counters summed at the end (G++ 11.2 -O1, 4 threads, one real run on the build machine):

Both totals are correct; the shared atomic forces every increment to own the same cache line in turn, while per-thread padded counters run independently (the compiler may even fold each local loop into a single addition — part of the point: unshared data can be optimised freely).

#include <atomic>
#include <chrono>
#include <iostream>
#include <thread>
#include <vector>

int main() {
    constexpr int threads = 4, per = 5'000'000;
    auto time = [](auto&& fn) {
        auto t0 = std::chrono::steady_clock::now(); fn();
        return std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t0).count();
    };
    std::atomic<long> shared{0};
    double t_shared = time([&] {
        std::vector<std::jthread> ts;
        for (int t = 0; t < threads; ++t) ts.emplace_back([&] { for (int i = 0; i < per; ++i) shared.fetch_add(1, std::memory_order_relaxed); });
    });
    struct alignas(64) Padded { long v = 0; };
    std::vector<Padded> local(threads);
    double t_local = time([&] {
        std::vector<std::jthread> ts;
        for (int t = 0; t < threads; ++t) ts.emplace_back([&, t] { for (int i = 0; i < per; ++i) local[t].v += 1; });
    });
    long sum = 0;
    for (auto& p : local) sum += p.v;
    std::cout << "shared atomic counter : " << shared << " in " << t_shared << " ms\n";
    std::cout << "per-thread counters   : " << sum << " in " << t_local << " ms\n";
}

shared atomic counter : 20000000 in 351.025 ms
per-thread counters   : 20000000 in 7.9639 ms

Performance and Scalability Implications

Atomics avoid blocking but not contention. Scalable designs reduce sharing (per-thread or per-CPU counters, LongAdder in Java, sharded counters) and use the weakest correct memory order only after proving it.

Security Considerations

Reference-count races (missing atomic decrement or wrong ordering) lead to use-after-free — a classic exploit primitive. Use library smart pointers (shared_ptr, Arc) rather than hand-rolled counts.

Platform and Runtime Caveats

x86 is strongly ordered (TSO), so some missing-ordering bugs never show there but do on Arm/POWER/RISC-V.

Java volatile fields and AtomicXxx give sequentially consistent semantics by default; VarHandle offers weaker modes. C# Volatile.Read/Write are acquire/release; Interlocked operations are full fences.

16-byte CAS (cmpxchg16b) is not used inline by every compiler/library (as the output shows for GCC).

Go sync/atomic operations are sequentially consistent (documented since Go 1.19's memory model update).

Real-World Applications

Reference counting, metrics counters, sequence/ticket numbers, lock implementations, work-stealing deques, RCU pointer swaps, configuration hot reload via atomic pointer exchange.

Best Practices

Default to seq_cst (or locks); weaken orders only with a written justification.

Pair every release with the acquire that consumes it, and document the pair.

Use CAS loops with compare_exchange_weak; strong outside loops.

Pad hot atomics; prefer per-thread accumulation.

Use proven libraries for lock-free containers; test on weak-memory hardware.

Exercises

E1 · Beginner. What does fetch_add(1) return, and why is that useful for allocating unique IDs?

Answer: The value before the addition. Each caller receives a distinct old value, so id = counter.fetch_add(1) hands out unique IDs without a lock.

E2 · Intermediate. In the publication example, what can go wrong if the writer uses memory_order_relaxed for the store of ready?

Answer: The store of ready may become visible before the writes that initialise Config (compiler or CPU reordering), so the reader can see ready == true and read uninitialised fields — a data race on shared_config's pointee, i.e. undefined behavior.

E3 · Advanced challenge. Implement fetch_multiply for std::atomic<int> using CAS and state its progress guarantee.

Answer: int old = a.load(); while (!a.compare_exchange_weak(old, old * k)) {} return old; — lock-free (some thread always succeeds) but not wait-free (one thread can retry indefinitely under contention).

Quiz

? Why is memory_order_relaxed enough for a statistics counter read after join()?
+ Each fetch_add is atomic, and join() synchronizes the final read with the threads' completion. :: No other data is published through the counter.
- Relaxed operations are sequentially consistent on all CPUs. :: They are not.
- The counter does not need to be atomic. :: Plain increments would race.
- join() makes all memory relaxed. :: join creates happens-before.

? What does compare_exchange_weak do differently from compare_exchange_strong?
+ It may fail spuriously even when the value matches, so it belongs in a loop. :: Cheaper on LL/SC architectures.
- It ignores memory ordering. :: Both take memory orders.
- It never updates the expected value. :: Both update expected on failure.
- It only works on booleans. :: It works on any atomic type.

? Which statements are true? (select all that apply)
+ A lock-free algorithm guarantees that some thread always makes progress. :: Definition of lock-freedom.
- Lock-free code is always faster than locks. :: Often not, especially under contention.
+ A version tag paired with a pointer defends a CAS against ABA. :: A->B->A changes the tag.
- Two consecutive ato
…

Summary

Atomics provide indivisible loads, stores and read-modify-writes, including CAS — the building block of lock-free code. Memory orders decide what *other* writes become visible: relaxed for independent counters, release/acquire for publication, seq_cst as the safe default. ABA, contention, false sharing and reclamation make lock-free programming hard; prefer mutexes and proven libraries unless measurements and proofs justify otherwise.