Число консенсуса: почему для очереди нужен CAS, а не флаги

Если ты знаешь, что такое консенсус и число консенсуса, почему у регистров оно 1, у очереди 2, а у CAS бесконечно, и что из этого следует для неблокирующих структур, листай до «Теперь сам».

Как думаешь, хватит ли чтений и записей

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

Ответь себе до чтения. Кажется, что да: записать своё, прочитать чужое, выбрать меньшее. Разбор покажет расписание, где первый решит 5, а второй 3. И это не неудачный протокол: удачного нет.

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

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

Механизм: валентность и критическое состояние

Доказательство для регистров - рассуждение о состояниях протокола. Назовём состояние двувалентным, если из него ещё достижимы оба решения, и одновалентным, если исход уже предрешён. Начальное состояние, когда потоки предлагают разное, двувалентно: если первым и в одиночку пойдёт поток A, решит его значение, если B - его. Протокол обязан закончиться, значит, найдётся критическое состояние. Идём от начального состояния шагами, каждый раз выбирая шаг, после которого исход ещё не предрешён; бесконечно так идти нельзя - wait-free протокол конечен, - значит, придём в состояние, где уже любой шаг предрешает исход. Это и есть критическое: двувалентное, но следующий шаг A делает исход «как предложил A», а следующий шаг B - «как предложил B».

Каким может быть этот шаг? Если один из потоков читает - другой этого не видит: состояния «A прочитал, потом B шагнул» и «B шагнул» для B неразличимы, и он, продолжая в одиночку, решит одинаково - противоречие. Если оба пишут в разные ячейки - порядок записей не важен, состояния совпадают. Если оба пишут в одну - вторая запись стирает первую, и B снова не отличит одно от другого. Противоречие во всех случаях: у чтений и записей число консенсуса 1.

С очередью иначе: в ней лежат жетоны «победа» и «поражение», кто первым взял «победу» - решает своё, второй, вытянув «поражение», знает, что победил другой, и берёт его объявленное предложение. Для трёх это ломается: проигравших двое, и ни один не знает, кто из двух других победил. Число консенсуса очереди - 2. С CAS победитель один на любое число потоков: cas(первый, никто, я) проходит ровно у одного, и все читают его предложение.

Следствие (Херлихи и Шавит, глава 5): если объект решает консенсус для n потоков, его нельзя построить неблокирующим - ни wait-free, ни lock-free - из объектов с меньшим числом консенсуса. Очередь и стек решают консенсус для двух - значит, из одних регистров их не собрать. А универсальная конструкция Херлихи строит из CAS wait-free реализацию любого последовательного объекта: потоки договариваются консенсусом о порядке операций в общем журнале, и каждый применяет журнал к своей копии объекта. Чтобы никто не ждал вечно, потоки помогают друг другу: каждый объявляет свою операцию, и тот, кто добавляет запись в журнал, вписывает и чужие объявленные.

Правило

Число консенсуса - сколько потоков объект позволяет wait-free договориться о значении. Регистры (чтение и запись) - 1; очередь, стек, test-and-set, fetch-and-add, swap - 2; CAS и LL/SC - бесконечность. Объект с числом n нельзя неблокирующе построить из объектов с меньшим числом на n и более потоках. Из CAS неблокирующе строится любой объект.

Разбор: четыре протокола под перебором

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

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

def shag(protokol, s, p):
    k = len(s["pc"])
    pc = s["pc"][p]
    if pc == 0:                                  # объявить предложение
        s["predlog"][p] = s["vhod"][p]
    elif protokol == "очередь":                  # shared: очередь-жребий
        if pc == 1:
            s["loc"][p] = s["ochered"].pop(0)
        elif s["loc"][p] == "победа":
            s["reshenie"][p] = s["vhod"][p]
        else:                                    # проиграл - решает
            for q in range(k):                   # за другого
                if q != p and s["predlog"][q] != -1:
                    s["reshenie"][p] = s["predlog"][q]
    elif protokol == "CAS":
        if pc == 1:
            if s["pervyj"] == -1:                # cas(pervyj, -1, p)
                s["pervyj"] = p
        else:
            s["reshenie"][p] = s["predlog"][s["pervyj"]]
    else:                                        # чтения и записи
        if pc == 1:
            s["loc"][p] = s["predlog"][1 - p]
        elif s["loc"][p] == -1:
            s["reshenie"][p] = s["vhod"][p]
        else:
            s["reshenie"][p] = min(s["vhod"][p], s["loc"][p])
    s["pc"][p] = pc + 1

