Как работает функция CAS (compare-and-swap) в многопоточности

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

Понимаете ли вы, как устроены атомарные классы Java и чем неблокирующий подход отличается от synchronized. Следом спрашивают про проблему ABA и про то, что делать, когда CAS постоянно проигрывает при высокой конкуренции.

Как отвечать

CAS это атомарная инструкция процессора с тремя операндами: адрес, ожидаемое значение, новое значение. Если по адресу лежит ожидаемое, записывается новое и возвращается успех, иначе ничего не меняется. На x86 это lock cmpxchg, на ARM отдельные инструкции CAS или пара load-linked/store-conditional.

В Java это выглядит так:

• compareAndSet(expected, next): у AtomicInteger и соседей возвращает boolean. Семантика памяти как у volatile чтения и записи, изменения видны другим потокам;
• цикл повтора: прочитать значение, вычислить новое, попробовать CAS, при неудаче повторить. Руками его писать не нужно, есть incrementAndGet(), updateAndGet() и accumulateAndGet();
• VarHandle: с Java 9 даёт CAS над обычным полем без обёртки, в том числе compareAndExchange, который возвращает фактическое значение;
• где применяется: ConcurrentHashMap (вставка в пустую ячейку), AbstractQueuedSynchronizer, на котором построены ReentrantLock и семафоры, ConcurrentLinkedQueue.

Плюс подхода: поток не усыпляется и не переключается, взаимных блокировок нет. Минус: при большой конкуренции потоки крутятся в повторах и жгут процессор. Для счётчиков под нагрузкой берут LongAdder, который раскладывает значение по ячейкам и суммирует при чтении.

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

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

Считают, что CAS гарантирует продвижение каждому потоку. Алгоритм на CAS неблокирующий (lock-free), но не wait-free: отдельный поток может проигрывать сколь угодно долго.

Пытаются атомарно обновить две переменные двумя CAS подряд. Между ними другой поток увидит несогласованное состояние, нужна одна неизменяемая структура в AtomicReference или блокировка.