Un explorador de intercalados: encontrar errores enumerando planificaciones

Probar planificaciones a mano solo encuentra un error si adivina la correcta. Un explorador ejecuta el programa bajo todas las planificaciones, lista todos los resultados y le entrega la planificación que lo rompió. Para dos hilos que cuentan los días de subida de diez rendimientos de SPY hay 210 planificaciones, y solo 10 dan la cuenta correcta.

Una planificación es un orden de turnos, y el hilo t toma exactamente lengths[t] de ellos. Para contar los órdenes se ponen todos los turnos en fila (la suma de sus longitudes), que se pueden ordenar tantas maneras como el factorial de ese número; luego se divide por el factorial de los turnos de cada hilo, porque intercambiar dos turnos del mismo hilo no da una planificación nueva. Es el coeficiente multinomial. Crece rápido: dos hilos de 2 turnos tienen solo 6 planificaciones, tres hilos de 3 turnos tienen 1680 y dos hilos de 10 turnos tienen 184 756. Por eso nadie puede comprobar un programa concurrente probando planificaciones al azar y esperando.

def count_schedules(lengths):    total = factorial(sum(lengths))    for n in lengths:        total //= factorial(n)    return totalprint(count_schedules([2, 2]))print(count_schedules([3, 3, 3]))print(count_schedules([10, 10]))

6
1680
184756

En el laboratorio anterior un hilo era una lista de pasos. El código real se escribe mejor en Python normal, así que desde ahora un hilo es un generador que toma el diccionario compartido y ejecuta yield antes de cada acceso a datos compartidos. Una llamada a next() hace avanzar el hilo hasta su próximo acceso y no más, de modo que un turno es exactamente un paso con el que otro hilo puede intercalarse. run_threads prepara cada generador (lo ejecuta hasta su primer yield), da un turno al hilo nombrado por cada entrada de la planificación y, cuando la planificación termina, deja que los hilos sin terminar acaben en orden de hilo. all_schedules lista todos los órdenes de turnos eligiendo qué hilo va primero y recurriendo sobre lo que queda. A continuación, las seis planificaciones de dos hilos que incrementan una vez cada uno.

def all_schedules(lengths):    if sum(lengths) == 0:        return [[]]    out = []    for tid, n in enumerate(lengths):        if n:            rest = list(lengths)            rest[tid] -= 1            out += [[tid] + tail for tail in all_schedules(rest)]    return outdef run_threads(make_threads, schedule, shared=None):    shared = dict(shared or {})    threads = make_threads(shared)    alive = [True] * len(threads)    def turn(tid):        try:            next(threads[tid])        except StopIteration:            alive[tid] = False    for tid in range(len(threads)):        turn(tid)    for tid in schedule:        if alive[tid]:            turn(tid)    while any(alive):        for tid in range(len(threads)):            if alive[tid]:                turn(tid)    return sharedtwo = lambda shared: [increments(1)(shared), increments(1)(shared)]for schedule in all_schedules([2, 2]):    print(schedule, run_threads(two, schedule))

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

Dos de las seis planificaciones terminan en 2 y las otras cuatro en 1. Las dos buenas son aquellas en que un hilo hace sus dos pasos antes de que empiece el otro. En las otras cuatro ambos hilos leen antes de que alguno escriba, que es exactamente la actualización perdida del laboratorio anterior, ahora encontrada sin adivinar.

explore ejecuta el programa bajo todas las planificaciones y cuenta cuántas dan cada estado final. La clave es una tupla ordenada de pares (nombre, valor) para que estados iguales sean la misma clave. find_schedule hace la pregunta de un informe de error: ¿qué planificación rompe mi invariante? Devuelve la primera y, como run_threads es determinista, se puede repetir, imprimir o pegar en una prueba. Si devuelve None, el invariante se cumple bajo todas las planificaciones, lo que es una demostración para este programa pequeño, no una esperanza.

def explore(make_threads, lengths, shared=None):    outcomes = {}    for schedule in all_schedules(lengths):        key = tuple(sorted(run_threads(make_threads, schedule, shared).items()))        outcomes[key] = outcomes.get(key, 0) + 1    return outcomesdef find_schedule(make_threads, lengths, check, shared=None):    for schedule in all_schedules(lengths):        if not check(run_threads(make_threads, schedule, shared)):            return schedule    return Noneprint(explore(two, [2, 2]))print(find_schedule(two, [2, 2], lambda shared: shared["x"] == 2))

{(('x', 2),): 2, (('x', 1),): 4}
[0, 1, 0, 1]

returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:10]ups = [sum(1 for r in returns[start::2] if r > 0) for start in (0, 1)]lengths = [2 * k for k in ups]many = lambda shared: [increments(k)(shared) for k in ups]print(ups, count_schedules(lengths))print({dict(key)["x"]: n for key, n in explore(many, lengths).items()})

[2, 3] 210
{5: 10, 4: 70, 3: 104, 2: 26}

La respuesta correcta, x = 5, aparece en solo 10 de 210 planificaciones, alrededor del 5 %. Una prueba que ejecute el programa una vez, o cien veces en una máquina real donde los hilos rara vez se solapan exactamente así, pasaría casi siempre y aun así entregaría un error. El explorador no puede fallar, y find_schedule le entrega el primer culpable: [0, 0, 0, 1, 0, 1, 1, 1, 1, 1].

El laboratorio sigue la lección: el número de planificaciones, la lista de todas, la máquina que ejecuta hilos generadores bajo una planificación, el explorador que cuenta resultados, la búsqueda de la primera planificación que rompe un invariante y el estudio de dos hilos que cuentan días de subida de SPY.

• Función · preguntaSe apoya en
• count_schedules(lengths)¿Cuántas planificaciones tiene el programa?Aritmética simple
• all_schedules(lengths)¿Cuáles son, en orden?Aritmética simple
• run_threads(make_threads, schedule, shared)¿Qué deja una planificación?Aritmética simple
• explore(make_threads, lengths, shared)¿Qué resultados existen y cuántas veces?all_schedulesrun_threads
• find_schedule(make_threads, lengths, check)¿Qué planificación rompe primero el invariante?all_schedulesrun_threads
• study(bars)¿Cuántas planificaciones del conteo de SPY salen mal?count_schedulesexplorefind_schedule

Siguiente tema: el explorador muestra que el error es real; ahora lo reparamos. Atómicas y lectura-modificación-escritura añade las operaciones que un procesador puede hacer en un paso indivisible, como fetch-and-add y compare-and-swap, y comprueba con el explorador que el contador es correcto bajo todas las planificaciones.