Garanties de progression : de l'absence d'obstruction à l'absence d'attente

Trois compteurs donnent la bonne réponse sous tous les ordonnancements, et pourtant ils ne sont pas pareils. Mettez un thread en pause au pire moment : le verrou tournant arrête tout le monde, le compteur à comparer-et-échanger laisse passer quelqu'un, et le compteur fetch-and-add laisse chaque thread finir en 1 tour. Ce sont les trois échelons de l'échelle des garanties de progression.

Un vrai système d'exploitation peut retirer un thread de son cœur à tout moment : sa tranche de temps se termine, un défaut de page l'envoie sur le disque, une interruption arrive. Une bonne structure concurrente doit y survivre. Nous précisons la question avec un adversaire. Il exécute un prefix de tours de son choix, puis met un thread en pause pour toujours, et nous donnons un budget de tours à tous les autres. Si un thread non suspendu n'a toujours pas fini, la structure peut être arrêtée. Un verrou tournant échoue à ce test de la façon la plus simple : si l'adversaire met en pause le thread qui détient le verrou, les autres tournent jusqu'à la fin du budget.

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]

Après un tour, le thread 0 détient le verrou ('lock': 1). Mettez-le en pause là et le thread 1 ne finit rien en cinquante tours : []. Laissez d'abord le thread 0 faire ses quatre tours et le verrou est de nouveau libre, donc le thread 1 finit : [1]. La différence tient seulement à l'endroit où l'adversaire frappe. Un verrou transforme toute pause dans la section critique en pause du programme entier.

is_blocking automatise l'adversaire. Il essaie tous les préfixes de quelques tours, met en pause chaque thread vivant à tour de rôle, et demande à progress_without si les autres finissent encore. Pour le verrou tournant, la réponse est oui après un seul tour. Pour le compteur à comparer-et-échanger, jamais : un thread en pause entre sa lecture et son échange laisse simplement la valeur inchangée, donc l'échange de l'autre thread réussit. C'est la définition du sans verrou : le système dans son ensemble avance toujours, même si un thread est arrêté pour toujours.

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

Le compteur à comparer-et-échanger et le compteur fetch-and-add sont tous deux non bloquants. L'échelle a un troisième échelon parce que « sans verrou » permet encore une mauvaise journée à un thread : il peut perdre toutes les courses.

Une opération sans attente a une borne sur ses propres tours qu'aucun voisin ne peut dépasser. worst_own_turns la mesure : le plus grand nombre de tours qu'un thread prend sur tous les ordonnancements complets. classify pose alors la question décisive. Le pire cas du thread 0 reste-t-il le même quand son voisin a 1 incrément et quand il en a 3 ? Si oui, le thread 0 est sans attente. S'il croît, le voisin peut faire réessayer davantage le thread 0, donc la structure est seulement sans verrou.

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

Lisez les barres : le thread fetch-and-add a besoin de 1 tour quelle que soit l'activité de son voisin, alors que le thread à comparer-et-échanger en demande 4, 6, puis 8 à mesure que le voisin fait plus d'incréments. Chaque incrément supplémentaire à côté peut faire perdre une course de plus au thread 0 et lui faire répéter sa lecture et son échange. Cette croissance est exactement ce qui sépare sans verrou de sans attente.

Le labo suit le cours : le compteur à verrou tournant, l'exécution avec des threads en pause, le test qui dit si la pause d'un thread peut arrêter les autres, le pire cas des tours propres d'un thread, la classification d'un compteur et l'étude des trois compteurs sur les jours de hausse de SPY.

• Fonction · questionS'appuie sur
• locked_increments(k)Un compteur qui attend un verrou ?De l'arithmétique simple
• progress_without(make_threads, prefix, paused, budget)Qui finit si des threads sont en pause ?run_prefix
• is_blocking(make_threads, depth, budget)Un thread en pause peut-il arrêter tout le monde ?progress_without
• worst_own_turns(make_threads, tid)De combien de tours un thread peut-il avoir besoin ?run_prefix
• classify(factory, others)Bloquant, sans verrou ou sans attente ?is_blockingworst_own_turns
• study(bars)Où se situent les trois compteurs sur SPY ?classifyis_blockingworst_own_turns

Sujet suivant : vous savez maintenant ce qu'une file pourrait promettre. Un tampon circulaire à un producteur et un consommateur construit la file sans verrou utile la plus simple, avec un écrivain et un lecteur, une mémoire fixe et aucune lecture-modification-écriture atomique, et l'explorateur vérifie qu'elle ne perd ni ne réordonne jamais un tick.