Compare-And-Swap

Compare-And-Swap (CAS, сравнение с обменом) — это атомарная инструкция процессора, используемая в многопоточном программировании для реализации неблокирующих синхронизаций. CAS выполняет одну операцию: сравнивает значение в ячейке памяти с ожидаемым значением и, если они совпадают, заменяет его на новое значение. Вся операция выполняется как единое, неделимое действие (атомарно), что предотвращает состояние гонки между потоками.

История и происхождение

Концепция CAS восходит к ранним работам в области параллельных вычислений. В 1970-х годах в рамках проекта IBM System/370 была предложена инструкция «Compare and Swap» (CS) для мейнфреймов. В 1980-х годах эта идея была развита в архитектуре процессоров x86 (инструкция CMPXCHG). Широкое распространение CAS получила с развитием многопроцессорных систем и многоядерных процессоров, когда традиционные блокировки (мьютексы) стали узким местом производительности из-за накладных расходов на переключение контекста и ожидание. Алгоритмы, использующие CAS, легли в основу многих неблокирующих структур данных (стеков, очередей, хеш-таблиц) и примитивов синхронизации в языках программирования (например, java.util.concurrent.atomic в Java или std::atomic в C++).

Принцип работы

Операция CAS принимает три операнда:

1. Адрес памяти (ptr), где хранится значение.
2. Ожидаемое значение (expected).
3. Новое значение (new_value).

Алгоритм выполнения:

1. Процессор атомарно считывает текущее значение по адресу ptr.
2. Сравнивает его с expected.
3. Если значения равны, процессор записывает new_value по адресу ptr и возвращает признак успеха (истина).
4. Если значения не равны, запись не производится, возвращается признак неудачи (ложь), а текущее значение обычно сохраняется для повторной попытки.

Важно, что вся последовательность «чтение-сравнение-запись» выполняется как единая атомарная операция на аппаратном уровне. Никакой другой поток или процессор не может изменить значение в ячейке памяти между чтением и записью.

Проблема ABA

Классическая проблема, возникающая при использовании CAS, — это проблема ABA. Она проявляется, когда значение в ячейке памяти изменяется с A на B, а затем снова на A между двумя проверками CAS. Алгоритм, полагающийся только на сравнение значений, может ошибочно посчитать, что состояние не изменилось, и выполнить операцию, которая приведёт к некорректному результату.

Например, в неблокирующем стеке, реализованном через CAS, поток может прочитать указатель на вершину стека (A). Другой поток может временно изменить вершину на B, а затем вернуть её обратно на A. Первый поток, выполняя CAS, увидит, что вершина всё ещё A, и запишет новый элемент, хотя структура стека уже изменилась (например, были добавлены и удалены другие элементы). Это может привести к потере ссылок или повреждению данных.

Для решения проблемы ABA применяются:

• Метка (tag) или счётчик версий: вместе с указателем хранится дополнительное целое число (счётчик), которое увеличивается при каждом изменении. CAS сравнивает пару (указатель, счётчик). Даже если указатель вернулся к старому значению, счётчик будет другим, и CAS не выполнится.
• Аппаратная поддержка: в некоторых архитектурах (например, x86 с инструкцией CMPXCHG16B) реализована двойная CAS (double-word CAS), позволяющая атомарно работать с 128-битными значениями, что даёт место для счётчика.
• Алгоритмы без ABA: некоторые структуры данных (например, неблокирующие очереди Майкла-Скотта) спроектированы так, чтобы проблема ABA не возникала при корректной реализации.

Реализация в процессорах

CAS реализована на уровне машинных инструкций в большинстве современных процессорных архитектур:

• x86/x86-64: инструкции CMPXCHG (сравнение с обменом одного слова), CMPXCHG8B (сравнение с обменом 8 байт) и CMPXCHG16B (сравнение с обменом 16 байт). Для обеспечения атомарности на многопроцессорных системах перед выполнением этих инструкций используется префикс LOCK, который блокирует шину памяти или кэш-линию.
• ARM: инструкции LDREX (эксклюзивная загрузка) и STREX (эксклюзивное сохранение), которые вместе реализуют механизм загрузки-связывания (load-link/store-conditional, LL/SC). Это более гибкий, чем CAS, примитив, позволяющий реализовать CAS и другие атомарные операции.
• RISC-V: инструкции lr (load-reserved) и sc (store-conditional), аналогичные ARM.
• PowerPC: инструкции lwarx (load word and reserve indexed) и stwcx (store word conditional indexed).

Применение

CAS является фундаментальным строительным блоком для многих механизмов синхронизации и структур данных:

Неблокирующие структуры данных

CAS позволяет реализовать стеки, очереди, списки и хеш-таблицы без использования традиционных блокировок. Это даёт преимущество в производительности на сильно конкурентных системах, так как потоки не блокируются и не тратят время на ожидание освобождения ресурса. Примеры:

• Неблокирующий стек (Treiber stack): использует CAS для атомарной замены вершины стека.
• Неблокирующая очередь (Michael-Scott queue): использует CAS для атомарного добавления и удаления элементов из двусвязного списка.

Атомарные переменные

В языках программирования высокого уровня (C++11, Java, C#, Rust) CAS лежит в основе реализации атомарных типов данных (std::atomic, AtomicInteger, AtomicReference). Эти типы предоставляют методы compare_exchange_weak и compare_exchange_strong, которые напрямую транслируются в аппаратные инструкции CAS.

Реализация блокировок

CAS может использоваться для реализации спин-блокировок (spinlock) и других примитивов синхронизации. Например, спин-блокировка может быть реализована как цикл, в котором поток пытается с помощью CAS изменить флаг с 0 (свободно) на 1 (занято). Если CAS не удаётся, поток продолжает попытки в цикле (спиннинг).

Управление памятью

В некоторых системах сборки мусора и управления памятью CAS используется для атомарного обновления указателей и счётчиков ссылок, например, в реализации алгоритмов Hazard Pointer или RCU (Read-Copy-Update).

Критика и ограничения

Несмотря на широкое применение, CAS имеет ряд недостатков:

• Проблема ABA: как описано выше, требует дополнительных мер для предотвращения.
• Накладные расходы на неудачные попытки: в условиях высокой конкуренции, когда множество потоков одновременно пытаются изменить одну и ту же ячейку памяти, большинство операций CAS будут неудачными, что приводит к холостому расходу процессорного времени (особенно в спин-блокировках).
• Сложность отладки: алгоритмы, использующие CAS, сложнее в проектировании, тестировании и отладке по сравнению с традиционными блокировками. Ошибки (например, пропущенная проблема ABA) могут приводить к трудно воспроизводимым сбоям.
• Аппаратные ограничения: на некоторых архитектурах (например, старых ARM) реализация LL/SC может быть подвержена ложным сбоям (spurious failure) из-за прерываний или конфликтов кэша, что требует использования слабых форм CAS (compare_exchange_weak).

Источники

• Herlihy, M., & Shavit, N. (2008). The Art of Multiprocessor Programming. Morgan Kaufmann.
• Intel Corporation. (2023). Intel® 64 and IA-32 Architectures Software Developer’s Manual.
• ARM Limited. (2022). ARM Architecture Reference Manual ARMv8-A.
• C++ Standard Committee. (2020). Working Draft, Standard for Programming Language C++ (N4868).