Races

Chapter 38 ended with an experiment in C: two threads each add one to a shared counter a million times, and the total comes out a little over a million on one run, nearly two million on another, and different every time. Virtual memory put processes into separate address spaces, so another process can’t spoil our numbers. But the threads of one process live in the same memory. They never have to send each other data, and for the same reason two of them can grab one number at once, each sure it is alone. Bugs of this kind can’t be seen in the text of a program, and they vanish the moment you start looking for them. We’ll learn to catch them on a repair job, and the job is on another planet.

Mars, July 1997. The computer reboots

We’ll find out what they saw in the trace at the end of the chapter, the same way they did: by reproducing the fault on a copy here on Earth. But the trace makes no sense without threads, locks and priorities, and the fault hides in an awkward combination of the three. Along the way you’ll meet puzzles of one kind: a short piece of code looks right, and your job is to find an order of steps that breaks it.

Threads: one memory for all

A process, as we saw in Chapter 36, is a program with its own memory, its open files and at least one line of execution: a program counter, registers and a call stack. A process can have several such lines, and each is called a thread. The scheduler from Chapter 37 hands out cores to threads: each thread has its own place in the program and its own local variables, while everything else (global variables, lists, dictionaries, files) is shared by all the threads of a process. In Python you start a thread with the threading module.

Both threads append to the same list, and the entries land interleaved as the threads wake up: ['A0', 'B0', 'A1', 'B1', 'A2', 'B2']. The list is shared; nothing had to be sent anywhere. start launches a thread, and join waits for it to end. Next comes last chapter’s experiment, this time in Python: two threads each add one to a shared counter a million times.

Not a single increment lost, although in C hundreds of thousands went missing. You might conclude that Python is safe from races. Put that to the test on code that could sit on any website: a counter of page views. Each visitor is served by a thread of its own, and each thread adds one to the view count of its page.

This time views go missing. When this chapter was written, the sandbox lost anywhere from 80 to 800 thousand views out of two million, a different number each time. Run it again and the numbers will change. If a program gives different answers on the same data, look for threads that share that data.

The window between a read and a write

To see why one line loses increments and the other doesn’t, we need the bytecode of both. We learned to read it in Chapter 33.

Each line breaks up into several actions. counter += 1 is four instructions: read counter (LOAD_GLOBAL), push a one, add, write (STORE_GLOBAL). The view count takes about ten: load the dictionary, call its get method (CALL), add, store the result in the dictionary (STORE_SUBSCR). Between reading the old value and writing the new one there is always a gap. If another thread reads the same old value during that gap, both threads write the same number, and one increment is lost.

That leaves the question of when the interpreter switches threads. Python does it on its own: every few milliseconds it asks the running thread to give up its place. You can look up the interval: sys.getswitchinterval() in the sandbox returns 0.005 seconds. But a thread can honor the request only where the interpreter checks for it, and since version 3.10 there are few such places. In our 3.13 they are entering a function, jumping back to start a new turn of a loop, and returning from a call to a built-in function. There is no check inside the four instructions of counter += 1, so in our version of Python that line was never interrupted halfway through. In count_view, though, a check sits right after CALL: the thread has read the old number, returns from get, sees the request and gives up the core, holding the number it read.

That is luck, not protection. On Python 3.9 the same counter.py loses increments: we ran it there and got between 1.1 and 1.8 million instead of two. In Python without the interpreter lock (more about it at the end of the chapter) the increment isn’t protected either, and in C, Java and Go even less so, as last chapter’s experiment in C showed. Any future version of Python may put the check somewhere else. Where the interpreter switches threads is not something you can rely on.

A bug in which the result depends on the order in which threads performed their steps is called a race condition, or a race for short: the threads seem to be racing each other, and the answer depends on who gets there first. The property our increment lacked is called atomicity: an operation is atomic if other threads see the state before it or after it, never the middle. Read-modify-write is not atomic until we make it so ourselves.

A puzzle: find the order

Catching a race by running code is awkward. In the cell above it strikes hundreds of thousands of times a second, because the threads do nothing but hammer the same spot. In a working program the window opens rarely, and the bug can hide for months and then strike on Mars. Reasoning is more reliable. Picture each thread as a list of steps and decide for yourself whose step comes next, as a scheduler would. An order in which the steps of threads are mixed together is called an interleaving. A race is an interleaving that gives the wrong answer. Find one.

