Как работает инструкция compare-and-swap на уровне архитектуры процессора и как она реализована в разных архитектурах

Что проверяют

Понимаете ли вы, на чём держатся AtomicInteger, ConcurrentHashMap и весь lock-free код в Java, и чем CAS на x86 отличается от ARM. Следом почти всегда спрашивают про проблему ABA и про то, почему CAS под высокой конкуренцией может работать хуже обычной блокировки.

Как отвечать

CAS атомарно сравнивает значение по адресу с ожидаемым и, если они совпали, записывает новое. Результат говорит, удалась ли замена, и на этом строится цикл: прочитал, посчитал, попробовал записать, при неудаче повторил.

По архитектурам:

• x86: LOCK CMPXCHG, для двойного слова CMPXCHG16B. Без префикса LOCK операция не атомарна между ядрами. На современных процессорах блокируется не шина, а строка кэша через протокол когерентности, до шины дело доходит только при невыровненном доступе через границу строки. Инструкция с LOCK работает как полный барьер памяти;
• ARM: пара load-linked/store-conditional, в ARMv7 это LDREX/STREX, в AArch64 LDXR/STXR и варианты с acquire/release. Запись проходит, только если с момента чтения адрес никто не трогал, иначе цикл повторяется. В ARMv8.1 появилось расширение LSE с прямыми инструкциями CAS и CASAL;
• POWER: тоже LL/SC, lwarx и stwcx.;
• RISC-V: LR/SC плюс атомарные AMO-инструкции.

В Java CAS доступен через AtomicXxx.compareAndSet и VarHandle (с Java 9), внутри JDK через Unsafe. JIT превращает эти вызовы в интринсики: на x86 получается lock cmpxchg, а getAndIncrement компилируется в lock xadd вообще без цикла. weakCompareAndSet существует как раз из-за LL/SC, где возможен ложный отказ.

Где спотыкаются

Говорят, что CAS «ничего не стоит». При сотне потоков на одной переменной строка кэша мечется между ядрами, большинство попыток проваливается, и LongAdder с разнесёнными счётчиками выигрывает в разы.

Не знают про ABA: значение успело смениться с A на B и обратно, а CAS считает, что ничего не произошло. Для ссылок это лечится AtomicStampedReference с версией.

Путают lock-free и wait-free. CAS-цикл гарантирует прогресс системы в целом, но отдельный поток может проигрывать бесконечно.