Современные серверные процессоры представляют собой массивно-параллельные машины с общей памятью: один двухсокетный сервер обычно объединяет от 128 до 256 физических ядер (и до 512 аппаратных потоков с учётом SMT), конкурирующих за единое кэш-когерентное адресное пространство (ccNUMA). При проектировании планировщиков ядра ОС, биржевых ядер высокочастотного трейдинга (HFT), обратных вызовов цифровой обработки аудиосигналов (DSP) в реальном времени или движков СУБД классический примитив синхронизации — мьютекс (mutex, взаимное исключение) — превращается из механизма защиты в катастрофическое узкое место.

Представьте, что 128 потоков одновременно добавляют и извлекают задачи из общей очереди, защищённой std::mutex. Само переключение указателя занимает едва ли 15 наносекунд. Но если единственный поток $T_1$, удерживающий мьютекс, будет вытеснен (Preempted) планировщиком ОС по истечении кванта времени или столкнётся с ошибкой страницы памяти (Page Fault), эти 15 наносекунд растянутся на несколько миллисекунд. Всё это время остальные 127 ядер процессора полностью простаивают, ожидая пробуждения спящего потока.

Чтобы разорвать эту фатальную зависимость, была создана теория и практика неблокирующей синхронизации (Non-Blocking Synchronization): Lock-Free и Wait-Free алгоритмов. Однако, как только мы отказываемся от блокировок и начинаем менять указатели напрямую с помощью атомарных аппаратных инструкций вроде Compare-And-Swap (CAS), мы сталкиваемся с одной из самых коварных ошибок в информатике — проблемой ABA (ABA Problem) и задачей безопасного освобождения памяти (Safe Memory Reclamation, SMR) в языках без сборщика мусора (C, C++, Rust).

Глава 1: Почему мьютексы (mutex) терпят крах в системах со сверхнизкой задержкой

Даже высокооптимизированные мьютексы вроде futex (Fast Userspace Mutex) в Linux страдают от четырёх фундаментальных патологий блокирующей синхронизации:

1. Вытеснение в критической секции и эффект конвоя (Lock Convoying): Если поток, захвативший блокировку, приостанавливается планировщиком или обработчиком страничного прерывания, все остальные потоки выстраиваются в очередь ожидания внутри ядра. Даже после освобождения мьютекса последовательное пробуждение потоков, переключения контекста и сброс кэш-линий (Cache Line Bouncing) между узлами NUMA создают затяжной затор — «конвой блокировок».
2. Неограниченная инверсия приоритетов (Priority Inversion) — урок марсохода Mars Pathfinder (1997): В июле 1997 года космический аппарат NASA Mars Pathfinder на поверхности Марса начал страдать от постоянных аварийных перезагрузок. В ОС реального времени VxWorks низкоприоритетная метеорологическая задача $T_{\text{low}}$ захватила мьютекс шины данных; высокоприоритетная задача управления шиной $T_{\text{high}}$ заблокировалась в ожидании этого мьютекса; тем временем среднеприоритетные задачи связи $T_{\text{med}}$ (которым этот мьютекс вообще не был нужен!) вытеснили $T_{\text{low}}$ с процессора, косвенно вызвав голодание $T_{\text{high}}$ и срабатывание сторожевого таймера (Watchdog Reset).
3. Взаимоблокировки (Deadlock) и отсутствие композиционности: Две потокобезопасные хэш-таблицы $A$ и $B$ с внутренними мьютексами нельзя безопасно объединить в атомарную операцию transfer(A, B) без глобального порядка захвата блокировок из-за риска перекрёстного дедлока AB-BA.
4. Абсолютный запрет в обработчиках сигналов, прерываний (ISR) и аудио-колбэках реального времени: Вызов mutex_lock внутри асинхронного обработчика сигналов POSIX (SIGINT, SIGSEGV) приводит к мгновенному самодедлоку (Self-Deadlock), если прерванный поток уже удерживал этот замок. В аудио-колбэке DSP ($48\,\text{кГц}$, буфер 64 сэмпла $\implies$ жёсткий дедлайн $1{,}33\,\text{мс}$) любой уход в сон через futex вызывает опустошение буфера (слышимые щелчки и треск).

Глава 2: Линеаризуемость и три гарантии неблокирующего прогресса

2.1 Критерий корректности: Линеаризуемость (Herlihy & Wing, 1990)

