Атомарные инструкции
Предпосылки: ISA (инструкции, x86 vs ARM), когерентность кешей (MESI, Modified, кеш-линия).
Когерентность гарантирует, что запись одного ядра станет видна другим. Но операция counter++ — это три шага: load, add, store. Между load и store другое ядро может выполнить свой load, и один инкремент потеряется. Когерентность работает корректно — каждый отдельный store виден. Проблема в том, что последовательность из трёх шагов не неделима.
Процессор решает эту задачу специальными инструкциями, которые выполняют read-modify-write как единое целое. Для любого наблюдателя (другого ядра) операция либо ещё не произошла, либо уже завершена целиком — промежуточного состояния не видно. Такие инструкции называются атомарными (atomic, от греч. ἄτομος — неделимый). Разные архитектуры реализуют эту гарантию по-разному.
Два подхода: LOCK и LL/SC
x86: префикс LOCK
На x86 атомарность обычной инструкции достигается добавлением префикса LOCK. Процессор захватывает кеш-линию в эксклюзивное владение (состояние Exclusive в протоколе MESI), выполняет всю инструкцию — в ходе записи линия переходит в Modified — и только после этого позволяет другим ядрам обращаться к этой линии.
LOCK XADD — атомарное прибавление: прочитать значение, прибавить, записать результат, вернуть старое значение. Одна инструкция вместо трёх шагов.
LOCK CMPXCHG — атомарное сравнение и замена: прочитать значение, сравнить с ожидаемым, если совпало — записать новое. Если не совпало — оставить как есть и сообщить о неудаче.
ARM: LL/SC (Load-Linked / Store-Conditional)
ARM использует пару инструкций вместо одной.
LDXR (load-exclusive) загружает значение и помечает адрес как отслеживаемый (exclusive monitor). STXR (store-exclusive) записывает новое значение, но только если монитор не был сброшен. Монитор сбрасывается при записи другого ядра в ту же линию, при прерывании (exception entry) и в ряде других случаев — поэтому STXR может отказать даже без реальной конкуренции (ложный отказ, spurious failure). Код всегда обёрнут в цикл повтора.
Отличие от x86: LOCK удерживает линию на всё время инструкции. LL/SC не удерживает — вместо этого обнаруживает конфликт постфактум и повторяет операцию. При низкой конкуренции оба подхода стоят примерно одинаково, хотя на ARM возможны лишние повторы из-за ложных отказов.
CAS: программная абстракция
LOCK XADD и LOCK CMPXCHG покрывают конкретные операции — инкремент и замену с проверкой. Для произвольного атомарного обновления нужен более общий инструмент: прочитать текущее значение, вычислить новое и атомарно записать его, только если никто не вмешался. Этот паттерн и есть CAS (compare-and-swap) — абстракция, доступная программисту. CAS принимает три аргумента: адрес ячейки памяти, ожидаемое значение и новое значение. Вся операция неделима: если текущее значение совпадает с ожидаемым — CAS записывает новое и возвращает успех; если нет — не трогает ячейку и возвращает неудачу.
На x86 CAS транслируется в LOCK CMPXCHG. На ARM CAS строится поверх LL/SC: LDXR загружает значение, код сравнивает его с ожидаемым, STXR пытается записать новое — если STXR отказал, цикл повторяется. Компилятор или стандартная библиотека реализует CAS под конкретную архитектуру, и программисту не нужно думать о разнице между LOCK и LL/SC.
CAS-цикл: атомарный инкремент
С помощью CAS можно атомарно обновить значение — не только прибавить 1, но и применить произвольную функцию:
atomic_increment(addr):
повторять:
old = прочитать(addr)
new = old + 1
если CAS(addr, old, new) успешен:
выйти
// другое ядро изменило addr между чтением и CAS —
// CAS обнаружил расхождение, повторяем с новым значениемПоток читает текущее значение, вычисляет новое, затем пытается записать через CAS. Если между чтением и CAS другое ядро изменило значение, CAS обнаруживает расхождение и отказывает — цикл повторяется с обновлённым значением. При низкой конкуренции на x86 цикл срабатывает с первой попытки; на ARM возможен лишний повтор из-за ложного отказа STXR.
Для простых операций (инкремент, побитовое ИЛИ) компилятор использует специализированные атомарные инструкции (LOCK XADD, LOCK OR на x86) вместо CAS-цикла — одна инструкция эффективнее цикла.
Стоимость: когерентность определяет цену
CAS-цикл выглядит дёшево — несколько инструкций и условный повтор. Но любая атомарная инструкция — это когерентная транзакция, и у неё есть цена. Чтобы выполнить неделимый read-modify-write, процессор должен получить эксклюзивный доступ к кеш-линии на время операции.
Если линия уже принадлежит текущему ядру (состояние Modified или Exclusive), атомарная инструкция добавляет лишь несколько тактов — порядка ~6-8 нс. Ядру не нужно обращаться к другим — данные локальны.
Если линию держит другое ядро, процессор должен выполнить когерентную транзакцию: послать запрос, дождаться передачи линии, получить её в Modified. Это стоит ~40-70 нс — те же десятки наносекунд, что описаны в стоимости когерентности. Когда два ядра непрерывно обращаются к одной линии атомарными инструкциями, возникает ping-pong — линия мечется между кешами, и каждая операция стоит столько же, сколько промах в кеше.
Эта цена особенно заметна на общем счётчике. Два потока на разных ядрах, каждый выполняет атомарный инкремент 100 миллионов раз:
shared counter = 0
поток 0 (Core 0): поток 1 (Core 1):
повторить 100M раз: повторить 100M раз:
atomic_increment(counter) atomic_increment(counter)Один поток с обычным (неатомарным) инкрементом выполняет 100 миллионов итераций за доли секунды — данные всё время в L1. Два потока с атомарным инкрементом — в десятки раз медленнее. Причина — не сама атомарная инструкция (она добавляет лишь несколько тактов), а когерентный протокол: каждый инкремент вынуждает одно ядро забрать кеш-линию у другого.
Грубая оценка: 200 миллионов передач владения × ~50 нс = ~10 секунд. Почти всё время программа ждёт, пока кеш-линия перелетает между ядрами. Это и есть ping-pong — линия непрерывно мечется между кешами двух ядер, никогда не задерживаясь надолго.
Обычную запись процессор часто прячет за store buffer: ядро кладёт данные в буфер и продолжает выполнение, пока когерентная транзакция идёт в фоне. Для атомарного read-modify-write это невозможно — инструкция должна дождаться завершения захвата линии, иначе неделимость была бы фикцией. Поэтому атомарные операции над общей ячейкой, за которую одновременно борются несколько ядер, особенно чувствительны к цене когерентности.
Ограничение: одна ячейка
CAS гарантирует неделимость операции над одной ячейкой памяти. Но многие задачи требуют атомарного обновления нескольких связанных ячеек. Банковский перевод: списать сумму с одного счёта и зачислить на другой. CAS может атомарно обновить баланс одного счёта, но между обновлением первого и второго другой поток увидит несогласованное состояние — деньги исчезли из одного счёта, но не появились на другом.
Для атомарности произвольных блоков кода нужны программные примитивы синхронизации, которые строятся поверх аппаратных атомарных инструкций. Эти примитивы — тема операционной системы и параллельного программирования.
См. также
- Упорядочение памяти — какие гарантии порядка дают атомарные инструкции помимо неделимости
- Примитивы синхронизации — мьютексы, семафоры и другие абстракции, построенные поверх CAS
- Lock-free структуры данных: проблема ABA — ситуация, когда CAS видит «то же» значение, а контекст изменился; центральная проблема lock-free программирования
- Атомарность команд Redis — атомарность на другом уровне: однопоточный event loop гарантирует неделимость целой команды без аппаратных примитивов
Sources
- John L. Hennessy, David A. Patterson, 2017, Computer Architecture: A Quantitative Approach — Chapter 5: Thread-Level Parallelism, Section 5.5
- Intel, 2024, Intel 64 and IA-32 Architectures Software Developer’s Manual — Volume 2, LOCK prefix; Volume 3, Chapter 8 (Multiple-Processor Management)
- ARM, 2023, ARM Architecture Reference Manual — Section B2.9: Exclusive access instructions (LDXR/STXR)