Краткий ответ

Это классическая проблема ABA: CAS видит прежнее значение A и считает, что состояние не менялось, хотя между двумя чтениями стек уже прошёл через состояние B. В результате операция может успешно применить устаревшее обновление и потерять элемент или повредить структуру данных.

Исторический контекст

Lock-free алгоритмы часто используют атомарный compare-and-swap: операция изменяет значение только тогда, когда оно всё ещё равно ранее прочитанному. Такой подход позволяет синхронизировать потоки без блокировок, но простое сравнение только текущего значения не фиксирует промежуточные изменения.

Именно для этого класса ошибок появилось понятие ABA. Оно особенно важно в структурах с атомарными указателями, где адрес узла может быть освобождён, повторно использован или снова установлен в корневое поле.

Постановка проблемы

Поток 1 считывает вершину стека A и готовит заменить её на следующий узел B. Пока он приостановлен, поток 2 снимает A, выполняет другие операции, а затем устанавливает вершиной другой узел или повторно использованный адрес A.

Когда поток 1 возобновляется, CAS сравнивает только адрес и видит A. Проверка проходит, хотя прочитанные ранее связанные данные уже могут быть устаревшими. Неверное обновление способно потерять элементы, нарушить связи узлов или обратиться к уже недействительной памяти.

Подробное решение

CAS проверяет равенство значения, но не историю его изменений. Поэтому последовательности A→B→A недостаточно, чтобы обнаружить, что значение фактически изменялось.

use std::sync::atomic::{AtomicUsize, Ordering};

let top = AtomicUsize::new(1); // условно: адрес A
let observed = top.load(Ordering::Acquire);
top.store(2, Ordering::Release); // A -> B
top.store(1, Ordering::Release); // B -> A
let result = top.compare_exchange(
    observed, 3, Ordering::AcqRel, Ordering::Acquire
);
assert!(result.is_ok()); // значение A совпало, хотя оно уже менялось

В реальном стеке вместо чисел используются указатели и связанные поля узлов. Обычно проблему решают добавлением счётчика версии к указателю: CAS сравнивает пару «указатель плюс версия», поэтому переход A→B→A получает новую версию и уже не совпадает со старым снимком.

Другой слой проблемы — безопасное освобождение памяти. Версионирование предотвращает часть логических ошибок, но само по себе не гарантирует, что старый узел можно безопасно разыменовать. Для этого применяют схемы epoch-based reclamation, hazard pointers или другие протоколы управления временем жизни памяти.

Обычный Ordering не устраняет ABA. Более сильный порядок памяти может обеспечить нужную видимость операций, но не добавляет к значению информацию о том, сколько раз оно менялось.

Ситуация из практики

В lock-free стеке поток читает вершину A и её поле next, равное B. Другой поток снимает A, освобождает её и распределитель памяти возвращает тот же адрес новому узлу C. Затем вершиной снова становится адрес A.

Вариант с одним атомарным указателем прост и быстр, но CAS может принять адрес A за неизменившуюся вершину; при этом сохранённый next уже относится к старому объекту. Вариант с версионированным указателем обнаруживает изменение даже при возврате адреса A, но требует атомарного представления указателя и счётчика, а также учитывает возможное переполнение версии.

На практике выбирают версионирование вместе с безопасной схемой reclamation. Это предотвращает как ошибочное принятие устаревшего CAS, так и использование памяти после завершения её жизненного цикла. Цена решения — дополнительная сложность, память для метаданных и возможные ограничения конкретной платформы на атомарность составного значения.

Что кандидаты часто упускают

1. Устраняет ли Acquire/Release проблему ABA?

Нет. Эти порядки определяют видимость и порядок памяти, но CAS по-прежнему сравнивает только текущее значение. Если оно вернулось к A, операция без версии не отличит A→B→A от состояния, в котором изменений не было.

2. Достаточно ли добавить счётчик версии, чтобы безопасно освободить узел?

Нет. Счётчик помогает обнаружить изменение значения, но не защищает память от освобождения в момент, когда другой поток ещё собирается её прочитать. Нужен отдельный механизм управления временем жизни: например, epoch-based reclamation или hazard pointers.

3. Может ли безопасный Rust полностью исключить ABA?

Нет. Безопасный Rust предотвращает множество ошибок владения и разыменования, но логическая ошибка алгоритма на атомарных значениях остаётся возможной. Кроме того, низкоуровневые lock-free структуры часто используют сырые указатели и unsafe, поэтому разработчик сам обязан доказать корректность синхронизации и reclamation.