Part 2 of 7 · 3 min read
Race condition
In plain words: Two clerks update the same page of a paper ledger. Each reads the current total, adds a sale and writes the new total back. If both read 100 before either writes, and each adds 1, both write 101. One sale is lost. The analogy stops in one place: clerks can see each other's hands, but threads on different processors cannot see each other's half-finished steps.
A thread increments a counter with counter++, which looks like one step. The processor does it in three:
- Load the value of
counterfrom memory into a register. - Add 1 to the register.
- Store the register back to memory.
Here is a trace of two threads, A and B, when their steps interleave. The counter starts at 0:
| Step | Thread A | Thread B | Memory counter |
|---|---|---|---|
| 1 | load 0 into register | 0 | |
| 2 | load 0 into register | 0 | |
| 3 | add 1 (register is 1) | 0 | |
| 4 | add 1 (register is 1) | 0 | |
| 5 | store 1 | 1 | |
| 6 | store 1 | 1 |
Two increments were done and the counter is 1, not 2. An update was lost. The final result depends on how the steps are interleaved, which the programmer does not control.
A program shows it. Two threads each add 1 to a shared counter one million times:
#include <stdio.h>
#include <pthread.h>
#define N 1000000
static int counter;
static void *inc(void *a) { (void)a; for (int i = 0; i < N; i++) counter++; return NULL; }
int main(void) {
pthread_t t[2];
for (int i = 0; i < 2; i++) pthread_create(&t[i], NULL, inc, NULL);
for (int i = 0; i < 2; i++) pthread_join(t[i], NULL);
printf("expected %d, got %d\n", 2 * N, counter);
return 0;
}
Four runs on the test machine (two processors) printed:
expected 2000000, got 1087857
expected 2000000, got 1038807
expected 2000000, got 1012125
expected 2000000, got 1140485
Almost half of the increments were lost, and the answer is different each time. Such a bug is also hard to catch: with one thread it never appears, and a program with fewer iterations can pass every test.
Race condition
A race condition is a flaw in which the result of a program depends on the relative timing of its threads or processes, usually because two of them access the same data at the same time and at least one of them changes it.
Example: two threads each execute counter++ on a shared variable; if their load and store steps interleave, one increment is lost.
Check yourself:
1. Into which three steps does counter++ split?
2. In the trace, what value does thread B store, and why?
3. Why can a program with few iterations pass every test?