Гарантии прогресса: взаимоблокировка, lock-free и wait-free

Если ты знаешь четыре условия взаимоблокировки, как её исключает порядок захвата и чем lock-free отличается от wait-free, листай до «Теперь сам».

Как думаешь, что случится

Три потока переводят деньги по кругу: первый со счёта 0 на счёт 1, второй с 1 на 2, третий с 2 на 0. Каждый захватывает замок счёта-отправителя, потом счёта-получателя, переводит и отпускает оба. Код каждого потока по отдельности верен. Что может пойти не так?

Ответь себе до чтения. Если каждый успел захватить свой первый замок, все трое ждут второй - а он у соседа. Ждать будут вечно. Насколько это часто, при случайном планировщике покажет разбор: больше трети прогонов.

На что это похоже

Перекрёсток без светофора, где каждая из четырёх машин въехала на середину и ждёт, пока проедет машина справа. Каждая держит свой кусок перекрёстка и ждёт чужой - никто не сдвинется. Правило «въезжай, только если свободен весь путь» или общий порядок проезда эту ничью разбивает.

А неблокирующий алгоритм похож на кольцевую развязку: машина, заглохшая на кольце, мешает только тем, кто прямо за ней, остальные объезжают её и продолжают движение.

Механизм: условия взаимоблокировки и лестница гарантий

Взаимоблокировка возможна, только если выполнены все четыре условия Коффмана (1971): ресурс держит один поток; поток держит ресурс и ждёт другой; ресурс нельзя отнять; есть цикл ожидания. Разорвать любое - значит исключить взаимоблокировку. Проще всего разорвать цикл: все потоки захватывают замки в одном общем порядке, например по номеру счёта. Тогда цикл невозможен: каждое ожидание направлено к замку с большим номером, а по возрастающей цепочке номеров нельзя вернуться в начало.

Для неблокирующих алгоритмов замков нет совсем, и гарантии описывают так:

• obstruction-free - если поток работает один (остальные приостановлены), он закончит за конечное число шагов;
• lock-free - при любом планировании какая-то операция заканчивается за конечное число шагов: система в целом движется, хотя отдельный поток может проигрывать вечно;
• wait-free - каждая операция заканчивается за ограниченное число шагов своего потока, что бы ни делали остальные.

Цикл CAS - lock-free: неудачная попытка означает, что чья-то попытка удалась. Но невезучий поток может проигрывать бесконечно, поэтому wait-free он не является. fetch_add в процессоре - wait-free: одна инструкция, а в модели вычислений атомарная инструкция считается одним шагом, который всегда завершается.

Правило

Взаимоблокировка требует цикла ожидания; общий порядок захвата замков его исключает. Замок не защищает от остановки владельца: уснувший с замком поток останавливает всех. Неблокирующие гарантии: obstruction-free (один закончит), lock-free (кто-то всегда заканчивает), wait-free (каждый заканчивает за ограниченное число шагов). Цикл CAS - lock-free, но не wait-free.

Разбор: переводы по кругу

Три потока, переводы 0 → 1, 1 → 2, 2 → 0. Шаги потока: захватить первый замок, захватить второй, перевести и отпустить оба. Планировщик выбирает случайный поток из тех, кто может сделать шаг; если таких нет, а работа не закончена, - взаимоблокировка. Сравним «сначала отправитель» и «сначала меньший номер».

import random

def progon(poryadok, seed):
    # у потока t перевод со счёта perevody[t][0] на perevody[t][1]:
    # замок одного счёта, потом другого, перевести, отпустить оба
    random.seed(seed)
    perevody = [[0, 1], [1, 2], [2, 0]]
    zamok = [-1, -1, -1]
    shag = [0, 0, 0]
    while True:
        gotovye = []
        for t in range(3):
            if shag[t] == 3:
                continue
            a = perevody[t][0]
            b = perevody[t][1]
            if poryadok:
                pervyj = min(a, b)
                vtoroj = max(a, b)
            else:
                pervyj = a
                vtoroj = b
            # шаги 0, 1 - взять замки; шаг 2 (-1) - перевести, отпустить
            nuzhen = [pervyj, vtoroj, -1][shag[t]]
            if nuzhen == -1 or zamok[nuzhen] == -1:
                gotovye.append([t, nuzhen])
        if len(gotovye) == 0:
            for t in range(3):
                if shag[t] != 3:
                    return "взаимоблокировка"
            return "всё переведено"
        t, nuzhen = gotovye[random.randint(0, len(gotovye) - 1)]
        if nuzhen == -1:
            for k in range(3):
                if zamok[k] == t:
                    zamok[k] = -1
        else:
            zamok[nuzhen] = t
        shag[t] = shag[t] + 1

for poryadok in [False, True]:
    bloki = 0
    for seed in range(200):
        if progon(poryadok, seed) == "взаимоблокировка":
            bloki = bloki + 1
    print("общий порядок:", poryadok, "- блокировок из 200:", bloki)

общий порядок: False - блокировок из 200: 75
общий порядок: True - блокировок из 200: 0

Без порядка - 75 взаимоблокировок из 200 прогонов, больше трети. С порядком - ни одной. Порядок не требует знать, что делают другие потоки: достаточно, чтобы все соблюдали одно правило. В базах данных так же: если все транзакции захватывают одни и те же строки в порядке первичного ключа и ничего больше не держат, взаимоблокировок между ними не бывает.

