Una actualización perdida ocurre porque una lectura y una escritura son dos turnos con un hueco entre ellos. Una operación atómica cierra el hueco: la lectura, el cambio y la escritura ocurren en un paso indivisible. Con ella el contador es correcto bajo todas las planificaciones: 4 planificaciones en lugar de 28, y ninguna es errónea.
Un turno, sin hueco
En nuestra máquina un turno va de un yield al siguiente, así que nada de lo escrito entre dos yield puede intercalarse. Una función que no contiene ningún yield se comporta, pues, como una operación atómica. La más común es fetch-and-add: lee el valor viejo, escribe old + n y devuelve old, todo dentro de un turno. Un hilo contador que la llama tiene un solo yield para todo el incremento en lugar de dos, así que los dos hilos ya no pueden leer el mismo valor viejo.
def fetch_add(shared, name, n): old = shared.get(name, 0) shared[name] = old + n return olddef atomic_increments(k): def thread(shared): for _ in range(k): yield fetch_add(shared, "x", 1) return threadtwo = lambda shared: [atomic_increments(1)(shared), atomic_increments(1)(shared)]for prefix in ([0, 1], [1, 0]): print(prefix, run_prefix(two, prefix))
[0, 1] ({'x': 2}, [])
[1, 0] ({'x': 2}, [])Ambos órdenes terminan en {'x': 2} y ningún hilo queda vivo. Con un turno por incremento el programa solo tiene las dos planificaciones [0, 1] y [1, 0] (4 en el estudio, para 1 y 3 incrementos), y ninguna puede perder una actualización.
Comparar e intercambiar y el bucle de reintento
Fetch-and-add solo sabe sumar. Para todo lo demás hace falta la herramienta general, comparar-e-intercambiar (CAS). El patrón es un bucle: leer el valor viejo, calcular el nuevo a partir de él y pedir al CAS que lo instale solo si nadie cambió el valor entre tanto. Si el CAS falla, alguien llegó antes, así que se lee de nuevo y se reintenta. A continuación, dos contadores CAS: cuando el hilo 1 lee antes de que el hilo 0 haya escrito, su CAS falla una vez, cuenta un reintento y el segundo intento tiene éxito. La actualización nunca se pierde porque una escritura obsoleta es rechazada.
def compare_and_swap(shared, name, expected, new): if shared.get(name, 0) != expected: return False shared[name] = new return Truedef cas_increments(k): def thread(shared): for _ in range(k): while True: yield old = shared.get("x", 0) yield if compare_and_swap(shared, "x", old, old + 1): break fetch_add(shared, "retries", 1) return threadcas = lambda shared: [cas_increments(1)(shared), cas_increments(1)(shared)]print(run_prefix(cas, [0, 1, 0, 1]))print(run_prefix(cas, [0, 1, 0, 1, 1, 1]))
({'x': 1, 'retries': 1}, [1])
({'x': 2, 'retries': 1}, [])Tras [0, 1, 0, 1] el diccionario compartido es {'x': 1, 'retries': 1} y el hilo 1 sigue vivo: leyó 0, pero el hilo 0 ya había guardado 1, así que su comparar-e-intercambiar fue rechazado. Dando al hilo 1 sus dos turnos siguientes (leer de nuevo, intercambiar de nuevo) termina en x = 2. Note el precio: el perdedor hizo el trabajo dos veces. Fetch-and-add nunca reintenta; el CAS reintenta tantas veces como chocan los hilos.
Explorar cuando el número de turnos varía
El explorador del tema anterior suponía que cada hilo toma un número fijo de turnos, lengths. Un bucle de reintento lo rompe: un hilo que pierde una carrera toma turnos extra, y cuántos depende de la planificación. La solución es recorrer las planificaciones como un árbol. Desde un prefijo de turnos, run_prefix repite el programa y dice qué hilos siguen vivos; si no queda ninguno, la planificación está completa y se cuenta su estado final, y si quedan, se ramifica en cada uno. Esta búsqueda en profundidad visita cada planificación completa exactamente una vez. values_of lee después un nombre compartido de todos los resultados.
def explore_all(make_threads, shared=None): outcomes = {} def visit(prefix): final, alive = run_prefix(make_threads, prefix, shared) if not alive: key = tuple(sorted(final.items())) outcomes[key] = outcomes.get(key, 0) + 1 return for tid in alive: visit(prefix + [tid]) visit([]) return outcomesdef values_of(outcomes, name): return sorted({dict(key).get(name, 0) for key in outcomes})print(explore_all(cas))racy = lambda shared: [increments(1)(shared), increments(1)(shared)]print(values_of(explore_all(racy), "x"), values_of(explore_all(cas), "x"))
{(('x', 2),): 2, (('retries', 1), ('x', 2)): 4}
[1, 2] [2]En esta máquina cada operación es vista por todos los hilos a la vez y en orden. Un procesador real no lo promete para las lecturas y escrituras normales, e incluso una operación atómica hace que los núcleos se disputen la línea de caché. El siguiente tema elimina la primera suposición.
returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:6]ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]for name, factory in (("racy", increments), ("atomic", atomic_increments), ("cas", cas_increments)): outcomes = explore_all(lambda shared, f=factory: [f(k)(shared) for k in ups]) print(name, sum(outcomes.values()), "schedules, x in", values_of(outcomes, "x"))
racy 28 schedules, x in [1, 2, 3, 4] atomic 4 schedules, x in [4] cas 144 schedules, x in [4]
Las dos reparaciones son correctas bajo todas las planificaciones y se diferencian en el coste. Fetch-and-add hace el trabajo en un turno por incremento: 4 planificaciones. El contador CAS tiene 144 planificaciones, porque una colisión añade turnos, y en la peor un hilo reintenta 3 veces. Es el compromiso del código sin cerrojos: nadie espera un cerrojo, pero el ganador de cada carrera obliga al perdedor a repetir su trabajo.
Una operación que lee un valor compartido, calcula uno nuevo a partir de él y lo escribe de vuelta en un paso indivisible. Fetch-and-add y comparar-e-intercambiar son las dos que más usará; toda estructura sin cerrojos se construye con ellas.
Lo que va a construir
El laboratorio sigue la lección: fetch-and-add, comparar-e-intercambiar, un hilo contador construido sobre cada uno, el explorador que maneja hilos con un número variable de turnos, una utilidad que lee los valores de un nombre sobre todos los resultados y el estudio de tres contadores sobre los días de subida de SPY.
- Función · preguntaSe apoya en
- fetch_add(shared, name, n)¿Sumar n y qué había antes?Aritmética simple
- compare_and_swap(shared, name, expected, new)¿El valor seguía siendo lo que leí?Aritmética simple
- atomic_increments(k)¿Un contador sin hueco?fetch_add
- cas_increments(k)¿Un contador que reintenta en vez de perder?compare_and_swapfetch_add
- explore_all(make_threads, shared)¿Todos los resultados, sea cual sea el número de turnos?run_prefix
- values_of(outcomes, name)¿Qué valores toma este nombre?Aritmética simple
- study(bars)¿Cómo se comparan los tres contadores en SPY?explore_allvalues_of
Siguiente tema: supusimos que cada hilo ve cada escritura de inmediato y en orden. Un procesador real no lo promete. El modelo de memoria: acquire y release añade un búfer de escritura a la máquina, muestra a un lector que ve una bandera antes que los datos que protege y lo repara con el orden que menos cuesta.
Lab: qué se califica
7 tareas · 100 pts- Fetch-and-add5 pts
- Comparar e intercambiar10 pts
- Un contador con fetch-and-add10 pts
- Un contador con bucle de reintento20 pts
- Explorar todas las planificaciones20 pts
- Los valores de un nombre5 pts
- El estudio con la tabla de SPY30 pts