Courses critiques et raison d'être des verrous

Deux threads ajoutent 1 au même compteur, et le compteur finit faux, sans erreur ni plantage. La ligne x += 1 n'est pas une étape mais trois, et l'ordre dans lequel deux threads entrelacent ces étapes décide du résultat. Sur 1 085 jours de hausse de SPY, 542 mises à jour disparaissent ; un verrou les ramène toutes.

Un processeur ne peut pas ajouter à une valeur qui vit en mémoire. Il charge la valeur dans un registre, ajoute au registre, puis range le registre en mémoire. Donc x += 1 est load x, add 1, store x. Un thread seul fait les trois d'affilée et rien ne peut mal tourner. Avec deux threads, la machine peut exécuter une étape de l'un, puis une étape de l'autre, dans n'importe quel ordre. Pour le voir, nous écrivons une minuscule machine. Un thread est une liste d'étapes, avec son propre registre ; les threads partagent un dictionnaire de valeurs nommées. La fonction execute exécute une étape d'un thread. Ci-dessous nous jouons à la main les six étapes de deux threads, une étape chacun à tour de rôle.

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. 1Les deux threads chargent avant que l'un range : chaque registre contient 0.

Lisez la sortie ligne par ligne. Le thread 0 charge 0, le thread 1 charge 0 aussi (le thread 0 n'a pas encore rangé), les deux ajoutent 1 à un registre qui contient 0, et les deux rangent 1. Deux threads ont chacun fait leur x += 1, pourtant x vaut 1, pas 2. Une mise à jour a été perdue. Rien ne clochait dans le code de l'un ou l'autre thread ; le bug n'existe que dans cet ordre d'étapes.

Dans le monde réel, l'ordonnancement est choisi par le système d'exploitation et change d'une exécution à l'autre, ce qui rend une course si difficile à reproduire. Dans notre machine, nous le choisissons. Un ordonnancement est une liste de numéros de threads, et run donne un tour au thread nommé par chaque entrée. Deux ordonnancements simples comptent. Dans l'ordonnancement en série, le thread 0 exécute toutes ses étapes, puis le thread 1 : c'est ce qu'on espère. Dans l'ordonnancement en tourniquet, les threads font une étape chacun à tour de rôle : c'est le pire cas pour notre compteur, car les étapes des deux threads se chevauchent partout. La fonction lost_updates compare ce que les incréments auraient dû ajouter avec ce que montre le compteur.

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

L'ordonnancement en série [0, 0, 0, 1, 1, 1] donne 2 ; l'ordonnancement en tourniquet [0, 1, 0, 1, 0, 1] donne 1 et perd une mise à jour. Remarquez ce que fait run quand l'ordonnancement se termine trop tôt : les threads non terminés continuent à prendre des tours, une étape chacun dans l'ordre des threads, si bien que chaque programme finit toujours. Remarquez aussi qu'un thread terminé ignore ses tours, donc toute liste de numéros de threads est un ordonnancement valide.

Un verrou règle la course en interdisant le chevauchement. Un thread prend le verrou avant load et le libère après store. Un second thread qui demande le verrou entre-temps ne l'obtient pas : son tour ne fait rien et il reste à la même étape jusqu'à ce que le verrou soit libre. Les étapes entre lock et unlock s'exécutent donc comme un seul bloc, et aucun autre thread ne peut s'y glisser. La fonction counter_program construit le programme d'un thread qui incrémente un compteur, avec ou sans verrou. Les verrous apportent un nouveau danger, montré à la fin du code : deux threads qui prennent deux verrous dans des ordres opposés peuvent chacun détenir le verrou dont l'autre a besoin, et aucun ne peut plus avancer. C'est un interblocage, et notre run le détecte quand un passage complet ne fait aucun progrès.

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}

Sans verrou, l'ordonnancement en tourniquet garde les deux threads à une étape d'écart, si bien qu'ils chargent toujours la même valeur et que chaque paire d'incréments ne compte qu'une fois : environ la moitié des 1 085 jours de hausse est perdue. Un verrou rétablit le total exact, au prix de faire attendre un thread.

Le labo suit le cours : une étape d'un thread, la machine entière sous un ordonnancement, les deux ordonnancements simples, le décompte des mises à jour perdues, le programme d'un thread compteur avec et sans verrou, et l'étude de deux threads qui comptent les jours de hausse de SPY.

• Fonction · questionS'appuie sur
• execute(op, shared, regs, locks, tid)Que fait une étape, et le thread doit-il attendre ?De l'arithmétique simple
• run(programs, schedule, shared)Que laissent les threads sous cet ordonnancement ?execute
• serial_schedule(programs)Un thread après l'autre ?De l'arithmétique simple
• round_robin_schedule(programs)Une étape chacun à tour de rôle ?De l'arithmétique simple
• lost_updates(programs, schedule)Combien d'incréments disparaissent ?run
• counter_program(increments, locked)Que fait un thread compteur ?De l'arithmétique simple
• study(bars)Combien de mises à jour une course coûte-t-elle sur SPY ?counter_programrunlost_updates

Sujet suivant : vous avez trouvé la mise à jour perdue en choisissant un ordonnancement à la main. Un vrai programme a beaucoup trop d'ordonnancements pour les essayer à la main. Dans Un explorateur d'entrelacements, vous énumérez tous les ordonnancements d'un petit programme, comptez ceux qui le cassent, et gardez l'explorateur comme outil pour le reste de la compétence.