Кратко и по существу.
Что такое атомарные операции
- Атомарная операция — операция над памятью, которая выполняется целиком без наблюдаемого прерывания другими потоками/ядрами. Реализуется аппаратно (например, инструкции x86 `LOCK`/`CMPXCHG`) и в библиотеках как атомарные примитивы.
- Частые примитивы: $\text{fetch\_add}(addr,v)$, $\text{test\_and\_set}(addr)$, $\text{CAS}(addr,expected,new)$ (compare-and-swap).
- Важна семантика памяти (memory ordering): relaxed, acquire/release, sequentially-consistent — влияет на видимость операций между потоками.
Примитивы синхронизации
1) Мьютекс (mutex)
- Описание: блокировка, которая переводит поток в спящий (blocked) режим при конфликте; обычно реализуется с поддержкой ОС (системные вызовы) для ожидания/пробуждения.
- Когда хорош: критические секции средней/длительной длительности, когда допустимы контекстные переключения; прост в использовании; обеспечивает справедливость/корректность.
- Минусы: стоимость контекстного переключения при высокой конкуренции; риск взаимной блокировки (deadlock) при неправильном использовании.
2) Спинлок (spinlock)
- Описание: busy-wait — поток активно опрашивает флаг в цикле, не засыпая.
- Когда хорош: очень короткие критические секции, где время ожидания меньше стоимости переключения контекста; в низкоуровневом коде или в контексте, где спать нельзя (IRQ, ядро).
- Минусы: тратит CPU при ожидании; плохо масштабируется при высокой конкуренции; требует экспоненциального/экспоненциального бэкоффа для снижения нагрузки.
3) Compare-and-Swap (CAS)
- Описание: базовый атомарный примитив. Семантика: $\text{CAS}(addr,expected,new)$ — атомарно: если $\ast addr==expected$ тогда $\ast addr:=new$ и возврат true, иначе возвращает false и не меняет $\ast addr$.
- Применение: строительный блок для неблокирующих структур (lock-free) — стеков, очередей, счетчиков и т.д.
- Типичный шаблон:
\( \text{do \{} \; old := head; \; node->next := old; \; \text{while}(!\text{CAS}(&head, old, node)); \; \text{\}} \)
(push в lock-free стеке).
Когда использовать неблокирующие структуры вместо блокировок
- Используйте mutex по умолчанию — проще, безопаснее и часто достаточно.
- Рассмотрите lock-free, если:
- Нужна высокая масштабируемость под высокую конкуренцию и низкая задержка.
- Критерии реального времени или требование избегать блокировок/приоритетной инверсии.
- Критические секции очень короткие и конфликтные, и системные переключения создают узкое место.
- Ограничения и расходы lock-free:
- Сложность реализации и верификации.
- ABA-проблема (решения: теги/версии, double-width CAS, hazard pointers, epoch-based reclamation).
- Управление памятью/освобождением объектов (hazard pointers, RCU, epoch GC).
- Возможная несправедливость и starvation; при сильной конкуренции lock-free код может деградировать.
- Практические рекомендации:
- Профилируйте: переход на lock-free оправдан при измеримой проблеме с блокировками.
- Для коротких критических секций на одном узле: spinlock с backoff может быть проще и быстрее, чем mutex.
- Для сложных структур с долгоживущими операциями или когда нужна простая корректность — mutex.
- Для масштабируемых очередей/стеков/словесных счетчиков при высокой нагрузке — lock-free с продуманной схемой управления памятью.
Коротко о безопасности памяти и упорядочении
- При использовании атомиков задавайте правильные барьеры: lock — acquire, unlock — release; для строгой корректности можно использовать sequentially-consistent.
- Не забывайте про инструменты (hazard pointers, epoch GC) для безопасного освобождения памяти в lock-free структурах.
Итог: mutex — простой и безопасный выбор; spinlock — для очень коротких критических секций или когда нельзя спать; CAS/lock-free — мощный, но более трудоёмкий путь для высокой производительности и масштабируемости, требующий решений для ABA и управления памятью.