Before you start
- Process states and the timer interrupt (lesson Processes and their states).
- Round Robin and the quantum (lesson CPU scheduler).
- Reading a three-line pseudo-assembly listing. No programming needed.
Theory
A thread is a sequence of instructions being executed inside a process. A process can have several threads, and they all share its memory (code, global variables, heap) and its open files. What each thread keeps to itself are its registers, its program counter and its stack.
The operating system schedules threads like it schedules processes: there is one CPU, one thread uses it at a time, and the timer can take it away when its quantum ends. In this lesson the quantum is counted in instructions.
A line like counter++ on a global variable looks like one step, but the CPU runs three instructions:
| Instruction | What it does |
|---|---|
load |
reg = counter: copies the value from memory into one of the thread’s registers. |
add |
reg = reg + 1: only the register changes; memory stays the same. |
store |
counter = reg: copies the register back to memory. |
When the system switches threads, it saves the registers of the outgoing thread and restores them when it comes back. Memory is not saved or restored: it is shared.
Example: one thread and
counter = 5. Afterload, the register holds 5. Afteradd, the register holds 6 andcounteris still 5. Afterstore,counteris 6.
Predict
The board below starts with the Two increments scenario: two threads, T1 and T2, each run counter++ once, starting from counter = 0. There is one CPU and the timer switches threads every 2 instructions.
What will counter hold when both have finished? Pick a value in the Your prediction panel before you run.
Run
Threads and program
As three instructions, another thread can slip in between them. Atomic, it is one indivisible instruction.
Who decides the interleaving
Round Robin: each thread runs at most one quantum of instructions, then the next one gets its turn.
Your prediction
What will counter hold when every thread has finished? It starts at 0.
The board before the first turn
One CPU. The timer switches threads every 2 instructions.
Shared memory
counter 0
- WaitingRegister empty
load reg = counter, next instructionadd reg = reg + 1store counter = reg
- WaitingRegister empty
load reg = counter, next instructionadd reg = reg + 1store counter = reg
What happened this turn
Press Run or step one instruction at a time. Here you will see what each thread does and with which value.
Writes to counter
Nobody has written to counter yet.
A store is stale when counter changed between the thread's read and its write: it overwrites what others wrote in the meantime, usually their increments.
As it runs, watch three moments:
- After instruction 2, what does T1’s register hold? And
counter? - At instruction 3, T2 reads
counter. Is the value it reads up to date? - At instruction 6, T2 writes. What was in
counterjust before?
Below the board, the write log records who wrote, what it had read and what memory held just before.
Explain
This stage opens when you run the simulation to the end.
Go to the simulationThe right answer was 1. Two increments were requested and only one survives.
counter++ is not an indivisible step. After instruction 2, T1 has 1 in its register but has not written it yet: counter is still 0. The timer interrupts it right there. T2 reads that 0, adds 1 and also ends up with 1. In the end both write 1. T2’s store is stale: it computed it from a value that was no longer current, and it erases T1’s increment.
One CPU is enough. The threads did not need to run at the same time on two cores. It was enough for the timer to cut T1 between its load and its store.
This is called a race condition: the result depends on the order in which the scheduler interleaves the threads. The piece of code that touches the shared data, here the three instructions from load to store, is a critical section. What we need is mutual exclusion: at most one thread inside the critical section at a time.
Passing the tests proves nothing. With quantum 3, each turn holds a whole counter++ and the result is 2. But nothing in the code guarantees it: another thread, a page fault or an interrupt shifts the turns, and the race is back. That is why the result is called indeterminate: the same program, with the same input, gives 1 or 2.
A longer quantum does not fix it. On Three threads with quantum 4, the turns cut the second increment between load and store, and 2 out of 6 are lost. Fewer interruptions make the race rarer, not impossible.
It can go very wrong. On Three threads with quantum 2, six increments leave counter at 2. A single stale store can erase several increments at once: all the ones others made between its read and its write. With two threads doing n increments each (n ≥ 2), the result can drop to 2.
What threads share. T1’s 1 was safe in its register while T2 ran, because each thread has its own registers and the system saves them on every switch. counter, on the other hand, exists once in memory. That is exactly why there is a race.
The hardware’s answer: atomic instructions. Processors offer read-modify-write instructions that complete without another thread touching that memory in between: lock xadd on x86, atomic_fetch_add in C11, std::atomic<int>::fetch_add in C++, AtomicInteger in Java. With them counter++ is a single indivisible operation, and no interleaving can split it. Critical sections longer than one instruction need locks, the topic of the next module.
In real systems. With several cores threads truly run in parallel and caches add surprises (memory reordering), but the lost update already appears with one core. In C and C++, two unsynchronized accesses to the same variable, at least one of them a write, are a data race and the behavior is undefined; tools like ThreadSanitizer detect them. In Python, counter += 1 is several bytecode instructions and is not atomic either; the build without the GIL (officially supported since Python 3.14) only makes the race show up more often.
Experiment
This stage opens when you run the simulation to the end.
Go to the simulationUse the board to solve these challenges. Each one has a possible solution when you expand it.
1. Make Two increments end at 2 without making counter++ atomic.
Set the quantum to 3 (or more). Each turn holds a whole load, add, store, so no thread ever reads an out-of-date value. It is correct by luck: it depends on where the turns fall.
2. Make Three threads lose increments with a quantum larger than 3.
Quantum 4 (or 5): counter ends at 4 and 2 are lost. Turns of 4 instructions cut the second increment between load and store. T1’s stale store erases two increments at once, T2’s and T3’s.
3. With two threads doing three increments each, make counter end at 2.
Choose You decide and build this order (or load Worst case): T1; T2 six times; T1 twice; T2; T1 six times; T2 twice. T1 reads 0 and holds it while T2 makes two whole increments; writing 1 erases them. Then T2 reads that 1 and waits while T1 makes its last two increments; writing 2 erases them.
4. Make every interleaving give the right answer.
Choose Atomic. counter++ becomes a single indivisible instruction: there is no point where another thread can slip in between the read and the write.
Check
This stage opens when you run the simulation to the end.
Go to the simulationGo deeper
- Locks and semaphores. To protect critical sections longer than one instruction, the next module builds mutual exclusion.
- Memory reordering. On multicore processors, one thread’s writes can be seen in a different order from another core. The C11 and Java memory models say which orders are guaranteed.
- Check-then-act.
if (!exists(f)) create(f)has a race even if each call is atomic: another thread can create the file between the check and the creation. - Race detectors. ThreadSanitizer (
-fsanitize=threadin GCC and Clang) watches memory accesses and reports the data races that happen during a run.
Further reading:
- Arpaci-Dusseau and Arpaci-Dusseau, Operating Systems: Three Easy Pieces, ch. 26, sections 26.3 and 26.4. Free online.
- Silberschatz, Galvin and Gagne, Operating System Concepts, 10th ed., sections 4.1 and 6.1.
- cppreference, Multi-threaded executions and data races: en.cppreference.com.
- PEP 779, criteria for supported status for free-threaded Python: peps.python.org.