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.
One line, three instructions, twenty orderings, eighteen wrong answers
1 The line, as the machine actually does it
Nothing in hardware increments a variable in memory in one go. 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
- chance of the wrong answer
- 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.
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; none of them removes any.
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.