The first two take a few presses, and they share a solution: the second thread must read or check the shared value before the first one has written its own. The last-seat case shows this most clearly. The check “seats greater than zero” is true when it is made, but by the time of the sale the world has changed. This kind of race is called check-then-act, and it lives wherever a decision rests on something read earlier: “no such file, so I’ll create it,” “the username is free, so I’ll take it,” “there’s enough money, so I’ll withdraw it.”

Before you take on the third puzzle, place your bet.

Two short threads have few interleavings, and a program can go through all of them. A thread’s steps are a list, and the interleavings are built by recursion, like the permutations in Chapter 9: the first step belongs either to one thread or to the other, and after it come all the interleavings of what is left.

Six interleavings, and only two give the correct 2: the ones where one thread finished before the other began. Model checkers work the same way on a large scale: they go through every interleaving, looking for a bad one. But the number of interleavings gets very large very fast.

Two threads of $k$ steps each have $\binom{2k}{k}$ interleavings: out of the $2k$ places in the combined order, you choose the ones that go to the first thread. For twenty steps that is already over a hundred billion, and for three threads of twenty, $5.8 \cdot 10^{26}$. The growth is exponential, like brute force in Chapter 13. Tests try a vanishing fraction of the orders, and the same ones every time: the order in which threads run on your laptop is up to the scheduler, which is predictable until the load changes. That is why races so often pass every test and then surface on users’ machines.

The first rule of defense, and the cheapest, is not to share what you don’t have to. Let each thread count views in a dictionary of its own, and let the main thread add the dictionaries up at the end. With no shared data, a race has nowhere to happen. Big counting systems work this way too: each server accumulates its own numbers and now and then hands them over to the common total. But some data is shared by its very nature: an account balance, the free seats in a theater, the list of open files. That data needs a different tool.

A fitting room for one

If shared data has to change, we must make sure nobody slips in between the read and the write. The simplest way is to let threads into that stretch of code one at a time, like a fitting room with a lock on the door: go in and lock it, come out and unlock it, and the next person waits outside. The stretch of a program where a thread works with shared data and where no second thread may be is called a critical section, and the object that guards it is a lock, also called a mutex, from “mutual exclusion.” In Python it is threading.Lock. The acquire method takes the lock, or waits until it is released; release lets it go. It is more convenient to write with lock:: the lock is then released automatically, even if an exception is raised inside.

Two million on the dot, three times in a row. Correctness costs time: when this chapter was written, the same two million calls took about 0.2 seconds in the sandbox without the lock and two to three times as long with it, from 0.4 to 0.7 seconds on different runs. A lock is work: take it, release it, and when threads compete for it, wake up the one that is waiting. So a critical section holds only what can’t be done outside it, and printing, reading a file or waiting on the network stay outside.

It is tempting to build the lock itself as a “busy” flag: if the flag is down, raise it and go in. But “if it’s down, raise it” is the same check-then-act race: two threads see the lowered flag at the same moment and both go in. A lock is hard to build out of ordinary reads and writes; it needs help from the hardware. Processors provide special instructions that read a memory cell and write a new value into it in one indivisible step, even when there are many cores: “swap,” for example, or “compare-and-swap.” While such an instruction runs, no other core can get at the cell: the cores’ caches come to an agreement, and the cache line from Chapter 34 that holds the cell belongs to one core for that moment. And so that a thread waiting for a lock doesn’t spin uselessly, the operating system kernel puts it to sleep and wakes it when the lock comes free; Linux has a system call for this, futex.

A lock comes with three rules. Every access to the shared data must happen under the lock, reads included: a thread that reads without the lock may see the middle of someone else’s write. It must be one and the same lock for that data: with threading.Lock(): inside a function creates a new lock on every call, and each thread locks a door of its own. And it must be held briefly, or everyone else stands in line. The last rule is about more than speed: a lock held too long once stopped a spacecraft on Mars.

Therac-25

A lost page view hurts nobody. But races also happen in programs that control machines, and one of them cost people their lives. This story has been told in courses on software reliability for more than thirty years.

The causes were examined in detail by Nancy Leveson and Clark Turner in a 1993 paper in the IEEE journal Computer. One of the bugs they found was a race. One task of the program handled the operator’s input on the screen, and another handled the setup of the equipment, which took several seconds. If the operator chose X-ray mode by mistake, immediately corrected the letter to electron mode and confirmed, all within eight seconds of the first keystroke, the correction never reached the equipment. The screen said one thing, and the machine did another. An operator who had run hundreds of treatments easily fit into eight seconds. In testing, nobody had typed that fast.

