Races and why locks exist

Two threads add 1 to the same counter, and the counter ends up wrong, with no error and no crash. The line x += 1 is not one step but three, and the order in which two threads interleave those steps decides the answer. On 1,085 up days of SPY, 542 updates vanish; a lock brings them all back.

A processor cannot add to a value that lives in memory. It loads the value into a register, adds to the register, and stores the register back. So x += 1 is load x, add 1, store x. One thread alone does the three in a row and nothing can go wrong. With two threads, the machine may run a step of one, then a step of the other, in any order. To see this we write a tiny machine. A thread is a list of steps, each with its own register; the threads share a dictionary of named values. The function execute runs one step of one thread. Below we play the six steps of two threads by hand, one step each in turn.

def execute(op, shared, regs, locks, tid):    kind = op[0]    if kind == "load":        regs[tid] = shared.get(op[1], 0)    elif kind == "add":        regs[tid] += op[1]    elif kind == "store":        shared[op[1]] = regs[tid]    elif kind == "lock":        if op[1] in locks:            return False        locks[op[1]] = tid    elif kind == "unlock":        del locks[op[1]]    return Trueshared, regs, locks = {"x": 0}, {0: 0, 1: 0}, {}turns = [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2), (1, 2)]1for tid, step in turns:    execute(INCREMENT[step], shared, regs, locks, tid)    print("thread", tid, INCREMENT[step], "->", shared, regs)

thread 0 ('load', 'x') -> {'x': 0} {0: 0, 1: 0}
thread 1 ('load', 'x') -> {'x': 0} {0: 0, 1: 0}
thread 0 ('add', 1) -> {'x': 0} {0: 1, 1: 0}
thread 1 ('add', 1) -> {'x': 0} {0: 1, 1: 1}
thread 0 ('store', 'x') -> {'x': 1} {0: 1, 1: 1}
thread 1 ('store', 'x') -> {'x': 1} {0: 1, 1: 1}

1. 1Both threads load before either stores: each register holds 0.

Read the output line by line. Thread 0 loads 0, thread 1 loads 0 as well (thread 0 has not stored yet), both add 1 to a register that holds 0, and both store 1. Two threads each did their x += 1, yet x is 1, not 2. One update was lost. Nothing was wrong with either thread's code; the bug exists only in this order of steps.

In the real world the schedule is chosen by the operating system and changes from run to run, which is why a race is so hard to reproduce. In our machine we choose it. A schedule is a list of thread numbers, and run gives the thread named by each entry one turn. Two simple schedules matter. In the serial schedule thread 0 runs all its steps, then thread 1: it is what we hope for. In the round-robin schedule the threads take one step each in turn: it is the worst case for our counter, because the steps of the two threads overlap everywhere. The function lost_updates compares what the increments should have added with what the counter shows.

def run(programs, schedule, shared=None):    shared = dict(shared or {})    regs = {tid: 0 for tid in range(len(programs))}    pcs = [0] * len(programs)    locks = {}    for tid in schedule:        if pcs[tid] < len(programs[tid]) and execute(programs[tid][pcs[tid]], shared, regs, locks, tid):            pcs[tid] += 1    while any(pcs[t] < len(programs[t]) for t in range(len(programs))):        progress = False        for tid in range(len(programs)):            if pcs[tid] < len(programs[tid]) and execute(programs[tid][pcs[tid]], shared, regs, locks, tid):                pcs[tid] += 1                progress = True        if not progress:            raise RuntimeError("deadlock")    return shareddef serial_schedule(programs):    return [tid for tid, program in enumerate(programs) for _ in program]def round_robin_schedule(programs):    longest = max((len(program) for program in programs), default=0)    return [tid for step in range(longest) for tid, program in enumerate(programs) if step < len(program)]def lost_updates(programs, schedule, name="x"):    expected = sum(op[1] for program in programs for op in program if op[0] == "add")    return expected - run(programs, schedule).get(name, 0)two = [INCREMENT, INCREMENT]print(serial_schedule(two), run(two, serial_schedule(two)))print(round_robin_schedule(two), run(two, round_robin_schedule(two)))print("lost:", lost_updates(two, round_robin_schedule(two)))

