Un explorateur d'entrelacements : trouver les bugs en énumérant les ordonnancements

Essayer des ordonnancements à la main ne trouve un bug que si l'on devine le bon. Un explorateur exécute le programme sous tous les ordonnancements, liste tous les résultats et vous remet l'ordonnancement qui l'a cassé. Pour deux threads qui comptent les jours de hausse de dix rendements SPY, il y a 210 ordonnancements, et seuls 10 donnent le bon compte.

Un ordonnancement est un ordre de tours, et le thread t en prend exactement lengths[t]. Pour compter les ordres, on met tous les tours à la file (la somme de leurs longueurs), ce qui se range d'autant de façons que la factorielle de ce nombre ; puis on divise par la factorielle des tours de chaque thread, car échanger deux tours d'un même thread ne donne pas un nouvel ordonnancement. C'est le coefficient multinomial. Il croît vite : deux threads de 2 tours n'ont que 6 ordonnancements, trois threads de 3 tours en ont 1 680 et deux threads de 10 tours en ont 184 756. C'est pourquoi personne ne peut vérifier un programme concurrent en essayant des ordonnancements au hasard et en espérant.

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

Dans le labo précédent, un thread était une liste d'étapes. Le vrai code s'écrit mieux en Python ordinaire : désormais un thread est un générateur qui prend le dictionnaire partagé et exécute yield avant chaque accès aux données partagées. Un appel de next() fait alors avancer le thread jusqu'à son prochain accès et pas plus, si bien qu'un tour est exactement une étape avec laquelle un autre thread peut s'entrelacer. run_threads amorce chaque générateur (l'exécute jusqu'à son premier yield), donne un tour au thread nommé par chaque entrée de l'ordonnancement, et quand l'ordonnancement se termine laisse les threads non terminés finir dans l'ordre des threads. all_schedules liste tous les ordres de tours en choisissant quel thread passe en premier puis en récurrant sur le reste. Ci-dessous, les six ordonnancements de deux threads qui incrémentent une fois chacun.

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}

Deux des six ordonnancements finissent à 2, les quatre autres à 1. Les deux bons sont ceux où un thread fait ses deux étapes avant que l'autre commence. Dans les quatre autres, les deux threads lisent avant que l'un écrive, ce qui est exactement la mise à jour perdue du labo précédent, trouvée cette fois sans deviner.

explore exécute le programme sous tous les ordonnancements et compte combien donnent chaque état final. La clé est un tuple trié de paires (nom, valeur) pour que des états égaux soient la même clé. find_schedule pose la question d'un rapport de bug : quel ordonnancement casse mon invariant ? Il renvoie le premier, et comme run_threads est déterministe on peut le rejouer, l'afficher ou le coller dans un test. S'il renvoie None, l'invariant tient sous tous les ordonnancements, ce qui est une preuve pour ce petit programme, pas un espoir.

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 bonne réponse, x = 5, n'apparaît que dans 10 ordonnancements sur 210, soit environ 5 %. Un test qui exécute le programme une fois, ou cent fois sur une vraie machine où les threads se chevauchent rarement de cette façon, passerait presque à chaque fois et livrerait quand même un bug. L'explorateur ne peut pas le rater, et find_schedule vous remet le premier coupable : [0, 0, 0, 1, 0, 1, 1, 1, 1, 1].

Le labo suit le cours : le nombre d'ordonnancements, la liste de tous, la machine qui exécute des threads générateurs sous un ordonnancement, l'explorateur qui compte les résultats, la recherche du premier ordonnancement qui casse un invariant et l'étude de deux threads qui comptent les jours de hausse de SPY.

• Fonction · questionS'appuie sur
• count_schedules(lengths)Combien d'ordonnancements le programme a-t-il ?De l'arithmétique simple
• all_schedules(lengths)Lesquels, dans l'ordre ?De l'arithmétique simple
• run_threads(make_threads, schedule, shared)Que laisse un ordonnancement ?De l'arithmétique simple
• explore(make_threads, lengths, shared)Quels résultats existent, et combien de fois ?all_schedulesrun_threads
• find_schedule(make_threads, lengths, check)Quel ordonnancement casse l'invariant en premier ?all_schedulesrun_threads
• study(bars)Combien d'ordonnancements du comptage SPY tournent mal ?count_schedulesexplorefind_schedule

Sujet suivant : l'explorateur montre que le bug est réel ; il faut maintenant le réparer. Atomiques et lecture-modification-écriture ajoute les opérations qu'un processeur peut faire en une seule étape indivisible, comme fetch-and-add et compare-and-swap, et vous vérifiez avec l'explorateur que le compteur est juste sous tous les ordonnancements.