Race Conditions

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.

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.

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.

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.