Every way to make an update atomic
A lock-prefixed read-modify-write, an exchange, fetch-and-add, compare-and-swap, an LL/SC loop or an LSE atomic, a CAS retry loop, or a lock. How much the update does decides.
Ask what the update is.
- Add to or subtract from a counter (and maybe learn the old
value) → one fetch-and-add: x86-64
lock add/lock xadd, ARM64ldadd(LSE), RISC-Vamoadd. In C++,fetch_add. - Swap in a new value unconditionally (take a flag, publish a
pointer) →
xchg(always locked on x86-64),swp(LSE),amoswap. - Any other single-word update (double it, push onto a list,
take the max) → a compare-and-swap loop: read, compute,
cmpxchg/cas, retry on failure. Without LSE, ARM64 and RISC-V build it from load-exclusive / store-conditional, which can fail spuriously. - Several words at once, or a long critical section → a lock (a spinlock for very short sections, a mutex that sleeps otherwise).
volatile and a plain single instruction are not on this list:
neither makes a read-modify-write atomic. And atomicity is separate
from ordering: see "Every way to order memory between threads".
Why plain code isn't enough
Section
Why count++ is not atomic
A load, an add and a store that another core can interleave with.
Term
lost update
Term
data race
One instruction does the whole update
Section
Atomic instructions on x86-64
lock add, lock xadd, xchg and lock cmpxchg.
Term
lock prefix
Example
[rdi] = 5, eax = 1: lock xadd [rdi], eax leaves memory 6 and eax 5.Section
Atomics on ARM64 and RISC-V
LSE's ldadd/cas and RISC-V's amo* instructions, or an LL/SC pair.
Read, compute, try to store, retry
Formal. CAS(p, expected, desired) performs, as one atomic step with respect to every other core:
- Read v = *p.
- If v = expected, store *p = desired and report success.
- Otherwise leave *p unchanged and report failure, returning v.
On x86-64, lock cmpxchg [p], desired takes the expected value in
rax (eax for 32 bits), sets ZF = 1 on success, and on failure loads the
value it found into rax. C++ std::atomic<T>::compare_exchange_strong(expected, desired) returns true or false and, on failure, writes the found value
into expected.
In plain English. "If the value is still what I last saw, replace it with my new one; if somebody changed it, don't touch it and tell me what it is now." No other thread can change the value between the check and the write.
Example. A counter holds 5. Thread A runs CAS(p, 5, 6) and succeeds: the counter is 6. Thread B, which also read 5, then runs CAS(p, 5, 6) and fails, because the value is now 6; B gets 6 back and can try CAS(p, 6, 7) instead. Both increments survive.
Why this rule exists. Compare-and-swap is the general atomic step: any update that can be computed from the old value can be made atomic with it, by retrying until the value it was computed from is still current.
Section
CAS loops and a spinlock
Any update you can compute from the old value, retried until no one got in between.
Example
ldaxr w9, [x8] … stlxr w10, w11, [x8]; cbnz w10, retry loops when the store-conditional fails.A successful CAS proves the value matched, not that nothing happened in between.
Give up and take a lock
Term
spinlock
Term
mutex
Term