Замок на n потоков: фильтр, пекарня Лэмпорта и нижняя граница

Если ты знаешь, как устроены фильтр и пекарня, почему пекарня даёт «кто первый пришёл, тот первый вошёл» и откуда нижняя граница в n ячеек, листай до «Теперь сам».

Как думаешь, сколько обгонов

Пять потоков стоят в очереди к замку-пекарне. Поток только что взял талон. Сколько раз, в худшем случае, другие потоки войдут в критическую секцию раньше него?

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

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

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

Фильтр похож на систему шлюзов на канале: в каждой шлюзовой камере пропускают всех, кроме одного, и после нескольких камер дальше проходит ровно один корабль.

Механизм: уровни фильтра и талоны пекарни

Фильтр. У каждого потока уровень level[i], у каждого уровня L - жертва victim[L]. Поток проходит уровни L = 1, …, n − 1: пишет level[i] = L, затем victim[L] = i и ждёт, пока кто-то другой стоит на уровне L или выше И жертва уровня - он сам. Записать level = L могут все сразу, но ПРОЙТИ уровень L одновременно могут не больше n − L потоков: последний назвавший себя жертвой ждёт, пока остальные не продвинутся или не выйдут. После уровня n − 1 остаётся один - он в секции. На выходе level[i] = 0.

Пекарня. Поток поднимает флаг «хочу», читает талоны всех, берёт себе на единицу больше максимума и ждёт, пока у кого-то с поднятым флагом пара (талон, номер) меньше его пары. Чтение максимума и запись своего талона - разные шаги, поэтому двое могут взять одинаковый талон; ничью разбивает номер потока. Свойство «кто первый пришёл, тот первый вошёл»: если поток A записал талон раньше, чем B начал брать свой, B получит талон больше и не войдёт раньше A. Отсюда граница обгонов: опередить можно только тех, кто брал талон одновременно или раньше, - каждого не больше одного раза.

Правило

Фильтр: n − 1 уровней, на каждом - Петерсон с переменной-жертвой; даёт взаимоисключение и отсутствие голодания. Пекарня: талон на единицу больше максимума, ждать всех с меньшей парой (талон, номер); даёт «кто первый пришёл, тот первый вошёл» - не больше n − 1 обгонов, но талоны растут без предела. Любой замок без взаимоблокировки на одних чтениях и записях использует не меньше n ячеек памяти (Бёрнс и Линч: чужую запись в ячейку можно затереть так, что никто её не увидит) - отсюда нужда в аппаратных атомарных операциях.

Разбор: фильтр, проверенный перебором

Тот же приём, что для Петерсона: состояние - где стоит каждый поток плюс массивы level и victim. Перебор обходит все достижимые состояния и запоминает, сколько потоков бывало в секции одновременно.

