Что такое механизм CAS (Compare-And-Swap)?

Механизм CAS (Compare-And-Swap) — это атомарная операция, выполняющая три действия:

1. Чтение текущего значения ячейки памяти.
2. Сравнение прочитанного значения с ожидаемым (old value).
3. Если значения совпадают, запись нового значения (new value) в ячейку.

Все эти действия выполняются как единая, неделимая операция на аппаратном уровне, что предотвращает состояния гонки в многопоточной среде без использования явных блокировок.

CAS используется в классы из пакета java.util.concurrent.atomic, такие как AtomicInteger, AtomicLong, AtomicReference.

Пример псевдокода для операции compareAndSet(expectedValue, newValue):

// На основе псевдокода для иллюстрации
boolean compareAndSet(int expectedValue, int newValue) {
    // Получаем текущее значение из памяти
    int currentValue = memory[address]; // Атомарное чтение

    // Сравниваем текущее значение с ожидаемым
    if (currentValue == expectedValue) {
        // Если совпадают, записываем новое значение
        memory[address] = newValue; // Атомарная запись, если сравнение истинно
        return true; // Операция успешна
    } else {
        // Если не совпадают, ничего не делаем
        return false; // Операция не успешна
    }
}

Преимущества CAS:

• Неблокирующий: Потоки, пытающиеся выполнить операцию CAS, не блокируют друг друга напрямую (в отличие от блокировок). При неудаче поток может просто повторить попытку.
• Высокая производительность: На многих современных процессорах CAS имеет аппаратную поддержку, что делает его очень быстрой операцией.
• Избегание взаимоблокировок: Поскольку потоки не удерживают блокировки, исключается риск взаимоблокировок.

Недостатки CAS:

• Проблема ABA: Если в промежутке между чтением значения и попыткой записи другое значение было сначала изменено на B, а затем обратно на A, операция CAS посчитает, что изменений не было, хотя они произошли. Для решения этой проблемы используются AtomicStampedReference или AtomicMarkableReference, которые добавляют к значению метку или признак изменения.
• Циклы ожидания (Spinning): Если операция CAS выполняется в цикле до тех пор, пока она не будет успешной, это может привести к загрузке процессора в случае высокой конкуренции, так как потоки многократно пытаются выполнить операцию.

CAS является фундаментальным building block'ом для многих неблокирующих алгоритмов в Java Concurrent Framework.