Стек Трайбера: положить и снять одним CAS

Если ты знаешь, как устроены push и pop стека Трайбера, где у них точка линеаризации и почему стек lock-free, листай до «Теперь сам».

Как думаешь, что пойдёт не так

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

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

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

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

Механизм: две операции, одна ячейка

CAS из прошлого раздела: cas(ячейка, ожидаемое, новое) атомарно сравнивает и записывает, возвращая успех.

положить(x):
    узел = новый узел со значением x
    повторять:
        t = вершина
        узел.следующий = t
        если cas(вершина, t, узел): выйти

снять():
    повторять:
        t = вершина
        если t пусто: вернуть «пусто»
        n = t.следующий
        если cas(вершина, t, n): вернуть t.значение

Почему верно. CAS проходит, только если в вершине то же значение t. Он не проверяет историю: вершина могла уйти и вернуться (это проблема следующего урока). Но если узлы не переиспользуются, узел t и его «следующий» никогда не меняются, и всё, что поток подготовил, - узел.следующий = t или n = t.следующий - по-прежнему соответствует стеку. Изменения видны другим потокам с момента успешного CAS: это и есть точка линеаризации вставки и непустого снятия. Снятие из пустого стека линеаризуется на чтении пустой вершины и не вызывает CAS. Так в модели урока, где каждая запись сразу видна всем; в настоящем коде публикации CAS-ом нужен ещё порядок памяти (в C++ - memory_order_release у CAS и acquire у чтения вершины), иначе другой поток может увидеть узел раньше его поля «следующий».

Почему lock-free. CAS проваливается, только если вершину изменил другой поток, - а это и есть чужой успешный CAS. Значит, при любом планировании кто-то всегда продвигается. Wait-free стек при этом не является: невезучий поток может проигрывать сколько угодно раз.

Цена. Все потоки бьют в одну ячейку, и под нагрузкой CAS проваливается всё чаще. Херлихи и Шавит описывают лечение - устранение (elimination, Хендлер, Шавит, Ерушалми, 2004): «положить» и «снять», встретившиеся в отдельном массиве-обменнике, отдают элемент друг другу, не трогая вершину вовсе.

Правило

Стек Трайбера: вершина - одна ячейка, «положить» и «снять» - цикл «прочитать вершину, подготовить, CAS». Вставка и непустое снятие линеаризуются на успешном CAS, пустое снятие - на чтении пустой вершины. Lock-free: провал CAS означает чужой успех. Без CAS - простая запись вершины - стек теряет и дублирует элементы.

Разбор: все чередования двух потоков

Модель: шаг потока - одно атомарное действие с общей памятью. Узел - [значение, следующий], в начале в стеке один узел A. Поток 0 кладёт B и снимает, поток 1 кладёт C и снимает. Перебираем все чередования шагов и собираем разные итоги - с CAS и с обычной записью вершины. Модель укрупнена: чтение t.следующий склеено с CAS в один шаг. Здесь узлы не меняются, и порядок этих двух действий ничего не решает; в модели следующего урокаРазбирается в разделе 25, глава «Неблокирующие структуры, консенсус и ABA»: Проблема ABA: CAS видит то же значение, а мир уже другой, где узлы переиспользуются, это уже отдельные шаги.

# стек Трайбера в модели: шаг потока - одно атомарное действие с общей
# памятью. Узел - [значение, следующий]; вершина - номер узла или -1.
# Новый узел на каждое «положить», узлы не переиспользуются.

def nachalo(programmy):
    return {"verh": 0, "uzly": [["A", -1]], "pc": [0] * len(programmy),
            "op": [0] * len(programmy), "t": [-1] * len(programmy),
            "x": [-1] * len(programmy), "vyshlo": []}

def kopiya(s):
    uzly = []
    for u in s["uzly"]:
        uzly.append(u[:])
    return {"verh": s["verh"], "uzly": uzly, "pc": s["pc"][:],
            "op": s["op"][:], "t": s["t"][:], "x": s["x"][:],
            "vyshlo": s["vyshlo"][:]}

def shag(s, p, programmy, s_cas):
    op = programmy[p][s["op"][p]]
    pc = s["pc"][p]
    if op == "pop":
        if pc == 0:                          # прочитать вершину
            s["t"][p] = s["verh"]
            s["pc"][p] = 1
        elif s["t"][p] == -1:                # стек был пуст
            s["vyshlo"].append("пусто")
            s["op"][p] = s["op"][p] + 1
            s["pc"][p] = 0
        # с CAS - запись, только если вершина та же; без - всегда
        elif not s_cas or s["verh"] == s["t"][p]:
            s["verh"] = s["uzly"][s["t"][p]][1]
            s["vyshlo"].append(s["uzly"][s["t"][p]][0])
            s["op"][p] = s["op"][p] + 1
            s["pc"][p] = 0
        else:
            s["pc"][p] = 0                   # CAS провалился - заново
    else:
        if pc == 0:                          # новый узел, вершина - next
            s["uzly"].append([op, s["verh"]])
            s["x"][p] = len(s["uzly"]) - 1
            s["t"][p] = s["verh"]
            s["pc"][p] = 1
        elif not s_cas or s["verh"] == s["t"][p]:
            s["verh"] = s["x"][p]
            s["op"][p] = s["op"][p] + 1
            s["pc"][p] = 0
        else:
            s["uzly"][s["x"][p]][1] = s["verh"]   # перечитать вершину
            s["t"][p] = s["verh"]