В конкурентной среде каждый вызов метода $op_i$ занимает временной интервал $[t_{\text{inv}}(op_i), t_{\text{resp}}(op_i)]$. Морис Херлихи и Жаннетт Винг определили, что конкурентный объект является линеаризуемым (Linearizable), если каждой операции $op_i$ можно сопоставить мгновенную точку времени — точку линеаризации $t_{\text{lin}}(op_i) \in [t_{\text{inv}}(op_i), t_{\text{resp}}(op_i)]$ — так, что упорядочение всех операций по их точкам $t_{\text{lin}}$ образует корректную последовательную историю. Линеаризуемость — локальное (композиционное) свойство.

2.2 Три уровня неблокирующего прогресса (Liveness)

1. Obstruction-Free (Свобода от помех): Поток гарантированно завершит операцию за конечное число шагов, если в конечном итоге будет выполняться изолированно (без вмешательства других потоков). Подвержен livelock при конкуренции и требует менеджера конкуренции с экспоненциальной задержкой (backoff).
2. Lock-Free (Свобода от блокировок): Независимо от скорости, вытеснения или полного отказа (crash-stop) других потоков, гарантируется, что хотя бы один поток среди всех активных потоков завершит свою операцию за конечное число шагов. Если инструкция CAS одного потока терпит неудачу, это математически означает, что CAS другого потока завершился успешно и продвинул глобальное состояние системы вперёд!
3. Wait-Free (Свобода от ожидания): Каждый отдельный поток гарантированно завершает свою операцию за конечное ограниченное число собственных шагов ($O(1)$ или $O(P)$), полностью исключая голодание (Zero Starvation). Достигается за счёт механизма помощи (Helping): медленный поток публикует дескриптор своей операции в глобальном массиве announce[i], а быстрые потоки помогают выполнить ожидающие операции других потоков перед завершением собственных.

Глава 3: Атомарные инструкции и иерархия консенсуса Мориса Херлихи (1991)

В фундаментальной работе “Wait-Free Synchronization” (1991, премии Гёделя и Дейкстры) Морис Херлихи классифицировал вычислительную мощность любого примитива синхронизации $\mathcal{O}$ через его консенсусное число (Consensus Number) $C(\mathcal{O})$: максимальное число потоков $N$, для которых можно решить задачу Wait-Free консенсуса (Согласие, Обоснованность и Завершаемость), используя объекты типа $\mathcal{O}$ и атомарные регистры чтения/записи.

• $C = 1$: Атомарные регистры чтения/записи (MOV + барьер памяти): Не способны решить консенсус даже для $N = 2$ потоков! Доказательство через бивалентность: Начиная с бивалентного начального состояния (когда достижимы оба решения 0 и 1), система неизбежно попадает в критическое бивалентное состояние $S_{\text{crit}}$, где шаг $e_A$ потока $A$ ведёт в 0-валентное состояние $S_0$, а шаг $e_B$ потока $B$ — в 1-валентное состояние $S_1$. В решающем случае, когда оба шага пишут в один и тот же регистр $R$, выполнение $e_A$, а затем сразу $e_B$ приводит к тому, что запись потока $B$ полностью перезаписывает и уничтожает запись потока $A$! Для потока $B$ 0-валентное состояние $e_B(e_A(S_{\text{crit}}))$ становится абсолютно неотличимым (Indistinguishable) от 1-валентного состояния $e_B(S_{\text{crit}})$, что приводит к противоречию при дальнейшем одиночном выполнении $B$.
• $C = 2$: Test-and-Set (TAS), Swap (XCHG), Fetch-and-Add (LOCK XADD), стеки и очереди FIFO: Решают консенсус для 2 потоков, но математически бессильны при $N \ge 3$ потоках! В Fetch-and-Add, если потоки $A$ и $B$ прибавляют 1 к регистру, из-за коммутативности сложения итоговое значение равно $r+2$ независимо от порядка; третий поток $C$ не может определить, кто был первым. Важнейшее следствие: невозможно построить универсальную Lock-Free очередь или стек для $\ge 3$ потоков, используя только Fetch-and-Add или Swap!
• $C = \infty$ (Универсальные примитивы): Compare-And-Swap (CAS) и Load-Linked / Store-Conditional (LL/SC): При вызове CAS(&decision, UNDECIDED, my_val) только самый первый поток меняет значение регистра, а все остальные $N-1$ потоков терпят неудачу, не затирая решение победителя. Поэтому CAS и LL/SC универсальны для любого числа потоков $N \to \infty$.

