Элиминационный стек: встретить противоположную операцию

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Тысяча потоков попеременно кладёт и забирает элементы. Каждая операция меняет один общий указатель вершины, хотя некоторые пары полностью отменяют друг друга. Можно ли передать новый элемент ожидающему pop и оставить вершину прежней? Ответ зависит от того, можно ли вставить такую пару в корректную последовательную историю стека.

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

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

Механизм: от определения к алгоритму

Стек Трайбера выполняет CAS на вершине: push публикует новый узел, pop заменяет вершину следующим узлом. При конкуренции проигравшие повторяют чтение и CAS. Элиминация добавляет возможность встретить противоположную операцию в независимом слоте массива. Push предлагает значение, pop предлагает запрос; успешный обмен завершает обе.

Почему LIFO не нарушается? Возьми успешную пару и выбери момент её атомарного подтверждения. В последовательную историю помести push(x) и сразу pop(), вернувший x. Между ними нет другой операции, после них старый стек не меняется. Их реальные интервалы должны пересекаться; заранее завершённый pop нельзя задним числом сопоставить будущему push. Для двух push или двух pop такого взаимного уничтожения нет.

Слот обмена имеет состояния вроде EMPTY, WAITING, BUSY и метку типа операции. Переход от ожидания к подтверждённой паре атомарен. При таймауте ожидающий пытается убрать собственное предложение CAS. Если не смог, партнёр уже подтвердил встречу: нужно забрать результат, а не повторять операцию на центральном стеке. Иначе push может опубликовать один элемент дважды или pop получить несуществующий.

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

Модель памяти и освобождение узлов никуда не исчезают. Элиминация снижает число обращений к вершине, но fallback по-прежнему требует корректного CAS, публикации и защиты от ABA. В среде со сборкой мусора одни проблемы проще, в ручном управлении памятью нужны hazard pointers, эпохи или другой доказанный протокол.

Правило

Напрямую завершаются только перекрывающиеся push/pop с атомарным подтверждением; после подтверждённой встречи операция не должна повторяться в центральном стеке.

Разбор: проследим вычисление

Смоделируем последовательный стек с одной уже найденной парой перекрывающихся операций. Для проверки линеаризации сравним прямой обмен с обычными push и pop, поставленными рядом. Счётчик CAS в этой модели - число центральных успешных изменений, не реальные попытки под конкуренцией. Программа не реализует многопоточный Exchanger.

class CentralStack:
    def __init__(self, items):
        self.items = list(items)
        self.changes = 0

    def push(self, value):
        self.items.append(value)
        self.changes += 1

    def pop(self):
        if not self.items:
            return None
        self.changes += 1
        return self.items.pop()

normal = CentralStack([10, 20])
normal.push(99)
answer = normal.pop()

exchanged = CentralStack([10, 20])
# Момент подтверждения пары: push(99), затем pop()->99.
paired_answer = 99
assert normal.items == exchanged.items
assert answer == paired_answer
print("pop получил", paired_answer)
print("стек после пары", exchanged.items)
print("изменений вершины", normal.changes, exchanged.changes)

# Без противоположного типа оба push идут в стек.
for value in (30, 40):
    exchanged.push(value)
print("две вставки", exchanged.items)
# Подтверждённый обмен нельзя повторять как fallback.
broken = CentralStack([10, 20])
broken.push(99)
print("ошибка повторной вставки", broken.items != normal.items)

pop получил 99
стек после пары [10, 20]
изменений вершины 2 0
две вставки [10, 20, 30, 40]
ошибка повторной вставки True

Разбор: где проходит граница

Пусть стек пуст и есть только push. Никто не сможет забрать предложенные значения. Каждый после ограниченного ожидания обязан вернуться к центральному стеку. Если каждый push ждёт партнёра бесконечно, программа перестаёт быть lock-free, хотя сам стек Трайбера этим свойством обладает. При одних pop встречи тоже бесполезны: пустота проверяется в центральном протоколе, а не выдумывается вторым потребителем.

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

Неатомарное снятие предложения по таймауту конкурирует с подтверждением партнёра. Проверка «слот пуст» без версии может спутать старую и новую встречу. Подмена пустого значения специальным маркером требует исключить этот маркер из обычных данных либо хранить отдельный тип результата. Тест с конечным итоговым размером не обнаружит обмен не теми значениями: сверяй также мультимножество выданного и добавленного.

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

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

Теперь сам

Центральный стек [A,B], где B сверху. Перекрываются push(C) и pop, встреча подтверждена. Что вернёт pop и что останется в центральном стеке? Сколько таких пар составят 7 push и 3 pop?