Проблема ABA¶

Проблема ABA (англ. ABA problem) — это класс ошибок синхронизации в многопоточных и конкурентных вычислениях, возникающий при использовании неблокирующих алгоритмов, основанных на операциях сравнения с обменом (CAS, compare-and-swap). Суть проблемы заключается в том, что значение в памяти может измениться с A на B и затем обратно на A между двумя последовательными операциями чтения, что приводит к ложному срабатыванию CAS, который считает значение неизменным и выполняет некорректное действие.

¶История возникновения

Проблема ABA была впервые описана в контексте разработки неблокирующих структур данных в 1990-х годах, в частности, при работе над свободными от блокировок (lock-free) стеками и очередями. Одним из первых, кто обратил внимание на эту проблему, стал американский учёный в области информатики Морис Херлихи (Maurice Herlihy) в своей работе 1991 года «Wait-Free Synchronization». Позднее, в 1993 году, IBM-исследователи Джон М. Меллор-Крамми (John M. Mellor-Crummey) и Майкл Л. Скотт (Michael L. Scott) в своей статье «Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors» детально описали сценарии, приводящие к проблеме ABA, и предложили первые методы её решения. Проблема стала особенно актуальной с развитием многоядерных процессоров и необходимостью создания высокопроизводительных, масштабируемых алгоритмов, не использующих традиционные блокировки.

¶Механизм возникновения

¶Операция CAS

Операция сравнения с обменом (CAS) — это атомарная инструкция, которая выполняет следующую последовательность действий:

1. Считывает текущее значение из указанной ячейки памяти.
2. Сравнивает его с ожидаемым значением.
3. Если значения совпадают, записывает в ячейку новое значение.
4. Возвращает признак успеха операции.

CAS является фундаментальным строительным блоком для многих неблокирующих алгоритмов, таких как стеки, очереди и списки.

¶Классический сценарий ABA

Рассмотрим реализацию неблокирующего стека на основе односвязного списка. Поток A хочет удалить верхний элемент (pop). Он:

1. Считывает указатель на вершину стека (top) — получает значение A.
2. Считывает следующий элемент за вершиной — получает значение B.
3. Планирует выполнить CAS, чтобы заменить top с A на B.

Однако между шагами 2 и 3 происходит следующее:

• Поток B удаляет элемент A (top становится B).
• Поток B добавляет обратно элемент A (top снова становится A).
• Поток B удаляет элемент A, но при этом изменяет его внутреннее состояние (например, указатель next становится равен C, а не B).

Теперь поток A выполняет CAS: сравнивает top с ожидаемым значением A. Значение top снова равно A, поэтому CAS успешно заменяет top на B. Однако в реальности структура данных изменилась: элемент A уже не является вершиной, а B — это не следующий элемент после A. Стек оказывается в некорректном состоянии, что может привести к потере данных, повреждению памяти или неопределённому поведению программы.

¶Примеры проявления

¶Неблокирующий стек (Treiber Stack)

Стек Трейбера — одна из первых lock-free реализаций стека, использующая CAS. Проблема ABA в нём проявляется, как описано выше, когда между чтением вершины и CAS происходит повторное использование удалённого узла. Это может привести к тому, что стек теряет часть элементов или зацикливается.

¶Неблокирующая очередь (Michael-Scott Queue)

В очереди Майкла-Скотта проблема ABA может возникнуть при работе с указателями на голову и хвост очереди. Если узел, который был удалён из очереди, повторно добавляется, CAS может ошибочно считать, что структура не изменилась, и выполнить некорректную операцию вставки или удаления.

¶Управление памятью и сборка мусора

В системах с ручным управлением памятью (C, C++) проблема ABA усугубляется тем, что освобождённый и повторно выделенный блок памяти может иметь тот же адрес, что и ранее. Это делает CAS уязвимым к ложным срабатываниям, даже если данные по адресу изменились.

¶Методы решения

¶Тегированные указатели (Tagged Pointers)