The second bug was an overflow, familiar from Chapter 11 and Chapter 28. A flag meaning “a check is needed” was not set to one: the program added one to it. Every so often the variable overflowed and became zero, and at that moment the check was skipped.

Leveson and Turner insisted that no single line of code explains these accidents: “focusing on particular software bugs is not the way to make a safe system.” They saw the main cause in the way the software was designed, tested and maintained. The protection of human life was entrusted to one program, with no independent check and no hardware backup. Two lessons bear directly on this chapter. Testing can’t rule out a race, because a race lives in orders that tests never try. And when a bug can kill, correct code alone is not enough: you need a safeguard that works even when the code is wrong.

Deadlock

Back to the explorer: now the threads have locks. First, try to break a counter that a lock protects. Then each thread takes two locks, and the goal is different: stop both threads forever.

The first can’t be solved: while A holds the lock, B’s button goes dim at lock.acquire(), and nobody gets in between the read and the write. Two threads of four steps have seventy interleavings, and the lock leaves only two of them possible: all of A and then all of B, or the other way round. Both give 2. The second, though, takes two presses, and it shows a new kind of trouble. Thread A has locked account a and waits for account b. Thread B has locked b and waits for a. Neither will let go of what it holds until it gets what the other holds, and both will wait forever. This standstill is called a deadlock. With live threads it looks like two transfers between the same pair of accounts going in opposite directions. So that the cell doesn’t hang until the sandbox runs out of time, it waits at most a second for the second lock.

For a second the cell says nothing: each transfer holds one lock and waits for the other. Then one of them runs out of patience, gives up and releases its lock, and the other transfer goes through. Which of the two gives up is a matter of chance. Remove timeout=1 and the cell hangs until the sandbox’s ten-second limit.

Four conditions

In 1971 Edward Coffman and his coauthors listed the conditions without which a deadlock can’t happen. All four can be seen in our cell.

1. Mutual exclusion. A resource belongs to one thread at a time: a lock has a single holder.
2. Hold and wait. A thread holds one thing and waits for another without letting go of the first.
3. No preemption. A resource can’t be taken away by force: only its holder releases a lock.
4. Circular wait. There is a cycle: A waits for B and B waits for A, or a longer one, in which A waits for B, B for C and C for A.

Draw a graph with an arrow from each thread to the thread that holds the lock it needs, and a deadlock is a cycle in that graph. We’ve known how to find cycles since Chapter 19, and that is how databases catch deadlocks: they build a wait-for graph and, when they find a cycle, abort one of the transactions. It is better still not to let deadlocks happen at all, and for that it is enough to break any one of the four conditions. Breaking the last one pays off most. Agree to always take locks in the same order, say by increasing account number. Then a cycle is impossible: the waiting arrows go only from smaller numbers to larger ones, and on such a staircase you never get back to where you started. How to do this for transfers you’ll work out in the task “A transfer without deadlock,” which has a catch.

Five philosophers

The most famous deadlock problem was devised by Edsger Dijkstra in 1965 as an exam exercise for students. In his version, five computers competed for tape drives. Soon he recast it as a meal, and its present name, the dining philosophers, came from Tony Hoare. Five philosophers sit at a round table, each with a plate in front of him, and between each pair of neighbors lies one fork, five in all. A philosopher alternates between thinking and eating, and he can eat only with two forks, the left one and the right one. Each behaves sensibly: he picks up the left fork, then the right, eats, and puts both down.

Sooner or later all five get hungry at almost the same moment, each picks up his left fork, and nobody has a right one. That is circular wait in its purest form. Each rule that cures it breaks a condition of its own. “Lower number first” is lock ordering: philosopher 4 reaches for fork 0 first, and the circle opens. “Both or none” removes hold and wait: a hungry philosopher never holds one fork while waiting for the other. A waiter who lets no more than four hungry philosophers to the table keeps the circle from closing: five can’t wait for each other if only four are at the table, and among four people with five forks, somebody is bound to get a pair.

The meal counters reveal another kind of trouble. The rule “both or none” prevents deadlock, but a philosopher whose two neighbors take turns eating may wait a long time for both forks to be free at once. This is the starvation of Chapter 18 and Chapter 37, only now in the literal sense.

The semaphore

The waiter needs a counter of free places at the table. Dijkstra invented that tool too, even before the philosophers: in 1962–1963, when his group was writing an operating system for the Dutch computer Electrologica X8. A semaphore is an integer with two indivisible operations. Operation P decreases it by one, and if it is already zero, waits until someone increases it. Operation V increases it and wakes one of the threads waiting. The letters come from Dutch words, though Dijkstra explained them differently at different times. The name comes from the railroad semaphore: an arm held out horizontally means stop, an arm tilted means proceed.

