CS Notes

atomic-instructions

5 min read

Атомарные инструкции

Предпосылки: ISA (инструкции, x86 vs ARM), когерентность кешей (MESI, Modified, кеш-линия).

Когерентность гарантирует, что запись одного ядра станет видна другим. Но операция counter++ — это три шага: load, add, store. Между load и store другое ядро может выполнить свой load, и один инкремент потеряется. Когерентность работает корректно — каждый отдельный store виден. Проблема в том, что последовательность из трёх шагов не неделима.

Процессор решает эту задачу специальными инструкциями, которые выполняют read-modify-write как единое целое. Для любого наблюдателя (другого ядра) операция либо ещё не произошла, либо уже завершена целиком — промежуточного состояния не видно. Такие инструкции называются атомарными (atomic, от греч. ἄτομος — неделимый).

Два подхода: LOCK и LL/SC

Архитектуры x86 и ARM решают задачу по-разному.

x86: префикс LOCK

На x86 атомарность обычной инструкции достигается добавлением префикса LOCK. Процессор захватывает кеш-линию в эксклюзивное владение (состояние Modified в протоколе MESI), выполняет всю инструкцию и только после этого позволяет другим ядрам обращаться к этой линии.

LOCK XADD — атомарное прибавление: прочитать значение, прибавить, записать результат, вернуть старое значение. Одна инструкция вместо трёх шагов.

LOCK CMPXCHG — атомарное сравнение и замена: прочитать значение, сравнить с ожидаемым, если совпало — записать новое. Если не совпало — оставить как есть и сообщить о неудаче.

ARM: LL/SC (Load-Linked / Store-Conditional)

ARM использует пару инструкций вместо одной.

LDXR (load-exclusive) загружает значение и помечает адрес как отслеживаемый (exclusive monitor). STXR (store-exclusive) записывает новое значение, но только если монитор не был сброшен. Монитор сбрасывается при записи другого ядра в ту же линию, при переключении контекста и в ряде других случаев — поэтому STXR может отказать даже без реальной конкуренции (spurious failure). Код всегда обёрнут в цикл повтора.

Отличие от x86: LOCK удерживает линию на всё время инструкции. LL/SC не удерживает — вместо этого обнаруживает конфликт постфактум и повторяет операцию. При низкой конкуренции оба подхода стоят примерно одинаково.

CAS: программная абстракция

CAS (compare-and-swap) — абстракция, доступная программисту: прочитать текущее значение, сравнить с ожидаемым, если совпало — записать новое. Вся операция неделима. На x86 CAS реализуется одной инструкцией LOCK CMPXCHG. На ARM CAS строится поверх LL/SC: LDXR загружает значение, код сравнивает его с ожидаемым, STXR пытается записать новое — если STXR отказал, цикл повторяется.

CAS принимает три аргумента: адрес ячейки памяти, ожидаемое значение и новое значение. Если текущее содержимое ячейки совпадает с ожидаемым — CAS записывает новое и возвращает успех. Если содержимое изменилось (другое ядро успело записать своё) — CAS не трогает ячейку и возвращает неудачу.

CAS-цикл: атомарный инкремент

С помощью CAS можно атомарно обновить значение — не только прибавить 1, но и применить произвольную функцию:

atomic_increment(addr):
    повторять:
        old = прочитать(addr)
        new = old + 1
        если CAS(addr, old, new) успешен:
            выйти
        // другое ядро изменило addr между чтением и CAS —
        // CAS обнаружил расхождение, повторяем с новым значением

Поток читает текущее значение, вычисляет новое, затем пытается записать через CAS. Если между чтением и CAS другое ядро изменило значение, CAS обнаруживает расхождение и отказывает — цикл повторяется с обновлённым значением. При низкой конкуренции цикл срабатывает с первой попытки.

Для простых операций (инкремент, побитовое ИЛИ) компилятор использует специализированные атомарные инструкции (LOCK XADD, LOCK OR на x86) вместо CAS-цикла — одна инструкция эффективнее цикла.

Стоимость: когерентность определяет цену

Атомарная инструкция — это когерентная транзакция. Чтобы выполнить неделимый read-modify-write, процессор должен получить эксклюзивный доступ к кеш-линии на время операции.

Если линия уже принадлежит текущему ядру (состояние Modified или Exclusive), атомарная инструкция добавляет лишь несколько тактов — порядка ~6-8 нс. Ядру не нужно обращаться к другим — данные локальны.

Если линию держит другое ядро, процессор должен выполнить когерентную транзакцию: послать запрос, дождаться передачи линии, получить её в Modified. Это стоит ~40-70 нс — те же десятки наносекунд, что описаны в стоимости когерентности. Когда два ядра непрерывно обращаются к одной линии атомарными инструкциями, возникает ping-pong — линия мечется между кешами, и каждая операция стоит столько же, сколько промах в кеше.

Ограничение: одна ячейка

CAS гарантирует неделимость операции над одной ячейкой памяти. Но многие задачи требуют атомарного обновления нескольких связанных ячеек. Банковский перевод: списать сумму с одного счёта и зачислить на другой. CAS может атомарно обновить баланс одного счёта, но между обновлением первого и второго другой поток увидит несогласованное состояние — деньги исчезли из одного счёта, но не появились на другом.

Для атомарности произвольных блоков кода нужны программные примитивы синхронизации, которые строятся поверх аппаратных атомарных инструкций. Эти примитивы — тема операционной системы и параллельного программирования.

См. также

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)

Graph View

Backlinks