Concurrency from Scratch — Locks, Atomics, and Memory Models

Why data races happen and why they refuse to reproduce in your tests, starting from zero. Locks, atomic operations, CAS, and memory models, built up through metaphor, math, and code.

One Kitchen, Two Cooks

There are ten eggs in the fridge. A note on the wall reads "remaining: 10". Every cook follows the same procedure: read the note, take one egg, subtract one from the number you read, write it back.

With one cook, nothing goes wrong. With two working at once, it breaks. A and B both read the note and see "10". Both take an egg. Both write back "9". The fridge holds eight eggs; the note claims nine. Nobody made a mistake, and yet the books no longer balance.

That is a data race. The eggs are a variable, the note is memory, the cooks are threads. The nasty part is that it only happens sometimes. Shift the timing slightly and you get the right answer, so the tests pass, it never reproduces on your machine, and the books go wrong only during the busy hour in production.

A quick distinction while we are here. Concurrency is a structural property — the lifetimes of several tasks overlap — and it exists even on a single core. Parallelism is an execution property: things literally run at the same instant. The bug in this article is born on the concurrency side. Even with one core, the OS can preempt a thread mid-procedure, and that is all it takes.

"Add One" Is Not One Step

The single line that breaks most often is this one.

counter += 1

It looks like one action. In machine code it is at least three: load from memory, add in a register, store back to memory. It is the cook's read-modify-write, and another thread can slip in between any two of those steps. Run it 100,000 times on each of two threads and the total will not be 200,000. It comes up short by however many updates were lost, and the number is different every run.

Formally, a data race is when two or more threads access the same memory location, at least one of them writes, and nothing orders the accesses relative to each other. In C and C++ a program containing one has undefined behavior. The compiler is entitled to optimize on the assumption that races do not exist, so "it happened to print the right number" guarantees nothing at all.

The neighbouring term, race condition, is broader: any design bug whose outcome depends on timing. You can lock every individual operation and still go negative, if something interleaves between "check the balance" and "debit the account". Deciding which span needs protecting is a human's job, not the lock's.

Why It Won't Reproduce — Combinatorial Explosion

Failure to reproduce is not bad luck; it is arithmetic. If two threads each have $n$ instructions, the number of possible execution orders — interleavings — is the number of ways to riffle-shuffle two decks together.

Read it as: out of $2n$ total steps, choose which $n$ of them belong to thread 1. At $n=10$ that is 184,756 orderings; at $n=20$ it is roughly 137 billion. Real functions run to hundreds of steps each, and adding a third or fourth thread pushes the count up again. Perhaps only a handful of those orderings break. Running your test once draws a single card from that pile — and drawing a blank is not proof that the pile holds no winners.

Worse, the bug disappears when you observe it. Add a print, set a breakpoint, turn up the logging — each of those changes how long the threads spend where, which changes the odds of drawing the bad card. "I added logging and it went away" means the probability dropped, not that the bug did. This species has a name: a heisenbug.

Which is why the everyday standard — it ran, so it's correct — is worthless here. You cannot establish correctness by executing the program. You have to show structurally that the race cannot occur. The rest of this article is the toolkit for doing that.