--- title: 'Race Conditions' source: 'https://academia.sh/en/courses/operating-system-concepts/race-conditions' course: 'Operating System Concepts' language: en updated: '2026-08-17T18:08:19+00:00' license: 'CC BY-SA 4.0' --- # Race Conditions All interleavings of the read-increment-write triplet, the number of interleavings that produce a wrong result, and how the scheduler's quantum makes the error invisible. The previous lesson measured the scheduler's cost in time: as the quantum shrank, context switching increased and the run took longer. There, the quantum was a **performance** setting. This lesson brings out a second face of the same setting — the quantum also determines **in which orders** the steps of two threads can interleave, and therefore whether the program **produces a correct result** at all. This is where the course must pay off its most valuable claim: **a correct output does not mean a correct program.** The measurement below shows this once, in numbers. The machine being measured is, again, the machine from the shared definition; no real thread is ever created, and no real time is measured. ## One Increment Is Three Steps Incrementing a shared counter is a single line in the source text. It is not a single step in execution: the value is **read**, **incremented** by one, and **written** back. The scheduler can switch to another thread between these three steps. **CC1.** A counter increment is three separate steps; execution can be split between them. **CC2.** There are two threads, each incrementing the counter once; the expected result is **2**. **CC3.** Reads and writes are instantaneous; two steps never coincide in the same time unit. Execution can always be described by an **interleaving** — a single ordering of the two step sequences. The shared definition's `counter_run` routine takes an interleaving and returns the counter value it produces. An interleaving is a sequence of 0s and 1s showing which thread advances at each step. ```python def counter_run(pattern: list[int]) -> int: """Two threads each do read-increment-write once. pattern: who advances at each step.""" counter, local = 0, {0: None, 1: None} stage = {0: 0, 1: 0} for who in pattern: s = stage[who] if s == 0: local[who] = counter # read elif s == 1: local[who] = local[who] + 1 # increment else: counter = local[who] # write stage[who] = s + 1 return counter def interleavings(a: int, b: int) -> list[list[int]]: """All interleavings of two sequences of length a and b.""" if a == 0: return [[1] * b] if b == 0: return [[0] * a] left = [[0] + s for s in interleavings(a - 1, b)] right = [[1] + s for s in interleavings(a, b - 1)] return left + right for name, pattern in (("sequential", [0, 0, 0, 1, 1, 1]), ("fully interleaved", [0, 1, 0, 1, 0, 1]), ("partial", [0, 0, 1, 1, 1, 0])): print(f"{name:18s} {pattern} -> counter {counter_run(pattern)}") everything = interleavings(3, 3) correct = [d for d in everything if counter_run(d) == 2] wrong = len(everything) - len(correct) print() print(f"interleavings {len(everything)} | correct {len(correct)} | wrong {wrong} " f"| wrong ratio {wrong / len(everything):.4f}") print("correct ones:", correct) ``` ``` sequential [0, 0, 0, 1, 1, 1] -> counter 2 fully interleaved [0, 1, 0, 1, 0, 1] -> counter 1 partial [0, 0, 1, 1, 1, 0] -> counter 1 interleavings 20 | correct 2 | wrong 18 | wrong ratio 0.9000 correct ones: [[0, 0, 0, 1, 1, 1], [1, 1, 1, 0, 0, 0]] ``` Two three-step sequences have **20** interleavings. Only **2** of them produce the expected result; **18**, that is **ninety percent** of the execution orders, leave the counter at 1. The two interleavings that do produce the correct result are already saying the same thing: one thread finishes completely before the other begins. ## Where the Loss Happens It is enough to trace the interleaving `[0, 1, 0, 1, 0, 1]` step by step. The first thread reads the counter and sees **0**. The second thread also reads and sees **0** as well — the first thread's write has not happened yet. Both set their local copy to 1. The first writes, and the counter becomes 1; the second writes, and the counter becomes 1 again. The second write **overwrote** the first thread's result. This is called a **race condition**: the result depending on the order of the steps rather than on the work itself. The programmer does not choose the order of the steps; the scheduler does. This is why a race condition is a defect that cannot be seen by reading the source text — the source text has only **one** increment line, and that line is correct. The region where the counter breaks is called the **critical section**: the sequence of steps in which two threads must never both be present at the same time. Here, the critical section is three steps. ## Two Distinct Defects The situation above stacks two defects on top of each other, and the two must not be confused. A **data race** is two unordered accesses to the same memory location where at least one is a write. It is a structural property: it is detected by looking at the accesses, not at the result. A **race condition**, by contrast, is the result depending on step order; it is a correctness property. The counter example has both at once. But one does not require the other. If a container is locked on every access, there is no data race; yet if the sequence "check whether it is empty, and if not, take an element" consists of two separately locked operations, another thread can take the last element between the two, and the result still depends on order. The data race is gone; the race condition remains. The practical consequence of this distinction is: **protecting each access separately is not enough.** What needs protection is not the access but **the span over which an invariant could be violated** — the boundary of the critical section is drawn by the programmer, not by a tool. ## The Quantum Constrains Interleaving The scheduler from the previous lesson does not switch threads at every step; it holds a thread for the length of the **quantum** and releases it once the quantum is used up. So not all 20 interleavings are reachable. **CC4.** The scheduler switches only at quantum boundaries; there is no preemption within a quantum. **CC5.** What is measured is not a probability but whether an interleaving is **reachable**: that interleaving either can or cannot be produced by this scheduler. The shared definition's `quantum_interleavings` routine counts the interleavings producible with a given quantum. ```python def counter_run(pattern: list[int]) -> int: counter, local = 0, {0: None, 1: None} stage = {0: 0, 1: 0} for who in pattern: s = stage[who] if s == 0: local[who] = counter elif s == 1: local[who] = local[who] + 1 else: counter = local[who] stage[who] = s + 1 return counter def quantum_interleavings(steps: int, quantum: int) -> list[list[int]]: """Interleavings reachable when the scheduler switches only every `quantum` steps.""" result = [] def walk(remaining_a, remaining_b, current, sequence): if not remaining_a and not remaining_b: result.append(list(sequence)) return for candidate in (0, 1): remaining = remaining_a if candidate == 0 else remaining_b if not remaining: continue n = min(quantum, remaining) if candidate != current else min(quantum, remaining) sequence.extend([candidate] * n) walk(remaining_a - n if candidate == 0 else remaining_a, remaining_b - n if candidate == 1 else remaining_b, candidate, sequence) del sequence[len(sequence) - n:] walk(steps, steps, None, []) distinct = [] for d in result: if d not in distinct: distinct.append(d) return distinct print("quantum reachable wrong wrong ratio") for quantum in (1, 2, 3, 4, 5): reachable = quantum_interleavings(3, quantum) wrong = sum(1 for d in reachable if counter_run(d) != 2) print(f" {quantum:3d} {len(reachable):9d} {wrong:5d} " f"{wrong / len(reachable):11.4f}") print() print("quantum 2 reachable:") for d in quantum_interleavings(3, 2): print(" ", d, "-> counter", counter_run(d)) print("quantum 3 reachable:") for d in quantum_interleavings(3, 3): print(" ", d, "-> counter", counter_run(d)) ``` ``` quantum reachable wrong wrong ratio 1 20 18 0.9000 2 6 4 0.6667 3 2 0 0.0000 4 2 0 0.0000 5 2 0 0.0000 quantum 2 reachable: [0, 0, 0, 1, 1, 1] -> counter 2 [0, 0, 1, 1, 0, 1] -> counter 1 [0, 0, 1, 1, 1, 0] -> counter 1 [1, 1, 0, 0, 0, 1] -> counter 1 [1, 1, 0, 0, 1, 0] -> counter 1 [1, 1, 1, 0, 0, 0] -> counter 2 quantum 3 reachable: [0, 0, 0, 1, 1, 1] -> counter 2 [1, 1, 1, 0, 0, 0] -> counter 2 ``` At quantum 1, the scheduler can switch at every step, and **all 20 interleavings** are reachable; the wrong ratio is **0.9000**. At quantum 2, the reachable interleavings drop to **6**, wrong is **4**, and the ratio is **0.6667**. At quantum 3, the reachable interleavings drop to **2**, and **none of them are wrong**. ## The Error Did Not Disappear, It Became Invisible The two interleavings that remain at quantum 3 are `[0, 0, 0, 1, 1, 1]` and `[1, 1, 1, 0, 0, 0]`. Both run one thread's three steps uninterrupted. Because the quantum is **greater than or equal to** the critical section, no switch can land in the middle of the critical section. How this result is read is the course's distinguishing point. The program **has not changed**: the counter is still unprotected, the increment is still three steps, the critical section is still open. The only thing that changed is **the scheduler's setting**. If run a thousand times at quantum 3, it would print 2 a thousand times; these runs produce **no evidence at all** that the program is correct — they only show that the error is unreachable at that setting. The setting is not a guarantee. Drop to quantum 2, and the wrong result **comes back immediately**: 4 of the 6 interleavings are broken. If the critical section grows from three steps to four, quantum 3 is no longer enough either. And once a second core — the subject of the next lesson — is added, the quantum's protection disappears entirely, because the two threads then genuinely advance at the same time. The rule that follows is this: **the existence of a concurrency error is tested not by output but by the set of reachable interleavings.** Output is a sample; the set is proof. ## Run Count Is Not Proof The quantum is not the only way to forbid a switch; making it **rare** produces the same result. A real critical section is a few steps, and a real quantum is thousands of steps; the probability of a switch landing on exactly those few steps is small. Small does not mean absent, but it **erases the observation**. **CC6.** The switch probability is per step and constant throughout the run; sampling changes not the reachable set but how often that set is visited. The measurement below counts this. At every step, the scheduler switches to the other thread with a certain probability; two thousand runs are performed and the wrong results are counted. The generator is the shared definition's generator, with the same seed; the result is deterministic. ```python SEED = 20260218 def generator(seed): """Deterministic pseudo-random generator. The same seed gives the same sequence.""" d = seed def next_val(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_val def counter_run(pattern: list[int]) -> int: counter, local = 0, {0: None, 1: None} stage = {0: 0, 1: 0} for who in pattern: s = stage[who] if s == 0: local[who] = counter elif s == 1: local[who] = local[who] + 1 else: counter = local[who] stage[who] = s + 1 return counter def sample_run(r, per_ten_thousand: int) -> list[int]: """The scheduler switches to the other thread with probability `per_ten_thousand` at each step.""" remaining, who, pattern = {0: 3, 1: 3}, 0, [] while remaining[0] or remaining[1]: if not remaining[who] or (remaining[1 - who] and r(10000) < per_ten_thousand): who = 1 - who pattern.append(who) remaining[who] -= 1 return pattern print("switch probability runs wrong observed wrong ratio") for per_ten_thousand in (5000, 1000, 100, 10, 1): r = generator(SEED) wrong = sum(1 for _ in range(2000) if counter_run(sample_run(r, per_ten_thousand)) != 2) print(f" per 10000 {per_ten_thousand:6d} 2000 {wrong:6d} {wrong / 2000:21.4f}") ``` ``` switch probability runs wrong observed wrong ratio per 10000 5000 2000 1519 0.7595 per 10000 1000 2000 346 0.1730 per 10000 100 2000 40 0.0200 per 10000 10 2000 1 0.0005 per 10000 1 2000 0 0.0000 ``` The last row is the lesson's sentence: in two thousand of two thousand runs the counter comes out 2 — and the program is still wrong. The rows in between are just as instructive — at a probability of ten per ten thousand, only **1** wrong result is seen in two thousand runs. A test that happens to catch this single observation will, if run again, most likely come back clean, and the bug will be considered "fixed." The reachable interleaving set did not change across any of these five rows: **20 interleavings, 18 wrong**. What changed is only how often the sample visits that set. Increasing the run count is not a solution; seeing the error at its **expected value** at a probability of one per ten thousand requires hundreds of thousands of runs, and even that number produces no proof — only observation. ## Three Numbers | Metric | Baseline without abstraction | Setup with abstraction | Cost | |---|---|---|---| | Execution order | single thread, **1** order | two threads, **20** interleavings | 19 extra orders | | Wrong result | **0** | **18** | 18 broken executions | | Wrong ratio | 0.0000 | 0.9000 | — | A fourth row shows what the quantum setting does: at quantum 3, reachable interleavings are **2**, wrong is **0**, ratio **0.0000**. This row enters the table not as a **fix** but as a measure of **visibility**. The error itself is still sitting in 18 interleavings; those interleavings cannot be reached with this setting. ## The Real Fix Is Exclusion, Not a Setting What eliminates a race condition cannot be how the scheduler happens to be set, because the scheduler is not under the program's control. What eliminates it is **mutual exclusion**: protecting the critical section so that it admits at most one thread at any given moment. The shared definition's `counter_run` routine carries this as an option: when `lock=True` is passed, the critical section is treated as indivisible, and the routine returns **2** regardless of the interleaving. All twenty of the twenty interleavings become correct. What is gained is not narrowing the reachable set but **making every interleaving in that set correct**. This has a cost, and that cost is the next lesson's measurement: once the critical section is serialized, threads wait for one another, waiting steps accumulate, and processor utilization drops. ## Summary - Incrementing a shared counter is three steps — read, increment, write; execution can be split between them, and when it is, one write overwrites the other. - Two threads' three-step sequences have **20** interleavings; **18** produce a wrong result, a wrong ratio of **0.9000**. - The scheduler's quantum narrows the reachable interleaving set: 20 interleavings are reachable at quantum 1, 6 at quantum 2, and 2 at quantum 3. - When the quantum is greater than or equal to the critical section, **none** of the reachable interleavings are wrong; the program has not changed, only the error has become unreachable. - A concurrency error cannot be tested by output; testing is done over the reachable interleaving set. ## Next Step This lesson set up the problem and named the fix: mutual exclusion. The next lesson builds that fix and **counts its cost**. Threads with a 10-step critical section and 10 steps of non-critical work will be run under a mutex; it will be shown that a single thread takes 20 time units, that a second thread raises this to 29, a fourth to 47, and an eighth to 83, and that the waiting steps rise from zero to 252. How a semaphore brings that number down, and what it relaxes in doing so, sits in the same table.