Answers · How a program runs
Why can two threads that each work correctly still give the wrong answer?
In shortEach thread reads the shared value and writes it back in two separate steps, so the other thread can run in between and one increment silently overwrites the other.
Both threads are correct line by line and the program is wrong, because the read of the counter and the write back to it are two separate steps with a gap between them, and the scheduler may run the other thread inside that gap. Any order that keeps each thread's own steps in sequence is a legal execution, and of the six such orders for four steps, four leave the counter at one.
Six orders, two answers
Give each thread two steps and the whole space is small enough to write out. Thread one does A1 then A2, thread two does B1 then B2. Choosing which two of the four slots belong to thread one fixes the order, and there are six ways to choose. Take A1, A2, B1, B2: thread one reads 0 and stores 1, thread two then reads 1 and stores 2, and the answer is right. The reverse, B1, B2, A1, A2, is also right, ending at 2. The other four are not. In A1, B1, A2, B2 both threads read 0 before either writes; thread one stores 1, then thread two stores 1 over it. In A1, B1, B2, A2 the same two reads happen and the same overwrite happens, only the last writer changes. B1, A1, A2, B2 and B1, A1, B2, A2 are those two again with the threads swapped. All four end at 1. The count grows fast from here: five steps each gives 252 orders, ten steps each gives 184,756, so writing them out is something you do once, at the smallest size, and never again.
| first | second | third | fourth | final counter | |
|---|---|---|---|---|---|
| A1 A2 B1 B2 | 1 | 1 | 2 | 2 | 2 |
| A1 B1 A2 B2 | 1 | 2 | 1 | 2 | 1 |
| A1 B1 B2 A2 | 1 | 2 | 2 | 1 | 1 |
| B1 A1 A2 B2 | 2 | 1 | 1 | 2 | 1 |
| B1 A1 B2 A2 | 2 | 1 | 2 | 1 | 1 |
| B1 B2 A1 A2 | 2 | 2 | 1 | 1 | 2 |
The natural guess is that correctness belongs to each thread, so two correct threads make a correct program. That holds only if one thread's steps cannot be separated by another's. The source never says that. A read and the write that depends on it are written as one line, and a line is not a unit of execution; the machine sees two instructions with nothing between them. Once the pair can be split, the wrong answer is not an edge case: four of six legal orders produce it. It looks rare because an unloaded machine tends to run the first thread to completion before the second gets going, which picks one of the two good orders almost every time.
| step | step | what runs | thread one copy | thread two copy | counter | what happened |
|---|---|---|---|---|---|---|
| 1 | 1 | A1 reads | 0 | none | 0 | Thread one copies zero. The counter is untouched. |
| 2 | 2 | B1 reads | 0 | 0 | 0 | Thread two copies zero as well. Both threads hold the same stale value and neither can tell. |
| 3 | 3 | A2 writes | 0 | 0 | 1 | Thread one writes its copy plus one. As far as thread one is concerned the increment succeeded. |
| 4 | 4 | B2 writes | 0 | 0 | 1 | Thread two writes its copy plus one, which is one, over a one. The first increment is gone. |
The gap is the bug
The failure has a shape worth naming, because it recurs everywhere. Two threads read the same value, both compute from it, both store a result, and the second store erases the first. This is the lost update. It needs three things at once: a variable shared between threads, a read whose result feeds a later write, and no exclusion between the two. Take away any one and it disappears, which is exactly why the fixes look the way they do.
Running the program and seeing 2 is close to no evidence. Each run executes one order, and on an idle machine with threads started microseconds apart it is nearly always the same order, so a thousand passes sample one order a thousand times. Under load the sampling changes: more threads, more cores and more timer switches, and the four bad orders start coming up several times a second. The bug then looks intermittent and unreproducible, though every individual run is fully determined by the order it happened to get.
The composition does hold once the gap is closed. A lock held across both the read and the write makes A1 and A2 one indivisible step, and the six orders collapse to two, both correct. It also holds if the value is only ever read, or if each thread accumulates into its own variable and the results are combined afterwards, since then nothing is shared and nothing can be lost. What does not help is making each step individually atomic: an atomic read followed by a separate atomic write is still two steps with a gap, and the gap is precisely where the other thread lives. How much has to sit inside the indivisible region is the whole question, and choosing it too small gives the same bug back with more machinery around it.
Worth keeping
- Two threads that are each correct can still be wrong together, because correctness of a thread does not constrain the order of its steps relative to another thread's.
- An atomic read followed by a separate atomic write still loses updates; the read and the write have to be indivisible together.
- With two steps per thread there are six legal orders and four of them are wrong, so the failure is the common case rather than an unlucky one.
Where this goes next
This question is one step of What Two Threads Can Break, a course that works through its subject from the beginning. The page that teaches this part of it is All the Orders It Could Run In, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- Why does 2 + 3 * 4 equal 14 and not 20?The multiplication is done first: three times four makes twelve, and only then is the two added, giving fourteen. Reading left to right would give twenty.
- How many samples does a profiler need before a percentage in the report means anything?It depends on how many samples landed on that line: you need a few hundred samples on the line you care about, because the relative error is roughly one over the square root of that count.
- If I make one part of my program twice as fast, how much faster does the whole program get?Less than twice as fast: only the share of run time you actually touch can improve, so the untouched remainder caps the gain, often at a few per cent.
- Why does reading one byte from memory load 64 bytes?Memory hardware moves data in fixed sixty-four-byte blocks, so a one-byte read fetches the whole block; the extra bytes cost almost nothing because reaching the memory row costs most of the time.
- My change made it 4% faster — how do I know that isn't just noise?You cannot tell from one pair of runs. Run the unchanged program ten times first: only then does a four per cent gap mean anything.
- Why does the compiler catch a type mismatch but not division by zero?A compiler checks types before running because types are known for every possible run; it cannot know a divisor is zero until the program actually runs.