Что такое lock-free программирование и CAS? Объясните проблему ABA и когда это использовать.

Question

IT Interview Practice · Accepted Answer

**Lock-free программирование координирует потоки без мьютексов, используя атомарные циклы compare-and-swap (CAS), так что хотя бы один поток всегда продвигается, даже если другие застревают.** Ни один поток не может быть заблокирован другим, удерживающим блокировку.

## CAS

**Compare-and-swap** атомарно устанавливает ячейку в новое значение только если она всё ещё содержит ожидаемое старое значение; иначе он терпит неудачу, и вы повторяете. Это примитив, стоящий за lock-free стеками, очередями и счётчиками.

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # атомарно, неделимо
  else: return false
```

```java
// Lock-free инкремент через цикл повтора CAS
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // повтор, если кто-то другой выиграл
```

## Проблема ABA

CAS проверяет только то, что значение всё ещё ожидаемое, — а не то, что оно никогда не менялось. Если оно прошло A → B → A между вашим чтением и CAS, CAS проходит успешно, но мир изменился под вами (например, освобождённый и переиспользованный узел).

```text
Поток 1: читает A ............... CAS(A→X) успешно ✗ (но список изменился!)
Поток 2:      pop A, push B, push A снова
```

**Исправление**: соедините указатель со счётчиком версии (`AtomicStampedReference`, tagged pointers), чтобы A-с-тегом-1 ≠ A-с-тегом-2, или используйте hazard pointers / epoch reclamation для безопасности памяти.

## Когда это использовать

- **Используйте** для горячего, мелкогранулярного общего состояния (счётчики, single-producer очереди), где доминирует конкуренция за блокировки, или где поток никогда не должен блокироваться (реальное время, обработчики сигналов).
- **Избегайте** как варианта по умолчанию: это трудно сделать правильно, легко внести ABA и баги упорядочивания памяти, и часто это не быстрее хорошего мьютекса при низкой конкуренции.

## Почему это важно

Lock-free структуры дают гарантии продвижения и избегают взаимоблокировок и инверсии приоритетов, но планка корректности высока. Знание CAS, ABA и проблемы освобождения памяти сигнализирует, что вы умеете рассуждать на уровне модели памяти — и, что критично, знаете, когда *не* стоит к этому обращаться.

CAS

Проблема ABA

Когда это использовать

Почему это важно

Похожие вопросы