Мьютекс превращает параллельную работу в последовательную: пока один поток держит блокировку, остальные стоят в очереди. При низкой нагрузке это незаметно, но с ростом числа потоков мьютекс становится горлышком бутылки.
Мьютекс как узкое место
Допустим, in-memory кэш маршрутов обслуживает 64 потока веб-сервера. Каждый поток при обработке запроса обращается к кэшу — читает или обновляет запись. Вся работа с кэшем защищена одним мьютексом.
При 1 миллионе операций в секунду на поток система выполняет 64 миллиона lock/unlock в секунду. Одна пара lock/unlock на неконкурентном мьютексе стоит ~20 нс, но под нагрузкой время растёт: поток захватывает мьютекс за 20 нс, остальные 63 потока встают в очередь планировщика. Каждый из них тратит время на засыпание (~1 мкс на переключение контекста), ожидание, пробуждение, повторную попытку захвата. При 64 потоках среднее время ожидания блокировки вырастает до 5-10 мкс.
В пересчёте: 64M операций * 5 мкс ожидания = поток проводит в ожидании мьютекса больше времени, чем в полезной работе. Пропускная способность выходит на плато и перестаёт расти с числом ядер. Добавление потоков только увеличивает contention — каждый новый поток замедляет остальных.
Проблема не в мьютексе как абстракции — он корректен и прост. Проблема в сериализации: параллельная структура данных пропускает через себя не больше одного потока за раз.
Определение: lock-free vs wait-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 структура — стек, предложенный Трайбером (Treiber) в 1986 году. Стек — это связный список, где top указывает на вершину. Вся синхронизация сводится к CAS на одном указателе.
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 ));}
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;}
memory_order_acquire при чтении top гарантирует: поток видит все записи, которые были выполнены до release-операции, установившей это значение top.
Оба метода — цикл: прочитать состояние, подготовить новое, попытаться применить через CAS, при неудаче — повторить. Под низкой нагрузкой CAS срабатывает с первой попытки. Под высокой — потоки конкурируют и повторяют цикл, но ни один поток не может заблокировать остальных навсегда: каждая неудачная попытка одного потока означает, что другой поток успешно завершил свою операцию.
Проблема ABA
Код стека выглядит корректным, но содержит неочевидный дефект. CAS сравнивает значение указателя — числовой адрес в памяти. Одинаковый адрес не означает одинаковое состояние.
Сценарий
Начальное состояние стека: top -> X -> Y -> Z.
Поток A: pop()
1. Читает old_top = X, new_top = X->next = Y
2. Приостановлен [планировщиком](../foundations/scheduler.md)
(поток 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
Tagged pointer: счётчик версий в указателе
Идея: к указателю добавляется счётчик, который увеличивается при каждой модификации. CAS сравнивает не только указатель, но и счётчик. Даже если указатель вернулся к прежнему значению, счётчик будет другим — и CAS провалится.
На x86-64 с 4-уровневой таблицей страниц виртуальные адреса используют 48 бит из 64 (старшие 16 бит — расширение знака 47-го бита). Это оставляет 16 бит для счётчика в верхней части 64-битного слова. С 5-уровневой таблицей (LA57, поддерживается серверными процессорами с 2019 года) адреса занимают 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-битных значений (double-width CAS). С ней можно хранить полный 64-битный указатель и 64-битный счётчик, полностью исключая проблему оборачивания.
Hazard pointers: защита от преждевременного освобождения
ABA возникает, когда освобождённый узел переиспользуется. Hazard pointers (Майкл, 2004) решают проблему на стороне освобождения памяти: узел нельзя освободить, пока хотя бы один поток может к нему обратиться.
Каждый поток публикует в разделяемом массиве указатели на узлы, с которыми он сейчас работает — это и есть hazard pointers. Перед освобождением узла поток проверяет массив: если чей-то hazard pointer указывает на этот узел — освобождение откладывается.
Стоимость: при каждом чтении узла поток записывает hazard pointer (одна атомарная запись). При освобождении — сканирование массива всех потоков. Для N потоков и K hazard pointers на поток — массив размером N*K. На практике K = 1-2 (поток работает с 1-2 узлами одновременно), и сканирование массива из 64-128 записей занимает десятки наносекунд.
Epoch-based reclamation: амортизация по эпохам
Вместо отслеживания каждого указателя — грубое разделение времени на эпохи (epoch). Глобальный счётчик эпох увеличивается периодически. Каждый поток при входе в критическую секцию записывает текущую эпоху. Узлы, помеченные для удаления, помещаются в список отложенного освобождения с номером эпохи. Когда все потоки перешагнули эпоху N — узлы из эпохи N-2 можно безопасно освободить.
Преимущество перед hazard pointers — меньше атомарных записей на операцию. Каждый поток обновляет свою эпоху один раз на входе в критическую секцию, а не при каждом обращении к узлу. В Rust эту схему реализует библиотека crossbeam-epoch — она используется внутри crossbeam-skiplist, crossbeam-deque и других lock-free структур.
Недостаток: если один поток надолго задерживается в критической секции (например, попал в page fault), все накопленные узлы не могут быть освобождены, пока он не выйдет. Это может привести к росту потребления памяти.
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 — единицы миллисекунд в обоих вариантах.
rcu_read_lock();struct route *r = rcu_dereference(route_table);// ... использование r, никаких мьютексов, никаких CAS ...rcu_read_unlock();
В не-preemptible ядре стоимость rcu_read_lock() — ноль атомарных операций, ноль инвалидированных cache line. Для таблицы маршрутизации, к которой обращается каждый входящий пакет на каждом CPU, это критически важно.
RCU широко используется в ядре для таблицы маршрутизации, списка файловых дескрипторов, dentry cache, модульной системы, сетевых фильтров. В ядре Linux 6.x более 10 000 вызовов rcu_read_lock().
Для userspace RCU существует библиотека liburcu, но без гарантий ядра (контроль переключения контекста) определение grace period сложнее и дороже.
Lock-free очередь Майкла-Скотта
Стек — учебный пример, но на практике чаще нужна очередь (FIFO, First In First Out). Очередь Майкла-Скотта (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, Grand Central Dispatch.
Когда lock-free не нужен
Lock-free — не универсальное улучшение. У него есть конкретная область применимости и конкретная цена.
На неконкурентном пути CAS стоит 5-20 нс — сопоставимо с мьютексом (10-20 нс при отсутствии contention). Преимущество lock-free проявляется под нагрузкой: при 64 потоках contended мьютекс стоит 1-10 мкс (переключение контекста, очередь ожидания), а contended CAS — 50-500 нс (повторы цикла, но без засыпания и пробуждения). Разница в 10-20 раз.
Причина разницы — в механизме ожидания. Contended мьютекс в Linux (futex) при неудачной попытке захвата переводит поток в состояние сна: системный вызов futex(FUTEX_WAIT), переключение контекста (~1-3 мкс), постановка в очередь ожидания ядра. Когда мьютекс освобождается — futex(FUTEX_WAKE), пробуждение потока, ещё одно переключение контекста. Суммарно два переключения контекста на одну операцию. CAS-цикл обходится без ядра: поток остаётся на CPU и повторяет попытку. Стоимость повтора — десятки наносекунд (загрузка кэш-линии из L3 или от другого ядра через протокол MESI (Modified/Exclusive/Shared/Invalid)), а не микросекунды переключения контекста.
Обратная сторона 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), которая скрывает многие ошибки порядка памяти. Тот же код на ARM-сервере (Graviton в AWS, Apple M-серия) начинает терять элементы, потому что ARM допускает переупорядочивание store-load, которое x86 запрещает. Инструменты вроде 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