Что такое CAS?

Concurrent Addition and Subtraction (Сложение и Вычитание в Конкурентной Среде) - часто шуточное толкование, на самом деле Compare-And-Swap.

Atomic-операция, которая атомарно сравнивает значение в памяти с ожидаемым значением и, если они совпадают, обновляет его новым значением.

Аналогично псевдокоду:

// current_value - текущее значение в памяти
// expected_value - ожидаемое значение
// new_value - новое значение
if (current_value == expected_value) {
  current_value = new_value;
  return true; // Операция успешна
} else {
  return false; // Ожидаемое значение не совпало, операция не выполнена
}

Применяется в низкоуровневых примитивах синхронизации и неблокирующих алгоритмах для обеспечения потокобезопасности без использования блокировок (мьютексов, семафоров). Java предоставляет поддержку CAS через классы из пакета java.util.concurrent.atomic, например:

• AtomicInteger
• AtomicLong
• AtomicReference

Пример использования AtomicInteger:

import java.util.concurrent.atomic.AtomicInteger;

public class CasExample {

    public static void main(String[] args) {
        AtomicInteger counter = new AtomicInteger(0);

        boolean success = counter.compareAndSet(0, 1); // Сравниваем текущее 0 с ожидаемым 0, если совпадает, устанавливаем 1
        System.out.println("CAS successful: " + success); // Вывод: true
        System.out.println("Current value: " + counter.get()); // Вывод: 1

        success = counter.compareAndSet(0, 2); // Сравниваем текущее 1 с ожидаемым 0, не совпадает
        System.out.println("CAS successful: " + success); // Вывод: false
        System.out.println("Current value: " + counter.get()); // Вывод: 1
    }
}

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

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

Недостатки:

• Проблема ABA: Если значение изменялось с A на B, а затем снова на A между чтением и выполнением CAS, операция будет считаться успешной, даже если значение фактически изменилось. Некоторые классы (например, AtomicStampedReference) решают эту проблему, добавляя "метку" (stamp).
• Spurious wakeups: Потоки могут "вертеться" (spin) в цикле, пытаясь выполнить CAS, что потребляет ресурсы процессора.
• Сложность: Разработка неблокирующих алгоритмов с использованием CAS может быть сложнее, чем с использованием блокировок.