Race
Two threads run the same line of code: count = count + 1. It is one line and three instructions, so between them there are six instructions and twenty ways those six can be ordered. Eighteen of the twenty end with the counter reading one instead of two. Not eighteen found by testing. Eighteen of twenty, because there are only twenty, and every one of them is on this page.
New to concurrency? Start here
Two things at once
A program you write reads top to bottom, one step after the last. Once two of them run at the same time, that stops being true of the pair: their steps interleave, in an order nobody chose and nothing wrote down.
The hard part is that the order is not random so much as unconstrained. Any interleaving the hardware permits is one you have to treat as possible, even if no test you ever run happens to produce it: nothing promises that a scheduler will eventually choose it, and nothing promises it will not, on someone else's machine, months later, on the run you were not watching. So the machines in this topic are not about making the right order happen. They are about which orders are possible, which of those are wrong, and what it costs to rule them out.
One line, three instructions, twenty orderings, eighteen wrong answers
1 The line, as the machine actually does it
An ordinary unsynchronised increment is not one operation. The value is read into a register, one is added to the register, and the register is written back — and hardware does have single instructions that do all three atomically, which is what Compare and Swap is about. The value is read into a register, one is added to the register, and the register is written back. Each thread has its own register, and that is the whole reason this can go wrong: the value a thread writes back is the one it read, not whatever is in memory by then.
2 Every order the six instructions can happen in
Each thread's own three stay in sequence, and otherwise the machine may run them in any order it likes. That gives twenty. Twenty is small enough to print, so here are all of them, and no sampling is involved anywhere on this page.
| # | order | count ends at | verdict |
|---|---|---|---|
| AAABBB | 2 | correct | |
| AABABB | 1 | lost an update | |
| AABBAB | 1 | lost an update | |
| AABBBA | 1 | lost an update | |
| ABAABB | 1 | lost an update | |
| ABABAB | 1 | lost an update | |
| ABABBA | 1 | lost an update | |
| ABBAAB | 1 | lost an update | |
| ABBABA | 1 | lost an update | |
| ABBBAA | 1 | lost an update | |
| BAAABB | 1 | lost an update | |
| BAABAB | 1 | lost an update | |
| BAABBA | 1 | lost an update | |
| BABAAB | 1 | lost an update | |
| BABABA | 1 | lost an update | |
| BABBAA | 1 | lost an update | |
| BBAAAB | 1 | lost an update | |
| BBAABA | 1 | lost an update | |
| BBABAA | 1 | lost an update | |
| BBBAAA | 2 | correct |
3 One of them, instruction by instruction
Press any row above to follow it. The interesting column is the one holding each thread's own register, because a lost update is the moment a thread writes back a number that was already stale when it read it.
| step | thread | does | its register | count |
|---|---|---|---|---|
| 1 | A | read count into its own register | 0 | 0 |
| 2 | A | add one to the register | 1 | 0 |
| 3 | A | write the register back to count | 1 | 1 |
| 4 | B | read count into its own register | 1 | 1 |
| 5 | B | add one to the register | 2 | 1 |
| 6 | B | write the register back to count | 2 | 2 |
Ordering AAABBB ends with count at 2, which is right. One thread finished entirely before the other began, which is the only way this comes out correct.
4 What a lock actually does
A lock does not make the instructions faster, and it does not make them fewer. It deletes orderings. Every interleaving in which one thread begins before the other has finished simply cannot occur any more, and what survives is the two runs where nothing overlaps at all.
- orderings that can happen
- 20
- of those, ones that lose an update
- 18
- share of those orderings
- 90 per cent
18 of the 20 orderings lose an update. The two that do not are the ones where a thread finishes before the other starts, which is the thing a lock is for.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| two threads of 3 steps interleave 20 ways, and every one is listed | yes | not sampled and not simulated: the orderings are enumerated |
| 18 of those 20 end with one increment lost, which is 90 per cent | yes | a race that always lost would be a bug; one that never lost would not be a race |
| every losing order ends at 1 rather than somewhere arbitrary | yes | one thread writes back the value it read, so exactly one increment disappears |
| a lock leaves 2 of the same 20 orderings and loses none of them | yes | the two serial runs. Locking is subtraction from a space that already existed, not a different mechanism |
| and what survives is exactly the orderings where one thread finishes before the other starts | yes | that sentence is what mutual exclusion means, written as a filter over the enumeration |
What is real here, and what is not
Twenty is the count for this shape, not for concurrency
Two threads of three instructions each interleave twenty ways, and that is exactly the binomial coefficient six-choose-three. It is a fact about two sequences of three, not a general fact about threads. Three threads would be 1,680, and a longer critical section grows it faster still. The number is small here because the example is small, which is the only reason every case can be printed.
A real machine is worse than this, not better
This page assumes each instruction happens completely, one at a time, in some order. That is the model Dijkstra sets up and it is generous. Real processors reorder instructions, keep values in per-core caches that are not immediately visible to other cores, and compilers hoist reads out of loops entirely. Those add failure modes on top of the ones counted here. What removes the ones counted here is an atomic read-modify-write, which is a different instruction rather than a different schedule.
Where the bug is, exactly
Not in the read, and not in the write. Dijkstra's postulate is that each of those is indivisible, and this page keeps that assumption. The bug is that they are two separate actions with a gap between them, and the gap is where the other thread fits. That is why no amount of making a single instruction more atomic fixes it, and why the fix is a rule about the gap rather than a faster instruction.
The lock here deletes orderings and costs nothing
Shown as a filter over the same twenty, which is honest about what mutual exclusion means and quiet about what it costs. A real lock is an instruction with a price, it serialises work that might have run in parallel, and holding two of them in the wrong order is its own famous failure. None of that is on this page.