Condiciones de carrera y por qué existen los cerrojos

Dos hilos suman 1 al mismo contador y el contador termina mal, sin error ni fallo. La línea x += 1 no es un paso sino tres, y el orden en que dos hilos intercalan esos pasos decide el resultado. En 1085 días de subida de SPY, 542 actualizaciones desaparecen; un cerrojo las devuelve todas.

Un procesador no puede sumar a un valor que vive en memoria. Carga el valor en un registro, suma al registro y guarda el registro de vuelta. Así que x += 1 es load x, add 1, store x. Un hilo solo hace los tres seguidos y nada puede salir mal. Con dos hilos, la máquina puede ejecutar un paso de uno y luego un paso del otro, en cualquier orden. Para verlo escribimos una pequeña máquina. Un hilo es una lista de pasos, cada uno con su propio registro; los hilos comparten un diccionario de valores con nombre. La función execute ejecuta un paso de un hilo. A continuación jugamos a mano los seis pasos de dos hilos, un paso cada uno por turnos.

def execute(op, shared, regs, locks, tid):    kind = op[0]    if kind == "load":        regs[tid] = shared.get(op[1], 0)    elif kind == "add":        regs[tid] += op[1]    elif kind == "store":        shared[op[1]] = regs[tid]    elif kind == "lock":        if op[1] in locks:            return False        locks[op[1]] = tid    elif kind == "unlock":        del locks[op[1]]    return Trueshared, regs, locks = {"x": 0}, {0: 0, 1: 0}, {}turns = [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2), (1, 2)]1for tid, step in turns:    execute(INCREMENT[step], shared, regs, locks, tid)    print("thread", tid, INCREMENT[step], "->", shared, regs)

thread 0 ('load', 'x') -> {'x': 0} {0: 0, 1: 0}
thread 1 ('load', 'x') -> {'x': 0} {0: 0, 1: 0}
thread 0 ('add', 1) -> {'x': 0} {0: 1, 1: 0}
thread 1 ('add', 1) -> {'x': 0} {0: 1, 1: 1}
thread 0 ('store', 'x') -> {'x': 1} {0: 1, 1: 1}
thread 1 ('store', 'x') -> {'x': 1} {0: 1, 1: 1}

1. 1Ambos hilos cargan antes de que alguno guarde: cada registro tiene 0.

Lea la salida línea a línea. El hilo 0 carga 0, el hilo 1 también carga 0 (el hilo 0 aún no ha guardado), ambos suman 1 a un registro que tiene 0 y ambos guardan 1. Dos hilos hicieron cada uno su x += 1, pero x vale 1, no 2. Se perdió una actualización. Nada fallaba en el código de ninguno de los hilos; el error existe solo en este orden de pasos.

En el mundo real la planificación la elige el sistema operativo y cambia de una ejecución a otra, por eso una carrera es tan difícil de reproducir. En nuestra máquina la elegimos nosotros. Una planificación es una lista de números de hilo, y run da un turno al hilo nombrado por cada entrada. Importan dos planificaciones simples. En la planificación en serie el hilo 0 ejecuta todos sus pasos y luego el hilo 1: es lo que esperamos. En la planificación por turnos los hilos dan un paso cada uno por turnos: es el peor caso para nuestro contador, porque los pasos de los dos hilos se solapan en todas partes. La función lost_updates compara lo que los incrementos debieron sumar con lo que muestra el contador.

def run(programs, schedule, shared=None):    shared = dict(shared or {})    regs = {tid: 0 for tid in range(len(programs))}    pcs = [0] * len(programs)    locks = {}    for tid in schedule:        if pcs[tid] < len(programs[tid]) and execute(programs[tid][pcs[tid]], shared, regs, locks, tid):            pcs[tid] += 1    while any(pcs[t] < len(programs[t]) for t in range(len(programs))):        progress = False        for tid in range(len(programs)):            if pcs[tid] < len(programs[tid]) and execute(programs[tid][pcs[tid]], shared, regs, locks, tid):                pcs[tid] += 1                progress = True        if not progress:            raise RuntimeError("deadlock")    return shareddef serial_schedule(programs):    return [tid for tid, program in enumerate(programs) for _ in program]def round_robin_schedule(programs):    longest = max((len(program) for program in programs), default=0)    return [tid for step in range(longest) for tid, program in enumerate(programs) if step < len(program)]def lost_updates(programs, schedule, name="x"):    expected = sum(op[1] for program in programs for op in program if op[0] == "add")    return expected - run(programs, schedule).get(name, 0)two = [INCREMENT, INCREMENT]print(serial_schedule(two), run(two, serial_schedule(two)))print(round_robin_schedule(two), run(two, round_robin_schedule(two)))print("lost:", lost_updates(two, round_robin_schedule(two)))

