Two Threads, Four Steps, and Six Different Programs You Did Not Write
The code you read is one order. The machine may run any order that keeps each thread internally in sequence. Write them all out once and the whole subject becomes concrete.
What an interleaving is
Here is a program that is wrong. Nothing about reading it suggests that.
shared counter = 0
thread one:
A1 read counter into a local copy
A2 write local copy plus one back to counter
thread two:
B1 read counter into a local copy
B2 write local copy plus one back to counter
afterwards, counter should be 2The scheduler running these threads has one constraint and total freedom
otherwise. The constraint is that the steps of a single thread keep their
relative order: A1 always happens before A2, and B1 always happens before B2,
because that is what writing them in sequence means.
Everything else is available to it. It may run all of thread one and then all
of thread two. It may alternate. It may switch between any two steps, including
between reading a value and writing it back, because nothing in the source says
those two things belong together.
There is no probability attached to any of this. The scheduler is not trying to
find a bad order and it is not avoiding one. It switches when a timer fires,
when a thread blocks, when another core becomes free, and when the operating
system feels like it.
How many orders there are
Count them for the four-step case. An order is a sequence of four slots, two of
which are the steps of thread one in order and two of which are the steps of
thread two in order. Choosing which two slots belong to thread one determines
everything, so there are as many orders as ways to choose two slots from four,
which is six.
- number of possible orders
- steps in the first thread
- steps in the second thread
Finding the bad one
Six orders is few enough to write out completely, and writing them out is the
exercise that makes everything else in this course concrete.
| 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 |
Two thirds of the available orders are wrong. That is not a near miss or an
unlucky edge, it is the common case, and it only looks rare because the
scheduler happens to pick one of the other two 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 takes a copy of zero. The counter is untouched. |
| 2 | 2 | B1 reads | 0 | 0 | 0 | Thread two takes a copy of zero as well. Both threads now hold the same stale value and neither has any way of knowing. |
| 3 | 3 | A2 writes | 0 | 0 | 1 | Thread one writes its copy plus one. The counter is now one, correctly as far as thread one is concerned. |
| 4 | 4 | B2 writes | 0 | 0 | 1 | Thread two writes its copy plus one. Its copy was zero, so it writes one over a one. The increment from thread one is gone without trace. |
Notice what makes it invisible in the source. The read and the write are one
line of code. Between them the counter can change, and nothing at the source
level marks that gap as a place where anything happens. That gap is the subject
of the next lesson.
Why testing misses it
A test run executes one order out of the six. Which one depends on how the
scheduler happened to behave, and it is almost always the same one, because the
machine is not loaded, the threads start at different moments, and the first
thread usually finishes its two steps before anything interrupts it.
Running the test a thousand times samples the same order a thousand times. It
feels like strong evidence and it is nearly no evidence at all.
Three consequences follow. A concurrency test that passes tells you almost
nothing, so the confidence it produces is unearned. Production finds these bugs
because load changes the sampling: more threads, more switching, more cores,
and orders that never came up start coming up several times a second. And the
bug will look intermittent and unreproducible, which it is not, since it is
perfectly deterministic given the order and you simply cannot see the order.
What replaces testing is reasoning about the whole set of orders at once, which
is what the rest of this course builds. The next lesson takes the gap between
the read and the write seriously and shows how many steps a single line of
source really is. From there the course derives what a lock actually promises,
and why the region it protects has to be chosen with more care than people
expect.
Recap
- A concurrent program is not one program, it is every order the steps could run in, and your code only constrains the order within each thread.
- Write the orders out by hand once, for four steps. The bad one is always there and it is always obvious on paper and invisible in the source.
- The number of orders grows so fast that testing samples a vanishing fraction of them, which is why concurrency bugs survive testing and appear under load.
This is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents