Two threads each run the statement `count = count + 1` a thousand times on the same shared variable, and the final total is less than two thousand. Explain why, and what it means for an operation to be an atomic read-modify-write.
answer
- one line = load, add, store
- both read 41, both write 42 = lost update
- preemption makes it happen on one core too
- RMW = read+modify+write indivisibly
- visibility fixes staleness, not the gap
basics
~20 sThe statement is three steps: read, add one, write back. Two threads can read the same old value and both write the same new value, so one increment is lost. An atomic read-modify-write performs all three steps as one indivisible hardware operation that no other thread can interleave with.
solid answer
~50 s`count = count + 1` is not one operation. It compiles to a load, an add, and a store. Any interleaving is possible between them, so two threads can both load 41, both compute 42, and both store 42 — one increment vanishes. This is a lost update, and it happens even on a single core, because a thread can be preempted between the load and the store. An **atomic read-modify-write** is a single hardware operation that reads a memory location, computes a new value from it, and writes it back with no other thread able to observe or intervene at an intermediate point. Fetch-and-add, exchange, and compare-and-swap are the usual primitives. The processor achieves this by taking exclusive ownership of the cache line for the duration. Note that making the variable merely *visible* across threads is not enough. Visibility fixes staleness; it does nothing for the read-then-write gap. You need atomicity of the whole trio, which means an atomic operation or a lock.
code
text · 7 linesNON-ATOMIC ATOMIC
count = 41 count = 41
T1 load 41 T1 fetch_add(count,1) -> 41
T2 load 41 T2 fetch_add(count,1) -> 42
T1 store 42 count = 43
T2 store 42
count = 42 (one lost)go deeper
Say the three steps out loud and walk the two-thread interleaving that loses an increment; name atomic increment or a lock as the fix.
Add why visibility alone is insufficient, and name the concrete primitives (fetch-and-add, exchange, compare-and-swap).
Point out that atomicity per operation does not compose into atomicity of a sequence, and mention the cache-line ownership cost of read-modify-write instructions.
Question whether the counter should be shared at all: per-thread accumulation, sharding, or approximate counting often beat making the hot path atomic.
## Why one line is three operations Processors do not compute on memory; they compute in registers. An increment therefore always becomes: ``` load r <- count # read add r <- r + 1 # modify store count <- r # write ``` Each step is individually indivisible, but the sequence is not. Between any two steps, another thread on another core can execute freely, and even on one core the scheduler can preempt between them. ``` count = 41 T1: load r1 = 41 T2: load r2 = 41 T1: r1 = 42 ; store count = 42 T2: r2 = 42 ; store count = 42 count = 42 (two increments applied, one survived) ``` Nothing was corrupted at the bit level — each store wrote a legal value. What was lost is the *dependency*: T2's write should have been based on T1's result and was not. This class of bug is called a **lost update**, and it is the simplest possible data race. A key detail candidates get wrong: this is not merely a multicore phenomenon. Preemption on a single core creates the same interleaving. "We only run one core" is not a defence; neither is "the window is tiny" — it just makes the loss rare and load-dependent, which is worse for diagnosis. ## What atomic read-modify-write means An operation is **atomic** with respect to other threads if no thread can observe it half-done and no thread's operation can interleave inside it. A **read-modify-write (RMW)** atomic does all three phases as one unit: - **fetch-and-add(loc, delta)** — adds and returns the previous value. - **exchange(loc, v)** — stores v and returns the previous value. - **compare-and-swap(loc, expected, new)** — stores new only if the location currently equals expected; reports whether it did. - **fetch-and-or / fetch-and-and** and similar bitwise forms. With fetch-and-add, the earlier trace becomes impossible: the hardware serialises the two operations, so one returns 41 and the other returns 42, and the final value is 43. Every RMW has a single, well-defined position in a total order of operations on that location. ## How hardware provides it On cache-coherent machines, the core executing an RMW acquires the target cache line in an exclusive state and holds it for the duration of the operation, so no other core can read or write it in between. Alternatively the architecture provides load-linked/store-conditional, where the store fails if the line was touched since the load, and the operation is retried. Either way the cost is real: an RMW forces exclusive ownership of a line, which is far more expensive than a plain load and gets worse as more cores contend for the same line. ## Atomicity is not visibility, and not compound safety Three distinctions worth stating explicitly: **Atomicity versus visibility.** Marking a variable as "always read from memory" or otherwise ensuring writes become visible to other threads solves staleness — it does not close the read-then-write gap, because two threads can still both read the freshest value and both write the same result. Increment needs atomicity, not just visibility. **Atomicity of one operation versus of a sequence.** An atomic increment protects one increment. It does not protect `if (count < LIMIT) count = count + 1`, because the check and the update are two atomic operations with a gap between them. Compound invariants need either a compare-and-swap loop that re-validates, or a lock. **Atomicity versus ordering.** An atomic RMW guarantees indivisibility of that operation on that location. Whether surrounding ordinary reads and writes are seen in program order by other threads is governed by the memory ordering the operation carries — a related but separate concern. ## The other correct answer: don't share The cheapest atomic operation is the one you never perform. If each thread keeps a private counter and the totals are summed at the end, there is no shared mutable state, no contention, and no correctness question. Sharing a hot counter should be a deliberate choice, not a default.
- If the shared variable is declared so that every read sees the latest written value, is the increment now safe?No. Guaranteeing freshness fixes visibility, not atomicity. Two threads can both read the newest value, both add one, and both store the same result, losing an update exactly as before. Only an atomic read-modify-write, or a lock held across the read and the write, makes the increment safe.
- An atomic increment is safe. Is `if (count < limit) atomicIncrement(count)` also safe?No. The comparison and the increment are two separate atomic operations, and another thread can push the counter to the limit in the gap between them, so the counter can exceed it. Correct approaches are a compare-and-swap loop that re-reads the value and re-checks the condition before installing the new one, or holding a lock across the whole check-and-act sequence.
Two people update the same total on a whiteboard. Both read 41, both walk away and compute 42, both write 42. Nobody misread anything; the second write was just based on a stale reading.
saying these in an interview costs you the question
- Believing a single source line executes as one indivisible step
- Claiming the bug cannot occur on a single-core machine
- Thinking a visibility guarantee alone makes increment safe
- Assuming that if every individual operation is atomic, any sequence of them is atomic
- Dismissing it because 'the window is too small to matter'