Наиболее распространённый способ борьбы с проблемой ABA — использование тегированных указателей. Вместо того чтобы хранить в CAS только адрес памяти, алгоритм хранит пару (адрес, тег). Тег — это монотонно возрастающее число (например, счётчик), которое увеличивается каждый раз, когда узел освобождается или повторно используется. CAS сравнивает и обновляет всю пару целиком. Даже если адрес возвращается к прежнему значению, тег будет другим, и CAS не сработает.

Этот метод требует, чтобы адрес и тег умещались в одно машинное слово (обычно 64 бита), что возможно на большинстве современных архитектур. В 32-битных системах тег может занимать часть битов адреса, что ограничивает адресное пространство.

¶Алгоритмы с двойной CAS (DCAS)

Некоторые архитектуры (например, Motorola 68020) поддерживают операцию двойного сравнения с обменом (DCAS), которая позволяет атомарно обновлять два независимых слова в памяти. Это может быть использовано для одновременного обновления указателя и счётчика, решая проблему ABA без необходимости упаковки данных в одно слово. Однако DCAS сложнее реализовать на аппаратном уровне, и она не поддерживается в x86-64.

¶Hazard Pointers (Опасные указатели)

Техника «опасных указателей» (hazard pointers) позволяет потокобезопасно управлять памятью в lock-free структурах. Каждый поток объявляет, какие узлы он в данный момент использует. Поток, желающий освободить узел, сначала проверяет, не объявлен ли он как опасный другим потоком. Если да, освобождение откладывается. Это предотвращает повторное использование узла, пока на него есть активные ссылки, что исключает возможность возникновения проблемы ABA.

¶RCU (Read-Copy-Update)

Механизм RCU (чтение-копирование-обновление), используемый в ядре Linux, решает проблему ABA на уровне синхронизации, разделяя операции чтения и обновления. Читатели могут обращаться к данным без блокировок, а обновления выполняются путём создания новой версии данных и атомарной замены указателя. Старая версия данных освобождается только после того, как все читатели, которые могли её использовать, завершили работу. Это делает RCU устойчивым к проблеме ABA, но требует поддержки со стороны операционной системы и имеет другие ограничения.

¶Использование транзакционной памяти (TM)

Аппаратная транзакционная память (HTM) и программная транзакционная память (STM) позволяют выполнять группу операций над памятью как атомарную транзакцию. Если в процессе транзакции обнаруживается конфликт (например, изменение данных другим потоком), транзакция откатывается и повторяется. Транзакционная память автоматически обрабатывает проблему ABA, так как она видит все изменения, произошедшие между началом и концом транзакции, и не допускает ложных срабатываний. Однако HTM имеет ограничения по размеру транзакций и может быть подвержена сбоям, а STM налагает накладные расходы.

¶Значение и влияние

Проблема ABA является одной из ключевых трудностей при проектировании неблокирующих (lock-free и wait-free) алгоритмов. Её решение требует либо аппаратной поддержки (тегированные указатели, DCAS, HTM), либо сложных программных методов управления памятью (hazard pointers, RCU). Непонимание или игнорирование этой проблемы приводит к трудноуловимым ошибкам, которые могут проявляться редко и в условиях высокой нагрузки, что делает их особенно опасными в критически важных системах (базы данных, операционные системы, высоконагруженные серверы).

Современные компиляторы и библиотеки (например, C++11 <atomic>, Java java.util.concurrent.atomic) предоставляют встроенные средства для работы с CAS и тегированными указателями, что упрощает разработку корректных неблокирующих структур данных. Однако ответственность за правильное применение этих средств и предотвращение проблемы ABA по-прежнему лежит на разработчике.

¶Источники

• Herlihy, M. (1991). «Wait-Free Synchronization». ACM Transactions on Programming Languages and Systems.
• Mellor-Crummey, J. M., & Scott, M. L. (1993). «Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors». ACM Transactions on Computer Systems.
• Michael, M. M. (2004). «Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects». IEEE Transactions on Parallel and Distributed Systems.
• McKenney, P. E., & Slingwine, J. D. (1998). «Read-Copy-Update: Using Execution History to Solve Concurrency Problems». Proceedings of the 1998 International Conference on Parallel and Distributed Computing Systems.