O modelo de memória: acquire e release

Um processador é livre para executar duas leituras e escritas independentes em qualquer ordem, e outro núcleo pode ver o resultado dessa escolha. Publique um preço do SPY e depois levante uma flag: um leitor que vê a flag ainda pode ler um preço de 0. Das quatro maneiras de ordenar o escritor e o leitor, só uma é segura: release no escritor pareado com acquire no leitor.

Buffers de escrita, caches e o compilador deixam um núcleo terminar uma escrita ou leitura posterior antes de uma anterior, desde que uma única thread não perceba. Outra thread percebe. Nossa máquina modela isso diretamente: uma thread é uma lista de operações e pode executar, em qualquer ordem, toda operação cujas restrições de ordem estejam satisfeitas. Operações no mesmo endereço sempre mantêm a ordem, senão uma thread não veria suas próprias escritas. Um carregamento acquire bloqueia tudo o que vem depois; uma escrita release espera tudo o que vem antes. Duas funções dizem tudo: must_wait lista o que uma operação espera e eligible lista o que pode executar a seguir.

def must_wait(ops, j):    waits = []    for i in range(j):        same = ops[i][1] == ops[j][1]        after_acquire = ops[i][0] == "load" and ops[i][3] == "acquire"        release = ops[j][0] == "store" and ops[j][3] == "release"        if same or after_acquire or release:            waits.append(i)    return waitsdef eligible(ops, done):    return [j for j in range(len(ops)) if j not in done and all(i in done for i in must_wait(ops, j))]writer = [("store", "data", 1, "relaxed"), ("store", "flag", 1, "release")]reader = [("load", "flag", "r1", "acquire"), ("load", "data", "r2", "relaxed")]print(must_wait(writer, 1), eligible(writer, set()), eligible(writer, {0}))print(must_wait(reader, 1), eligible(reader, set()))print(eligible([("load", "flag", "r1", "relaxed"), ("load", "data", "r2", "relaxed")], set()))

[0] [0] [1]
[0] [0]
[0, 1]

A escrita release da flag espera a posição 0, a escrita dos dados, então o escritor só pode executar suas operações em ordem. O carregamento acquire da flag bloqueia o carregamento dos dados que vem depois, então o leitor também executa em ordem. Com carregamentos simples, ambos são elegíveis ao mesmo tempo e o leitor pode ler os dados primeiro.

outcomes é o explorador dos tópicos anteriores para esta nova máquina. Um estado é quais operações cada thread já fez, a memória e os registradores. A partir de um estado, tenta cada operação elegível de cada thread, e quando não resta nada a executar os registradores são um resultado. Como muitas ordens chegam ao mesmo estado, ele lembra dos estados já vistos. O teste de passagem de mensagem publica com duas escritas, os dados e depois a flag, e consome com dois carregamentos, a flag e depois os dados. O consumidor erra quando vê r1 == 1 (a flag) e r2 == 0 (ainda sem dados), o que reads_stale verifica.

def outcomes(programs, memory=None):    found = set()    seen = set()    def visit(done, mem, regs):        state = (tuple(frozenset(d) for d in done), tuple(sorted(mem.items())), tuple(sorted(regs.items())))        if state in seen:            return        seen.add(state)        moved = False        for tid, ops in enumerate(programs):            for j in eligible(ops, done[tid]):                moved = True                kind, address, x, _ = ops[j]                mem2, regs2 = dict(mem), dict(regs)                if kind == "store":                    mem2[address] = x                else:                    regs2[x] = mem.get(address, 0)                done2 = [set(d) for d in done]                done2[tid].add(j)                visit(done2, mem2, regs2)        if not moved:            found.add(tuple(sorted(regs.items())))    visit([set() for _ in programs], dict(memory or {}), {})    return founddef mp_programs(write_order, read_order):    return [        [("store", "data", 1, "relaxed"), ("store", "flag", 1, write_order)],        [("load", "flag", "r1", read_order), ("load", "data", "r2", "relaxed")],    ]def reads_stale(results):    return any(dict(outcome).get("r1") == 1 and dict(outcome).get("r2") == 0 for outcome in results)for pair in (("relaxed", "relaxed"), ("release", "acquire")):    results = outcomes(mp_programs(*pair))    print(pair, sorted(results), "stale:", reads_stale(results))

