Two threads each run the statement `counter = counter + 1` one thousand times on a shared variable, with no synchronization. The final value is often less than 2000. Explain why, using what the hardware actually executes.
answer
- one statement, three steps: load, add, store
- both read 5, both write 6 → lost update
- atomic ⇔ nobody sees the middle
- compound action: read-modify-write, check-then-act
- fix: lock, CAS, or don't share
basics
~20 sThat one statement is three machine steps: read the value, add one, write it back. Two threads can read the same old value, both add one to it, and both write the same new value — so two increments produce one. Updates are lost whenever the steps interleave.
solid answer
~50 s`counter = counter + 1` looks atomic in source but is a **read-modify-write**: load the current value, compute value+1, store the result. Nothing stops another thread from running between the load and the store. Interleave two threads starting at 5: both load 5, both compute 6, both store 6. Two increments happened; the counter advanced by one. That is a **lost update**, and with a thousand iterations each you lose an unpredictable number of them, so the result is anything between 1000 and 2000. The general rule: an operation is atomic only if no other thread can observe or interfere with its intermediate state. A sequence of individually-safe steps is not automatically a safe sequence — that is a **compound action**, and it needs to be made atomic explicitly: hold a lock across the whole read-modify-write, use a hardware atomic increment or compare-and-swap, or give each thread its own counter and combine at the end.
code
text · 7 linescounter starts at 5
time ->
A: load(5) .... add(6) .......... store(6)
B: ..... load(5) .... add(6) ............ store(6)
two increments performed, counter == 6go deeper
Show the three steps and walk one concrete interleaving where both threads read the same value; name it a lost update and give one fix.
Generalize to compound actions — read-modify-write and check-then-act — and compare the fixes: lock, atomic/CAS, per-thread accumulation, immutability.
Stress that atomicity of individual accesses is a different property from atomicity of the compound action, and that the right question is where the atomic boundary must sit.
Frame it as invariant design: which state must change together, whether the counter should be shared at all, and when to prefer per-thread reduction or single-owner state over synchronizing a hot shared location.
## What the statement really is Source code hides how much work a statement is. `counter = counter + 1` compiles to roughly three operations: 1. **load** — copy the current value of `counter` from memory into a register; 2. **add** — compute register + 1; 3. **store** — write the register back to `counter`. A thread can be preempted between any two of those, and on a multicore machine two threads execute genuinely simultaneously anyway. There is no rule that says these three steps happen as a unit — that property is called **atomicity**, and you only get it if something provides it. ## The interleaving that loses an update Start with counter = 5. ``` Thread A Thread B counter load -> 5 5 load -> 5 5 add -> 6 5 add -> 6 5 store 6 6 store 6 6 ``` Both threads did their job correctly. Both incremented "the value they read". But B's read happened before A's write, so B computed from a stale value and overwrote A's result. Two increments, one net change: a **lost update**. With a thousand iterations per thread, this happens an unpredictable number of times, which is why the total is some non-deterministic value ≤ 2000. It is also why the bug is so treacherous: the window is nanoseconds wide, so on a lightly loaded developer machine the count is often exactly right, and it only misbehaves on the production machine with more cores and more contention. ## The general shape: compound actions Increment is one instance of a family. A **compound action** is a sequence of operations that must appear indivisible to be correct. Two forms cover almost all of them: - **Read-modify-write** — read a value, derive a new one from it, write it back. Increment, append, "add this amount to the balance", "set flag if larger". - **Check-then-act** — test a condition, then act on the assumption that the condition still holds. "If the key is absent, insert it." "If the file does not exist, create it." "If balance ≥ amount, withdraw." In both, the danger is the **gap**: between the read (or check) and the write (or act), another thread can change the thing you based your decision on. Your decision is then based on a fact that is no longer true, and you act on stale information. ## Why "it's just one line" is not a defense The atomicity of an operation has nothing to do with how it looks in source. Whole-statement atomicity is not something languages generally promise for arbitrary expressions on shared variables. Even a single machine instruction is not automatically atomic across cores unless it is specified to be — that is exactly what dedicated atomic instructions (atomic add, compare-and-swap) exist to provide. Note also that making the variable's individual reads and writes atomic (so no torn or half-written value is ever observed) does **not** fix this bug. Every read and every write above was clean; the problem is that the *pair* was not a unit. Visibility/atomicity of single accesses and atomicity of a compound action are different properties, and increment needs the second. ## The fixes, and what each one costs 1. **Mutual exclusion.** Acquire a lock before the load and release it after the store. Correct and general — it works for arbitrarily complex compound actions, including ones spanning several variables. Costs contention when many threads hit the same lock. 2. **A hardware atomic operation.** Atomic increment, or a compare-and-swap retry loop: read the value, compute the new one, and swap it in *only if* the variable still holds the value you read; if not, retry. This closes the gap by making the check and the write one indivisible step. Fast and lock-free, but only applies to a single memory location. 3. **Don't share.** Give each thread its own counter and sum them at the end (per-thread accumulation / reduction), or confine the counter to a single owning thread and send it messages. No contention at all; costs a combining step and some memory. 4. **Immutability.** If a value never changes after publication, no read-modify-write exists to race. ## The interview-ready summary Ask of any shared-state operation: *is there a moment between my read and my write where another thread could change the value I based the write on?* If yes, the operation is a compound action, it is not atomic just because it is one statement, and you must widen the atomic unit — with a lock, with a hardware atomic, or by not sharing the state at all.
- If reads and writes of the counter were guaranteed atomic and immediately visible to all threads, would the count now be correct?No. Every individual read and write in the losing interleaving was already clean and well-formed; nothing was torn or stale in the hardware sense. The bug is that the read and the write are not a single unit, so another thread can slip in between them. Fixing visibility fixes a different problem — it stops threads reading indefinitely stale values — but leaves the lost update intact.
- Give another everyday example of the same bug that is not a counter, and say what makes it the same."If the key is absent, insert it" over a shared map: two threads both find the key absent and both insert, so one overwrites the other or a duplicate is created. Likewise "if balance ≥ amount, subtract amount" lets two withdrawals both pass the check and overdraw the account. In each case a decision is made from a read value and acted on later, and the state can change in the gap — check-then-act, the sibling of read-modify-write.
Two people update the same paper tally by reading the number, writing it on a sticky note, adding one, and copying it back. If both read '5' before either writes, the pad ends up at 6 no matter how carefully each of them did their arithmetic.
saying these in an interview costs you the question
- 'It's a single statement so it's atomic'
- 'It only loses updates if the OS preempts the thread' — on multiple cores they run simultaneously with no preemption needed
- 'Making the variable's reads and writes atomic/visible fixes the count'
- 'It worked on my machine a hundred times, so it's fine' — the window is nanoseconds and load-dependent
- 'Just make the loop faster / add a small sleep' as a fix