def soderzhimoe(s):
    out = []
    v = s["verh"]
    while v != -1 and len(out) < 20:
        out.append(s["uzly"][v][0])
        v = s["uzly"][v][1]
    return out

def obojti(s, programmy, s_cas, itogi):
    # все чередования шагов; итог - содержимое стека и выданное
    hodit = []
    for p in range(len(programmy)):
        if s["op"][p] < len(programmy[p]):
            hodit.append(p)
    if len(hodit) == 0:
        vyshlo = s["vyshlo"][:]
        vyshlo.sort()
        itogi.append(str(soderzhimoe(s)) + " выдано " + str(vyshlo))
        return
    for p in hodit:
        s2 = kopiya(s)
        shag(s2, p, programmy, s_cas)
        obojti(s2, programmy, s_cas, itogi)

programmy = [["B", "pop"], ["C", "pop"]]
for s_cas in [True, False]:
    itogi = []
    obojti(nachalo(programmy), programmy, s_cas, itogi)
    raznye = []
    for i in itogi:
        if i not in raznye:
            raznye.append(i)
    raznye.sort()
    print("CAS:", s_cas, "- чередований", len(itogi))
    for i in raznye:
        print("  ", i)

CAS: True - чередований 174
   ['A'] выдано ['B', 'C']
CAS: False - чередований 70
   ['A'] выдано ['B', 'B']
   ['A'] выдано ['B', 'C']
   ['A'] выдано ['C', 'C']
   ['B', 'A'] выдано ['B', 'C']
   ['B', 'A'] выдано ['C', 'C']
   ['C', 'A'] выдано ['B', 'B']
   ['C', 'A'] выдано ['B', 'C']
   [] выдано ['A', 'B']
   [] выдано ['A', 'C']

С CAS - 174 чередования (провалы CAS добавляют повторы) и единственный итог: в стеке A, выданы B и C. Это и есть все возможные последовательные исходы по составу (программа сортирует выданное, порядок выдачи B, C или C, B она не различает): каждый снимает после своей вставки, поэтому A не снимет никто, а B и C уйдут оба.

Разбор: что делает простая запись

Без CAS 70 чередований дают девять разных итогов, и восемь из них невозможны при последовательном исполнении. выдано ['B', 'B'] - оба потока прочитали одну вершину B и оба её «сняли»: элемент выдан дважды. ['C', 'A'] с выдано ['B', 'B'] - то же, плюс лишний C остался в стеке. [] выдано ['A', 'B'] - вставка C записала свой узел поверх вершины, которую тут же затёрла чужая запись, и C пропал совсем, а снять пришлось A. Граница правила «CAS делает операцию атомарной»: CAS защищает только одну ячейку. Всё, что поток прочитал до CAS, должно быть верно, пока ячейка не изменилась, - в следующем уроке это условие нарушится.

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

«Прочитал - записал» без CAS. Потерянные вставки и двойные выдачи; в тестах на двух потоках - редко, под нагрузкой - постоянно.

Замок вокруг стека. Работает, но поток, уснувший с замком, останавливает всех (раздел про разделяемую память), а очередь на замок под нагрузкой хуже провалов CAS.

Горячая вершина. Тысячи потоков на одном CAS: почти все попытки проваливаются, процессоры заняты перечитыванием одной строки кеша. Лечат устранением, разнесением на несколько стеков или паузой между попытками.

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

Стек Трайбера - основа пулов свободных объектов и списков задач в планировщиках: аллокаторы памяти держат освобождённые блоки в таких стеках, деки кражи работы из прошлого раздела строятся по тем же правилам («прочитай - подготовь - CAS»). Тот же шаблон - в java.util.concurrent и crossbeam в Rust. И почти везде, где он реализован на языке без сборщика мусора, рядом стоит защита от проблемы следующего урока.

Теперь сам

1. Где точка линеаризации операции «снять» у стека, который оказался пуст?
2. Почему CAS в «положить» сравнивает вершину именно с t, а не с чем-то ещё?
3. Поток 0 провалил CAS в «снять» пять раз подряд. Что можно сказать про остальные потоки?