There are never more than two cars in the lot: the third waits at the gate until someone drives out. A lock is a semaphore with one place. The turnstile asyncio.Semaphore(3) from Chapter 37 is the same semaphore for coroutines, and the waiter at the philosophers’ table is a semaphore with four places. In the task “Dinner without deadlock” you can put one at the table yourself.

Hand to hand

Threads often split work along a chain: one takes orders and another fills them; one reads a file and another parses the lines. You could keep a shared list under a lock, but then two more problems have to be solved. When the list is empty, the worker must wait without spinning uselessly. When the worker falls behind and the list keeps growing, the supplier must wait, or memory runs out. This is the producer–consumer problem, and Dijkstra solved it with two semaphores, one counting free places and the other counting ready items, plus a lock to guard the list itself.

In Python all of this comes ready-made in queue.Queue. It is a message queue: put adds an item and waits if the queue is full, get takes one out and waits if it is empty, and all the locking is hidden inside.

The baker puts down four pies at once: the packer takes the first right away, leaving three on the belt, which is now full. From then on the baker puts down the next pie only when the packer frees a place, every 0.2 seconds. The slow consumer holds back the fast producer by itself, and nobody keeps more than three pies in memory. The last item, None, is an agreed signal for “end of work”: without it, the packer would wait forever.

You’ve met a belt like this before. The pipe from Chapter 36 works the same way, except that it lives in the kernel and carries bytes: in the sandbox it holds 65,536 bytes, and the writing process sleeps until the reading one makes room. You’ll build a belt of your own out of semaphores in the task “A belt of your own.”

A queue changes how you think about threads. As long as data is shared, every thread has to remember the locks, and one forgotten line breaks everything. When threads only pass messages to each other, every item has one owner at any moment, and there is nothing to share. The documentation of the Go language puts the rule this way: “Do not communicate by sharing memory; instead, share memory by communicating.” Whole languages and systems are built on this idea: Erlang processes, Go channels, actors. The course sandbox relies on it too: your program and the server share nothing, and they exchange lines of text through a pipe.

The copy on Earth

Now we have everything we need to take the Pathfinder failure apart. According to the account that spread across the internet in December 1997 (Mike Jones of Microsoft retold a talk by David Wilner, the chief technical officer of Wind River), the parts of the spacecraft exchanged data through an “information bus”: a shared area of memory whose access was guarded by a mutex. We need three of the players.

• Bus, a high-priority task, distributes data over the bus every eighth of a second. It needs the mutex, and it must finish before the next cycle.
• Weather, a low-priority task, now and then writes weather data to the bus. It needs the mutex too.
• Comms, medium-priority tasks, never touch the bus but run for a long time.

The VxWorks scheduler always gives the processor to the ready task with the highest priority. If the high-priority task hasn’t finished its cycle in time, the flight software decides that something serious has happened and reboots the computer. A guard of this kind is called a watchdog timer: it fixes nothing itself, it only returns the system to a known state. Here is the copy on Earth. Reproduce the fault.

A reset happens when three events coincide. The weather task has taken the mutex. While it is writing its data, comms wakes up: its priority is higher, so it takes the processor away from the weather task, which is still holding the mutex. The bus wakes up, needs the mutex, and waits for the weather task. The weather task waits for the processor, which comms is using. The task with the highest priority is stuck behind a task of medium priority, though the two share no mutex at all. This is called priority inversion: the priorities have been turned upside down, and the most important task in effect runs as the least important one.

The same story can be told more briefly, as a program. Time here is counted in ticks, and each task has a priority, an arrival tick and a list of steps; steps marked “B” need the bus mutex. On every tick the scheduler takes the task with the highest priority among those not waiting for the mutex.

The “CPU” line shows who ran on each tick. The bus ran on tick 0, the weather task took the mutex on tick 1, and comms arrived on tick 2 and took the processor for fourteen ticks. On tick 8 the bus woke up and began waiting for the mutex; its letter never appears in the line again. On tick 16 the watchdog sees that the bus hasn’t finished its last cycle and reboots the computer. Each step on its own is correct: the scheduler picks the ready task with the highest priority, and the mutex never lets two tasks in. Only the combination breaks.