Разбор: поток уснул посреди операции

Четыре потока прибавляют к счётчику. Поток 0 в какой-то момент засыпает на 600 шагов - планировщик ОС снял его с ядра или случилась страничная ошибка (нужная страница памяти оказалась на диске, и поток ждёт, пока её прочитают) - и засыпает посреди операции: либо держа замок, либо уже прочитав значение для CAS.

import random

def progon(vid, seed):
    # 4 потока прибавляют к счётчику. Поток 0 засыпает на 600 шагов в
    # первый момент после шага 300, когда он посреди операции: держит
    # замок или уже прочитал c для CAS. Сколько прибавлений успеют
    # остальные, пока он спит?
    random.seed(seed)
    c = 0
    zamok = -1
    faza = [0] * 4
    prochital = [0] * 4
    son = -1
    za_son = 0
    for vremya in range(1500):
        if son == -1 and vremya >= 300 and faza[0] == 1:
            son = vremya
        spit = son != -1 and vremya < son + 600
        t = random.randint(0, 3)
        if t == 0 and spit:
            continue
        if vid == "замок":
            if faza[t] == 0 and zamok == -1:
                zamok = t
                faza[t] = 1
            elif faza[t] == 1:
                c = c + 1
                faza[t] = 2
                if spit:
                    za_son = za_son + 1
            elif faza[t] == 2:
                zamok = -1
                faza[t] = 0
        else:
            if faza[t] == 0:
                prochital[t] = c
                faza[t] = 1
            else:
                if c == prochital[t]:
                    c = c + 1
                    if spit:
                        za_son = za_son + 1
                faza[t] = 0
    return za_son

for vid in ["замок", "CAS"]:
    rezultaty = []
    for seed in range(6):
        rezultaty.append(progon(vid, seed))
    print(vid, "- прибавлений, пока поток 0 спал:", rezultaty)

замок - прибавлений, пока поток 0 спал: [0, 0, 0, 0, 0, 0]
CAS - прибавлений, пока поток 0 спал: [137, 131, 136, 124, 129, 122]

С замком - ноль прибавлений за всё время сна, во всех шести прогонах: остальные три потока исправны, но ждут замка, который держит спящий. С CAS - 122-137 прибавлений: спящий поток прочитал значение и уснул, но никому не мешает; когда проснётся, его CAS провалится, и он повторит попытку. Это и есть lock-free: остановка одного потока не останавливает систему. Шесть прогонов - иллюстрация, а гарантия держится на рассуждении: провал CAS бывает, только если чей-то CAS удался.

Что ломается без этого

Инверсия приоритетов. Низкоприоритетная задача держит замок, высокоприоритетная его ждёт, а среднеприоритетная, которой замок не нужен, вытесняет низкую - и владелец замка не получает процессор. В 1997 году так на марсоходе Mars Pathfinder сторожевой таймер раз за разом перезагружал бортовой компьютер; лечение - наследование приоритета: владелец замка временно получает приоритет того, кто его ждёт.

Замок в обработчике сигнала. Обработчик сигнала запускается в том же потоке, прерывая его в любом месте. Если поток в этот момент держал замок, обработчик ждёт его вечно: взаимоблокировка из одного потока. Поэтому в обработчиках сигналов разрешены только операции без замков.

«Lock-free» вместо «wait-free». Цикл CAS в системе реального времени: в среднем быстро, но конкретный поток может проигрывать сколько угодно раз, и гарантировать время ответа нельзя.

Зачем это в работе

Общий порядок захвата - стандартное правило в ядре Linux, его проверяет инструмент lockdep: он запоминает, в каком порядке захватывались замки, и сообщает о возможном цикле ещё до того, как взаимоблокировка случилась. Неблокирующие структуры - очереди в java.util.concurrent, crossbeam в Rust, очереди сообщений с одним писателем - выбирают там, где нельзя допустить, чтобы один медленный поток остановил остальных.

Сами неблокирующие структуры - стек ТрайбераРазбирается в разделе 25, глава «Неблокирующие структуры, консенсус и ABA»: Стек Трайбера: положить и снять одним CAS, очередь Майкла - СкоттРазбирается в разделе 25, глава «Неблокирующие структуры, консенсус и ABA»: Очередь Майкла - Скотт: два конца и помощь соседу - и их главная ловушка, проблема ABAРазбирается в разделе 25, глава «Неблокирующие структуры, консенсус и ABA»: Проблема ABA: CAS видит то же значение, а мир уже другой, когда CAS видит «то же самое» значение, которое на деле уже успело смениться и вернуться, - тема следующего раздела. Там же иерархия консенсуса: почему из чтений и записей неблокирующую очередь не построить, а из CAS - можно любой объект.

Теперь сам

1. Четыре потока захватывают замки A и B: два - в порядке A, B, два - в порядке B, A. Возможна ли взаимоблокировка? А если все - A, B?
2. Цикл CAS: поток 0 провалил CAS сто раз подряд. Нарушена ли гарантия lock-free?
3. Почему замок не может быть lock-free ни при какой реализации?