The question this answers
If two tasks each run three indivisible steps, what are the possible orderings, and which of them produce a wrong answer?
Two tasks, A and B, each executing counter = counter + 1 exactly once against a shared counter that starts at 0.
One integer counter in memory, reachable by both tasks. Nothing else is shared; each task has its own copy of the intermediate value it read.
counter equals the number of increments that have returned — after two completed increments from 0, counter must be 2.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
One source line, three indivisible steps
The mental model that produces the bug is that counter = counter + 1 is a thing that happens. It is not. It is a *read* of counter into a register or a stack slot, an *add* on that private copy, and a *write* back to the shared location. The private copy is the whole problem: between the read and the write, the task is operating on a number that may already be out of date, and nothing in the source hints at the gap.
This is the read-modify-write shape, and it is everywhere once you see it: counter++, total += price, list = list.concat(x), cache[k] = cache[k] + 1, if (!m.has(k)) m.set(k, v). Each looks like one act of updating and is at least two accesses to shared memory with a window in between.
Where the switch may occur depends on the runtime, and this is the one place the difference genuinely matters. On preemptive threads the scheduler may interrupt between any two machine instructions, so the window is real on every line. In a single-threaded event loop the window opens only at an await, which makes the failing schedule rare rather than impossible — and rare is worse, because it reaches production before it reaches a test.
1# what you wrote2counter = counter + 13 4# what the runtime schedules — three steps, two of them touching shared memory5 1 LOAD tmp <- counter # shared read. tmp is private to this task.6 2 ADD tmp <- tmp + 1 # private. no other task can see or affect this.7 3 STORE counter <- tmp # shared write. overwrites whatever is there now.8 9# a task switch is legal at every arrow:10# ... -> 1 -> ... -> 2 -> ... -> 3 -> ...11#12# Step 3 is the dangerous one: it is a blind write. It does not check13# whether counter still holds the value that step 1 read. Nothing in the14# language asks that question for you; see [[compare-and-swap]] for the15# primitive whose entire job is asking it.The schedule that loses an update
Six steps, two actors, three steps each. The number of distinct interleavings that preserve each actor's internal order is C(6,3) = 20. Most of them are fine. The ones that are not share a signature: A's read happens before B's write, *and* A's write happens after B's read. When both reads precede both writes, both tasks compute 1 from 0, both store 1, and one increment is gone.
Read the trace below and watch the counter column. There is no moment at which anything is corrupt, no torn value, no exception. Every step is individually legal and every value is individually well-formed. The invariant dies at step 5 not because a step was wrong but because step 5 wrote a number derived from a snapshot that step 4 had already invalidated.
This is the canonical *lost update*, and it is the reason the word "atomic" appears in this domain at all. The fix is never to make the individual steps smaller. It is to make steps 1 through 3 indivisible with respect to steps 4 through 6 — by a mutex (Mutexes: What They Protect and What They Do Not), by an atomic read-modify-write instruction (Atomics: What Is Actually Indivisible), or by a compare-and-swap retry loop that detects the stale snapshot and starts over (Compare-and-Swap and the Retry Loop).
| # | Task A — counter = counter + 1 | Task B — counter = counter + 1 | State |
|---|---|---|---|
| 1 | LOAD tmpA <- counter | · | counter=0 tmpA=0 |
| 2 | · | LOAD tmpB <- counter | counter=0 tmpA=0 tmpB=0 |
| 3 | ADD tmpA <- tmpA + 1 | · | counter=0 tmpA=1 tmpB=0 |
| 4 | STORE counter <- tmpA | · | counter=1 tmpA=1 tmpB=0 |
| 5 | · | ADD tmpB <- tmpB + 1 | counter=1 tmpB=1 |
| 6 | · | STORE counter <- tmpB | counter=1 tmpB=1 ✕ Two increments completed; counter is 1. B's blind write overwrote A's with a value derived from a snapshot taken before A ran. |
Enumerating the twenty, and why the tests pass
The reason this bug survives review is arithmetic. Of the 20 orderings, 14 give the right answer under a uniformly random scheduler on this example — so a test that runs the pair once has roughly a 70% chance of passing, and a test that runs it a thousand times in a loop on a machine where A almost always finishes its three steps inside one scheduler quantum has a much higher chance than that. The failing schedules require a switch to land inside a two-instruction window.
That is the deep point about testing concurrency: a passing test tells you that *one* schedule was correct. It says nothing about the other nineteen, and the scheduler is under no obligation to ever show you them on your laptop while cheerfully producing them on a 64-core production box under load. See Heisenbugs: The Bug That Leaves When You Look at It and Stress Testing: A Test That Passed Once Proves Nothing.
The enumeration itself is a technique you should be able to do by hand for two actors. List each actor's shared accesses in order — ignore the private steps, they cannot interact. For A: read, write. For B: read, write. Then ask the single diagnostic question: *can B's read fall between A's read and A's write?* If yes, there is a lost update. That question generalises to every check-then-act and read-modify-write in the codebase, which is what Reasoning About Races: A Method, Not an Instinct turns into a method.
| Class of ordering | Shape (shared accesses only) | Count | Final counter | Invariant |
|---|---|---|---|---|
| Fully serial — A then B | Ra Wa Rb Wb | 4 of 20 | 2 | holds |
| Fully serial — B then A | Rb Wb Ra Wa | 4 of 20 | 2 | holds |
| Overlapped but writes ordered after both reads | Ra Rb Wa Wb / Rb Ra Wb Wa | 8 of 20 | 1 | BROKEN — lost update |
| Overlapped, one write lands between the other read and write | Ra Rb Wb Wa / Rb Ra Wa Wb | 4 of 20 | 1 | BROKEN — lost update |
Key points
counter = counter + 1is read, modify, write. The modify is private; the read and the write are the two shared accesses, and everything hinges on what happens between them.- The blind write is the defect. Step 3 stores a value derived from step 1's snapshot without ever asking whether that snapshot is still current.
- Two tasks of three steps admit 20 interleavings; 12 of them are correct on this example and 8 lose an update — which is exactly why the test suite passes.
- Enumerate only the *shared* accesses. Private steps cannot interact and only make the list longer.
- The diagnostic question, in one line: can the other task's read fall between my read and my write?
- The fix makes the read and write indivisible together — a lock, an atomic RMW instruction, or a CAS loop that retries on a stale snapshot. Never a smaller step.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • The compiler or interpreter lowers the assignment into a load of the shared location, an arithmetic operation on a private temporary, and a store back to the shared location.
- • The runtime is free to suspend the task at any point between those steps — a timer interrupt on a preemptive thread, a bytecode boundary in an interpreter, an
awaitin an async task. - • While A is suspended between its load and its store, B executes its own load and observes the pre-update value, because A never published anything.
- • Both tasks now hold private temporaries derived from the same original value.
- • Both stores execute. The second one wins, and the increment carried by the first is discarded with no signal to anyone.
- • A reads 0; A writes 1; B reads 1; B writes 2 — correct. This is the schedule your test produces.
- • A reads 0; B reads 0; A writes 1; B writes 1 — the counter is 1 after two increments. The canonical lost update.
- • A reads 0; B reads 0; B writes 1; A writes 1 — same outcome, different order. The loser is A this time; nothing distinguishes them.
- • B reads 0; B writes 1; A reads 1; A writes 2 — correct, and indistinguishable from the first case in any log you would normally have.
- • With ten tasks incrementing concurrently, the correct schedules require every read to follow the previous write; the probability of that under real contention is low, so the counter drifts by a percentage of throughput rather than by a fixed amount.
- • The language guarantees each task's own steps execute in an order consistent with its source — it guarantees nothing about how those steps interleave with another task's.
- • It does not guarantee that a value read is still current when written back. No mainstream language checks that for you on a plain assignment.
- • A single-threaded runtime guarantees no switch mid-statement, but the moment
counter = await f() + 1appears, the window is back and is now hundreds of milliseconds wide. - • CPython's bytecode-level interpreter lock guarantees that individual bytecodes do not interleave;
x += 1compiles to several bytecodes, so it guarantees nothing about this example. Verified against CPython 3.12disoutput.
- • None in the broken version — that is precisely why it is fast and wrong. Lost updates cost no wall-clock time.
- • Every fix introduces contention proportional to how often the window is entered: a mutex serialises the region, an atomic RMW serialises the cache line, a CAS loop burns retries.
- • On a single hot counter, all three fixes converge to the same bottleneck: one cache line, one core at a time. See What Contention Actually Costs and False Sharing: Different Variables, Same Cache Line.
- • The scalable fix is not a better primitive but a different decomposition — per-task counters summed at read time, which trades exact-at-every-instant for exact-at-read. See Parallel Reduce.
- • Lost update — the headline failure. Two increments, one recorded, no error anywhere.
- • Undercounting that scales with load — the error rate rises with concurrency, so the metric looks fine in staging and is wrong in production exactly when it matters.
- • Data race, in the strict sense, if the accesses are unsynchronized and the language memory model says so. In C++ this is undefined behaviour, not merely a wrong count; see Data Race Is Not Race Condition.
- • Non-reproducibility — the failing schedule is not under your control, so "cannot reproduce" is the bug report you will receive. See Heisenbugs: The Bug That Leaves When You Look at It.
- • Enumerating interleavings helps most on code that already looks obviously correct — a two-line function is where the failing schedule hides, because nobody thinks to look.
- • It helps in review: walking the shared accesses of a diff takes under a minute and catches the entire lost-update family before it merges.
- • It helps when choosing a primitive, because the enumeration tells you *which region* must be indivisible, which is the input to Finding the Critical Section.
- • Enumeration by hand does not scale past two or three actors with a handful of shared accesses. Beyond that use a model checker or a race detector; see Race Detectors: What They Find, and What They Structurally Cannot.
- • It is the wrong tool when the state is not actually shared — time spent enumerating schedules over task-local data is time wasted.
- • Over-applied, it produces defensive locking everywhere, which converts a correctness problem into a contention problem and often a deadlock problem. See Concurrency Anti-Patterns.
- • Compare the counter against an independently derived total — a database
COUNT(*), a log-line count, a billing reconciliation. Drift that grows with traffic is the signature. - • Run the operation N times from K tasks and assert the result is exactly N×K. A single run proves nothing; the assertion must be exact, not approximate.
- • Use a race detector rather than intuition where one exists: ThreadSanitizer for C and C++, the Go race detector, Java's
jcstressharness. See Race Detectors: What They Find, and What They Structurally Cannot. - • Increase the pressure deliberately — more tasks than cores, a yield inserted between read and write in a debug build — so the rare schedule becomes the common one. See Stress Testing: A Test That Passed Once Proves Nothing.
- • Every shared read-modify-write becomes a place where the reader of the code must reconstruct the interleavings themselves. That reconstruction cost is paid on every future change.
- • The fix adds a synchronization object whose scope is now a permanent invariant of the module: every new writer must acquire it, and nothing in most type systems enforces that.
- • Sharded counters trade one clear number for K numbers plus a summation rule and a staleness window, which must be documented or it will be misread as a bug.
- • An atomic increment instruction, when the invariant really is just "this one number counts things". One instruction, no lock object, no critical section to get wrong. See Atomics: What Is Actually Indivisible.
- • Do not share the counter: increment a task-local value and sum at the end. Correct by construction and usually faster; see Parallel Reduce.
- • Push the increment to a system that already arbitrates —
UPDATE t SET n = n + 1in a transaction, or an atomicINCRin a key-value store. See The Database Solves Concurrency For Its Data, Not For Your Memory. - • Serialise the whole operation onto one owner task and send it messages, which removes the interleaving instead of managing it. See The Actor Model.
Two increments, twenty schedules: find the one that loses an update
| # | Task A — counter++ | Task B — counter++ | State |
|---|---|---|---|
| 1 | rA ← counter | · | counter=0 rA=0 rB=0 |
| 2 | rA ← rA + 1 | · | counter=0 rA=1 rB=0 |
| 3 | counter ← rA | · | counter=1 rA=1 rB=0 |
| 4 | · | rB ← counter | counter=1 rA=1 rB=1 |
| 5 | · | rB ← rB + 1 | counter=1 rA=1 rB=2 |
| 6 | · | counter ← rB | counter=2 rA=1 rB=2 |
The lost update, step by step
| # | Task A — counter++ | Task B — counter++ | State |
|---|---|---|---|
| 1 | rA ← counter | · | counter=0 rA=0 rB=— |
| 2 | · | rB ← counter | counter=0 rA=0 rB=0 |
| 3 | rA ← rA + 1 | · | counter=0 rA=1 rB=0 |
| 4 | counter ← rA | · | counter=1 rA=1 rB=0 |
| 5 | · | rB ← rB + 1 | counter=1 rA=1 rB=1 |
| 6 | · | counter ← rB | counter=1 rA=1 rB=1 ✕ 2 increments completed, counter = 1 |
counter++ with and without atomicity
r ← counter r ← r + 1 counter ← r
fetch_add(counter, 1) # no schedule can cut inside this
What people believe, and what is true
counter++ is a single operation — it is one character.
It is a read, an add and a write in every mainstream language. ++ is syntax for the sequence, not a promise about it. Only an explicitly atomic type makes it indivisible.
It passed a thousand-iteration test, so it is fine.
A thousand iterations sample a thousand schedules out of a space the scheduler chooses non-uniformly. The failing schedule needs an interrupt inside a two-instruction window, which your idle laptop rarely delivers and a loaded production host delivers constantly.
I made the write atomic, so the increment is safe now.
An atomic *store* still stores a stale value. Safety requires the read and the write to be atomic *together* — that is what an atomic fetch-and-add or a CAS loop provides and a plain atomic store does not.
Single-threaded runtimes do not have this problem.
They have a smaller set of switch points, not none. x = await get() + 1 has a window the width of a network round trip — the widest one in this lesson.
Go deeper
Overview
One line of source is several steps at runtime. Another task can run between them and see, or overwrite, a half-finished update. That is the whole idea.
Practical
Find every read-modify-write and check-then-act on shared state. For each, ask whether another task's access can land between the read and the write. If it can, the pair must be made indivisible together — not each half separately.
Advanced
Enumerate only shared accesses; private computation is irrelevant to the interleaving space. For two actors with m and n shared accesses the count is C(m+n, m). Classify the orderings by outcome rather than listing them: what matters is the *shape* (both reads before both writes), not the specific permutation.
Internals
Whether the store is even visible to the other task is a separate question from ordering, and it is governed by the language memory model rather than the scheduler. A store can be buffered, and a load can be satisfied from a cache line that has not been invalidated yet, so "A wrote 1 before B read" does not by itself mean B reads 1. See What a Memory Model Defines and Happens-Before: The Edge That Makes a Write Visible.