[0, 0, 0, 1, 1, 1] {'x': 2}
[0, 1, 0, 1, 0, 1] {'x': 1}
lost: 1

La planificación en serie [0, 0, 0, 1, 1, 1] da 2; la planificación por turnos [0, 1, 0, 1, 0, 1] da 1 y pierde una actualización. Observe lo que hace run cuando la planificación termina antes: los hilos sin terminar siguen tomando turnos, un paso cada uno en orden de hilo, así que todo programa termina siempre. Observe también que un hilo terminado ignora sus turnos, de modo que cualquier lista de números de hilo es una planificación válida.

Un cerrojo arregla la carrera prohibiendo el solapamiento. Un hilo toma el cerrojo antes de load y lo suelta después de store. Un segundo hilo que pida el cerrojo entre tanto no lo consigue: su turno no hace nada y se queda en el mismo paso hasta que el cerrojo esté libre. Los pasos entre lock y unlock se ejecutan así como un solo bloque y ningún otro hilo puede colarse. La función counter_program construye el programa de un hilo que incrementa un contador, con o sin el cerrojo. Los cerrojos traen un peligro nuevo, mostrado al final del código: dos hilos que toman dos cerrojos en órdenes opuestos pueden tener cada uno el cerrojo que necesita el otro, y ninguno puede avanzar. Es un interbloqueo, y nuestro run lo detecta cuando una pasada completa no avanza.

def counter_program(increments, locked=False):    program = []    for _ in range(increments):        program += ([("lock", "m")] if locked else []) + INCREMENT + ([("unlock", "m")] if locked else [])    return programsafe = [counter_program(1, locked=True), counter_program(1, locked=True)]print(counter_program(1, locked=True))print(run(safe, round_robin_schedule(safe)))ab = [[("lock", "a"), ("lock", "b"), ("unlock", "b"), ("unlock", "a")],      [("lock", "b"), ("lock", "a"), ("unlock", "a"), ("unlock", "b")]]try:    run(ab, [0, 1])except RuntimeError as error:    print("error:", error)

[('lock', 'm'), ('load', 'x'), ('add', 1), ('store', 'x'), ('unlock', 'm')]
{'x': 2}
error: deadlock

def study(bars):    returns = [float(r) for r in bars["close"].pct_change().dropna()][:2000]    ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]    free = [counter_program(k) for k in ups]    locked = [counter_program(k, locked=True) for k in ups]    return {"up": sum(ups),            "serial": run(free, serial_schedule(free))["x"],            "racy": run(free, round_robin_schedule(free))["x"],            "locked": run(locked, round_robin_schedule(locked))["x"]}print(study(load_bars()))

{'up': 1085, 'serial': 1085, 'racy': 543, 'locked': 1085}

Sin cerrojo, la planificación por turnos mantiene a los dos hilos a un paso de distancia, así que siempre cargan el mismo valor y cada par de incrementos cuenta una sola vez: se pierde cerca de la mitad de los 1085 días de subida. Un cerrojo restablece el total exacto, al precio de hacer esperar a un hilo.

El laboratorio sigue la lección: un paso de un hilo, la máquina entera bajo una planificación, las dos planificaciones simples, el recuento de actualizaciones perdidas, el programa de un hilo contador con y sin cerrojo, y el estudio de dos hilos que cuentan los días de subida de SPY.

• Función · preguntaSe apoya en
• execute(op, shared, regs, locks, tid)¿Qué hace un paso y tiene que esperar el hilo?Aritmética simple
• run(programs, schedule, shared)¿Qué dejan los hilos bajo esta planificación?execute
• serial_schedule(programs)¿Un hilo tras otro?Aritmética simple
• round_robin_schedule(programs)¿Un paso cada uno por turnos?Aritmética simple
• lost_updates(programs, schedule)¿Cuántos incrementos desaparecen?run
• counter_program(increments, locked)¿Qué hace un hilo contador?Aritmética simple
• study(bars)¿Cuántas actualizaciones cuesta una carrera en SPY?counter_programrunlost_updates

Siguiente tema: encontró la actualización perdida eligiendo una planificación a mano. Un programa real tiene demasiadas planificaciones para probarlas a mano. En Un explorador de intercalados enumera todas las planificaciones de un programa pequeño, cuenta las que lo rompen y conserva el explorador como herramienta para el resto de la habilidad.