Threads & Synchronization

A race condition happens when two threads read and write the same variable without coordinating, so the result depends on which thread the scheduler runs next. The textbook case is counter = counter + 1: one line of Python, three machine steps, and a window in the middle where a second thread can read a number that is about to be wrong.

Two threads, three increments each, one shared counter. The program asks for 6. Under the default schedule in this lesson it finishes at 4. Nothing crashes, nothing logs a warning, and both threads run exactly the instructions they were written to run. Two increments just stop existing, and the only evidence is a number that is too small.

Two more runs follow from that one: the same schedule under a mutex, which ends at 6, and two locks taken in opposite orders, which ends nowhere at all.

How a Race Condition Happens

An ordinary counter = counter + 1 does not reach the hardware as one indivisible act. It fetches the value into a register, adds there, and writes the register back. Three steps, and the middle one operates on a private copy that no other thread can see. Processors do have dedicated atomic read-modify-write instructions, and an atomic integer type is exactly how you ask for one. But you have to ask. A short line of ordinary code does not get you one. That is the whole mechanism, and everything else in this lesson is a consequence of it.

The scheduler is allowed to take the CPU away between any two machine steps. It is not being adversarial. On a single core, running two threads means interleaving them, and the operating system chooses the switch points based on timer interrupts, other processes, and things you have no visibility into. What it cannot do is look inside your loop and notice that steps six through eight would rather be left alone.

So picture the failure directly. Thread 1 fetches counter, which reads 0, into its private tmp. The scheduler switches. Thread 2 fetches counter, still 0, adds one, and writes 1 back. Its increment is real and complete. The scheduler switches back. Thread 1 now adds one to the number it is holding, which is still 0, gets 1, and writes 1 to counter. The counter already said 1. Thread 2's work has been overwritten by a thread that was working from a snapshot taken before it.

Notice what did not go wrong. No instruction failed. No memory was corrupted. Thread 1 performed a perfectly legal store of a perfectly legal value. The bug is that the value was computed from a counter that no longer existed by the time it was written, and there is no layer in the machine whose job it is to notice that.

Threads and Synchronization Step by Step

The default run uses the schedule 1 222 11 222 111 2 111 22, one digit per machine step: 1 gives the CPU to T1, 2 gives it to T2. Eighteen machine steps, seven context switches. Each thread runs tmp = counter, tmp = tmp + 1, counter = tmp, three times over.

1. T1 loads. tmp₁ = counter = 0. Memory is untouched; T1 is holding a copy.
2. Context switch to T2. T1's register keeps its 0. Registers travel with their thread, which is exactly why the stale value survives the switch.
3. T2 loads. tmp₂ = counter = 0. Both threads now hold 0 and neither can see the other's register.
4. T2 adds. tmp₂ = 1. counter is still 0. Nothing shared has changed.
5. T2 stores. counter = 1. This increment lands. One of the six is done.
6. Context switch back to T1.
7. T1 adds. tmp₁ = 0 + 1 = 1. This is the beat that decides the run: T1's register was loaded when counter was 0, and counter is now 1, so T1 is computing an answer that was correct a moment ago and is not correct now.
8. T1 stores. counter = 1, over a counter that already read 1. T2's finished increment is erased. Two stores have executed and the counter has advanced by one.

From here the run repeats the same shapes, so the animation compresses them into one beat each.

9. T2 runs a whole increment: counter = 2.
10. T1 runs a whole increment: counter = 3.
11. T2 loads 3 and is preempted before it can use it.
12. T1 runs its last whole increment: counter = 4, and T1 is finished.
13. T2 finally adds and stores using the 3 it loaded back at step 11, writing 4 over a counter that already read 4. The second update is lost.

Final tally: six stores executed, counter reads 4, two increments gone. The strip along the bottom of the animation is the autopsy. Each slot is one machine step coloured by the thread that ran it, and the two slots marked with an X are the stores that erased somebody's work. They occur at machine steps 6 and 18, twelve step positions apart, which is the honest picture: this is not a rare exotic failure, it is what happens whenever a switch lands in the middle of three instructions.

What a Mutex Buys, and What It Costs

Switch the lesson to the Mutex variant and the schedule string stays byte-for-byte the same. That does not buy an identical run, and it is worth being precise about why: the locked program executes more instructions per iteration, and a blocked attempt still consumes a slot, so those eighteen characters wrap around and drive thirty-five machine steps with fourteen switches instead of seven. The comparison is not "same switch points, different outcome". It is better than that. The locked run is switched through twice as hard as the run that lost two updates, and the counter still ends at exactly 6.

A mutex prevents cooperating threads from entering the protected critical section together; it does not prevent the owner from being preempted. The lock has one owner. A thread that reaches lock.acquire() while somebody else holds it does not get to run its load, and does not get to spin through the section; it blocks, joins a wait queue, and the CPU goes back to the holder. Watch the trace and you will see the switch at step two still happen. T2 gets the CPU. The only instruction it can execute is the one that parks it.

That is the property worth taking away: critical sections guarded by the same mutex cannot overlap, although the owner may be paused and unrelated code may run. So the counter is right by construction, for every schedule, not just for the one you tested on.

