Fortschrittsgarantien: von obstruction-free bis wait-free

Drei Zähler liefern unter jedem Schedule die richtige Antwort, und doch sind sie nicht gleich. Halten Sie einen Thread im schlimmsten Moment an: Die Spinlock stoppt alle, der Compare-and-Swap-Zähler lässt jemanden durch, und der Fetch-and-Add-Zähler lässt jeden Thread in 1 Zug fertig werden. Das sind die drei Stufen der Leiter der Fortschrittsgarantien.

Ein echtes Betriebssystem kann einen Thread jederzeit von seinem Kern nehmen: Seine Zeitscheibe endet, ein Seitenfehler schickt ihn zur Platte, ein Interrupt kommt. Eine gute nebenläufige Struktur sollte das überstehen. Wir präzisieren die Frage mit einem Gegner. Er führt ein prefix von Zügen seiner Wahl aus, hält dann einen Thread für immer an, und wir geben allen anderen ein budget an Runden. Hat ein nicht angehaltener Thread dann immer noch nicht fertig, kann die Struktur gestoppt werden. Eine Spinlock scheitert an diesem Test auf die einfachste Weise: Hält der Gegner den Thread an, der die Sperre hält, drehen die anderen, bis das Budget endet.

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]

Nach einem Zug hält Thread 0 die Sperre ('lock': 1). Hält man ihn dort an, beendet Thread 1 in fünfzig Runden nichts: []. Lässt man Thread 0 erst seine vier Züge machen, ist die Sperre wieder frei, und Thread 1 wird fertig: [1]. Der Unterschied ist nur, wo der Gegner zuschlägt. Eine Sperre macht jede Pause im kritischen Abschnitt zu einer Pause des ganzen Programms.

is_blocking automatisiert den Gegner. Es probiert jedes Präfix von einigen Zügen, hält jeden lebenden Thread der Reihe nach an und fragt progress_without, ob die anderen noch fertig werden. Bei der Spinlock lautet die Antwort schon nach einem einzigen Zug ja. Beim Compare-and-Swap-Zähler nie: Ein Thread, der zwischen Lesen und Tausch angehalten wird, lässt den Wert einfach unverändert, sodass der Tausch des anderen Threads gelingt. Das ist die Definition von sperrfrei: Das Gesamtsystem kommt immer voran, selbst wenn ein Thread für immer angehalten ist.

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

Sowohl der Compare-and-Swap-Zähler als auch der Fetch-and-Add-Zähler sind nicht blockierend. Die Leiter hat eine dritte Stufe, weil „sperrfrei“ einem Thread noch einen schlechten Tag erlaubt: Er kann jedes Rennen verlieren.

Eine wait-free-Operation hat eine Schranke für ihre eigenen Züge, die kein Nachbar brechen kann. worst_own_turns misst sie: die größte Zahl von Zügen, die ein Thread über alle vollständigen Schedules nimmt. classify stellt dann die scharfe Frage. Bleibt der schlimmste Fall von Thread 0 gleich, wenn sein Nachbar 1 Inkrement hat und wenn er 3 hat? Wenn ja, ist Thread 0 wait-free. Wenn er wächst, kann der Nachbar Thread 0 öfter wiederholen lassen, die Struktur ist also nur 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

Lesen Sie die Balken: Der Fetch-and-Add-Thread braucht 1 Zug, egal wie beschäftigt sein Nachbar ist, während der Compare-and-Swap-Thread 4, dann 6, dann 8 Züge braucht, je mehr Inkremente der Nachbar macht. Jedes zusätzliche Inkrement nebenan kann Thread 0 ein weiteres Rennen verlieren und Lesen und Tausch wiederholen lassen. Dieses Wachstum trennt genau lock-free von wait-free.

Das Labor folgt der Lektion: der Spinlock-Zähler, das Ausführen mit angehaltenen Threads, der Test, ob das Anhalten eines Threads die anderen stoppen kann, der schlimmste Fall der eigenen Züge eines Threads, die Klassifikation eines Zählers und die Studie der drei Zähler an den SPY-Aufwärtstagen.

• Funktion · FrageBaut auf
• locked_increments(k)Ein Zähler, der auf eine Sperre wartet?Einfache Arithmetik
• progress_without(make_threads, prefix, paused, budget)Wer wird fertig, wenn Threads angehalten sind?run_prefix
• is_blocking(make_threads, depth, budget)Kann ein angehaltener Thread alle stoppen?progress_without
• worst_own_turns(make_threads, tid)Wie viele Züge kann ein Thread brauchen?run_prefix
• classify(factory, others)Blockierend, lock-free oder wait-free?is_blockingworst_own_turns
• study(bars)Wo stehen die drei Zähler bei SPY?classifyis_blockingworst_own_turns

Nächstes Thema: Sie wissen jetzt, was eine Warteschlange versprechen könnte. Ein Ringpuffer für einen Producer und einen Consumer baut die einfachste nützliche sperrfreie Warteschlange, mit einem Schreiber und einem Leser, festem Speicher und gar keinem atomaren Read-Modify-Write, und der Explorer prüft, dass sie nie einen Tick verliert oder umordnet.