Progress guarantees: from obstruction-free to wait-free

Three counters give the right answer under every schedule, and yet they are not the same. Pause one thread at the worst moment and the spin lock stops everybody, the compare-and-swap counter lets someone through, and the fetch-and-add counter lets every thread finish in 1 turn. These are the three levels of the ladder of progress guarantees.

A real operating system can take a thread off its core at any moment: its time slice ends, a page fault sends it to disk, an interrupt arrives. A good concurrent structure should survive that. We make the question precise with an adversary. It runs a prefix of turns of its choice, then pauses one thread for ever, and we give a budget of rounds to everybody else. If some thread that is not paused still has not finished, the structure can be stopped. A spin lock fails this test in the simplest way: if the adversary pauses the thread that holds the lock, the others spin until the budget ends.

def locked_increments(k):    def thread(shared):        for _ in range(k):            while True:                yield                if not shared.get("lock", 0):                    shared["lock"] = 1                    break            yield            value = shared.get("x", 0)            yield            shared["x"] = value + 1            yield            shared["lock"] = 0    return threaddef progress_without(make_threads, prefix, paused, budget=50):    n = len(make_threads({}))    allowed = [tid for tid in range(n) if tid not in paused]    _, alive = run_prefix(make_threads, list(prefix) + allowed * budget)    return [tid for tid in allowed if tid not in alive]lk = lambda shared: [locked_increments(1)(shared), locked_increments(1)(shared)]print(run_prefix(lk, [0]))print("thread 0 paused holding the lock:", progress_without(lk, [0], [0]))print("thread 0 finished first:         ", progress_without(lk, [0, 0, 0, 0], [0]))

({'lock': 1}, [0, 1])
thread 0 paused holding the lock: []
thread 0 finished first:          [1]

After one turn thread 0 holds the lock ('lock': 1). Pause it there and thread 1 finishes nothing in fifty rounds: []. Let thread 0 run its four turns first and the lock is free again, so thread 1 finishes: [1]. The difference is only where the adversary strikes. A lock turns any pause inside the critical section into a pause of the whole program.

is_blocking automates the adversary. It tries every prefix of a few turns, pauses each live thread in turn, and asks progress_without whether the others still finish. For the spin lock the answer is yes after a single turn. For the compare-and-swap counter it is never: a thread that is paused between its read and its swap simply leaves the value unchanged, so the other thread's swap succeeds. This is the definition of lock-free: the system as a whole always moves, even if one thread is stopped for ever.

def is_blocking(make_threads, depth=3, budget=50):    def visit(prefix):        _, alive = run_prefix(make_threads, prefix)        for paused in alive:            finished = progress_without(make_threads, prefix, [paused], budget)            if len(finished) < len([tid for tid in range(len(make_threads({}))) if tid != paused]):                return True        if len(prefix) < depth:            return any(visit(prefix + [tid]) for tid in alive)        return False    return visit([])cs = lambda shared: [cas_increments(1)(shared), cas_increments(1)(shared)]at = lambda shared: [atomic_increments(1)(shared), atomic_increments(1)(shared)]print("spin lock:", is_blocking(lk))print("compare-and-swap:", is_blocking(cs))print("fetch-and-add:", is_blocking(at))

spin lock: True
compare-and-swap: False
fetch-and-add: False

Both the compare-and-swap counter and the fetch-and-add counter are non-blocking. The ladder has a third step because lock-free still allows a bad day for one thread: it can lose every race.

A wait-free operation has a bound on its own turns that no neighbour can break. worst_own_turns measures it: the largest number of turns a thread takes over all complete schedules. classify then asks the sharp question. Does the worst case of thread 0 stay the same when its neighbour has 1 increment and when it has 3? If it does, thread 0 is wait-free. If it grows, the neighbour can make thread 0 retry more, so the structure is only lock-free.

def worst_own_turns(make_threads, tid):    worst = 0    def visit(prefix):        nonlocal worst        _, alive = run_prefix(make_threads, prefix)        if not alive:            worst = max(worst, prefix.count(tid))            return        for other in alive:            visit(prefix + [other])    visit([])    return worstdef classify(factory, others=(1, 3)):    def program(m):        return lambda shared: [factory(1)(shared), factory(m)(shared)]    if is_blocking(program(others[0])):        return "blocking"    light, busy = worst_own_turns(program(others[0]), 0), worst_own_turns(program(others[1]), 0)    return "wait-free" if light == busy else "lock-free"for neighbour in (1, 2, 3):    cas = lambda shared: [cas_increments(1)(shared), cas_increments(neighbour)(shared)]    atomic = lambda shared: [atomic_increments(1)(shared), atomic_increments(neighbour)(shared)]    print(neighbour, "increments next door: CAS", worst_own_turns(cas, 0), "turns, fetch-and-add", worst_own_turns(atomic, 0))print([classify(f) for f in (locked_increments, cas_increments, atomic_increments)])

1 increments next door: CAS 4 turns, fetch-and-add 1
2 increments next door: CAS 6 turns, fetch-and-add 1
3 increments next door: CAS 8 turns, fetch-and-add 1
['blocking', 'lock-free', 'wait-free']

returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:6]ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]for name, factory in (("locked", locked_increments), ("cas", cas_increments), ("atomic", atomic_increments)):    program = lambda shared, f=factory: [f(k)(shared) for k in ups]    blocking = is_blocking(program)    print(name, classify(factory), blocking, None if blocking else worst_own_turns(program, 0))

locked blocking True None
cas lock-free False 8
atomic wait-free False 1

Read the bars: the fetch-and-add thread needs 1 turn however busy its neighbour is, while the compare-and-swap thread needs 4, 6, then 8 turns as the neighbour does more increments. Each extra increment next door can make thread 0 lose one more race and repeat its read and its swap. That growth is exactly what separates lock-free from wait-free.

The lab follows the lecture: the spin-lock counter, running with some threads paused, the test that tells whether pausing one thread can stop the others, the worst case of a thread's own turns, the classification of a counter, and the study of the three counters on SPY up days.

• Function · questionBuilds on
• locked_increments(k)A counter that waits for a lock?Plain arithmetic
• progress_without(make_threads, prefix, paused, budget)Who finishes if some threads are paused?run_prefix
• is_blocking(make_threads, depth, budget)Can one paused thread stop everybody?progress_without
• worst_own_turns(make_threads, tid)How many turns can a thread need?run_prefix
• classify(factory, others)Blocking, lock-free or wait-free?is_blockingworst_own_turns
• study(bars)Where do the three counters stand on SPY?classifyis_blockingworst_own_turns

Next topic: you now know what a queue could promise. A single-producer single-consumer ring buffer builds the simplest useful lock-free queue, with one writer and one reader, fixed memory and no atomic read-modify-write at all, and the explorer checks that it never loses or reorders a tick.