Глава 4: Стек Трейбера (1986) и анатомия проблемы ABA

Рассмотрим наивную реализацию pop() в классическом неблокирующем стеке Р. Кента Трейбера (1986):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Наивный метод pop() стека Трейбера — уязвим к проблеме ABA и Use-After-Free!
bool pop(T& result) {
    Node* old_top = top.load(std::memory_order_acquire);
    while (old_top != nullptr) {
        Node* next_node = old_top->next; // Опасная точка 1: разыменование old_top
        if (top.compare_exchange_weak(   // Опасная точка 2: CAS проверяет только равенство адреса
                old_top, next_node,
                std::memory_order_acquire, std::memory_order_relaxed)) {
            result = old_top->data;
            delete old_top;              // Возврат памяти аллокатору (спусковой крючок катастрофы!)
            return true;
        }
    }
    return false;
}

4.1 Пятишаговая хронология разрушения кучи из-за проблемы ABA

Начальное состояние стека: $\text{top} \longrightarrow A(\texttt{0x1000}) \longrightarrow B(\texttt{0x2000}) \longrightarrow C(\texttt{0x3000})$.

1. [Шаг 1] Поток 1 начинает pop() и вытесняется прямо перед CAS: Поток 1 читает old_top = 0x1000 ($A$) и next_node = 0x2000 ($B$), но планировщик ОС усыпляет его непосредственно перед выполнением инструкции CAS(&top, 0x1000, 0x2000).
2. [Шаг 2] Поток 2 извлекает $A$ и $B$ и освобождает оба узла: Поток 2 дважды вызывает pop(): извлекает $A(\texttt{0x1000})$ (delete A), затем извлекает $B(\texttt{0x2000})$ и вызывает delete B. Адрес 0x2000 теперь является освобождённой памятью (висячим указателем), а стек имеет вид $\text{top} \to C(\texttt{0x3000})$.
3. [Шаг 3] Поток 2 выполняет push(), и аллокатор повторно использует адрес 0x1000: Поток 2 создаёт новый узел $A'$. Современные аллокаторы (jemalloc, tcmalloc, ptmalloc) немедленно переиспользуют только что освобождённые блоки из LIFO-списка ради локальности кэша L1 и выделяют узлу $A'$ точно такой же адрес 0x1000! После добавления в стек получаем $\text{top} \longrightarrow A'(\texttt{0x1000}) \longrightarrow C(\texttt{0x3000})$.
4. [Шаг 4] Поток 1 просыпается и выполняет устаревший CAS(&top, 0x1000, 0x2000): Процессор сравнивает текущий top (0x1000) с old_top (0x1000). Поскольку биты адреса совпадают ($A \to B \to A$), инструкция CAS вслепую срабатывает успешно!
5. [Шаг 5] Полное разрушение кучи: Указатель top перезаписывается адресом 0x2000 (уже удалённый узел $B$!), узел $C(\texttt{0x3000})$ навсегда теряется (утечка памяти), а следующее обращение к стеку вызывает Use-After-Free или SIGSEGV.

  flowchart TD
    subgraph S1["1. Начальное состояние и вытеснение Потока 1"]
        A1["Начальный стек: top -> A(0x1000) -> B(0x2000) -> C(0x3000)"] --> A2["Поток 1 читает old_top=0x1000, next=0x2000<br/>и вытесняется ОС прямо перед выполнением CAS"]
    end

    subgraph S2["2. Поток 2 вызывает переход A -> B -> A"]
        B1["Поток 2: дважды вызывает pop(), удаляя A(0x1000) и B(0x2000)<br/>delete B превращает 0x2000 в висячий указатель!"] --> B2["Поток 2: push() выделяет новый узел A'<br/>Аллокатор переиспользует адрес 0x1000!<br/>Стек сейчас: top -> A'(0x1000) -> C(0x3000)"]
    end

    subgraph S3["3. Пробуждение Потока 1 и разрушение кучи"]
        C1["Поток 1 выполняет CAS(&top, 0x1000, 0x2000)"] --> C2["Так как top == 0x1000, CAS вслепую проходит успешно!<br/>КАТАСТРОФА: top указывает на удалённый B(0x2000), узел C потерян!"]
    end

    S1 --> S2 --> S3

