O problema ABA e os ponteiros etiquetados

Compara-e-troca pergunta «o valor ainda é o que li?» e não consegue perguntar «foi mudado e mudado de volta?». Numa pilha sem travas esse ponto cego é o problema ABA: uma troca tem sucesso sobre uma ideia obsoleta da pilha e devolve um valor duas vezes. De 3021 escalonamentos de um pop contra uma thread que mexe na pilha, 21 corrompem a pilha simples e nenhum corrompe a etiquetada.

Uma pilha sem travas guarda seus nós no dicionário compartilhado: o nó i tem um valor val{i} e um elo next{i} para o nó de baixo, e head nomeia o topo (-1 se vazia). Para empilhar um nó, lê-se a cabeça, aponta-se o elo do novo nó para ela e troca-se a cabeça do valor lido para o novo nó; se a troca falha, alguém mudou a cabeça, então recomeça-se. Para desempilhar, lê-se a cabeça, lê-se o elo e o valor do nó do topo e troca-se a cabeça do nó lido para o seu elo. O pop vencedor registra seu valor em popped. Cada operação da pilha é um gerador, e uma thread a executa com yield from, que também devolve o 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)

Sozinha, a pilha é uma pilha comum: os pops devolvem 10, 20 e depois None, e a cabeça volta a -1. Tudo depende do que acontece quando outra thread trabalha entre as três leituras de um pop e a sua troca.

Aqui está a armadilha. Uma thread vítima começa um pop: lê head = 0 (nó A) e o elo next0 = 1 (nó B) e é pausada antes da sua troca. Uma thread agitadora então desempilha A, desempilha B e empilha o nó 0 de volta com um valor novo 99, de modo que head volta a ser 0, sem nada embaixo. A vítima acorda. Seu compara-e-troca só pergunta se head ainda é 0, e é, então a troca tem sucesso e instala o nó 1 como cabeça, um nó que não está mais na pilha. Seguimos o escalonamento [0, 0], depois nove turnos da agitadora, depois a vítima, e verificamos o resultado com conserved: os valores retirados mais os que restam na pilha devem ser exatamente os valores que foram colocados.

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

A vítima devolveu 10, que a agitadora já havia retirado (popped: (10, 20, 10)), a cabeça é o nó 1 embora o valor 20 também tenha sido retirado, então 20 está na pilha e em popped, e o novo valor 99 se perde. conserved diz False. Uma atualização perdida, um valor duplicado e um nó que não deveria existir: tudo por uma troca «correta» para o valor que comparou.

A correção é fazer a cabeça carregar sua própria história. Na versão com ponteiro etiquetado head é um par (nó, etiqueta), e cada push ou pop bem-sucedido o troca por (novo nó, etiqueta + 1). O compara-e-troca agora compara os dois campos, então a cabeça (0, 3) deixada pela agitadora não é o (0, 0) lido pela vítima. A troca da vítima falha, ela conta uma nova tentativa, lê a pilha real e retira 99. O mesmo escalonamento, com a etiqueta, termina corretamente.

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

Vinte e um escalonamentos em 3021 é menos de 1%. Um teste de estresse numa máquina real poderia rodar dias sem tocar em nenhum e depois falhar uma vez em produção. O explorador lista todos, e a etiqueta elimina todos.

O laboratório segue a aula: a pilha no dicionário compartilhado, push e pop com laço de compara-e-troca (simples e etiquetada), um percurso da pilha, a verificação de conservação, o programa ABA de uma vítima e uma agitadora, e o estudo das duas pilhas sobre todos os escalonamentos com dois fechamentos do SPY.

• Função · perguntaBaseia-se em
• make_stack(values, tagged)Como é a pilha compartilhada?Aritmética simples
• push(shared, node, value, tagged)Como um nó é empilhado?Aritmética simples
• pop(shared, tagged)Como um valor é retirado?Aritmética simples
• walk(shared, tagged)O que há na pilha?Aritmética simples
• conserved(shared, expected, tagged)Algo foi perdido ou duplicado?walk
• aba_program(tagged)Como é a armadilha ABA?poppush
• study(bars)Quantos escalonamentos a etiqueta salva?make_stackaba_programconserved

Próximo tópico: uma pilha é uma cabeça. Uma fila precisa de duas pontas e muitas threads em cada uma. Filas de vários produtores e vários consumidores constroem uma fila limitada em que produtores e consumidores reservam um tíquete com fetch-and-add e cada casa carrega um número de sequência, e o explorador a verifica sobre todos os escalonamentos.