vault

Atomicity Visibility and Ordering

15 min read

Atomicity Visibility and Ordering

Every bug in a shared-memory concurrent program is a failure of one of exactly three properties: atomicity (a compound read-modify-write is interrupted so another thread sees a half-finished state), visibility (one thread’s write never becomes observable to another), or ordering (operations appear to happen in an order different from the one written). This trichotomy — articulated most cleanly by Jeremy Manson, technical lead of Java’s memory-model overhaul JSR-133 (Manson 2007) — is the taxonomy the rest of concurrency theory hangs from. Each property has a distinct failure mode, a distinct example, and a distinct primitive that supplies it: atomicity comes from atomic read-modify-write (locks or hardware RMW instructions), visibility comes from release/acquire memory synchronization (a fence that flushes and reloads memory), and ordering comes from an ordering constraint (a barrier that forbids reordering). The subtle point, and the reason the three must be named separately, is that they are independent: you can have any one without the others, and a program can be perfectly atomic yet still broken by a visibility or ordering failure.

Mental Model

The cleanest way to hold the three properties in your head is as three different questions a concurrent program must answer about a single shared access, and three different mechanisms that answer them. Do not think of them as three names for the same thing — that conflation is the single most common source of “I added volatile/synchronized and it still breaks” confusion.

flowchart TD
    Q["A thread touches<br/>shared mutable state"]
    Q --> A["ATOMICITY<br/>Is the read-modify-write<br/>indivisible?<br/>(all-at-once or not-at-all)"]
    Q --> V["VISIBILITY<br/>Will another thread<br/>ever SEE this write?<br/>(does it propagate?)"]
    Q --> O["ORDERING<br/>Do operations APPEAR<br/>in a consistent sequence?<br/>(no surprising reorder)"]

    A --> AP["supplied by<br/>ATOMIC RMW<br/>lock / CAS / fetch-add"]
    V --> VP["supplied by<br/>RELEASE-ACQUIRE<br/>fence flush + reload"]
    O --> OP["supplied by<br/>ORDERING CONSTRAINT<br/>memory barrier"]

    AP -. "one primitive often<br/>supplies all three" .-> VP
    VP -. "e.g. a mutex, or a<br/>seq_cst atomic" .-> OP

What it shows and the insight to take: the three columns are genuinely independent axes — atomicity is about indivisibility of a compound operation, visibility is about propagation of a value between threads, ordering is about the apparent sequence of operations. Each maps to its own primitive (left-to-right). The dashed back-edges capture the practical reality that a single strong primitive — a mutex, or a sequentially-consistent atomic — bundles all three at once, which is why they get conflated. The teaching value is in pulling them apart: when you reach for a weaker, cheaper primitive (a relaxed atomic, a lock-free algorithm), you are choosing which of the three you still get, and a bug is you having assumed one you did not buy.

Atomicity — Indivisibility of a Compound Operation

An operation is atomic if, from every other thread’s vantage point, it happens all at once or not at all — there is no observable moment at which it is half-done (Manson 2007). The word comes from the Greek atomos, “indivisible.” The failure it guards against has two flavours.

The first is the torn read or torn write at the level of a single variable. If a 64-bit value is stored on a 32-bit machine as two 32-bit machine stores, a reader that runs between the two stores sees a Frankenstein value — the new high half spliced onto the old low half (Preshing 2013). This is a natural atomicity question: is a single load or store of this type, at this alignment, indivisible on this hardware? On common architectures an aligned, naturally-sized integer load/store is atomic, but this is a hardware property, not a language guarantee — an unaligned access, or a value wider than the machine word, can tear. This is why languages force you to say std::atomic<T> or AtomicLong even for a single variable: you are asking the compiler to guarantee the load/store is done with an instruction (or lock prefix) that cannot tear.

The second, and far more common, flavour is the compound read-modify-write (RMW). Consider counter++. That single line of source is three operations: read the current value, add one, write it back. Two threads each running counter++ can interleave so that both read the same starting value, both add one, both write back — and one increment is silently lost. Manson’s canonical illustration is a bank account where two threads each individually synchronize their read and their write, yet the compound operation “read balance, add deposit, write balance” is not atomic as a whole, so a deposit vanishes (Manson 2007). The insight is sharp: atomicity is a property of a compound action, not of its individual steps. Making each step atomic buys you nothing if the combination must be indivisible.

The primitive that supplies atomicity is an atomic read-modify-write: either mutual exclusion (a lock held across the whole compound operation, so no other thread can observe the intermediate state) or a hardware RMW instruction — compare-and-swap (CAS), fetch-and-add, load-linked/store-conditional — that performs read-modify-write as one indivisible unit. See Compare-and-Swap and Load-Linked Store-Conditional for the atomic RMW primitives and Race Conditions and Data Races for why the interleaving is a race in the first place.

Visibility — Whether a Write Propagates

