Part 10 — Concurrency

CAS, Acquire/Release, Relaxed, Sequential Consistency

This chapter covers compare-and-swap (CAS) and the C11 memory orders: relaxed, acquire/release, and sequential consistency.

Why This Matters

CAS is the universal atomic primitive for lock-free algorithms. The memory orders control how strongly operations are ordered, trading simplicity for performance. Misusing them produces subtle, catastrophic bugs.

Prerequisites

c.conc.5 — atomics and the memory model.

Core Concept

Compare-and-swap (CAS)

CAS atomically compares a value to an expected value and, if equal, replaces it with a new value:

#include <stdatomic.h>

atomic_int v = ATOMIC_VAR_INIT(0);
int expected = 0;
if (atomic_compare_exchange_strong(&v, &expected, 1)) {
    /* v was 0; now it is 1 */
} else {
    /* expected now holds the actual value of v */
}

There are _strong and _weak forms; _weak may fail spuriously and is used in loops.

Memory orders

Order	Guarantee
`memory_order_relaxed`	atomicity only; no ordering of other operations
`memory_order_acquire`	subsequent reads/writes are not reordered before this load
`memory_order_release`	prior reads/writes are not reordered after this store
`memory_order_acq_rel`	both acquire and release (for RMW)
`memory_order_seq_cst`	full sequential consistency (default)

Acquire/release form a synchronizes-with pair: a release store followed (observed) by an acquire load makes all prior writes visible to the acquiring thread.

Examples

CAS loop (lock-free increment)

#include <stdatomic.h>

void inc(atomic_int *v)
{
    int expected = atomic_load(v);
    while (!atomic_compare_exchange_weak(v, &expected, expected + 1))
        ; /* expected is updated on failure */
}

Release/acquire message passing

atomic_int flag = ATOMIC_VAR_INIT(0);
int data = 0;   /* non-atomic, protected by the flag */

/* producer */
data = 42;
atomic_store_explicit(&flag, 1, memory_order_release);

/* consumer */
while (atomic_load_explicit(&flag, memory_order_acquire) == 0)
    ;
int v = data;   /* guaranteed to see 42 */

The release store synchronizes-with the acquire load, so data = 42 is visible to the consumer.

How It Works

CAS maps to a hardware atomic instruction (lock cmpxchg on x86, ldaxr/stlxr on ARM). Memory orders translate to the appropriate fences: on x86 the hardware is strongly ordered (most things are already ordered), while on ARM acquire/ release requires explicit barrier instructions.

Variations

Weak vs. strong CAS

atomic_compare_exchange_weak may fail spuriously even when the comparison succeeds; always use it in a loop. _strong never fails spuriously but may be more expensive on some architectures.

Relaxed atomics

Use memory_order_relaxed when only atomicity matters (e.g., a simple counter where the *total* is read only at the end and ordering with other data is not required).

Common Mistakes

Using relaxed order when surrounding data must be ordered.
Forgetting to update expected in the CAS loop.
Assuming acquire/release is needed for a simple atomic counter (relaxed

suffices).

Mixing _weak and _strong incorrectly.

Undefined Behavior

A data race on the non-atomic data that a release/acquire pair is supposed

to protect (if the protocol is violated).

Using an invalid memory-order constant.

Portability

Memory orders are standard C11; the *cost* of each order is

architecture-dependent.

Under the Hood

On x86, acquire/release are nearly free (the hardware already provides strong ordering); seq_cst adds a mfence or lock prefix in some cases. On ARM, acquire/release require ldar/stlr or explicit dmb.

Practical Usage

Use seq_cst (default) until you understand the weaker orders.
Use acquire/release for message-passing and lock-free structures.
Use relaxed for counters and flags with no ordering dependencies.

Exercises

1. Implement a lock-free counter with a CAS loop. 2. Implement the release/acquire message-passing example and verify with TSan. 3. Compare the generated assembly for relaxed vs. seq_cst on x86 and ARM.

Deep Challenge

Implement a lock-free stack using CAS and release/acquire, and explain the ABA problem and how to avoid it (e.g., with tagged pointers or hazard pointers).

c.conc.5 — atomics.
c.conc.7 — fences.
c.conc.8 — lock-free programming.

References

ISO C §7.17 (atomics); C++ memory model references (the C model is similar).

Verification

Memory-order semantics are standard C11. VERIFIED
CAS loop pattern. VERIFIED
No example was executed during generation unless noted. `Execution not

verified.`

Progress

[ ] Read
[ ] Understand
[ ] Complete examples
[ ] Complete exercises
[ ] Complete deep challenge

Concept checkboxes

[ ] Compare-and-swap
[ ] Relaxed ordering
[ ] Acquire/release
[ ] Sequential consistency
[ ] Synchronizes-with

Mastery levels

Concept	Current level (0–8)	Target level
c.conc.cas	0	7
c.conc.acquire	0	7
c.conc.release	0	7
c.conc.relaxed	0	7
c.conc.seq-cst	0	7

← Prev Next →