def filtr(n):
    # n - 1 уровней; на уровне L поток пишет level[i] = L, потом
    # victim[L] = i и ждёт, пока другой на уровне >= L и жертва - он.
    # pc: 0 - вне замка; 3L - 2, 3L - 1, 3L - три шага уровня L;
    # sekciya = 3(n - 1) + 1 - критическая секция
    sekciya = 3 * (n - 1) + 1
    nachalo = [[0] * n, [0] * n, [-1] * n]
    vidim = {str(nachalo): True}
    stek = [nachalo]
    hudshee = 0
    while len(stek) > 0:
        pc, level, victim = stek.pop()
        v_sek = 0
        for t in range(n):
            if pc[t] == sekciya:
                v_sek = v_sek + 1
        hudshee = max(hudshee, v_sek)
        for t in range(n):
            p = pc[t]
            np = pc[:]
            nl = level[:]
            nv = victim[:]
            np[t] = p + 1
            if p == sekciya:
                nl[t] = 0
                np[t] = 0
            elif p % 3 == 1:
                nl[t] = (p + 2) // 3
            elif p % 3 == 2:
                nv[(p + 1) // 3] = t
            elif p > 0:
                L = p // 3
                kto_vyshe = False
                for k in range(n):
                    if k != t and level[k] >= L:
                        kto_vyshe = True
                if kto_vyshe and victim[L] == t:
                    continue
            s = [np, nl, nv]
            if str(s) not in vidim:
                vidim[str(s)] = True
                stek.append(s)
    return [len(vidim), hudshee]

for n in [2, 3]:
    print(n, "потока: состояний и наибольшее число в секции", filtr(n))

2 потока: состояний и наибольшее число в секции [43, 1]
3 потока: состояний и наибольшее число в секции [894, 1]

На двух потоках 43 состояния, на трёх - уже 894, и ни в одном двух потоков в секции нет: фильтр исключает при любом чередовании. Отсутствие голодания перебор не проверяет - его доказывают рассуждением (у Херлихи и Шавита это отдельная лемма). Рост числа состояний - цена метода: на четырёх потоках их десятки тысяч, на десяти - больше, чем можно перебрать. Поэтому перебор доказывает протокол для малого n, а для произвольного нужно рассуждение - то самое «уровень L проходят не больше n − L потоков», которое проверяется индукцией по уровням.

Разбор: честность пекарни и цена талонов

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

import random

def pekarnya(n, shagov, seed):
    # pc: 0 - флаг; 1 - прочитать max талонов; 2 - записать свой талон;
    # 3 - ждать; 4 - секция; 5 - выход
    random.seed(seed)
    flag = [0] * n
    talon = [0] * n
    moj = [0] * n
    nichej = 0
    pc = [0] * n
    vhodov = 0
    vhodov_pri_talone = [0] * n
    obgonov = 0
    max_talon = 0
    v_sekcii = 0
    for s in range(shagov):
        t = random.randint(0, n - 1)
        p = pc[t]
        if p == 0:
            flag[t] = 1
            pc[t] = 1
        elif p == 1:
            moj[t] = max(talon) + 1
            pc[t] = 2
        elif p == 2:
            talon[t] = moj[t]
            if talon.count(talon[t]) > 1:
                nichej = nichej + 1
            max_talon = max(max_talon, talon[t])
            vhodov_pri_talone[t] = vhodov
            pc[t] = 3
        elif p == 3:
            zhdat = False
            for k in range(n):
                if k != t and flag[k] == 1:
                    if talon[k] < talon[t] or (talon[k] == talon[t]
                                               and k < t):
                        zhdat = True
            if not zhdat:
                pc[t] = 4
                v_sekcii = v_sekcii + 1
                obgonov = max(obgonov, vhodov - vhodov_pri_talone[t])
                vhodov = vhodov + 1
        elif p == 4:
            if v_sekcii > 1:
                print("нарушение!")
            v_sekcii = v_sekcii - 1
            pc[t] = 5
        else:
            flag[t] = 0
            pc[t] = 0
    return [vhodov, obgonov, max_talon, nichej]

for n in [2, 3, 5]:
    print(n, "потоков: входов, худший обгон, max талон, ничьих",
          pekarnya(n, 4000, n))

2 потоков: входов, худший обгон, max талон, ничьих [440, 1, 404, 37]
3 потоков: входов, худший обгон, max талон, ничьих [292, 2, 270, 24]
5 потоков: входов, худший обгон, max талон, ничьих [189, 4, 172, 21]

Худший обгон ровно n − 1: 1 при двух потоках, 2 при трёх, 4 при пяти - больше не бывает никогда, сколько бы шагов ни прошло. Ничьих - десятки: двое прочитали один и тот же максимум, и номер потока решил, кто первый. А талоны растут почти как число входов: в этой версии при выходе талон не обнуляется (его игнорируют, пока флаг опущен), поэтому максимум растёт всегда; через 2³¹ ≈ 2,1 миллиарда входов знаковый 32-битный талон переполнится, и честность рухнет. Херлихи и Шавит разбирают ограниченные метки времени, которые решают это, но построение длинное и техническое.

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

Фильтр без отдельной записи уровня. Если сначала назвать себя жертвой, а потом поднять уровень, - повторяется ошибка Петерсона с переставленными строками: двое проходят уровень одновременно.

Пекарня без разбиения ничьих. Сравнение только по талону: двое с одинаковым номером оба видят, что меньших нет, и входят вместе. Ничьи в прогоне выше случались десятки раз.

Переполнение талонов. Знаковый 32-битный талон после 2³¹ − 1 в Java становится отрицательным, то есть самым маленьким (в C++ такое переполнение - неопределённое поведение), - поток обгоняет всю очередь, а в худшем случае вместе с кем-то попадает в секцию.

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

Сами фильтр и пекарня на практике не используются: порядка n ячеек на каждый замок и чтение всех чужих меток на каждом входе - слишком дорого. Но из них растут две вещи. Первая - доказательство (Бёрнс и Линч), что на чтениях и записях меньше n ячеек нельзя: ради этого в процессоры добавили test-and-set и compare-and-swap - следующая глава. Вторая - идея талонов: ticket lock, на котором ядро Linux жило с 2008 года, пока в 2015-м его не сменил qspinlock, - это пекарня, где талон выдаёт одна атомарная операция fetch_add, и честность «кто первый пришёл» сохраняется.

Теперь сам

1. Сколько уровней у фильтра на 8 потоков и сколько потоков могут одновременно пройти уровень 5?
2. Потоки взяли талоны: A - 7, B - 7, C - 5; номера потоков A = 0, B = 1, C = 2. В каком порядке они войдут?
3. Почему пекарня гарантирует не больше n − 1 обгонов, а не ноль?