Das ABA-Problem und getaggte Zeiger

Compare-and-Swap fragt „ist der Wert noch, was ich las?“ und kann nicht fragen „wurde er geändert und zurückgeändert?“. Bei einem sperrfreien Stack ist dieser blinde Fleck das ABA-Problem: Ein Tausch gelingt auf einer veralteten Vorstellung vom Stack und liefert einen Wert zweimal. Von 3.021 Schedules eines Pops gegen einen den Stack umwälzenden Thread machen 21 den einfachen Stack kaputt und keiner den getaggten.

Ein sperrfreier Stack hält seine Knoten im gemeinsamen Dictionary: Knoten i hat einen Wert val{i} und einen Link next{i} zum Knoten darunter, und head benennt die Spitze (-1 für leer). Um einen Knoten zu pushen, liest man den Head, lässt den Link des neuen Knotens darauf zeigen und tauscht den Head vom gelesenen Wert auf den neuen Knoten; schlägt der Tausch fehl, hat jemand den Head geändert, also beginnt man von vorn. Zum Pop liest man den Head, liest Link und Wert des obersten Knotens und tauscht den Head vom gelesenen Knoten auf dessen Link. Der gewinnende Pop protokolliert seinen Wert in popped. Jede Stack-Operation ist ein Generator, und ein Thread führt sie mit yield from aus, was auch den zurückgegebenen Wert liefert.

def make_stack(values, tagged=False):    top = 0 if values else -1    shared = {"head": (top, 0) if tagged else top, "popped": ()}    for i, value in enumerate(values):        shared["val%d" % i] = value        shared["next%d" % i] = i + 1 if i + 1 < len(values) else -1    return shareddef push(shared, node, value, tagged=False):    shared["val%d" % node] = value    while True:        yield        old = shared["head"]        yield        shared["next%d" % node] = old[0] if tagged else old        yield        new = (node, old[1] + 1) if tagged else node        if compare_and_swap(shared, "head", old, new):            returndef pop(shared, tagged=False):    while True:        yield        old = shared["head"]        idx = old[0] if tagged else old        if idx == -1:            return None        yield        nxt = shared["next%d" % idx]        value = shared["val%d" % idx]        yield        new = (nxt, old[1] + 1) if tagged else nxt        if compare_and_swap(shared, "head", old, new):            shared["popped"] = shared["popped"] + (value,)            return valuedef alone(shared):    def thread():        for _ in range(3):            print("popped", (yield from pop(shared)))    return [thread()]final, alive = run_prefix(alone, [0] * 20, make_stack([10, 20]))print(final["head"], final["popped"])

popped 10
popped 20
popped None
-1 (10, 20)

Allein ist der Stack ein gewöhnlicher Stack: Die Pops liefern 10, 20 und dann None, und der Head ist wieder -1. Alles hängt davon ab, was passiert, wenn ein anderer Thread zwischen den drei Lesezugriffen eines Pops und seinem Tausch arbeitet.

Hier ist die Falle. Ein Opfer-Thread beginnt einen Pop: Er liest head = 0 (Knoten A) und den Link next0 = 1 (Knoten B) und wird vor seinem Tausch angehalten. Ein Wirbel-Thread poppt dann A, poppt B und pusht Knoten 0 mit einem neuen Wert 99 zurück, sodass head wieder 0 ist, mit nichts darunter. Das Opfer erwacht. Sein Compare-and-Swap fragt nur, ob head noch 0 ist, und das ist es, also gelingt der Tausch und setzt Knoten 1 als Head, einen Knoten, der nicht mehr im Stack ist. Wir folgen dem Schedule [0, 0], dann neun Züge des Wirbel-Threads, dann dem Opfer, und prüfen das Ergebnis mit conserved: Die entnommenen Werte plus die im Stack verbliebenen müssen genau die eingefügten Werte sein.

def walk(shared, tagged=False):    values = []    idx = shared["head"][0] if tagged else shared["head"]    while idx != -1 and len(values) < 10:        values.append(shared["val%d" % idx])        idx = shared["next%d" % idx]    return valuesdef conserved(shared, expected, tagged=False):    return sorted(list(shared["popped"]) + walk(shared, tagged)) == sorted(expected)def aba_program(tagged=False):    def make_threads(shared):        def victim():            yield from pop(shared, tagged)        def churner():            yield from pop(shared, tagged)            yield from pop(shared, tagged)            yield from push(shared, 0, 99, tagged)        return [victim(), churner()]    return make_threadsprefix = [0, 0] + [1] * 9 + [0]final, alive = run_prefix(aba_program(), prefix, make_stack([10, 20]))print(final)print("still on the stack:", walk(final), "| conserved:", conserved(final, [10, 20, 99]))

