Опасные указатели и проблема ABA

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

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

Одно из решений — хранить рядом с указателем счётчик. Комбинированное значение изменяется при каждой операции, поэтому ABA можно обнаружить.

Для меток требуются атомарные операции двойной ширины, например CMPXCHG16B на x86. Они занимают больше места и могут быть недоступны на некоторых платформах.

Основной вопрос заключается в следующем: как удалить узел, к которому другие потоки всё ещё могут обращаться? В безблокировочном коде нельзя использовать простой delete.

Каждый поток публикует указатель, к которому он обращается в данный момент, в глобальном списке опасных указателей. Перед освобождением памяти поток просматривает этот список: если указатель используется, удаление откладывается.

Для каждого обращения:

1. Атомарно считайте указатель
2. Опубликуйте его как опасный
3. Считайте его повторно и убедитесь, что он не изменился, чтобы избежать гонки
4. Используйте его
5. Сбросьте опасный указатель

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

Другой вариант — разделить время на эпохи. Узел можно удалить, когда все потоки перейдут за эпоху, в которой этот узел был отложен. Такой подход используется в Crossbeam (Rust) и в структурах данных для конкурентного доступа.

При чтении увеличивайте счётчик узла, а после использования уменьшайте его. Это просто, но медленнее указателей опасности: каждая операция добавляет атомарные увеличения и уменьшения счётчика.

ABA становится проблемой только при наличии «списка свободных элементов» или повторном использовании адресов памяти. При безопасном освобождении памяти с помощью указателей опасности или эпох проблема часто исчезает.

Безблокировочные структуры данных таят множество ловушек. Используйте проверенные реализации из Folly, Boost или Crossbeam (Rust). Создавайте собственную реализацию только в учебных целях или для конкретных критически важных по производительности участков после тщательных измерений.

ThreadSanitizer обнаруживает гонки данных, но не все проблемы корректности безблокировочного кода. Инструменты формальной верификации, такие как CDSChecker и Relacy, систематически исследуют различные варианты чередования операций.

Что означает проблема ABA в безблокировочном программировании?

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