Конспект: неблокирующие структуры, ABA и консенсус

Понятия

Стек Трайбера - вершина в одной ячейке, «положить» и «снять» - цикл «прочитать, подготовить, CAS».

Проблема ABA - CAS видит то же значение (A → B → A) и проходит, хотя всё прочитанное до него устарело.

Метка версии - счётчик рядом с указателем, который CAS сверяет и увеличивает. LL/SC - запись, которая проваливается после любой записи в ячейку. Hazard pointers, эпохи, RCU - схемы безопасного освобождения: узел не переиспользуется, пока его может читать другой поток.

Очередь Майкла - Скотт - фиктивный узел, голова на него, хвост на последний или предпоследний; помощь - доделать чужую незаконченную операцию.

Консенсус - все потоки wait-free решают одно значение из предложенных. Число консенсуса - для скольких потоков объект это позволяет.

Что унести

СТЕК ТРАЙБЕРА (1986)
положить: узел.next = t = вершина; cas(вершина, t, узел); провал - заново
снять:    t = вершина; n = t.next; cas(вершина, t, n); провал - заново
вставка и непустое снятие: линеаризация на успешном CAS
пустое снятие: чтение пустой вершины; lock-free, не wait-free
модель: с CAS 174 чередования - один итог; запись без CAS - 9 итогов
под нагрузкой - устранение (Хендлер, Шавит, Ерушалми, 2004)

ABA
поток: t = A, n = B ... уснул
другие: снять A, снять B, положить D в узел A
CAS(A -> B) проходит: вершина B (уже в пуле), D потерян
модель: 121 состояние, 1 испорченный конец; с метками - 0
защита: метка версии (cmpxchg16b, AtomicStampedReference),
        LL/SC (ldxr/stxr, lr/sc), hazard pointers, эпохи, RCU
C++26: std::hazard_pointer (P2530), RCU (P2545)
метка не спасает от чтения освобождённой памяти

ОЧЕРЕДЬ МАЙКЛА - СКОТТ (1996)
вставка: cas(t.next, пусто, узел) - линеаризация
         потом cas(хвост, t, узел)
хвост отстал (t.next не пуст) - cas(хвост, t, t.next), заново
выемка: h == t и есть next - помочь хвосту; иначе cas(голова, h, next)
модель: 3 потока, 1059 состояний, 4 итога - все линеаризуемы
уснул между CAS: без помощи сосед - 100 шагов впустую, с помощью - 7
ConcurrentLinkedQueue в Java

КОНСЕНСУС (ХЕРЛИХИ, 1991)
чтения и записи                    1
очередь, стек, TAS, fetch_add      2
CAS, LL/SC                         ∞
объект с числом n не построить неблокирующе из объектов с меньшим
  числом на n и более потоках: очередь из регистров - нельзя
из CAS - любой объект (универсальная конструкция)
модель: регистры на 2 - разногласие 5/3; очередь на 3 - разногласие

Ловушки джокера

«Прочитал - записал» вместо CAS. Потерянные вставки и двойные выдачи.

Пул узлов в неблокирующей структуре. Возвращает ABA даже в языке со сборщиком мусора.

delete сразу после «снять» в C++. Другой поток ещё читает t.next у этого узла.

Узкая метка. 16 битов обходят круг за доли миллисекунды.

Ожидание вместо помощи. Поток, уснувший между двумя CAS, останавливает всех вставляющих.

Неблокирующая очередь на флагах. Невозможно в принципе: у чтений и записей число консенсуса 1.

Проверка случайными тестами. ABA - один конец из шести и немногие узкие расписания; ловит перебор, а не нагрузка.

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

• Счётная сеть: в покое 0≤y[i]-y[j]≤1 при i<j, локальные полосы дают i+w·t. Это quiescent consistency, не обязательно линеаризуемость. Дифракция пары разносит два токена без переключения общего бита.

• STM проверяет версии чтений и публикует буфер записей, HTM отслеживает доступ аппаратно и может отменяться по ресурсным причинам. Fallback синхронизируется с быстрым путём; внешние эффекты не откатываются автоматически.