Garantías de progreso: de obstruction-free a wait-free

Tres contadores dan la respuesta correcta bajo todas las planificaciones y aun así no son iguales. Pause un hilo en el peor momento: el cerrojo de espera activa detiene a todos, el contador con comparar e intercambiar deja pasar a alguien y el contador fetch-and-add deja que cada hilo termine en 1 turno. Son los tres peldaños de la escala de garantías de progreso.

Un sistema operativo real puede sacar un hilo de su núcleo en cualquier momento: termina su porción de tiempo, un fallo de página lo manda al disco, llega una interrupción. Una buena estructura concurrente debe sobrevivir a eso. Precisamos la pregunta con un adversario. Ejecuta un prefix de turnos a su elección, luego pausa un hilo para siempre y damos un budget de rondas a todos los demás. Si algún hilo no pausado aún no ha terminado, la estructura puede ser detenida. Un cerrojo de espera activa falla esta prueba de la forma más simple: si el adversario pausa el hilo que tiene el cerrojo, los demás giran hasta que acaba el presupuesto.

def locked_increments(k):    def thread(shared):        for _ in range(k):            while True:                yield                if not shared.get("lock", 0):                    shared["lock"] = 1                    break            yield            value = shared.get("x", 0)            yield            shared["x"] = value + 1            yield            shared["lock"] = 0    return threaddef progress_without(make_threads, prefix, paused, budget=50):    n = len(make_threads({}))    allowed = [tid for tid in range(n) if tid not in paused]    _, alive = run_prefix(make_threads, list(prefix) + allowed * budget)    return [tid for tid in allowed if tid not in alive]lk = lambda shared: [locked_increments(1)(shared), locked_increments(1)(shared)]print(run_prefix(lk, [0]))print("thread 0 paused holding the lock:", progress_without(lk, [0], [0]))print("thread 0 finished first:         ", progress_without(lk, [0, 0, 0, 0], [0]))

({'lock': 1}, [0, 1])
thread 0 paused holding the lock: []
thread 0 finished first:          [1]

Tras un turno el hilo 0 tiene el cerrojo ('lock': 1). Pausado ahí, el hilo 1 no termina nada en cincuenta rondas: []. Si deja que el hilo 0 haga primero sus cuatro turnos, el cerrojo vuelve a estar libre y el hilo 1 termina: [1]. La diferencia es solo dónde golpea el adversario. Un cerrojo convierte cualquier pausa dentro de la sección crítica en una pausa del programa entero.

is_blocking automatiza al adversario. Prueba todos los prefijos de unos pocos turnos, pausa cada hilo vivo por turno y pregunta a progress_without si los demás aún terminan. Para el cerrojo de espera activa la respuesta es sí tras un solo turno. Para el contador con comparar e intercambiar nunca lo es: un hilo pausado entre su lectura y su intercambio simplemente deja el valor sin cambiar, así que el intercambio del otro hilo tiene éxito. Esta es la definición de sin cerrojos: el sistema en su conjunto siempre avanza, aunque un hilo esté detenido para siempre.

def is_blocking(make_threads, depth=3, budget=50):    def visit(prefix):        _, alive = run_prefix(make_threads, prefix)        for paused in alive:            finished = progress_without(make_threads, prefix, [paused], budget)            if len(finished) < len([tid for tid in range(len(make_threads({}))) if tid != paused]):                return True        if len(prefix) < depth:            return any(visit(prefix + [tid]) for tid in alive)        return False    return visit([])cs = lambda shared: [cas_increments(1)(shared), cas_increments(1)(shared)]at = lambda shared: [atomic_increments(1)(shared), atomic_increments(1)(shared)]print("spin lock:", is_blocking(lk))print("compare-and-swap:", is_blocking(cs))print("fetch-and-add:", is_blocking(at))

spin lock: True
compare-and-swap: False
fetch-and-add: False

Tanto el contador con comparar e intercambiar como el contador fetch-and-add son no bloqueantes. La escala tiene un tercer peldaño porque «sin cerrojos» aún permite un mal día a un hilo: puede perder todas las carreras.

