Параллельные вычисления
Lock-Free структуры данных
Сервер принимает 10 миллионов запросов в секунду. Каждый запрос добавляет работу в очередь. Если очередь под mutex - один поток держит её, остальные 999 ждут. Lock-free очередь Майкла-Скотта работает без единого mutex. Это не академическая абстракция - это то, что внутри Java's ConcurrentLinkedQueue, Go channel под нагрузкой и Disruptor в HFT системах.
- **Java ConcurrentLinkedQueue:** реализует алгоритм Майкла-Скотта напрямую - это стандартная библиотека Java
- **Linux kernel RCU:** Read-Copy-Update - lock-free чтение данных ядра, используется в сетевом стеке
- **HFT системы (LMAX Disruptor):** lock-free ring buffer даёт задержку ~25ns против ~1000ns у mutex-очереди
CAS: Compare-And-Swap
Mutex гарантирует эксклюзивный доступ, блокируя всех остальных. Но что если один поток умирает держа mutex? Deadlock. Что если приоритетный поток ждёт низкоприоритетного? Priority inversion. **Lock-free** программирование строится на аппаратном атомарном примитиве - **Compare-And-Swap (CAS)** - который позволяет изменять данные без блокировок, но с гарантией корректности.
CAS принимает три аргумента: адрес, ожидаемое значение, новое значение. Процессор **атомарно** проверяет: если по адресу лежит ожидаемое значение - заменяет на новое и возвращает true. Если нет - ничего не делает и возвращает false. Это единственная инструкция, «всё или ничего», без возможности прерывания между проверкой и записью.
**x86 реализация:** `LOCK CMPXCHG` - одна инструкция с префиксом LOCK. **ARM реализация:** пара `LDREX/STREX` (Load-Link/Store-Conditional, LL/SC) - нет прямого CAS, поэтому `compare_exchange_weak` может дать spurious failure даже при совпадении значений - это нормально, loop обработает.
В CAS-loop поток вызывает compare_exchange_weak и получает false. Что это означает?
ABA проблема
CAS проверяет: «значение по адресу равно ожидаемому?». Но это не то же самое, что «ничего не изменилось». Пока поток A готовил CAS, поток B мог изменить значение A→B, а потом C снова вернуть значение B→A. CAS Потока A успешно завершится - он «не заметит» промежуточных изменений. Это **ABA проблема**, и она приводит к незаметным ошибкам в lock-free структурах.
**Классическое решение - tagged pointer (double-word CAS):** добавить к указателю счётчик версий. Даже если указатель вернулся к A, версия стала A.v2 - CAS с ожидаемым A.v1 завершится неудачей. На 64-bit системах можно использовать верхние 16 бит указателя под тег (tagged pointer) или 128-bit DCAS (`LOCK CMPXCHG16B` на x86).
**Альтернативы tagged pointer:** Hazard Pointers (следующий концепт), RCU (Read-Copy-Update), epoch-based reclamation. На практике в C++ используют либо tagged pointer для стека/очереди, либо epoch-based в библиотеках (Folly, libcds).
ABA проблема возникает потому что CAS проверяет:
Lock-Free очередь Майкла-Скотта
Michael & Scott (1996) предложили lock-free очередь, которая стала каноническим алгоритмом: enqueue и dequeue работают параллельно, никогда не блокируют друг друга. Идея: два независимых атомарных указателя - `head` (для dequeue) и `tail` (для enqueue). Они редко конкурируют, так как работают на разных концах очереди.
**Помощь (helping)** - ключевая идея lock-free: если поток видит незавершённую операцию другого потока (tail отстал), он помогает завершить её. Это гарантирует progress: даже если один поток застрял, другие продвигают работу. `delete h` в коде небезопасен без hazard pointers - следующий концепт.
В очереди Майкла-Скотта: поток читает tail, и видит что tail->next != nullptr. Что нужно сделать?
Hazard Pointers для memory reclamation
В коде очереди выше `delete h` после dequeue - это use-after-free ожидающий момента. Поток B мог прочитать h до того, как поток A удалил его. Это проблема **memory reclamation** в lock-free коде: нельзя удалить объект, если другой поток может к нему обращаться. **Hazard Pointers** (Maged Michael, 2004) решают это: перед обращением к указателю поток «объявляет» его hazardous, тем самым запрещая удаление.
**Альтернативы:** Epoch-Based Reclamation (используется в folly::ConcurrentHashMap) - проще в реализации, но может задержать GC на целую эпоху. RCU (используется в Linux kernel) - оптимален для read-heavy workloads. В C++26 обсуждается `std::hazard_pointer` как стандартный примитив.
Lock-free = быстрее mutex всегда
Lock-free гарантирует progress (один поток всегда продвигается), но не скорость. При низкой конкуренции mutex быстрее из-за меньших накладных расходов
Lock-free CAS-loop при высокой конкуренции вызывает многократные retry. Mutex даёт OS-управляемую очередь без retry-шторма
Зачем в hazard pointer protect() перечитывает указатель после записи в hazard slot?
Lock-Free структуры: ключевые идеи
- CAS - атомарный примитив: «замени если совпадает», retry при неудаче = lock-free loop
- ABA проблема: CAS не видит промежуточных изменений - решение: tagged pointer (версионирование)
- Очередь Майкла-Скотта: два независимых CAS для head и tail + helping незавершённых операций
- Hazard Pointers: объявить указатель защищённым перед чтением, retire (не delete) при удалении, scan периодически
Связанные темы
Lock-free структуры строятся поверх атомиков и требуют понимания memory ordering.
- Memory Ordering и барьеры — CAS с правильным memory_order - основа корректности lock-free кода
- Атомарные операции и std::atomic — std::atomic предоставляет CAS, load, store как базовые примитивы
- Мьютексы и условные переменные — Альтернатива lock-free - понять trade-offs между подходами
Вопросы для размышления
- Lock-free гарантирует progress, но не starvation-free: один поток теоретически может retry бесконечно. В каких реальных сценариях это проблема?
- Hazard Pointers задерживают удаление памяти. Как это влияет на peak memory usage в high-throughput системе?
- Почему Java использует алгоритм Майкла-Скотта в ConcurrentLinkedQueue, но не в ArrayDeque? Что определяет выбор?