Visibility answers a completely different question: once a thread has written a value, will another thread ever see it? On a multiprocessor, a write does not go straight to a single shared RAM that everyone reads. It lands in the writing core’s store buffer and cache; other cores hold their own cached copies. Absent an instruction that forces the issue, there is no guarantee the write is ever propagated to another core — and even absent caches, an optimizing compiler may keep the value in a register and never write it to memory at all, or hoist a read out of a loop so it is performed once and reused forever.

The Java tutorial’s minimal example makes the failure concrete: thread A executes counter++, then thread B executes println(counter). Even though A’s increment “logically” happened before B’s read, B may print 0, because nothing established that A’s write is visible to B (Oracle Java Tutorial). Manson’s LoopMayNeverEnd sharpens it: one thread spins on while (!done) {} while another sets done = true; without synchronization the spinning thread may loop forever because the compiler cached done in a register or the store never reached its cache (Manson 2007). Note that this is not an atomicity failure — a boolean write does not tear. It is purely about propagation.

The formal machinery for visibility is the happens-before relation. A write is guaranteed visible to a read only if the write happens-before the read, established through a synchronizing action. Java’s tutorial defines happens-before as exactly “a guarantee that memory writes by one specific statement are visible to another specific statement” (Oracle Java Tutorial). The Go memory model states the same requirement operationally: for an ordinary read r of location x to observe a write w, w must be visible to r — w must happen-before r, and no other write to x may intervene in happens-before order (The Go Memory Model).

The primitive that supplies visibility is release/acquire synchronization. A release operation (a lock release, a store(memory_order_release), an unbuffered channel send) acts as a flush: everything the thread wrote before it is pushed out. A matching acquire (a lock acquire, a load(memory_order_acquire), a channel receive) acts as a reload: it pulls in everything published before the paired release. When an acquire observes the value written by a release, a synchronizes-with edge forms and the releasing thread’s prior writes become visible to the acquiring thread (Preshing 2012). See Memory Fences and Barriers and Acquire Release and Fence Semantics for the barrier mechanics, and Happens-Before Relation for the partial order itself.

Ordering — The Apparent Sequence of Operations

Ordering is the third and most counter-intuitive property: even when writes are visible, the order in which one thread’s operations become visible to another may differ from program order (the order written in source). This happens because two independent agents reorder memory operations for performance. The compiler may reorder instructions whenever doing so cannot change a single thread’s observable result — reassociating arithmetic, hoisting loads, sinking stores (Wikipedia: Memory ordering). The hardware may reorder at run time: store buffers let a store be delayed past a later load, and weakly-ordered CPUs (ARM, POWER) allow loads and stores to commit to cache in an order unrelated to program order (Preshing 2012 weak vs strong).

Manson’s BadlyOrdered example is the classic trap: thread 1 does a = 1; b = 1; and thread 2 reads b then a. Intuitively, if thread 2 sees b == 1 it “must” also see a == 1. But nothing orders the two writes relative to each other as observed from thread 2, so thread 2 can legally see b == 1, a == 0 (Manson 2007). Again note this is neither an atomicity failure (single-word writes, no tearing) nor purely a visibility failure (both writes do become visible) — it is an ordering failure. The two became visible in a surprising order.

There are exactly four reorderings to reason about, named by the pair being swapped: LoadLoad, LoadStore, StoreStore, and StoreLoad (Preshing 2012). StoreLoad — a store being reordered after a later load — is the one even the strong x86 model permits and the most expensive to forbid. The primitive that supplies ordering is a memory barrier (fence) that forbids specific reorderings, or the ordering implied by release/acquire (a release forbids preceding reads/writes from sinking below it; an acquire forbids following reads/writes from hoisting above it). The strongest ordering, sequential consistency, forbids all four reorderings and makes the program behave as one global interleaving of each thread’s program order (Preshing 2012 weak vs strong); see Sequential Consistency.

Why the Three Are Independent — and Why One Primitive Bundles Them

The reason to hold atomicity, visibility, and ordering as separate axes is that each can fail while the others hold, and each has its own fix. The counter++ lost update is atomicity failing with visibility and ordering irrelevant. LoopMayNeverEnd is visibility failing with atomicity and ordering irrelevant. BadlyOrdered is ordering failing with atomicity and visibility both fine. A precise diagnostic vocabulary — “this is an ordering bug, not a visibility bug” — is what lets you pick the cheapest sufficient primitive rather than reflexively wrapping everything in a lock.

At the same time, the strong primitives deliberately supply all three at once, which is why they feel like a single concept in practice. A mutex gives atomicity (the critical section is indivisible), visibility (unlock is a release, lock is an acquire), and ordering (the barrier forbids critical-section operations from leaking out). A sequentially-consistent atomic — C++ memory_order_seq_cst, a Java volatile, a Go sync/atomic operation — supplies visibility and ordering, and for a single-variable RMW like fetch_add, atomicity too. The Go memory model states this equivalence directly: Go’s atomics behave as C++ sequentially-consistent atomics and as Java volatile (The Go Memory Model). This is also the deeper meaning of the DRF-SC guarantee — a data-race-free program (one where every conflicting access pair is ordered by happens-before) behaves with sequential consistency (The Go Memory Model; Preshing 2012 weak vs strong). Establish all three properties correctly on every shared access and the hardware’s reorderings become invisible; see Data-Race-Free Programs and the DRF-SC Theorem.

