Atomic Operations and Lock-Free Programming

This section covers std::atomic<T>``std::atomic_ref<T>The full set of atomic operations, std::atomic_flagThe lock-free/wait-free/obstruction-free progress guarantees, the ABA problem, a Lock-free stack implementation, and a spinlock using std::atomic_flag.

`std::atomic<T>`

std::atomic<T> [N4950 §31.7] is a template class that provides atomic access to a value of type T. All operations on std::atomic are atomic: they are indivisible from the perspective of all Threads.

The standard specifies which types T may be [N4950 §31.7.1]:

Scalar types: bool``char``int``float``pointer typesEtc.
** copyable types**: Any copyable type (C++17 and later), though not all operations may be available.

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

int main() {
    std::atomic<int> counter{0};
    constexpr int num_threads = 10;
    constexpr int iterations = 100"000;

    std::vector<std::jthread> threads;
    for (int i = 0; i < num_threads; ++i) {
        threads.emplace_back([&counter, iterations] {
            for (int j = 0; j < iterations; ++j) {
                counter.fetch_add(1, std::memory_order_relaxed);
            }
        });
    }

    std::cout << "Counter: " << counter.load() << "\n";
    std::cout << "Expected: " << num_threads * iterations << "\n";
    return 0;
}

`std::atomic_ref<T>` (C++20)

std::atomic_ref<T> provides atomic access to a non-atomic object through a reference wrapper. This Is useful when you need atomic operations on data that was not declared as std::atomic:

#include <atomic>
#include <iostream>

int main() {
    int value = 0;
    std::atomic_ref<int> ref(value);

    ref.store(42, std::memory_order_relaxed);
    std::cout << "value = " << value << "\n";

    int old = ref.exchange(99, std::memory_order_relaxed);
    std::cout << "old = " << old << ", value = " << value << "\n";
    return 0;
}

## Atomic Operations

The full set of atomic operations defined in [N4950 §31.7.2]:

Operation	Description
`load(order)`	Atomically reads the current value
`store(val, order)`	Atomically writes a value
`exchange(val, order)`	Atomically replaces the value and returns the old value
`compare_exchange_weak(expected, desired, success_order, failure_order)`	CAS with possible spurious failure
`compare_exchange_strong(expected, desired, success_order, failure_order)`	CAS without spurious failure
`fetch_add(val, order)`	Atomically adds and returns the old value
`fetch_sub(val, order)`	Atomically subtracts and returns the old value
`fetch_and(val, order)`	Atomically performs bitwise AND and returns old value
`fetch_or(val, order)`	Atomically performs bitwise OR and returns old value
`fetch_xor(val, order)`	Atomically performs bitwise XOR and returns old value

`std::atomic_flag`

std::atomic_flag [N4950 §31.7] is the simplest atomic type: a boolean flag guaranteed to be Lock-free. It provides only two operations:

test_and_set(order): Atomically sets the flag to true and returns the previous value.
clear(order): Atomically sets the flag to false.

Lock-Free vs Wait-Free vs Obstruction-Free

Guarantee	Definition	Blocking?
Obstruction-free	Progress guaranteed if all other threads are paused	No (if alone)
Lock-free	At least one thread makes progress within a bounded number of steps	No (system-wide)
Wait-free	Every thread makes progress within a bounded number of steps	No (per-thread)

These form a hierarchy: wait-free $\implies$ lock-free $\implies$ obstruction-free.

You can query the progress guarantee using std::atomic<T>::is_always_lock_free (compile-time) [N4950 §31.7.7] and a.is_lock_free() (runtime) [N4950 §31.7.2]:

#include <iostream>
#include <atomic>

int main() {
    std::cout << "atomic<int> lock-free: "
              << std::atomic<int>::is_always_lock_free << "\n";
    std::cout << "atomic<bool> lock-free: "
              << std::atomic<bool>::is_always_lock_free << "\n";

    std::atomic<long long> big_atomic;
    std::cout << "atomic<long long> lock-free (runtime): "
              << big_atomic.is_lock_free() << "\n";
    return 0;
}

ABA Problem and CAS

The ABA problem occurs in lock-free algorithms when a value changes from $A$ to $B$ and back to $A$ between a thread’s load and its CAS. The CAS succeeds because the value is still $A$ But the Intermediate change may have invalidated invariants:

