El modelo de memoria: acquire y release

Un procesador es libre de ejecutar dos lecturas y escrituras independientes en cualquier orden, y otro núcleo puede ver el resultado de esa elección. Publique un precio de SPY y luego levante una bandera: un lector que ve la bandera aún puede leer un precio de 0. De las cuatro maneras de ordenar al escritor y al lector, solo una es segura: release en el escritor emparejado con acquire en el lector.

Los búferes de escritura, las cachés y el compilador dejan que un núcleo termine una escritura o lectura posterior antes que una anterior, mientras un solo hilo no pueda notarlo. Otro hilo sí puede. Nuestra máquina lo modela directamente: un hilo es una lista de operaciones y puede ejecutar, en cualquier orden, toda operación cuyas restricciones de orden se cumplen. Las operaciones sobre la misma dirección conservan siempre su orden, si no un hilo no vería sus propias escrituras. Una carga acquire bloquea todo lo que sigue; una escritura release espera todo lo anterior. Dos funciones lo dicen todo: must_wait lista lo que una operación espera y eligible lista lo que puede ejecutarse a continuación.

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]

La escritura release de la bandera espera a la posición 0, la escritura de los datos, así que el escritor solo puede ejecutar sus operaciones en orden. La carga acquire de la bandera bloquea la carga de datos que le sigue, así que el lector también se ejecuta en orden. Con cargas simples, ambas son elegibles a la vez y el lector puede leer los datos primero.

outcomes es el explorador de los temas anteriores para esta nueva máquina. Un estado es qué operaciones ha hecho cada hilo, la memoria y los registros. Desde un estado prueba cada operación elegible de cada hilo y, cuando no queda nada por ejecutar, los registros son un resultado. Como muchos órdenes llegan al mismo estado, recuerda los estados ya vistos. La prueba de paso de mensajes publica con dos escrituras, los datos y luego la bandera, y consume con dos cargas, la bandera y luego los datos. El consumidor se equivoca cuando ve r1 == 1 (la bandera) y r2 == 0 (aún sin datos), lo que comprueba reads_stale.

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

Con órdenes relaxed el consumidor puede terminar con los cuatro pares (r1, r2), incluido (1, 0), el obsoleto. Con release en la escritura de la bandera y acquire en su carga solo quedan tres: el lector que ve la bandera ve también los datos, porque ningún lado puede reordenarse a través de la bandera.

¿Basta un solo lado? Probemos las cuatro parejas. Release solo en el escritor falla: el lector puede cargar los datos antes que la bandera. Acquire solo en el lector falla: el escritor puede guardar la bandera antes que los datos. Solo funciona la pareja, como muestra la tabla siguiente. Es el contrato release-acquire de std::atomic de C++ y de Rust, y la razón por la que una cola sin cerrojos publica una casilla con una escritura release de un índice y la lee con una carga 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))]

Con el primer cierre de SPY, 9369 centavos, el lector puede ver la bandera y un precio de 0 en tres de las cuatro configuraciones. Un error de este tipo pasa todas las pruebas en una máquina que conserva el orden y aparece en otra. Por eso la pareja segura debe demostrarse sobre todos los órdenes permitidos, como hace el explorador.

El laboratorio sigue la lección: lo que una operación debe esperar, qué operaciones pueden ejecutarse a continuación, todos los resultados de un conjunto de hilos, la prueba de paso de mensajes, la comprobación de datos obsoletos, la tabla de los cuatro órdenes y el estudio que publica un precio real de SPY.

• Función · preguntaSe apoya en
• must_wait(ops, j)¿Qué debe esperar esta operación?Aritmética simple
• eligible(ops, done)¿Qué operaciones pueden ir a continuación?Aritmética simple
• outcomes(programs, memory)¿Con qué pueden terminar los hilos?eligible
• mp_programs(write_order, read_order)¿Cómo es el paso de mensajes?Aritmética simple
• reads_stale(results)¿Puede el lector ver la bandera sin los datos?Aritmética simple
• ordering_table()¿Qué parejas de órdenes son seguras?outcomesmp_programs
• study(bars)¿Qué parejas protegen un precio real de SPY?outcomesmp_programs

Siguiente tema: ya tiene las herramientas para construir una estructura sin cerrojos y un vocabulario para describir lo que garantiza. Las garantías de progreso nombran los tres niveles, obstruction-free, lock-free y wait-free, y prueban cada contador que escribió contra un hilo pausado para siempre en el peor momento.