Una operación wait-free tiene una cota sobre sus propios turnos que ningún vecino puede romper. worst_own_turns la mide: el mayor número de turnos que un hilo toma sobre todas las planificaciones completas. classify hace entonces la pregunta aguda. ¿El peor caso del hilo 0 se mantiene igual cuando su vecino tiene 1 incremento y cuando tiene 3? Si sí, el hilo 0 es wait-free. Si crece, el vecino puede hacer reintentar más al hilo 0, así que la estructura es solo lock-free.

def worst_own_turns(make_threads, tid):    worst = 0    def visit(prefix):        nonlocal worst        _, alive = run_prefix(make_threads, prefix)        if not alive:            worst = max(worst, prefix.count(tid))            return        for other in alive:            visit(prefix + [other])    visit([])    return worstdef classify(factory, others=(1, 3)):    def program(m):        return lambda shared: [factory(1)(shared), factory(m)(shared)]    if is_blocking(program(others[0])):        return "blocking"    light, busy = worst_own_turns(program(others[0]), 0), worst_own_turns(program(others[1]), 0)    return "wait-free" if light == busy else "lock-free"for neighbour in (1, 2, 3):    cas = lambda shared: [cas_increments(1)(shared), cas_increments(neighbour)(shared)]    atomic = lambda shared: [atomic_increments(1)(shared), atomic_increments(neighbour)(shared)]    print(neighbour, "increments next door: CAS", worst_own_turns(cas, 0), "turns, fetch-and-add", worst_own_turns(atomic, 0))print([classify(f) for f in (locked_increments, cas_increments, atomic_increments)])

1 increments next door: CAS 4 turns, fetch-and-add 1
2 increments next door: CAS 6 turns, fetch-and-add 1
3 increments next door: CAS 8 turns, fetch-and-add 1
['blocking', 'lock-free', 'wait-free']

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 (("locked", locked_increments), ("cas", cas_increments), ("atomic", atomic_increments)):    program = lambda shared, f=factory: [f(k)(shared) for k in ups]    blocking = is_blocking(program)    print(name, classify(factory), blocking, None if blocking else worst_own_turns(program, 0))

locked blocking True None
cas lock-free False 8
atomic wait-free False 1

Lea las barras: el hilo fetch-and-add necesita 1 turno por muy ocupado que esté su vecino, mientras que el hilo con comparar e intercambiar necesita 4, 6 y luego 8 turnos a medida que el vecino hace más incrementos. Cada incremento extra al lado puede hacer que el hilo 0 pierda una carrera más y repita su lectura y su intercambio. Ese crecimiento es exactamente lo que separa lock-free de wait-free.

El laboratorio sigue la lección: el contador con cerrojo de espera activa, la ejecución con algunos hilos pausados, la prueba que dice si pausar un hilo puede detener a los demás, el peor caso de los turnos propios de un hilo, la clasificación de un contador y el estudio de los tres contadores sobre los días de subida de SPY.

• Función · preguntaSe apoya en
• locked_increments(k)¿Un contador que espera un cerrojo?Aritmética simple
• progress_without(make_threads, prefix, paused, budget)¿Quién termina si algunos hilos están pausados?run_prefix
• is_blocking(make_threads, depth, budget)¿Puede un hilo pausado detener a todos?progress_without
• worst_own_turns(make_threads, tid)¿Cuántos turnos puede necesitar un hilo?run_prefix
• classify(factory, others)¿Bloqueante, lock-free o wait-free?is_blockingworst_own_turns
• study(bars)¿Dónde quedan los tres contadores en SPY?classifyis_blockingworst_own_turns

Siguiente tema: ya sabe lo que una cola podría prometer. Un búfer circular de un productor y un consumidor construye la cola sin cerrojos útil más simple, con un escritor y un lector, memoria fija y ninguna lectura-modificación-escritura atómica, y el explorador comprueba que nunca pierde ni reordena un tick.