El problema ABA y los punteros etiquetados

Comparar e intercambiar pregunta «¿el valor sigue siendo lo que leí?» y no puede preguntar «¿se cambió y se volvió a cambiar?». En una pila sin cerrojos ese punto ciego es el problema ABA: un intercambio tiene éxito sobre una idea obsoleta de la pila y devuelve un valor dos veces. De 3021 planificaciones de un pop contra un hilo que remueve la pila, 21 corrompen la pila simple y ninguna corrompe la etiquetada.

Una pila sin cerrojos guarda sus nodos en el diccionario compartido: el nodo i tiene un valor val{i} y un enlace next{i} al nodo de abajo, y head nombra la cima (-1 si está vacía). Para apilar un nodo se lee la cabeza, se apunta el enlace del nuevo nodo a ella y se intercambia la cabeza del valor leído al nuevo nodo; si el intercambio falla, alguien cambió la cabeza y se empieza de nuevo. Para desapilar se lee la cabeza, se leen el enlace y el valor del nodo de la cima, y se intercambia la cabeza del nodo leído a su enlace. El pop que gana registra su valor en popped. Cada operación de la pila es un generador, y un hilo la ejecuta con yield from, que también devuelve el valor retornado.

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)

Sola, la pila es una pila normal: los pops devuelven 10, 20 y luego None, y la cabeza vuelve a -1. Todo depende de lo que pasa cuando otro hilo trabaja entre las tres lecturas de un pop y su intercambio.

Aquí está la trampa. Un hilo víctima empieza un pop: lee head = 0 (nodo A) y el enlace next0 = 1 (nodo B), y se pausa antes de su intercambio. Un hilo removedor desapila A, desapila B y apila el nodo 0 con un valor nuevo 99, así que head vuelve a ser 0, sin nada debajo. La víctima despierta. Su comparar e intercambiar solo pregunta si head sigue siendo 0, y lo es, así que el intercambio tiene éxito e instala el nodo 1 como cabeza, un nodo que ya no está en la pila. Seguimos la planificación [0, 0], luego nueve turnos del removedor, luego la víctima, y comprobamos el resultado con conserved: los valores sacados más los que quedan en la pila deben ser exactamente los valores que se metieron.

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 víctima devolvió 10, que el removedor ya había sacado (popped: (10, 20, 10)), la cabeza es el nodo 1 aunque el valor 20 también se sacó, así que 20 está en la pila y en popped, y el nuevo valor 99 se pierde. conserved dice False. Una actualización perdida, un valor duplicado y un nodo que no debería existir: todo por un intercambio «correcto» para el valor que comparaba.

La reparación es que la cabeza lleve su propia historia. En la versión con puntero etiquetado head es un par (nodo, etiqueta), y cada push o pop exitoso lo cambia por (nuevo nodo, etiqueta + 1). El comparar e intercambiar compara ahora ambos campos, así que la cabeza (0, 3) que deja el removedor no es el (0, 0) que leyó la víctima. El intercambio de la víctima falla, cuenta un reintento, lee la pila real y saca 99. La misma planificación, con la etiqueta, termina correctamente.

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

Veintiuna planificaciones de 3021 es menos del 1 %. Una prueba de estrés en una máquina real podría correr días sin tocar ninguna y luego fallar una vez en producción. El explorador las lista todas y la etiqueta las elimina todas.

El laboratorio sigue la lección: la pila en el diccionario compartido, push y pop con bucle de comparar e intercambiar (simple y etiquetada), un recorrido de la pila, la comprobación de conservación, el programa ABA de una víctima y un removedor, y el estudio de ambas pilas sobre todas las planificaciones con dos cierres de SPY.

• Función · preguntaSe apoya en
• make_stack(values, tagged)¿Cómo es la pila compartida?Aritmética simple
• push(shared, node, value, tagged)¿Cómo se apila un nodo?Aritmética simple
• pop(shared, tagged)¿Cómo se saca un valor?Aritmética simple
• walk(shared, tagged)¿Qué hay en la pila?Aritmética simple
• conserved(shared, expected, tagged)¿Se perdió o duplicó algo?walk
• aba_program(tagged)¿Cómo es la trampa ABA?poppush
• study(bars)¿Cuántas planificaciones salva la etiqueta?make_stackaba_programconserved

Siguiente tema: una pila tiene una cabeza. Una cola necesita dos extremos y muchos hilos en cada uno. Las colas de varios productores y varios consumidores construyen una cola acotada en la que productores y consumidores reservan un ticket con fetch-and-add y cada casilla lleva un número de secuencia, y el explorador la comprueba sobre todas las planificaciones.