{'head': 1, 'popped': (10, 20, 10), 'val0': 99, 'next0': -1, 'val1': 20, 'next1': -1}
still on the stack: [20] | conserved: False

Das Opfer gab 10 zurück, die der Wirbel-Thread schon entnommen hatte (popped: (10, 20, 10)), der Head ist Knoten 1, obwohl der Wert 20 auch entnommen wurde, also liegt 20 im Stack und in popped, und der neue Wert 99 ist verloren. conserved sagt False. Ein verlorenes Update, ein doppelter Wert und ein Knoten, der nicht existieren sollte: alles durch einen für den verglichenen Wert „korrekten“ Tausch.

Die Abhilfe ist, den Head seine eigene Geschichte tragen zu lassen. In der Version mit getaggtem Zeiger ist head ein Paar (Knoten, Tag), und jedes erfolgreiche Push oder Pop tauscht es gegen (neuer Knoten, Tag + 1). Das Compare-and-Swap vergleicht nun beide Felder, der vom Wirbel-Thread hinterlassene Head (0, 3) ist also nicht das (0, 0), das das Opfer las. Der Tausch des Opfers schlägt fehl, es zählt einen Wiederholversuch, liest den echten Stack und poppt 99. Derselbe Schedule endet mit dem Tag korrekt.

final, alive = run_prefix(aba_program(True), prefix, make_stack([10, 20], True))print(final["head"], "victim alive:", alive == [0])final, alive = run_prefix(aba_program(True), prefix + [0] * 6, make_stack([10, 20], True))print(final["popped"], walk(final, True), "| conserved:", conserved(final, [10, 20, 99], True))

(0, 3) victim alive: True
(10, 20, 99) [] | conserved: True

values = [int(round(float(c) * 100)) for c in load_bars()["close"].iloc[:2]]for tagged in (False, True):    outcomes = explore_all(aba_program(tagged), make_stack(values, tagged))    corrupt = sum(n for key, n in outcomes.items() if not conserved(dict(key), values + [99], tagged))    print("tagged" if tagged else "plain ", sum(outcomes.values()), "schedules,", corrupt, "corrupt")

plain  3021 schedules, 21 corrupt
tagged 3021 schedules, 0 corrupt

Einundzwanzig Schedules von 3.021 sind weniger als 1 %. Ein Stresstest auf einer echten Maschine könnte tagelang laufen, ohne einen zu treffen, und dann einmal in der Produktion scheitern. Der Explorer listet sie alle auf, und das Tag beseitigt alle.

Das Labor folgt der Lektion: der Stack im gemeinsamen Dictionary, Push und Pop mit Compare-and-Swap-Schleife (einfach und getaggt), ein Durchlauf des Stacks, die Erhaltungsprüfung, das ABA-Programm eines Opfers und eines Wirbel-Threads, und die Studie beider Stacks über alle Schedules mit zwei SPY-Schlusskursen.

• Funktion · FrageBaut auf
• make_stack(values, tagged)Wie sieht der gemeinsame Stack aus?Einfache Arithmetik
• push(shared, node, value, tagged)Wie kommt ein Knoten hinauf?Einfache Arithmetik
• pop(shared, tagged)Wie kommt ein Wert herunter?Einfache Arithmetik
• walk(shared, tagged)Was liegt auf dem Stack?Einfache Arithmetik
• conserved(shared, expected, tagged)Ging etwas verloren oder wurde dupliziert?walk
• aba_program(tagged)Wie sieht die ABA-Falle aus?poppush
• study(bars)Wie viele Schedules rettet das Tag?make_stackaba_programconserved

Nächstes Thema: Ein Stack hat einen Head. Eine Warteschlange braucht zwei Enden und viele Threads an jedem. Warteschlangen mit mehreren Producern und Consumern bauen eine beschränkte Warteschlange, in der Producer und Consumer mit Fetch-and-Add ein Ticket ziehen und jeder Slot eine Sequenznummer trägt, und der Explorer prüft sie über alle Schedules.