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;
}

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.

flowchart TD
    A[3_Atomic_Operations] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

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

Atomic Operations and Lock-Free Programming

std::atomic<T>

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

Atomic Operations

std::atomic_flag

Lock-Free vs Wait-Free vs Obstruction-Free

ABA Problem and CAS

Lock-Free Stack with compare_exchange_weak

Spinlock Using std::atomic_flag

See Also

Memory Order Arguments and Their Semantics

compare_exchange in Detail

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

std::atomic&lt;void*&gt; and Pointer Atomics

std::atomic&lt;bool&gt; as a Flag

std::atomic&lt;shared_ptr&gt; and std::atomic&lt;weak_ptr&gt; (C++20)

Tagged Pointers for ABA Prevention

Intuition

Common Pitfalls

Summary

Worked Examples

`std::atomic<T>`

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

`std::atomic_flag`

Lock-Free Stack with `compare_exchange_weak`

Spinlock Using `std::atomic_flag`

`compare_exchange` in Detail

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

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

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

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