Race Conditions and Mutexes Explained: The Lost Update

Two threads each add one to a shared counter that starts at zero. Most of the time the counter ends at 2. Occasionally it ends at 1, with no exception, no warning and no way to reproduce it on demand. That is a race condition, and it is less mysterious than it looks: a short list of possible orderings, and some of them are wrong. A mutex fixes it by making the wrong orderings impossible.

The problem it solves

count += 1 reads like one action, but a processor performs it as three: read the current value into a register or local, add one, write the result back. A thread can be paused between any two of those steps while another thread runs.

A race condition is any bug where the result depends on how the steps of concurrent threads happen to interleave. The version here — two read-modify-write sequences overlapping so that one write erases the other — is called a lost update. It is the same bug as two people editing a shared document offline and the second upload overwriting the first.

The intuition

Give each thread two steps: read (copy the shared value into a private variable) and write (store private + 1). Thread A's steps must happen in order, and so must B's, but the scheduler may interleave them any way it likes. With two steps each there are exactly six orderings.

The outcome depends on one question: did the second thread read before or after the first thread wrote? If A writes before B reads, B sees 1 and writes 2. If both read before either writes, both see 0 and both write 1. Four of the six orderings do the second thing.

A mutex (mutual-exclusion lock) is a token only one thread can hold. A thread takes it before the read and returns it after the write, so no other thread can start its read in between. The mutex does not speed anything up or change the arithmetic. It deletes the four bad orderings from the list of things the scheduler is allowed to do.

Watch it run

The animation plays the lesson's schedule on a two-lane timeline. Thread A reads 0, the scheduler switches, and thread B reads the same 0. A writes 1, then B writes 1 as well, computed from its stale copy — A's increment is gone. Then the same two threads run in the lucky order, and the same code produces 2.

The code

Real threads make races hard to study, because the schedule changes on every run. So the model below makes the schedule an input: a string like "ABAB" says which thread takes its next step. It enumerates every ordering with and without a lock:

from collections import Counter
from itertools import permutations

def run(schedule, locked):
    """Each letter is one step of that thread, alternating read and write:
    count += 1 split into its two halves. With locked=True a thread holds
    the lock from its read to its write; a schedule that makes another
    thread read in between is impossible, so it returns None."""
    count, local, holder, steps = 0, {}, None, Counter()
    for t in schedule:
        if steps[t] % 2 == 0:                    # read into a private copy
            if locked and holder not in (None, t):
                return None                      # would block: never happens
            holder = t if locked else None
            local[t] = count
        else:                                    # add one and write it back
            count = local[t] + 1
            holder = None
        steps[t] += 1
    return count

orders = sorted(set(permutations("AABB")))       # every interleaving
print(len(orders))                               # 6
print(Counter(run(o, locked=False) for o in orders))   # Counter({1: 4, 2: 2})
print(Counter(run(o, locked=True) for o in orders))    # Counter({None: 4, 2: 2})
print(run("ABAB", locked=False))                 # 1  -- the lesson's schedule

Without the lock, four of six orderings lose an update. With it, those same four are impossible — None marks a schedule in which a thread would have had to read while another held the lock — and the two that remain both give 2.

For more threads and more increments, enumerating every ordering gets large quickly, so the next check samples them. A random scheduler picks any thread that is allowed to run, and the result is compared with the brute-force answer: run the threads one at a time, which gives threads × increments:

import random

def random_schedule(threads, reps, locked):      # a scheduler that picks at random
    left = {t: 2 * reps for t in threads}
    holder, out = None, []
    while any(left.values()):
        ready = [t for t in threads if left[t] and
                 not (locked and holder not in (None, t))]
        t = random.choice(ready)
        if locked:
            holder = t if left[t] % 2 == 0 else None   # read takes, write frees
        out.append(t)
        left[t] -= 1
    return out

random.seed(8)
ok, runs_with_loss = True, 0
for _ in range(2000):
    threads = "ABCD"[: random.randint(2, 4)]
    reps = random.randint(1, 5)
    serial = len(threads) * reps                 # brute force: one at a time
    ok &= run(random_schedule(threads, reps, True), locked=True) == serial
    free = run(random_schedule(threads, reps, False), locked=False)
    ok &= free <= serial
    runs_with_loss += free < serial
print(ok, runs_with_loss)                        # True 1880

Every locked run matched the serial answer. Of 2,000 unlocked runs, 1,880 lost at least one update. Real code rarely looks that bad, because a real scheduler switches threads far less often than a uniformly random one — which is exactly why the bug hides in testing and appears under load.

Finally, the real thing with Python's threading.Lock:

import threading

counter = 0
lock = threading.Lock()

def bump(times):
    global counter
    for _ in range(times):
        with lock:                               # read-modify-write, one at a time
            counter += 1

workers = [threading.Thread(target=bump, args=(50_000,)) for _ in range(4)]
for w in workers: w.start()
for w in workers: w.join()
print(counter)                                   # 200000

Remove the lock and the result may or may not come out short on a given run, interpreter and machine. That uncertainty is the point: a race is a property of the allowed schedules, not of the runs you happened to see.

The complexity

A lock adds a small cost to every acquire and release, and a much larger one when threads contend: waiting threads do no useful work, so the critical section runs serially. Keep it short — only the read-modify-write of shared state — and never do slow input or output while holding a lock. When the shared state is a single number, an atomic increment or a compare-and-swap loop does the same job without blocking.

Where it goes wrong

• Locking only the write. The read must be inside the same critical section, or two threads still read the same stale value.
• Different locks for the same data. A mutex protects data only if every access to that data goes through the same lock.
• Check-then-act. if key not in cache: cache[key] = load() is a race for the same reason: the check and the act are two steps.
• Acquire without release. An exception between acquire() and release() leaves the lock held forever. with lock: releases it on every path.
• Two locks, two orders. Thread A holds lock 1 and waits for lock 2 while B holds 2 and waits for 1. That is a deadlock; always take locks in one global order.

How to say it in an interview

"count += 1 is a read, an add and a write, and another thread can run between them. If two threads both read before either writes, one update is lost. That's a race condition: the result depends on the interleaving. A mutex makes the whole read-modify-write a critical section, so only one thread can be between its read and its write at a time. The bad interleavings become impossible. The cost is serialisation, so I keep the critical section minimal, and for a single counter I'd consider an atomic operation instead."