The cost shows up in the same trace. In this run five separate slots of CPU time are spent by a thread discovering that it cannot work yet. The lock did not remove the scheduler's switches; it converted them from corruption into waiting. That trade is almost always worth it, but it is a trade, and it is why the interesting engineering question is how small you can make the critical section, not whether to have one.

Which primitive, then. A lone counter with nothing else riding on it is the case atomic integers exist for: an atomic read-modify-write operation, without a user-managed mutex. Whether the implementation is lock-free or uses one machine instruction depends on the type and platform. The moment the thing you are protecting spans more than one variable, say a balance and its transaction log, or a queue and its length, per-field atomicity buys you nothing, because the invariant is the relationship between the fields, and the design must coordinate the whole invariant, for example with a critical section covering the update. Separate atomic fields alone do not make a compound transaction atomic. And once one thread needs two locks, correctness stops being local: the order they are taken in becomes a property of the entire program, which is the next section.

When Locks Deadlock

The Two locks variant is the failure mode the lock brings with it. Two locks, lock_a and lock_b, and two functions that take them in opposite orders: t1 takes A then B, t2 takes B then A. Four machine steps is all it needs.

T1 takes lock_a. A switch lands. T2 takes lock_b. T2 then asks for lock_a, which T1 holds, and blocks. The CPU goes back to T1, which asks for lock_b, which T2 holds, and blocks too. Now every thread in the program is waiting for a lock held by a thread that is waiting. Nothing will release anything, because releasing comes after acquiring, and neither thread will ever finish acquiring. The counter never reaches 1.

Drawn as a graph of "who is waiting for what", the failure is a cycle: T1 → lock_b → T2 → lock_a → T1. That is the general definition, and it hands you the general fix. Pick a global order for your locks and make every thread acquire them in that order. Then a cycle is impossible, because a cycle requires somebody to have gone the other way round. The fix here is one line: have t2 take lock_a first, like t1 does. The loser of the race for lock_a blocks while holding nothing, and the winner walks straight through.

Edge Cases

• A lucky schedule. Run the unsynchronized code with 111222111222111222, which switches only at increment boundaries, and it finishes at 6 with no lock at all. The code did not become correct. In real runs the OS picks the schedule, which you rarely control or reproduce; this time it happened to be kind. This is the single most dangerous property of a race condition and the reason "it worked when I ran it" is not evidence.
• One store can erase several increments. With the schedule 122222222211111111, T1 loads 0, T2 runs all three of its increments to completion, and T1's one stale store drops the counter from 3 back to 1. The run ends at 3. The damage a stale write does is not one increment; it is however many landed while the register was sitting there.
• A thread that blocks costs CPU time anyway. In the mutex run, an attempt to acquire a held lock still consumes a slot on the strip. It is drawn as one, because pretending blocked threads are free is how people end up surprised by lock contention.
• A schedule shorter than the run repeats. Type 12 and the two threads alternate strictly for all eighteen steps. Type 1 and T1 runs to completion first, because a schedule slot naming a finished (or blocked) thread falls through to the other one.
• Two threads, not many. Every failure here reproduces with the minimum: two threads, one variable. More threads do not change the mechanism; how often it fires depends on load and scheduling.

Common Mistakes

• Assuming counter += 1 is atomic because it is one line. Line count is a property of your source file. Atomicity is a property of the instruction set. In CPython the GIL makes some of these operations look atomic some of the time, which is worse than if it never did, because your code passes for years and then fails on a different runtime.
• Protecting the write but not the read. A lock taken around counter = tmp alone changes nothing: the stale value was already in the register before the lock was acquired. The critical section must contain the read and the write, because the invariant being protected spans both.
• Concluding a test passed means there is no race. A green test run tells you one schedule out of an astronomical number did not trip the bug. Race conditions are found by reasoning about the code and by tools built for it, not by rerunning it.
• Fixing a deadlock by adding a timeout. A timeout turns a hang into an intermittent failure — and, if callers retry, possibly a retry storm. The wait-for cycle is still there. Order your locks.
• Making the critical section the whole function. The correct-and-slow fix is real, and it is the first thing to reach for, but a lock held across I/O or a long computation serializes the program you paid a threading library to parallelize. Shrink the section to the shared state it protects.

A Note on Simplification

This is a scale model, not an emulator. It runs one CPU core, so what you are watching is interleaving rather than true parallelism; on real multicore hardware two threads can execute the same instant, which gives contending updates more chances to overlap but does not change their kind. Every pseudo-instruction here is atomic, and there are no caches and no instruction reordering, both of which give real hardware additional ways to surprise you (which language memory models and synchronization primitives address; C/C++ volatile alone does not provide atomicity or thread synchronization). The mutex is modelled as ownership plus a FIFO wait queue, with no spinning, no futex, and no fairness guarantees beyond the queue. Semaphores and condition variables are cousins of the mutex shown here rather than separate ideas: a mutex is a binary semaphore with an owner, and a condition variable is the mechanism for waiting on a predicate instead of on a lock. Neither is animated in this lesson.