('relaxed', 'relaxed') [(('r1', 0), ('r2', 0)), (('r1', 0), ('r2', 1)), (('r1', 1), ('r2', 0)), (('r1', 1), ('r2', 1))] stale: True
('release', 'acquire') [(('r1', 0), ('r2', 0)), (('r1', 0), ('r2', 1)), (('r1', 1), ('r2', 1))] stale: False

Com ordens relaxed o consumidor pode terminar com os quatro pares (r1, r2), incluindo (1, 0), o obsoleto. Com release na escrita da flag e acquire no seu carregamento restam só três: o leitor que vê a flag vê também os dados, porque nenhum dos lados pode ser reordenado através da flag.

Um lado só basta? Teste os quatro pares. Release só no escritor falha: o leitor pode carregar os dados antes da flag. Acquire só no leitor falha: o escritor pode guardar a flag antes dos dados. Só o par funciona, como mostra a tabela a seguir. É o contrato release-acquire do std::atomic do C++ e do Rust, e o motivo de uma fila sem travas publicar uma casa com uma escrita release de um índice e lê-la com um carregamento acquire.

PAIRS = [("relaxed", "relaxed"), ("release", "relaxed"), ("relaxed", "acquire"), ("release", "acquire")]def ordering_table():    return {pair: reads_stale(outcomes(mp_programs(*pair))) for pair in PAIRS}for pair, stale in ordering_table().items():    print("write", pair[0], "| read", pair[1], "->", "can read stale data" if stale else "safe")

write relaxed | read relaxed -> can read stale data
write release | read relaxed -> can read stale data
write relaxed | read acquire -> can read stale data
write release | read acquire -> safe

price = int(round(float(load_bars()["close"].iloc[0]) * 100))programs = mp_programs("release", "acquire")programs[0][0] = ("store", "data", price, "relaxed")print(price, sorted(outcomes(programs)))

9369 [(('r1', 0), ('r2', 0)), (('r1', 0), ('r2', 9369)), (('r1', 1), ('r2', 9369))]

Com o primeiro fechamento do SPY, 9369 centavos, o leitor pode ver a flag e um preço de 0 em três das quatro configurações. Um bug desse tipo passa em todos os testes numa máquina que mantém a ordem e aparece em outra. Por isso o par seguro precisa ser provado sobre todas as ordens permitidas, como faz o explorador.

O laboratório segue a aula: o que uma operação deve esperar, quais operações podem executar a seguir, todos os resultados de um conjunto de threads, o teste de passagem de mensagem, a verificação de dados obsoletos, a tabela das quatro ordens e o estudo que publica um preço real do SPY.

• Função · perguntaBaseia-se em
• must_wait(ops, j)O que esta operação deve esperar?Aritmética simples
• eligible(ops, done)Quais operações podem ir a seguir?Aritmética simples
• outcomes(programs, memory)Com o que as threads podem terminar?eligible
• mp_programs(write_order, read_order)Como é a passagem de mensagem?Aritmética simples
• reads_stale(results)O leitor pode ver a flag sem os dados?Aritmética simples
• ordering_table()Quais pares de ordens são seguros?outcomesmp_programs
• study(bars)Quais pares protegem um preço real do SPY?outcomesmp_programs

Próximo tópico: agora você tem as ferramentas para construir uma estrutura sem travas e um vocabulário para descrever o que ela garante. Garantias de progresso nomeia os três níveis, obstruction-free, lock-free e wait-free, e testa cada contador que você escreveu contra uma thread pausada para sempre no pior momento.