Worked Example — One Flag, Three Properties

// Producer thread                      // Consumer thread
data = compute();                       while (atomic_load_explicit(
atomic_store_explicit(                       &ready, memory_order_acquire) == 0)
    &ready, 1, memory_order_release);       ;  /* spin */
                                        use(data);

Line-by-line, this snippet is a compact demonstration of all three properties working together:

  • data = compute(); — an ordinary, non-atomic write. It is not individually synchronized and does not need to be, because the flag will carry its visibility.
  • atomic_store_explicit(&ready, 1, memory_order_release) — the release. It supplies (a) atomicity of the flag write (no tearing of ready), (b) the flush half of visibility, publishing the prior data write, and (c) ordering: the release forbids data = compute() from being reordered after it.
  • The consumer’s atomic_load_explicit(&ready, ..., memory_order_acquire) — the acquire. When it observes the value 1, a synchronizes-with edge forms with the release, and the reload half of visibility fires: data is now guaranteed visible. The acquire also forbids use(data) from being hoisted before the flag is seen.
  • use(data) — an ordinary read, now safe, because happens-before ties it to the producer’s write.

Change release/acquire to memory_order_relaxed and you keep atomicity of the flag (still no tearing) but lose visibility and ordering of data — the consumer may see ready == 1 yet read a stale or partially-constructed data. That is the trichotomy made operational: relaxed atomics buy exactly one of the three properties and no more.

Common Misunderstandings

“volatile (Java) / atomic makes my operation thread-safe.” It supplies visibility and ordering, and single-access atomicity — but not compound atomicity. A volatile int still loses updates under ++, because ++ is a compound RMW and volatile does not make the read-add-write indivisible (SEI CERT Java: Concurrency, Visibility, and Memory). Use an atomic RMW (AtomicInteger.incrementAndGet, fetch_add) or a lock.

“C/C++ volatile helps with threads.” It does not. volatile in C/C++ prevents the compiler from eliding accesses (useful for memory-mapped I/O) but provides neither atomicity, visibility across cores, nor ordering against non-volatile accesses. This is a different keyword from Java’s volatile despite the shared spelling.

“A single machine instruction is atomic.” Not necessarily. An unaligned store, or a read-modify-write like inc [mem] without a lock prefix on x86, is a single instruction but not atomic against other cores (Preshing 2013). Atomicity is a property of the memory transaction, not the instruction count.

“If I see the new value of X, I see everything written before X.” Only if the write and read are release/acquire (or stronger). With relaxed or unsynchronized access, visibility of one variable implies nothing about the ordering of others — this is exactly the BadlyOrdered failure.

“It works on my x86 laptop, so it’s correct.” x86 is a strong (TSO) model that forbids three of the four reorderings for free, forgiving missing barriers that ARM/POWER will punish (Preshing 2012 weak vs strong). Passing on x86 is weak evidence of ordering correctness. See Total Store Order and Relaxed Memory Models.

Relation to Linearizability

The three properties are the low-level correctness vocabulary; the high-level counterpart for a whole concurrent object is linearizability — the guarantee that each operation appears to take effect atomically at some instant between its call and return, consistent with a sequential specification (Wikipedia: Linearizability). Linearizability is essentially “atomicity + a real-time ordering constraint” lifted from a single variable to an entire object’s method set. When you implement a linearizable data structure, you are establishing atomicity, visibility, and ordering on every internal access such that external observers can only ever see indivisible, correctly-ordered operations. See Linearizability as a Correctness Condition.

Production Notes

The trichotomy is not academic hair-splitting; it maps to distinct real-world failure signatures. Atomicity bugs surface as lost updates and impossible aggregate values — a reference count that drifts, a total that does not add up — and are often reproducible enough to find under stress testing. Visibility bugs surface as hangs and stale reads — the LoopMayNeverEnd spin, a worker that never notices a shutdown flag — and are notoriously load- and optimization-level-dependent (they vanish under a debugger, which disables the optimizations that cached the value). Ordering bugs are the worst: rare, architecture-specific, and invisible on x86, they typically appear only when the code is ported to ARM servers or when an aggressive compiler upgrade starts exploiting a reordering it previously left on the table.

The engineering discipline that follows is to classify every shared access before choosing a primitive: is this a compound operation needing indivisibility (atomicity → lock or RMW), a publish/subscribe of data (visibility + ordering → release/acquire), or both (a full mutex)? Dynamic race detectors like Go’s -race and ThreadSanitizer catch the visibility/ordering class by tracking happens-before edges and flagging conflicting accesses not ordered by one (The Go Memory Model) — but they cannot catch a compound-atomicity logic error where each access is individually synchronized. The takeaway the whole field keeps relearning: you cannot test correctness in, you must design each of the three properties in. See Dynamic Race Detection and Reasoning About Concurrent Programs.

See Also

Graph View

Backlinks