Wettlaufsituationen und warum es Sperren gibt

Zwei Threads addieren 1 zum selben Zähler, und der Zähler endet falsch, ohne Fehler und ohne Absturz. Die Zeile x += 1 ist nicht ein Schritt, sondern drei, und die Reihenfolge, in der zwei Threads diese Schritte verzahnen, entscheidet über das Ergebnis. An 1.085 Aufwärtstagen von SPY gehen 542 Updates verloren; eine Sperre bringt sie alle zurück.

Ein Prozessor kann nicht zu einem Wert addieren, der im Speicher liegt. Er lädt den Wert in ein Register, addiert zum Register und speichert das Register zurück. Also ist x += 1 gleich load x, add 1, store x. Ein einzelner Thread macht die drei hintereinander, und nichts kann schiefgehen. Bei zwei Threads kann die Maschine einen Schritt des einen und dann einen des anderen ausführen, in beliebiger Reihenfolge. Um das zu sehen, schreiben wir eine winzige Maschine. Ein Thread ist eine Liste von Schritten mit je eigenem Register; die Threads teilen ein Dictionary benannter Werte. Die Funktion execute führt einen Schritt eines Threads aus. Unten spielen wir die sechs Schritte zweier Threads von Hand durch, abwechselnd einen Schritt.

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. 1Beide Threads laden, bevor einer speichert: Jedes Register enthält 0.

Lesen Sie die Ausgabe Zeile für Zeile. Thread 0 lädt 0, Thread 1 lädt ebenfalls 0 (Thread 0 hat noch nicht gespeichert), beide addieren 1 zu einem Register mit 0, und beide speichern 1. Zwei Threads haben je ihr x += 1 gemacht, doch x ist 1, nicht 2. Ein Update ging verloren. Am Code keines Threads war etwas falsch; der Fehler existiert nur in dieser Reihenfolge der Schritte.

In der echten Welt wählt das Betriebssystem den Schedule, und er ändert sich von Lauf zu Lauf, weshalb ein Race so schwer zu reproduzieren ist. In unserer Maschine wählen wir ihn selbst. Ein Schedule ist eine Liste von Thread-Nummern, und run gibt dem durch jeden Eintrag genannten Thread einen Zug. Zwei einfache Schedules sind wichtig. Im seriellen Schedule führt Thread 0 alle seine Schritte aus, dann Thread 1: Das ist, was wir hoffen. Im Round-Robin-Schedule machen die Threads abwechselnd je einen Schritt: Das ist der schlimmste Fall für unseren Zähler, weil sich die Schritte der beiden Threads überall überlappen. Die Funktion lost_updates vergleicht, was die Inkremente hätten addieren sollen, mit dem, was der Zähler zeigt.

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

Der serielle Schedule [0, 0, 0, 1, 1, 1] ergibt 2; der Round-Robin-Schedule [0, 1, 0, 1, 0, 1] ergibt 1 und verliert ein Update. Beachten Sie, was run tut, wenn der Schedule früh endet: Die unfertigen Threads bekommen weiter Züge, ein Schritt pro Thread in Thread-Reihenfolge, sodass jedes Programm immer fertig wird. Beachten Sie auch, dass ein fertiger Thread seine Züge ignoriert, jede Liste von Thread-Nummern also ein gültiger Schedule ist.

Eine Sperre behebt das Race, indem sie die Überlappung verbietet. Ein Thread nimmt die Sperre vor load und gibt sie nach store frei. Ein zweiter Thread, der die Sperre dazwischen anfordert, bekommt sie nicht: Sein Zug tut nichts, und er bleibt beim selben Schritt, bis die Sperre frei ist. Die Schritte zwischen lock und unlock laufen also als ein Block, und kein anderer Thread kann sich hineinschieben. Die Funktion counter_program baut das Programm eines Threads, der einen Zähler erhöht, mit oder ohne Sperre. Sperren bringen eine neue Gefahr, die am Ende des Codes gezeigt wird: Zwei Threads, die zwei Sperren in entgegengesetzter Reihenfolge nehmen, können jeweils die Sperre halten, die der andere braucht, und keiner kann sich mehr bewegen. Das ist ein Deadlock, und unser run erkennt ihn, wenn ein ganzer Durchgang keinen Fortschritt macht.

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}

Ohne Sperre hält der Round-Robin-Schedule beide Threads einen Schritt auseinander, sodass sie immer denselben Wert laden und jedes Paar von Inkrementen nur einmal zählt: Etwa die Hälfte der 1.085 Aufwärtstage geht verloren. Eine Sperre stellt die exakte Summe wieder her, zum Preis, dass ein Thread warten muss.

Das Labor folgt der Lektion: ein Schritt eines Threads, die ganze Maschine unter einem Schedule, die beiden einfachen Schedules, die Zählung verlorener Updates, das Programm eines Zähl-Threads mit und ohne Sperre und die Studie zweier Threads, die die Aufwärtstage von SPY zählen.

• Funktion · FrageBaut auf
• execute(op, shared, regs, locks, tid)Was tut ein Schritt, und muss der Thread warten?Einfache Arithmetik
• run(programs, schedule, shared)Was hinterlassen die Threads unter diesem Schedule?execute
• serial_schedule(programs)Ein Thread nach dem anderen?Einfache Arithmetik
• round_robin_schedule(programs)Abwechselnd je ein Schritt?Einfache Arithmetik
• lost_updates(programs, schedule)Wie viele Inkremente verschwinden?run
• counter_program(increments, locked)Was tut ein Zähl-Thread?Einfache Arithmetik
• study(bars)Wie viele Updates kostet ein Race bei SPY?counter_programrunlost_updates

Nächstes Thema: Sie haben das verlorene Update gefunden, indem Sie einen Schedule von Hand wählten. Ein echtes Programm hat viel zu viele Schedules, um sie von Hand zu probieren. Im Interleaving-Explorer zählen Sie alle Schedules eines kleinen Programms auf, zählen die, die es brechen, und behalten den Explorer als Werkzeug für den Rest der Fähigkeit.