The cure had been invented a few years before the flight. In 1990 Lui Sha, Ragunathan Rajkumar and John Lehoczky described priority inheritance. While a higher-priority task waits for the mutex that a task holds, the holder runs with the waiting task’s priority. For a moment the weather task gets the priority of the bus, and comms can no longer push it aside. Within a tick the weather task finishes writing, releases the mutex and drops straight back to its humble priority. Change INHERIT to True in the cell: a “w” appears in the line on tick 8, a “b” on tick 9, and all deadlines are met.

A patch flies to Mars

The Pathfinder failure resembles the other bugs of this chapter. You won’t find it reading the code line by line, because every line is correct. The bug lives in the order in which three tasks took their steps, and it shows itself rarely. Two things helped find it, and both are worth remembering. The first is the event trace left in a program that was already in flight: without it the engineers would have been guessing. The second is a copy of the system on which the failure can be reproduced as many times as you like. The tests of the task “The view counter” use the same method: they deliberately widen the race window so that the race strikes every time.

Processes, threads and the interpreter lock

Work can be divided among the threads of one process or among processes. Processes are kept apart by the virtual memory of Chapter 38: they have no shared variables, so there is nothing for a race to fight over, and a process that crashes doesn’t take its neighbors down with it. On the other hand, data has to be sent from process to process, through pipes, queues or files, and that takes time; starting a process also costs more than starting a thread. Threads are cheap and see everything at once, but someone has to look after the shared data. Many browsers, for example, keep tabs in separate processes so that one frozen page doesn’t bring down the rest.

Python adds a complication of its own to this choice. Standard CPython holds a global interpreter lock, the GIL: at any moment only one thread of a process executes bytecode. Every Python object keeps a count of the references to it (we saw it in Chapter 38), and the counts change on every assignment. Without a common lock, each of those changes would need protection of its own, and single-threaded programs would get slower. One lock for everything made the interpreter simple and fast for a single thread, and useless for computing on several cores at once. It doesn’t get in the way of waiting: a thread that sleeps or waits for a file or the network releases the GIL.

Four threads that split the computation into four parts finish no faster than one, and sometimes slower: they have one lock among them and keep handing it back and forth. Four half-second waits fit into half a second: while a thread sleeps, it has no need for the GIL. The rule for standard Python is this: threads for programs that do a lot of waiting (on the network, the disk, the user), processes for computation. In the course sandbox, processes won’t speed up computation either, but for a different reason: as we found in Chapter 35, the sandbox gets the time of only one core.

People have been trying to get rid of the interpreter lock for a long time. In 2023 Sam Gross’s proposal to make it optional (PEP 703) was accepted. Python 3.13, released in October 2024, came with a separate experimental build without the GIL, python3.13t. In 3.14, released a year later, that build became officially supported, but it is still separate: standard Python runs with the lock. In the free-threaded build four threads compute on four cores in parallel, while single-threaded code, according to the 3.14 documentation, runs roughly 5–10% slower. The course sandbox uses the standard build, so we can’t show it here.

Be clear about one thing: the GIL never protected your data. It guards the insides of the interpreter (reference counts, the internals of dictionaries), not your “read, add, write.” The view counter lost data with the GIL switched on. Without the GIL the race window only gets wider: threads run on different cores at the same moment, and counter += 1 loses increments the way it did on Python 3.9. Code written by the rules of this chapter, with locks on shared data or with queues in their place, is correct with the interpreter lock and without it.

Tasks

Four tasks, and the tests of each are built like the Pathfinder copy on Earth. Races and deadlocks are rare, so the tests don’t count on luck: they run your code many times, make the interpreter switch threads as often as it can, and swap in data and locks of their own that linger a little at the dangerous spot. If your code has a window, the tests will hit it.

What next

The view counter is accurate now, transfers neither lose money nor get stuck in a deadlock, and Pathfinder no longer reboots. But all of this lives in the memory of a process. Restart the server, and two million carefully counted views are gone. Pathfinder lost none of the data it had collected when it reset, but only because the power stayed on through the reboot: the data in memory, Reeves wrote, “is recovered so long as power is not lost.” The memory we built from flip-flops in Chapter 31 remembers only while current flows.

To survive a reboot, data is written to disk. And there a new kind of race is waiting, a race against electricity. A program is writing a file, and halfway through, the power goes out. What ends up on the disk: the old file, the new one, half of each, or nothing? Worse things happen too: the disk itself breaks, or someone mistakenly types a command that erases everything. How to rescue data in each of these cases is the subject of the next chapter, which is built as a rescue drill.