Глава 5: Четыре архитектуры решения проблемы ABA и безопасного освобождения памяти (SMR)

5.1 Решение 1: Тегированные указатели (Tagged Pointers) и двойной CAS (DWCAS / CMPXCHG16B)

Объединяет 64-битный указатель ptr с монотонно растущим 64-битным счётчиком поколений tag в 128-битную структуру (ptr, tag), увеличивая tag при каждом обновлении: $(\texttt{0x1000}, 42) \to (\texttt{0x2000}, 43) \to (\texttt{0x1000}, 44)$. С помощью инструкции x86-64 LOCK CMPXCHG16B операция DWCAS обнаруживает tag 42 != 44 и безопасно отклоняет замену. Требует типобезопасного пула памяти (Type-Stable Freelist), чтобы чтение old_top->next не вызывало SIGSEGV.

5.2 Решение 2: Опасные указатели (Hazard Pointers — Maged Michael 2004, C++26 <hazard_pointer>)

Каждый поток-читатель $i$ публикует адрес p = top.load() в глобальном атомарном массиве HP[i].store(p, memory_order_seq_cst), после чего обязательно перепроверяет if (top.load(memory_order_seq_cst) != p) retry;. Пока HP[i] == p опубликован, ни один другой поток не имеет права освободить или переиспользовать адрес p. Извлечённые узлы помещаются в локальный список retired_list и удаляются через delete только после сканирования всех HP[]. Объём неосвобождённой памяти строго ограничен $O(P^2)$, но платой является тяжёлый барьер SeqCst (MFENCE) на каждый разыменованный указатель.

5.3 Решение 3: Освобождение на основе эпох (EBR — Keir Fraser 2004, Rust crossbeam-epoch)

Чтобы избавиться от барьеров памяти на каждом указателе, EBR использует глобальный счётчик эпох $E$ и 3 корзины мусора bag[0..2]. Входя в операцию (pin()), поток ставит флаг active = true и записывает local_e = E (всего один барьер памяти на всю операцию!). Удалённые узлы складываются в bag[E % 3]. Когда все активные потоки достигают эпохи $E$, глобальная эпоха увеличивается; при достижении эпохи $E+2$ ни один активный поток уже не может удерживать указатели из эпохи $E$, и корзина bag[E % 3] безопасно очищается целиком.

  flowchart TD
    subgraph HP["Hazard Pointers (Защита каждого указателя, C++26)"]
        H1["1. Прочитать p = top.load()"] --> H2["2. Опубликовать HP[tid] = p (Барьер SeqCst)"]
        H2 --> H3{"3. Перепроверка: top == p?"}
        H3 -- "Нет (Конфликт)" --> H1
        H3 -- "Да (Защита активна)" --> H4["4. Безопасно прочитать p->next и выполнить CAS"]
        H4 --> H5["5. Очистить HP[tid], отправить p в отставку и проверить HP[]"]
    end

    subgraph EBR["Epoch-Based Reclamation (Защита операции через 3 эпохи)"]
        E1["1. pin(): active=true, local_e = Global_E<br/>(Только 1 барьер памяти на весь обход!)"] --> E2["2. Обход любого числа указателей без барьеров и CAS"]
        E2 --> E3["3. Поместить отцепленный узел в корзину bag[Global_E % 3]"]
        E3 --> E4["4. unpin(): active=false"]
        E4 --> E5["5. Когда все активные потоки увидят Global_E: сдвинуть эпоху<br/>и массово очистить корзину двухэпохальной давности bag[(E-2)%3]"]
    end

5.4 Решение 4: Read-Copy-Update (RCU — Ядро Linux и liburcu)

Для структур с преобладанием чтения (таблицы маршрутизации, кэш VFS dcache) RCU обеспечивает Wait-Free чтение с нулевыми накладными расходами (rcu_read_lock() в невытесняемом ядре компилируется в ноль машинных инструкций и лишь запрещает переключение контекста). Писатель создаёт копию узла (Copy-on-Write), атомарно меняет указатель и через synchronize_rcu() ждёт окончания периода благодати (Grace Period) — пока каждое ядро CPU не пройдёт хотя бы через одно переключение контекста (Quiescent State) — после чего безопасно освобождает старый узел.