Atomic Operations and Compare-And-Swap (CAS) Mechanics
Master lock-free fundamentals: std::atomic<T>, atomic read-modify-write instructions, Compare-And-Swap (compare_exchange_weak vs strong), and ABA problem mitigation.
By the end, you’ll be able to…
- Implement lock-free state updates using std::atomic and hardware atomic assembly instructions (LOCK CMPXCHG)
- Contrast compare_exchange_weak (spurious failures, loop-friendly) with compare_exchange_strong
- Diagnose the ABA problem in lock-free node management and analyze tagged pointer mitigation
01The Architecture of std::atomic
When multiple threads mutate shared memory without mutexes, we must use std::atomic<T> (defined in <atomic>). An atomic operation is indivisible: hardware guarantees that no other CPU core can observe an atomic operation in an intermediate or partially completed state.
On x86_64, primitive types (int, long, pointers) are naturally atomic when aligned. However, standard operations like counter++ are NOT atomic! counter++ involves three distinct machine instructions: 1. Load memory into register. 2. Increment register. 3. Store register back to memory. If two threads interleave, increments are lost.
std::atomic<int> counter; counter++ compiles down to a single hardware atomic instruction: lock inc dword ptr [counter], asserting a hardware lock signal on the CPU cache line across all cores.
02Compare-And-Swap (CAS): The Engine of Lock-Free Algorithms
Compare-And-Swap (CAS) is the foundational primitive behind all lock-free queues, ring buffers, and concurrent skip-lists. In C++, CAS is exposed as compare_exchange_weak and compare_exchange_strong.
CAS atomically compares the value in memory with an expected value: 1. If memory matches expected, it updates memory with the new desired value and returns true. 2. If memory does NOT match expected (another thread mutated it first!), it updates expected with the current memory value and returns false.
compare_exchange_weak is allowed to fail spuriously on architectures like ARM (due to LL/SC monitor cache lines), but runs faster in loops. compare_exchange_strong guarantees no spurious failures and is preferred outside loops.
03The ABA Problem in Lock-Free Stacks
The ABA Problem is a classic flaw in lock-free node-based data structures (like Treiber Stacks).
Consider a stack with top pointing to node A, which points to node B. Thread 1 reads top (A) and prepares to pop it. Before Thread 1 executes CAS(top, A, B), Thread 1 is preempted.
Thread 2 pops A, pops B, and frees both. Later, Thread 2 allocates a brand-new node that happens to be assigned the exact same heap memory address as original node A! Thread 2 pushes A back onto the stack.
Thread 1 wakes up and executes CAS(top, A, B). Because top == A, CAS succeeds! However, node B was already freed, corrupting the stack into a dangling pointer crash.
Mitigation: Use Tagged Pointers (embedding a 16-bit monotonic version counter inside pointer bits) or Hazard Pointers / std::atomic<std::shared_ptr>.
04Atomic CAS Functions Comparison
Comparing weak vs strong compare-and-swap operations:
Always use compare_exchange_weak inside a retry while loop for maximum performance.
+-----------------------+---------------------+-------------------+-------------------------+| Function | Spurious Failures? | Best Suited For | Architecture Advantage |+-----------------------+---------------------+-------------------+-------------------------+| compare_exchange_weak | YES (Allowed) | while loop retry | Faster on ARM/RISC (LL/SC)| compare_exchange_stron| NO (Guaranteed) | Single check / if | Optimal on x86 (CMPXCHG)|+-----------------------+---------------------+-------------------+-------------------------+The ideas worth keeping.
- std::atomic guarantees indivisible hardware operations across CPU cores.
- Compare-And-Swap (CAS) loops form the algorithmic foundation of all lock-free structures.
- Use tagged pointers or version counters to eliminate the ABA problem.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Write a lock free atomic multiplication funct
Write a lock-free atomic multiplication function void atomic_multiply(std::atomic<int>& val, int factor) using a compare_exchange_weak loop.
Explore a worked solution
#include <atomic>void atomic_multiply(std::atomic<int>& val, int factor) noexcept { int current = val.load(std::memory_order_relaxed); while (!val.compare_exchange_weak(current, current * factor, std::memory_order_seq_cst, std::memory_order_relaxed)) { // current is updated automatically on failure }}Load current, then loop with compare_exchange_weak(current, current * factor).
Exercise 2: Explain how Tagged Pointers combining pointe
Explain how Tagged Pointers (combining pointer + counter) prevent the ABA problem in lock-free stacks.
Explore a worked solution
// In a tagged pointer, every pointer is paired with a monotonic version counter:// struct TaggedNode { Node* ptr; uint64_t tag; };// Every time a node is pushed or popped, the tag increments: (A, 1) -> (B, 2) -> (A, 3).// When Thread 1 attempts CAS(expected = (A, 1), desired = B), the CAS fails// because the tag is now 3, even though the raw pointer address A is identical!Every mutation increments a version tag, ensuring (A, 1) != (A, 2).
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Write a lock free atomic multiplication funct
Write a lock-free atomic multiplication function void atomic_multiply(std::atomic<int>& val, int factor) using a compare_exchange_weak loop.
Build completed. Binary executed. [Exit code: 0]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.