$\mathrm{Load(A) \to \mathrm{Other thread: A \to B \to A \to \mathrm{CAS(A, C) \mathrm{ succeeds — incorrectly$

compare_exchange_weak may fail spuriously (return false even when the expected value matches), Which can help in some ABA scenarios but does not fully solve the problem. Full solutions include:

Tagged pointers: Append a monotonically increasing counter to the value.
Hazard pointers: Track which objects are currently being accessed.
Epoch-based reclamation: Defer reclamation to epoch boundaries.

Lock-Free Stack with `compare_exchange_weak`

#include <iostream>
#include <atomic>
#include <memory>

template <typename T>
class lock_free_stack {
    struct node {
        T data;
        node* next;
        explicit node(T val) : data(std::move(val)), next(nullptr) {}
    };

    std::atomic<node*> head_{nullptr};

public:
    void push(T value) {
        node* new_node = new node(std::move(value));
        new_node->next = head_.load(std::memory_order_relaxed);

        while (!head_.compare_exchange_weak(
            new_node->next,
            new_node,
            std::memory_order_release,
            std::memory_order_relaxed
        )) {
            // new_node->next is updated to the current head on failure
        }
    }

    bool pop(T& result) {
        node* old_head = head_.load(std::memory_order_acquire);
        while (old_head) {
            node* next = old_head->next;
            if (head_.compare_exchange_weak(
                old_head,
                next,
                std::memory_order_acquire,
                std::memory_order_acquire
            )) {
                result = std::move(old_head->data);
                delete old_head;
                return true;
            }
        }
        return false;
    }

    ~lock_free_stack() {
        node* current = head_.load(std::memory_order_relaxed);
        while (current) {
            node* next = current->next;
            delete current;
            current = next;
        }
    }
};

int main() {
    lock_free_stack<int> stack;

    for (int i = 0; i < 100; ++i) {
        stack.push(i);
    }

    int value;
    int count = 0;
    while (stack.pop(value)) {
        ++count;
    }

    std::cout << "Popped " << count << " elements\n";
    return 0;
}

## Spinlock Using `std::atomic_flag`

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

class spinlock {
    std::atomic_flag flag_ = ATOMIC_FLAG_INIT;

public:
    void lock() {
        while (flag_.test_and_set(std::memory_order_acquire)) {
            // spin: yield the CPU to reduce contention
            std::this_thread::yield();
        }
    }

    void unlock() {
        flag_.clear(std::memory_order_release);
    }
};

int main() {
    spinlock mtx;
    int counter = 0;
    constexpr int num_threads = 8;
    constexpr int iterations = 100'000;

    std::vector<std::jthread> threads;
    for (int i = 0; i < num_threads; ++i) {
        threads.emplace_back([&mtx, &counter, iterations] {
            for (int j = 0; j < iterations; ++j) {
                mtx.lock();
                ++counter;
                mtx.unlock();
            }
        });
    }

    std::cout << "Counter: " << counter << "\n";
    std::cout << "Expected: " << num_threads * iterations << "\n";
    return 0;
}

## See Also

Memory Order Arguments and Their Semantics

Every atomic operation accepts a std::memory_order argument that constrains how the compiler and CPU may reorder operations around it [N4950 §31.7.2]. The six memory orders form a hierarchy of Strength:

Memory Order	Compiler Reordering	CPU Reordering	Use Case
`memory_order_relaxed`	No reorder with	No reorder	Simple counters, statistics
`memory_order_consume`	atomic ops	on atomics	Data-dependent ordering
`memory_order_acquire`			Guard reads of shared data
`memory_order_release`			Publish writes to shared data
`memory_order_acq_rel`			Read-modify-write with ordering
`memory_order_seq_cst`			Default; total order

#include <atomic>
#include <iostream>

void memory_order_overview() {
    std::atomic<int> x{0};
    std::atomic<int> y{0};

    // Relaxed: no ordering guarantees beyond atomicity
    x.store(1, std::memory_order_relaxed);

    // Release: all prior writes (non-atomic and atomic) are visible
    // to threads that acquire this atomic
    x.store(1, std::memory_order_release);

    // Acquire: all subsequent reads see writes from the releasing thread
    int v = x.load(std::memory_order_acquire);

    // Acquire-release (for RMW operations): combines acquire and release
    x.fetch_add(1, std::memory_order_acq_rel);

    // Sequentially consistent: total order across all seq_cst operations
    x.store(1, std::memory_order_seq_cst);  // default for store
    int v2 = x.load(std::memory_order_seq_cst);  // default for load
}

## `compare_exchange` in Detail

The CAS operation is the foundation of most lock-free algorithms. compare_exchange_weak and compare_exchange_strong differ in one key aspect [N4950 §31.7.2]:

compare_exchange_strong: Fails only if the current value does not equal expected.
compare_exchange_weak: May fail spuriously — returns false even when the value equals expected. This allows the implementation to use LL/SC (Load-Linked/Store-Conditional) instructions on architectures that support them (e.g., ARM, PowerPC).

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

void cas_strong_vs_weak() {
    std::atomic<int> counter{0};
    constexpr int iterations = 100'000;

    auto worker_strong = [&] {
        for (int i = 0; i < iterations; ++i) {
            int expected = counter.load(std::memory_order_relaxed);
            while (!counter.compare_exchange_strong(
                expected,
                expected + 1,
                std::memory_order_relaxed,
                std::memory_order_relaxed)) {
                // expected is automatically updated to the current value on failure
            }
        }
    };

    auto worker_weak = [&] {
        for (int i = 0; i < iterations; ++i) {
            int expected = counter.load(std::memory_order_relaxed);
            while (!counter.compare_exchange_weak(
                expected,
                expected + 1,
                std::memory_order_relaxed,
                std::memory_order_relaxed)) {
                // May retry even if expected == counter (spurious failure)
                // But expected is still updated on real failures
            }
        }
    };

    // Both produce the same result; weak may loop more iterations
    // but can be more efficient on LL/SC architectures
}

The success and failure memory orders can differ. This is a critical optimization: on CAS Failure, you do not need acquire semantics (no data was published), so you can use a weaker order:

// Optimal pattern: acquire on success, relaxed on failure
if (ptr.compare_exchange_weak(
        expected,
        desired,
        std::memory_order_acquire,    // success: need to see published data
        std::memory_order_relaxed))   // failure: no data to observe
{
    // Successfully replaced expected with desired
    // Acquire ensures we see all writes from the thread that released
}

`std::atomic_wait` and `std::atomic_notify` (C++20)

C++20 introduced wait()``notify_one()And notify_all() on std::atomic objects [N4950 §31.7.2]. These provide an efficient waiting mechanism that does not spin — the OS puts the thread To sleep until notification arrives:

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

void atomic_wait_notify_demo() {
    std::atomic<int> ready{0};

    std::jthread producer([&] {
        std::cout << "Producer: doing work...\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(200));
        ready.store(1, std::memory_order_release);
        ready.notify_one();  // Wake one waiting thread
    });

    std::jthread consumer([&] {
        int expected = 0;
        // Wait until ready != expected
        ready.wait(expected, std::memory_order_acquire);
        // After wake: ready.load(acquire) != 0, and all writes before the
        // producer's release store are visible
        std::cout << "Consumer: ready = " << ready.load() << "\n";
    });
}

## `std::atomic<void*>` and Pointer Atomics

std::atomic<T*> supports pointer arithmetic with fetch_add and fetch_subIncrementing or Decrementing the pointer by n * sizeof(T) [N4950 §31.7.2]:

#include <atomic>
#include <cstddef>
#include <iostream>

void pointer_atomic_demo() {
    int buffer[10] = {};
    std::atomic<int*> ptr{buffer};

    // Advance pointer by 3 elements
    int* old = ptr.fetch_add(3, std::memory_order_relaxed);
    std::cout << "Old: " << (old - buffer) << ", New: " << (ptr.load() - buffer) << "\n";
    // Old: 0, New: 3

    // Retreat by 1
    ptr.fetch_sub(1, std::memory_order_relaxed);
    std::cout << "After sub: " << (ptr.load() - buffer) << "\n";
    // After sub: 2
}

`std::atomic<bool>` as a Flag

std::atomic<bool> is the general-purpose atomic boolean. Unlike std::atomic_flagIt may Use a lock internally if the platform cannot implement it lock-free:

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

void atomic_bool_flag_demo() {
    std::atomic<bool> initialized{false};

    std::jthread initializer([&] {
        // Expensive initialization
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        initialized.store(true, std::memory_order_release);
    });

    // Spin-wait (for demo; prefer atomic_wait in production)
    while (!initialized.load(std::memory_order_acquire)) {
        std::this_thread::yield();
    }
    std::cout << "Initialized!\n";
}

## `std::atomic<shared_ptr>` and `std::atomic<weak_ptr>` (C++20)

C++20 provides atomic specializations for std::shared_ptr and std::weak_ptr [N4950 §31.7.1]. These are not lock-free — they use an internal mutex. They exist because reference counting Operations on shared_ptr are not atomic, and a data race on the control block is UB:

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

void shared_ptr_atomic_demo() {
    std::shared_ptr<int> global_ptr = std::make_shared<int>(42);

    std::vector<std::jthread> threads;

    for (int i = 0; i < 4; ++i) {
        threads.emplace_back([&] {
            // Read the shared_ptr atomically
            std::shared_ptr<int> local = std::atomic_load(&global_ptr);
            std::cout << "Thread sees: " << *local << "\n";

            // Update atomically
            auto new_ptr = std::make_shared<int>(*local + 1);
            std::atomic_store(&global_ptr, new_ptr);
        });
    }
}

## Tagged Pointers for ABA Prevention

A practical approach to solving the ABA problem is to use a tagged pointer — combine the pointer With a monotonically increasing counter in a single 64-bit atomic:

#include <atomic>
#include <cstdint>
#include <iostream>
#include <new>

struct tagged_ptr {
    std::uintptr_t ptr : 48;
    std::uintptr_t tag : 16;
};

static_assert(sizeof(tagged_ptr) == sizeof(std::uintptr_t),
    "tagged_ptr must fit in a single machine word");

class tagged_stack {
    struct node {
        int data;
        node* next;
        explicit node(int v) : data(v), next(nullptr) {}
    };

    // Pack pointer and tag into a single 64-bit atomic
    std::atomic<std::uintptr_t> head_{0};

    static constexpr std::uintptr_t TAG_MASK = 0xFFFF'0000'0000'0000ULL;
    static constexpr std::uintptr_t PTR_MASK = 0x0000'FFFF'FFFF'FFFFULL;
    static constexpr std::uintptr_t TAG_INC  = 0x0001'0000'0000'0000ULL;

    static tagged_ptr unpack(std::uintptr_t val) {
        tagged_ptr tp;
        tp.ptr = val & PTR_MASK;
        tp.tag = val & TAG_MASK;
        return tp;
    }

    static std::uintptr_t pack(node* ptr, std::uintptr_t tag) {
        return reinterpret_cast<std::uintptr_t>(ptr) | tag;
    }

public:
    void push(int value) {
        node* new_node = new node(value);
        std::uintptr_t old_val = head_.load(std::memory_order_relaxed);
        tagged_ptr old = unpack(old_val);

        new_node->next = reinterpret_cast<node*>(old.ptr);

        tagged_ptr desired;
        desired.ptr = reinterpret_cast<std::uintptr_t>(new_node);
        desired.tag = old.tag + TAG_INC;

        while (!head_.compare_exchange_weak(
            old_val,
            pack(new_node, desired.tag),
            std::memory_order_release,
            std::memory_order_relaxed)) {
            old = unpack(old_val);
            new_node->next = reinterpret_cast<node*>(old.ptr);
            desired.tag = old.tag + TAG_INC;
        }
    }

    ~tagged_stack() {
        std::uintptr_t val = head_.load(std::memory_order_relaxed);
        tagged_ptr tp = unpack(val);
        node* current = reinterpret_cast<node*>(tp.ptr);
        while (current) {
            node* next = current->next;
            delete current;
            current = next;
        }
    }
};

## Intuition

An atomic operation is like a bank transaction that either fully completes or doesn’t happen at all: When you transfer money, the bank doesn’t debit your account and then forget to credit the other account — the transaction is atomic. std::atomic gives you the same guarantee for memory operations: the read-modify-write happens as a single, indivisible step. No other thread can see a half-completed operation.

Why it matters: Atoms are the building blocks of lock-free programming. Instead of using a mutex (which blocks threads), you can use atomic operations to coordinate between threads without ever putting anyone to sleep. But lock-free doesn’t mean wait-free — a thread can still starve if other threads keep winning the CAS race.

The key insight: compare_exchange_weak may fail spuriously — this is not a bug, it’s an optimization for architectures that use LL/SC instructions. Always use it in a loop.

Common Pitfalls

Using memory_order_relaxed where ordering is needed: A relaxed store-release pair provides NO synchronization. If thread A stores data then sets a flag with relaxedThread B may see the flag but not the data (due to CPU store buffering and compiler reordering). Use release/acquire pairs for flag-based synchronization.
Forgetting that compare_exchange_weak can fail spuriously: Always use compare_exchange_weak inside a loop. The spurious failure is not an error — it is an implementation artifact of LL/SC instructions on some architectures. Never assume a single compare_exchange_weak succeeds.
std::atomic<T> is neither copyable nor movable: This is intentional. Copying an atomic would be a race condition (the copy would not be atomic with respect to other threads). Use load() and store() explicitly.
Lock-free does not mean wait-free: A lock-free algorithm guarantees system-wide progress (at least one thread advances), but individual threads may starve. A spinlock is lock-free but a thread waiting for the lock may spin forever under high contention.
std::atomic_flag initialization: Prior to C++20, std::atomic_flag had to be initialized with ATOMIC_FLAG_INIT. In C++20, it has a default constructor that initializes to clear. The ATOMIC_FLAG_INIT macro is deprecated in C++20.
False sharing with adjacent atomics: Two std::atomic<int> objects placed next to each other in memory share a cache line ( 64 bytes). Contention on one causes cache invalidation for the other, even if they are logically independent. Pad atomics to cache line boundaries to prevent this.

Summary

This topic covers the core concepts of atomic operations and lock-free programming, including underlying theory, practical implementation, and key applications.

Key concepts include:

variables, data types, and control flow
functions and procedures
object-oriented programming
error handling and debugging
modular design

Understanding these concepts thoroughly is essential for both examinations and practical programming, and requires both theoretical knowledge and hands-on practice.

Worked Examples

Worked examples demonstrating the application of key concepts are covered in the detailed sub-pages linked above.

Mark this page as reviewed

Atomic Operations and Lock-Free Programming