[0, 0, 0, 1, 1, 1] {'x': 2}
[0, 1, 0, 1, 0, 1] {'x': 1}
lost: 1

The serial schedule [0, 0, 0, 1, 1, 1] gives 2; the round-robin schedule [0, 1, 0, 1, 0, 1] gives 1 and loses one update. Notice what run does when the schedule ends early: the unfinished threads keep taking turns, one step each in thread order, so every program always finishes. Also notice that a finished thread ignores its turns, so any list of thread numbers is a valid schedule.

A lock fixes the race by forbidding the overlap. A thread takes the lock before load, and releases it after store. A second thread that asks for the lock in between cannot get it: its turn does nothing, and it stays at the same step until the lock is free. The steps between lock and unlock therefore run as one block, and no other thread can slip in. The function counter_program builds the program of a thread that increments a counter, with or without the lock. Locks bring a new danger, shown at the end of the code: two threads that take two locks in opposite orders can each hold the lock the other needs, and neither can ever move. That is a deadlock, and our run detects it when a whole pass makes no progress.

def counter_program(increments, locked=False):    program = []    for _ in range(increments):        program += ([("lock", "m")] if locked else []) + INCREMENT + ([("unlock", "m")] if locked else [])    return programsafe = [counter_program(1, locked=True), counter_program(1, locked=True)]print(counter_program(1, locked=True))print(run(safe, round_robin_schedule(safe)))ab = [[("lock", "a"), ("lock", "b"), ("unlock", "b"), ("unlock", "a")],      [("lock", "b"), ("lock", "a"), ("unlock", "a"), ("unlock", "b")]]try:    run(ab, [0, 1])except RuntimeError as error:    print("error:", error)

[('lock', 'm'), ('load', 'x'), ('add', 1), ('store', 'x'), ('unlock', 'm')]
{'x': 2}
error: deadlock

def study(bars):    returns = [float(r) for r in bars["close"].pct_change().dropna()][:2000]    ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]    free = [counter_program(k) for k in ups]    locked = [counter_program(k, locked=True) for k in ups]    return {"up": sum(ups),            "serial": run(free, serial_schedule(free))["x"],            "racy": run(free, round_robin_schedule(free))["x"],            "locked": run(locked, round_robin_schedule(locked))["x"]}print(study(load_bars()))

{'up': 1085, 'serial': 1085, 'racy': 543, 'locked': 1085}

With no lock, the round-robin schedule keeps both threads one step apart, so they always load the same value and each pair of increments counts once: about half of the 1,085 up days are lost. A lock restores the exact total, at the price of making one thread wait.

The lab follows the lecture: one step of a thread, the whole machine under a schedule, the two simple schedules, the count of lost updates, the program of a counter thread with and without a lock, and the study of two threads counting the up days of SPY.

• Function · questionBuilds on
• execute(op, shared, regs, locks, tid)What does one step do, and does the thread have to wait?Plain arithmetic
• run(programs, schedule, shared)What do the threads leave behind under this schedule?execute
• serial_schedule(programs)One thread after the other?Plain arithmetic
• round_robin_schedule(programs)One step each in turn?Plain arithmetic
• lost_updates(programs, schedule)How many increments vanish?run
• counter_program(increments, locked)What does a counting thread do?Plain arithmetic
• study(bars)How many updates does a race cost on SPY?counter_programrunlost_updates

Next topic: you found the lost update by choosing a schedule by hand. A real program has far too many schedules to try by hand. In An interleaving explorer you enumerate every schedule of a small program, count the ones that break it, and keep the explorer as the tool for the rest of the skill.