Мьютекс превращает параллельную работу в последовательную: пока один поток держит блокировку, остальные стоят в очереди. При низкой нагрузке это незаметно, но на production-сервере профайлер иногда показывает картину, которая сначала не поддаётся объяснению.
Мьютекс как узкое место
Кэш маршрутов в памяти обслуживает 64 потока веб-сервера. Вы добавили ядер, увеличили число потоков — а throughput не вырос. Профайлер показывает: потоки проводят большую часть времени не в полезной работе, а ожидая захвата одного мьютекса.
Причина арифметически простая. Одна пара lock/unlock на неконкурентном мьютексе стоит ~20 нс, но под нагрузкой за мьютекс конкурируют все 64 потока. Поток, не захвативший блокировку, не крутится в ожидании — он засыпает (~1-3 мкс на переключение контекста), встаёт в очередь ядра, потом просыпается и снова пробует захватить. При 64 потоках среднее время ожидания блокировки вырастает до 5-10 мкс — в сотни раз больше, чем стоит сама операция с кэшем.
Пропускная способность выходит на плато и перестаёт расти с числом ядер. Добавление потоков только увеличивает contention — каждый новый поток замедляет остальных.
Проблема не в мьютексе как абстракции — он корректен и прост. Проблема в сериализации: структура данных, защищённая одним мьютексом, пропускает через себя не больше одного потока за раз. Чтобы убрать это ограничение, нужна структура, которая не останавливает потоки вообще.
Lock-free: гарантия прогресса без блокировок
Lock-free (неблокирующая) структура данных гарантирует: хотя бы один поток завершает операцию за конечное число шагов, независимо от того, что делают остальные потоки. Ни один поток не способен заблокировать всю систему. Если поток A приостановлен планировщиком посреди операции — остальные продолжают работать. Сравните с мьютексом: если поток, держащий блокировку, приостановлен — все ждут.
Wait-free (безожидательная) — более строгая гарантия: каждый поток завершает операцию за ограниченное число шагов. Не «хотя бы один», а каждый без исключения. Wait-free структуры редки на практике, потому что реализация значительно сложнее, а выигрыш в throughput по сравнению с lock-free минимален. Большинство реальных библиотек — lock-free.
Между мьютексом и lock-free существует промежуточная ступень — obstruction-free (свободная от препятствий): поток гарантированно завершает операцию, если выполняется в изоляции (остальные приостановлены). Это слабее lock-free, потому что при одновременной работе потоки могут бесконечно мешать друг другу (livelock — живая блокировка). На практике obstruction-free алгоритмы дополняют backoff-стратегиями (выдержка паузы перед повторной попыткой — поток уступает процессорное время, чтобы соперник успел завершить операцию), чтобы снизить вероятность livelock.
Общее у всех трёх подходов — отсутствие мьютексов. Вместо блокировки потоки используют атомарные операции процессора, прежде всего CAS (compare-and-swap). Поток читает текущее состояние, готовит новое значение, затем атомарно заменяет старое на новое — но только если за это время никто другой не успел изменить состояние. Если успел — поток повторяет с начала.
Стек Трайбера: push и pop через CAS
Стек — самая простая отправная точка для lock-free структур, потому что всё состояние описывается одним указателем: top. Push — это «поставить узел в начало», pop — «снять узел с начала». Обе операции меняют только top, и один CAS заменяет пару lock/unlock.
Стек Трайбера (Treiber, 1986) — связный список, где вся синхронизация сводится к CAS на указателе top.
Push
Поток создаёт новый узел, записывает текущий top в node->next, затем пытается атомарно заменить top на свой узел. Если между чтением top и CAS другой поток успел изменить вершину — CAS вернёт false, и операция повторяется с актуальным значением top.
typedef struct node { void *data; struct node *next;} node_t;// top — атомарный указатель на вершину стека_Atomic(node_t *) top;void push(node_t *node) { node_t *old_top; do { old_top = atomic_load_explicit(&top, memory_order_relaxed); node->next = old_top; } while (!atomic_compare_exchange_weak_explicit( &top, &old_top, // expected: текущая вершина node, // desired: наш новый узел memory_order_release, memory_order_relaxed ));}
[[linux/concurrency/memory-ordering#release-гарантия-для-записи|memory_order_release]] при успешном CAS гарантирует: все записи в node (в том числе node->next) видны другим потокам до того, как они увидят новый top.
Pop
Поток читает текущий top, запоминает top->next (следующий элемент, который станет новой вершиной), затем атомарно заменяет top на top->next.
node_t *pop(void) { node_t *old_top; node_t *new_top; do { old_top = atomic_load_explicit(&top, memory_order_acquire); if (old_top == NULL) return NULL; // стек пуст new_top = old_top->next; } while (!atomic_compare_exchange_weak_explicit( &top, &old_top, // expected new_top, // desired: следующий элемент memory_order_acq_rel, memory_order_acquire )); return old_top;}
[[linux/concurrency/memory-ordering#acquire-гарантия-для-чтения|memory_order_acquire]] при чтении top гарантирует: поток видит все записи, которые были выполнены до release-операции, установившей это значение top.
Оба метода — цикл: прочитать состояние, подготовить новое, попытаться применить через CAS, при неудаче — повторить. Под низкой нагрузкой CAS срабатывает с первой попытки. Под высокой — потоки конкурируют и повторяют цикл, но ни один поток не может заблокировать остальных навсегда: каждая неудачная попытка одного потока означает, что другой поток успешно завершил свою операцию.
Стек выглядит корректным. Но есть сценарий, который не попадает в тесты, зато встречается в production под нагрузкой — особенно в системах с аллокаторами, переиспользующими память.
Проблема ABA
Дефект в том, что CAS сравнивает значение указателя — числовой адрес в памяти. Одинаковый адрес не означает одинаковое состояние.
Сценарий
Начальное состояние стека: top -> X -> Y -> Z. Планировщик может приостановить поток A между чтением top и CAS — в этот промежуток поток B успевает изменить стек.
Поток A: pop()
1. Читает old_top = X, new_top = X->next = Y
2. Приостановлен планировщиком
(поток A спит)
Поток B:
3. pop() — снимает X. Стек: top -> Y -> Z
4. pop() — снимает Y. Стек: top -> Z
5. push(X) — кладёт X обратно. Стек: top -> X -> Z
(X мог быть возвращён аллокатором, или B
переиспользовал его намеренно)
(поток A просыпается)
Поток A: продолжает pop()
6. CAS(&top, X, Y) — сравнивает top с X.
top == X? Да. CAS успешно заменяет top на Y.
Стек: top -> Y -> ...
Но Y был освобождён на шаге 4!
Визуально последовательность выглядит так:
Шаг 1-2: Поток A читает top
top ---> [X] ---> [Y] ---> [Z]
^
A запомнил: old_top=X, new_top=Y
Шаг 3: Поток B снимает X
top ---> [Y] ---> [Z] [X] (снят)
Шаг 4: Поток B снимает Y
top ---> [Z] [X] [Y] (оба сняты)
Шаг 5: Поток B кладёт X обратно (X->next = Z)
top ---> [X] ---> [Z] [Y] (освобождён)
Шаг 6: Поток A делает CAS(&top, X, Y)
top == X? Да! CAS успех.
top ---> [Y] ---> ???
^
Y уже освобождён — use-after-free
CAS проверил: «вершина всё ещё X?» — да. Но контекст изменился: X->next больше не указывает на Y (теперь X->next = Z), а Y уже освобождён. Стек повреждён: top указывает на освобождённую память.
Почему CAS не ловит ABA
CAS сравнивает битовое значение, а не идентичность состояния. Указатель на X — это число, скажем, 0x7fff'a000'1234. После того как X был снят, освобождён и снова помещён в стек (или аллокатор вернул тот же адрес для нового объекта), числовое значение указателя совпадает. CAS видит совпадение и считает, что состояние не менялось. Но между двумя моментами сравнения стек прошёл через три операции — и его внутренняя структура изменилась.
На практике это значит: под достаточной нагрузкой стек начинает терять элементы и читать освобождённую память — а тесты продолжают проходить, потому что воспроизвести точный порядок вытеснений в тесте практически невозможно.
ABA — центральная проблема lock-free программирования. Все решения сводятся к одному: дать CAS возможность различать «тот же указатель, то же состояние» и «тот же указатель, но состояние изменилось».
Решения проблемы ABA
Самый очевидный ответ: расширить то, что сравнивает CAS — добавить к указателю счётчик версий, который растёт при каждой модификации.
Tagged pointer: счётчик версий в указателе
К указателю добавляется счётчик: CAS сравнивает не только адрес, но и счётчик. Даже если указатель вернулся к прежнему значению — счётчик будет другим, и CAS провалится.
На x86-64 с 4-уровневой таблицей страниц виртуальные адреса используют 48 бит из 64 (старшие 16 бит — расширение знака 47-го бита). Это оставляет 16 бит для счётчика в верхней части 64-битного слова. С 5-уровневой таблицей (LA57 — Level-5 paging, поддерживается серверными процессорами начиная с Intel Ice Lake-SP 2021 года) адреса занимают 57 бит — свободных остаётся 7. На практике приём работает надёжно на большинстве текущих систем, но не является архитектурной гарантией — это распространённый трюк, зависящий от конфигурации.
16 бит = 65 536 значений. Счётчик оборачивается, но вероятность того, что другой поток выполнит ровно 65 536 модификаций за время паузы первого потока, исчезающе мала.
Для push: вместо CAS(&top, old_top, new_node) поток выполняет CAS(&top, {old_counter, old_ptr}, {old_counter + 1, new_node}). Если между чтением и CAS кто-то модифицировал стек — счётчик не совпадёт.
На x86-64 есть инструкция CMPXCHG16B — CAS для 128-битных значений. С ней можно хранить полный 64-битный указатель и 64-битный счётчик, полностью исключая проблему оборачивания. Ограничение tagged pointer в том, что он борется с симптомом: счётчик делает ABA крайне маловероятным, но не невозможным — и ничего не делает с самой проблемой переиспользования освобождённой памяти.
Hazard pointers: защита от преждевременного освобождения
Причина ABA — то, что освобождённый узел успевают переиспользовать. Если запретить освобождение узла, пока хотя бы один поток с ним работает, ABA невозможен. Именно это делают hazard pointers (Майкл, 2004).
Каждый поток публикует в разделяемом массиве указатели на узлы, с которыми он сейчас работает. Перед освобождением поток проверяет массив: если чей-то hazard pointer указывает на этот узел — освобождение откладывается.
Стоимость: при каждом чтении узла — одна атомарная запись (публикация hazard pointer). При освобождении — сканирование массива всех потоков. Для N потоков и K hazard pointers на поток — массив N*K записей. На практике K = 1-2, и сканирование 64-128 записей занимает десятки наносекунд. Главный недостаток — эта стоимость платится при каждом обращении к узлу, не только при освобождении.
Epoch-based reclamation: амортизация по эпохам
Если атомарная запись при каждом чтении дорого стоит, можно платить реже: обновлять не указатель на конкретный узел, а грубую временну́ю метку — эпоху (epoch).
Глобальный счётчик эпох увеличивается периодически. Каждый поток при входе в критическую секцию записывает текущую эпоху — один раз, а не при каждом обращении к узлу. Узлы, помеченные для удаления, помещаются в список отложенного освобождения с номером эпохи. Когда все потоки перешагнули эпоху N — узлы из эпохи N-2 можно безопасно освободить (значение N-2 выбрано с запасом: к моменту продвижения эпохи поток из N-1 мог ещё не выйти из секции).
В Rust эту схему реализует crossbeam-epoch — используется внутри crossbeam-skiplist, crossbeam-deque и других lock-free структур.
Слабое место epoch — долго живущие читатели. Если один поток надолго задерживается в критической секции (например, попал в page fault — ошибку страницы, когда ядро подгружает данные с диска), ни один накопленный узел не может быть освобождён, пока он не выйдет. В write-heavy сценариях с медленными потоками это приводит к росту потребления памяти.
RCU: решение ядра Linux
Read-Copy-Update — механизм, оптимизированный для нагрузки с преобладанием чтений. Читатели не выполняют никаких атомарных операций — ни CAS, ни атомарных записей, ни барьеров памяти. Чтение настолько дешёвое, что компилятор может инлайнить его полностью.
Писатель создаёт копию структуры, модифицирует её, затем атомарно заменяет указатель на новую версию. Старая версия остаётся в памяти до наступления grace period (льготного периода — интервала, в течение которого все читатели, видевшие старую версию, гарантированно завершат чтение).
Определение grace period зависит от конфигурации ядра. В классическом не-preemptible RCU (CONFIG_PREEMPT_NONE) rcu_read_lock() — это preempt_disable() (вызов ядра, запрещающий вытеснение текущего потока планировщиком), одна инструкция без барьера памяти. Критическая секция не может пересечь context switch, поэтому grace period наступает, когда каждый CPU хотя бы раз переключил контекст. В preemptible RCU (CONFIG_PREEMPT) читательская секция может быть прервана планировщиком, и grace period определяется через более сложный механизм отслеживания вложенных rcu_read_lock()/rcu_read_unlock(). Стоимость read-side в preemptible варианте чуть выше (атомарный инкремент/декремент счётчика), но всё ещё на порядки дешевле мьютекса.
Типичный grace period — единицы миллисекунд в обоих вариантах. Это следствие важно для write-heavy сценариев: пока grace period не истёк, старая версия структуры остаётся в памяти. При частых изменениях накапливается несколько старых копий одновременно — потребление памяти растёт пропорционально частоте записей.
rcu_read_lock();struct route *r = rcu_dereference(route_table);// ... использование r, никаких мьютексов, никаких CAS ...rcu_read_unlock();
В не-preemptible ядре стоимость rcu_read_lock() — ноль атомарных операций, ноль инвалидированных кеш-линий. Для таблицы маршрутизации, к которой обращается каждый входящий пакет на каждом CPU, это критически важно.
RCU широко используется в ядре для таблицы маршрутизации, списка файловых дескрипторов, dentry cache (кеша записей каталогов файловой системы), модульной системы, сетевых фильтров. В ядре Linux 6.x более 10 000 вызовов rcu_read_lock().
Для userspace RCU существует библиотека liburcu, но без гарантий ядра (контроль переключения контекста) определение grace period сложнее и дороже.
Lock-free очередь Майкла-Скотта
Стек хорошо демонстрирует принцип, но в реальных системах чаще нужна очередь (FIFO — First In First Out): задачи для воркеров, сообщения между потоками, логи. Те же проблемы — ABA, управление памятью — применимы и к очереди, но структура сложнее: у очереди два конца. Очередь Майкла-Скотта (1996) использует два указателя: head (откуда снимают) и tail (куда добавляют). Между ними — связный список с фиктивным (dummy) узлом в начале.
Инициализация: head и tail указывают на dummy-узел
head tail
| |
v v
[dummy] ---> NULL
После enqueue(A), enqueue(B):
head tail
| |
v v
[dummy] ---> [A] ---> [B] ---> NULL
После dequeue() -> A:
head tail
| |
v v
[dummy'] ---> [B] ---> NULL
(бывший A)
Фиктивный узел нужен, чтобы enqueue и dequeue работали с разными указателями: enqueue выполняет CAS на tail, dequeue — на head. Если очередь не пуста, эти операции не конкурируют друг с другом — они работают с противоположными концами списка.
Enqueue сложнее, чем push в стеке: нужно обновить и tail->next (добавить узел в список), и tail (сдвинуть хвост). Два CAS не могут быть атомарными, поэтому между ними очередь находится в промежуточном состоянии — tail отстаёт на один узел. Другие потоки обнаруживают это (tail->next != NULL) и «помогают» — сдвигают tail вперёд перед своей операцией. Эта техника — helping (кооперативное продвижение) — типична для lock-free алгоритмов: вместо ожидания поток исправляет чужую незавершённую операцию.
Dequeue снимает узел, на который указывает head->next (не сам dummy), и сдвигает head вперёд — старый dummy-узел становится мусором, а узел, который был первым элементом, становится новым dummy. Если head->next == NULL — очередь пуста.
Очередь Майкла-Скотта лежит в основе java.util.concurrent.ConcurrentLinkedQueue. В планировщиках Go и Tokio используются другие неблокирующие структуры (work-stealing deque на основе алгоритма Chase-Lev), но общий принцип — CAS-цикл вместо мьютекса — тот же.
Когда lock-free не нужен
Стек и очередь показывают, что lock-free работает — но ценой значительной сложности: ABA, управление памятью через hazard pointers или epoch, точные memory ordering. Прежде чем платить эту цену, стоит понять, в каких сценариях она оправдана.
На неконкурентном пути CAS стоит 5-20 нс — сопоставимо с мьютексом (10-20 нс при отсутствии contention). Преимущество lock-free проявляется под нагрузкой: при 64 потоках contended мьютекс стоит 1-10 мкс (переключение контекста, очередь ожидания), а contended CAS — 50-500 нс (повторы цикла, но без засыпания и пробуждения). Разница в 10-20 раз.
Причина разницы — в механизме ожидания. Contended мьютекс в Linux ([[linux/concurrency/synchronization#futex-быстрый-путь-без-ядра|futex]]) при неудачной попытке захвата переводит поток в состояние сна: системный вызов futex(FUTEX_WAIT), переключение контекста (~1-3 мкс), постановка в очередь ожидания ядра. Когда мьютекс освобождается — futex(FUTEX_WAKE), пробуждение потока, ещё одно переключение контекста. Суммарно два переключения контекста на одну операцию. CAS-цикл обходится без ядра: поток остаётся на CPU и повторяет попытку. Стоимость повтора — десятки наносекунд (RFO — Read For Ownership, запрос кеш-линии в эксклюзивное владение — через протокол MESI), а не микросекунды переключения контекста.
Обратная сторона CAS-цикла — потребление CPU. Поток, крутящийся в цикле, занимает ядро, даже если не делает полезной работы. При 64 потоках на 8 ядрах это значит, что потоки конкурируют и за CAS, и за процессорное время. На практике lock-free структуры масштабируются до числа физических ядер; дальше добавление потоков увеличивает число повторов CAS без роста throughput.
Сложность реализации
Lock-free структуры значительно сложнее в реализации и отладке. Корректность lock-free алгоритма невозможно проверить тестированием: гонка может не проявляться годами и выстрелить под специфической нагрузкой в production. Формальное доказательство корректности (linearizability — линеаризуемость, требование, чтобы каждая операция выглядела мгновенной в некоторой точке между вызовом и возвратом) — отдельная исследовательская задача. Порядок памяти (memory ordering) должен быть точным: один лишний relaxed вместо acquire — и структура корректна на x86 (сильная модель памяти), но ломается на ARM (слабая модель).
Типичный пример: разработчик тестирует lock-free стек на x86-сервере. Все тесты проходят — x86 обеспечивает TSO (Total Store Order), которая скрывает многие ошибки порядка памяти. Тот же код с ослабленными ordering (скажем, relaxed вместо release в push) на ARM-сервере (Graviton в AWS, Apple M-серия) начинает терять элементы, потому что ARM допускает переупорядочивание store-store и другие пары, которые x86 TSO запрещает: запись поля node->next и запись top могут оказаться видны другим ядрам в обратном порядке. Инструменты вроде ThreadSanitizer (TSan) и CDSChecker помогают находить такие ошибки, но не гарантируют полного покрытия.
Когда использовать
Если contention на мьютексе занимает менее 10% времени — мьютекс проще, быстрее в разработке и надёжнее. Если профилирование показывает, что потоки проводят значительное время в ожидании блокировки — сначала стоит попробовать уменьшить гранулярность: вместо одного мьютекса на всю структуру — отдельный мьютекс на каждый сегмент (striped lock — полосатая блокировка, по аналогии с чередованием полос на диске). Исторически ConcurrentHashMap в Java до Java 8 был устроен именно так: таблица делилась на сегменты, каждый с собственным мьютексом. В более новых реализациях дизайн сложнее, но сама идея “сначала попробуй striped locking, а не сразу lock-free” остаётся правильной.
Lock-free оправдан в двух случаях: структура данных используется десятками-сотнями потоков одновременно с высокой частотой, или требуется гарантия прогресса (ни один зависший поток не блокирует систему — критично для real-time систем и ядра ОС, где поток с мьютексом может быть прерван обработчиком прерываний).
На практике использовать готовые реализации, а не писать свои: java.util.concurrent (ConcurrentLinkedQueue, ConcurrentSkipListMap), crossbeam в Rust (очередь, deque, skiplist, epoch-based reclamation), boost::lockfree в C++ (spsc_queue, queue, stack), liblfds — чистый C.
Задача: stack pop и use-after-free
Частая ошибка:
node_t *pop(void) { node_t *old_top = atomic_load(&top); if (!old_top) return NULL; node_t *next = old_top->next; // <-- проблема if (atomic_compare_exchange(&top, &old_top, next)) return old_top; // ... retry}
Между atomic_load и чтением old_top->next другой поток может снять old_top и освободить его. Чтение old_top->next — use-after-free.
Решение: использовать hazard pointers или epoch-based reclamation. Поток публикует old_top как hazard pointer до чтения old_top->next — это гарантирует, что узел не будет освобождён, пока поток с ним работает.
См. также
Ruby Ractor — изоляция через запрет shared state вместо lock-free структур: сообщения копируются или помечаются shareable, MRI избегает сложности lock-free