def kopiya(s):
    return {"vhod": s["vhod"], "pc": s["pc"][:],
            "predlog": s["predlog"][:], "loc": s["loc"][:],
            "reshenie": s["reshenie"][:],
            "ochered": s["ochered"][:], "pervyj": s["pervyj"]}

def proverit(protokol, s, put, vidennye, schet):
    # обход состояний: одно и то же состояние разными путями - один раз
    klyuch = str(s)
    if klyuch in vidennye:
        return
    vidennye[klyuch] = True
    hodit = []
    for p in range(len(s["pc"])):
        if s["pc"][p] < 3:
            hodit.append(p)
    if len(hodit) == 0:
        schet[0] = schet[0] + 1
        if len(set(s["reshenie"])) > 1 and schet[1] == "":
            schet[1] = str(put) + " -> решения " + str(s["reshenie"])
        return
    for p in hodit:
        s2 = kopiya(s)
        shag(protokol, s2, p)
        proverit(protokol, s2, put + [p], vidennye, schet)

zhrebij2 = ["победа", "поражение"]
zhrebij3 = ["победа", "поражение", "поражение"]
for protokol, vhod, ochered in [["очередь", [5, 3], zhrebij2],
                                ["регистры", [5, 3], []],
                                ["CAS", [5, 3, 8], []],
                                ["очередь", [5, 3, 8], zhrebij3]]:
    k = len(vhod)
    s = {"vhod": vhod, "pc": [0] * k, "predlog": [-1] * k,
         "loc": [0] * k, "reshenie": [-1] * k, "ochered": ochered,
         "pervyj": -1}
    vidennye = {}
    schet = [0, ""]
    proverit(protokol, s, [], vidennye, schet)
    print(protokol, "на", k, "потоках: состояний", len(vidennye),
          "конечных", schet[0])
    if schet[1] == "":
        print("   все решили одинаково")
    else:
        print("   разногласие:", schet[1])

очередь на 2 потоках: состояний 20 конечных 2
   все решили одинаково
регистры на 2 потоках: состояний 28 конечных 3
   разногласие: [0, 0, 0, 1, 1, 1] -> решения [5, 3]
CAS на 3 потоках: состояний 104 конечных 3
   все решили одинаково
очередь на 3 потоках: состояний 122 конечных 6
   разногласие: [0, 0, 0, 1, 1, 1, 2, 2, 2] -> решения [5, 5, 3]

Очередь на двоих верна во всех состояниях: два конечных исхода - победил поток 0 или поток 1, и оба решают одинаково. Регистры ломаются на самом простом расписании: поток 0 проходит целиком один - записал 5, увидел пустую ячейку соседа, решил 5; потом поток 1 записал 3, прочитал 5 и взял меньшее - 3. CAS на трёх верен: три конечных исхода, по числу возможных победителей.

Разбор: где кончается очередь

Очередь на троих: поток 0 вытянул «победу» и решил 5. Потоки 1 и 2 вытянули «поражение» - и каждый знает только, что победил кто-то другой. Поток 1 видит объявленное предложение одного потока 0 и берёт 5. Поток 2 к своему решению видит предложения обоих, 5 и 3, и не может знать, чьё выиграло: он взял 3. Перебор показывает одну неудачную попытку, а не доказательство, - доказательство то же рассуждение о критическом состоянии: после двух снятий из очереди третий поток не отличит, кто снял первым. Дополнительные регистры не спасают: рассуждение верно для любых чтений и записей, а победитель может уснуть, не успев записать, что победил. И ещё одно упрощение модели: решение проигравшего - один шаг, читающий все объявления сразу; с отдельными чтениями состояний больше, но разногласие остаётся. Граница правила «очередь решает консенсус»: решает, но только для двух.

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

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

Атомарные переменные без CAS. В языке или на платформе есть только атомарные чтения и записи: значит, неблокирующих структур на них не будет, нужен замок.

Счётчик на fetch-and-add как основа всего. Fetch-and-add дешевле CAS и wait-free, но его число консенсуса 2: для универсальной конструкции на многих потоках его мало.

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

Иерархия объясняет, почему у всех распространённых процессоров есть CAS или LL/SC (x86 cmpxchg, ARM - cas или пара ldxr/stxr, RISC-V - lr/sc в расширении A), почему java.util.concurrent.atomic строится вокруг compareAndSet, и почему разговор «давайте обойдёмся без CAS» заканчивается замком. Она же - ответ на собеседовании на вопрос «почему неблокирующую очередь нельзя сделать на volatile-флагах».

Теперь сам

1. Какое число консенсуса у стека и почему не больше?
2. Протокол на test-and-set для двух потоков: что делает поток, у которого test-and-set вернул «уже было»?
3. Что следует из того, что у fetch-and-add число консенсуса 2, а у CAS бесконечно?