Le problème ABA et les pointeurs étiquetés

Comparer-et-échanger demande « la valeur est-elle encore ce que j'ai lu ? » et ne peut pas demander « a-t-elle été changée puis rechangée ? ». Sur une pile sans verrou, cet angle mort est le problème ABA : un échange réussit sur une idée périmée de la pile et renvoie une valeur deux fois. Sur 3 021 ordonnancements d'un pop contre un thread qui brasse la pile, 21 corrompent la pile simple et aucun ne corrompt la pile étiquetée.

Une pile sans verrou garde ses nœuds dans le dictionnaire partagé : le nœud i a une valeur val{i} et un lien next{i} vers le nœud du dessous, et head désigne le sommet (-1 si vide). Pour empiler un nœud, on lit la tête, on fait pointer le lien du nouveau nœud dessus, et on échange la tête de la valeur lue vers le nouveau nœud ; si l'échange échoue, quelqu'un a changé la tête, on recommence. Pour dépiler, on lit la tête, on lit le lien et la valeur du nœud du sommet, et on échange la tête du nœud lu vers son lien. Le pop qui gagne consigne sa valeur dans popped. Chaque opération de pile est un générateur, et un thread l'exécute avec yield from, qui rend aussi la valeur renvoyée.

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)

Seule, la pile est une pile ordinaire : les pops renvoient 10, 20 puis None, et la tête revient à -1. Tout dépend de ce qui se passe quand un autre thread travaille entre les trois lectures d'un pop et son échange.

Voici le piège. Un thread victime commence un pop : il lit head = 0 (nœud A) et le lien next0 = 1 (nœud B), puis est suspendu avant son échange. Un thread brasseur dépile alors A, dépile B, et empile le nœud 0 avec une nouvelle valeur 99, si bien que head vaut de nouveau 0, sans rien dessous. La victime se réveille. Son comparer-et-échanger demande seulement si head vaut encore 0, et c'est le cas, donc l'échange réussit et installe le nœud 1 comme tête, un nœud qui n'est plus dans la pile. Nous suivons l'ordonnancement [0, 0], puis neuf tours du brasseur, puis la victime, et vérifions le résultat avec conserved : les valeurs sorties plus les valeurs restantes dans la pile doivent être exactement les valeurs qu'on y a mises.

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

La victime a renvoyé 10, que le brasseur avait déjà sorti (popped: (10, 20, 10)), la tête est le nœud 1 alors que la valeur 20 a aussi été sortie, donc 20 est dans la pile et dans popped, et la nouvelle valeur 99 est perdue. conserved dit False. Une mise à jour perdue, une valeur dupliquée et un nœud qui ne devrait pas exister : tout cela par un échange « correct » pour la valeur qu'il comparait.

Le remède consiste à faire porter son histoire à la tête. Dans la version à pointeur étiqueté, head est une paire (nœud, étiquette), et chaque push ou pop réussi l'échange contre (nouveau nœud, étiquette + 1). Le comparer-et-échanger compare maintenant les deux champs, donc la tête (0, 3) laissée par le brasseur n'est pas le (0, 0) lu par la victime. L'échange de la victime échoue, elle compte un réessai, lit la vraie pile et dépile 99. Le même ordonnancement, avec l'étiquette, finit correctement.

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

Vingt et un ordonnancements sur 3 021, c'est moins de 1 %. Un test de charge sur une vraie machine pourrait tourner des jours sans en toucher un, puis échouer une fois en production. L'explorateur les liste tous, et l'étiquette les supprime tous.

Le labo suit le cours : la pile dans le dictionnaire partagé, push et pop avec boucle de comparer-et-échanger (simple et étiquetée), un parcours de la pile, la vérification de conservation, le programme ABA d'une victime et d'un brasseur, et l'étude des deux piles sur tous les ordonnancements avec deux cours SPY.

• Fonction · questionS'appuie sur
• make_stack(values, tagged)À quoi ressemble la pile partagée ?De l'arithmétique simple
• push(shared, node, value, tagged)Comment un nœud est-il empilé ?De l'arithmétique simple
• pop(shared, tagged)Comment une valeur est-elle dépilée ?De l'arithmétique simple
• walk(shared, tagged)Qu'y a-t-il sur la pile ?De l'arithmétique simple
• conserved(shared, expected, tagged)Quelque chose a-t-il été perdu ou dupliqué ?walk
• aba_program(tagged)À quoi ressemble le piège ABA ?poppush
• study(bars)Combien d'ordonnancements l'étiquette sauve-t-elle ?make_stackaba_programconserved

Sujet suivant : une pile n'a qu'une tête. Une file a deux extrémités et plusieurs threads à chacune. Les files à plusieurs producteurs et plusieurs consommateurs bâtissent une file bornée où producteurs et consommateurs réservent un ticket avec fetch-and-add et où chaque case porte un numéro de séquence, et l'explorateur la vérifie sur tous les ordonnancements.