Проблема ABA
В многозадачных вычислениях проблема ABA возникает при синхронизации, когда ячейка памяти читается дважды, оба раза прочитано одинаковое значение, и признак «значение одинаковое» трактуется как «ничего не менялось». Однако, другой поток может выполниться между этими двумя чтениями, поменять значение, сделать что-нибудь ещё и восстановить старое значение. Таким образом, первый поток обманется, считая, что не поменялось ничего, хотя второй поток уже разрушил это предположение.
Проблема ABA возникает, когда множество потоков (или процессов) обращается к разделяемой памяти поочерёдно. Вот пример последовательности событий, ведущих к проблеме ABA:
- Процесс [math]\displaystyle{ P_1 }[/math] читает значение A из разделяемой памяти,
- [math]\displaystyle{ P_1 }[/math] вытесняется, позволяя выполняться [math]\displaystyle{ P_2 }[/math],
- [math]\displaystyle{ P_2 }[/math] меняет значение A на B и обратно на A перед вытеснением,
- [math]\displaystyle{ P_1 }[/math] возобновляет работу, видит, что значение не изменилось, и продолжает…
Хотя [math]\displaystyle{ P_1 }[/math] может продолжать работу, возможно, что его поведение будет неправильным из-за других, скрытых изменений общей памяти (которые он не отслеживал).
Обычно с проблемой ABA сталкиваются при реализации lock-free структур и алгоритмов. Если из списка удалить элемент, уничтожить его, а затем создать новый элемент и добавить обратно в список, есть вероятность, что новый элемент будет размещён на месте старого. Указатель на новый элемент совпадёт с указателем на старый, что и приведёт к проблеме: равенство признаков не есть равенство данных целиком.
Пример
Рассмотрим lock-free стек:
/* Наивная реализация lock-free стека, страдающая проблемой ABA.*/
class Stack {
volatile Obj* top_ptr;
//
// Снимает верхний элемент и возвращает указатель на него.
//
Obj* Pop() {
while(1) {
Obj* ret_ptr = top_ptr;
if (!ret_ptr) return NULL;
Obj* next_ptr = ret_ptr->next;
// Если верхний элемент - всё ещё ret, считаем, что никто не менял стек.
// (Это утверждение не всегда истинно из-за проблемы ABA)
// Атомарно заменяем top на next.
if (CompareAndSwap(top_ptr, ret_ptr, next_ptr)) {
return ret_ptr;
}
// Иначе - стек изменён, пробуем заново.
}
}
//
// Добавляет obj_ptr на вершину стека.
//
void Push(Obj* obj_ptr) {
while(1) {
Obj* next_ptr = top_ptr;
obj_ptr->next = next_ptr;
// Если верхний элемент - всё ещё next, считаем, что никто не менял стек.
// (Это утверждение не всегда истинно, из-за проблемы ABA)
// Атомарно заменяем top на obj.
if (CompareAndSwap(top_ptr, next_ptr, obj_ptr)) {
return;
}
// Иначе - стек изменён, пробуем заново.
}
}
};
Этот код обычно может предотвращать проблемы с конкурентным доступом, но страдает проблемой ABA. Рассмотрим следующую последовательность:
Изначально стек содержит top → A → B → C
Поток 1 начинает выполнять pop:
ret = A; next = B;
Поток 1 прерывается непосредственно перед CompareAndSwap…
{ // Поток 2 выполняет pop:
ret = A;
next = B;
CompareAndSwap(A, A, B) // Удача, top = B
return A;
} // Теперь на стеке top → B → C
{ // Поток 2 выполняет pop ещё раз:
ret = B;
next = C;
CompareAndSwap(B, B, C) // Удача, top = C
return B;
} // Теперь на стеке top → C
delete B;
{ // Поток 2 добавляет A обратно на стек:
A->next = C;
CompareAndSwap(C, C, A) // Удача, top = A
}
Теперь стек содержит top → A → C
Поток 1 продолжает работу:
CompareAndSwap(A, A, B)
Эта инструкция выполняется успешно, поскольку top == ret (оба равны A), то она присваивает top значение next (которое равно B). Но B было уничтожено! Это приведёт к плохим последствиям…
.Net позволяет реализовать CompareAndSwap (CAS) функцию атомарно благодаря методу Interlocked.CompareExchange().
private static bool CAS( ref Node<T> location, Node<T> newValue, Node<T> comparand)
{
// 1. если comparand и location равны, то другой поток не трогал значение location
// 2. location будет присвоен newValue
// 3. Метод вернёт старое значение location независимо от присвоения
// 4. copmarand сравнится со старым значением location (т.е. oldLocation)
// 5. если oldLocation(старый, возвращённый) не был изменён другим потоком то и CAS вернёт true, т.к. он совпадёт с comparand
var oldLocation = Interlocked.CompareExchange<Node<T>>( ref location, newValue, comparand); // это атомарная операция
return comparand == oldLocation;
}
Пример lock-free стека для .Net с использованием атомарной функции CAS:
public class SimpleStack<T>
{
private class Node<V>
{
public Node<V> Next;
public V Item;
}
private Node<T> head;
public SimpleStack()
{
head = new Node<T>();
}
public void Push(T item)
{
Node<T> node = new Node<T>();
node.Item = item;
do
{
node.Next = head.Next;
}
while ( CAS(ref head.Next, node, node.Next) == false);
// ждём момента, когда node.Next и head.Next указывают на один и тот же элемент.
// Тогда можно делать перестановку указателей, чтобы head показывал на node. После этого выход из цикла.
}
public T Pop()
{
Node<T> node;
do
{
node = head.Next;
if (node == null)
return default(T);
}
while (CAS(ref head.Next, node.Next, node) == false); // 1. В CAS не будет ABA-проблемы.
// 2. node.Next не вызывает NullReferenceException (node != null),
// потому что в .Net память управляемая
return node.Item;
}
}
ABA-проблема для данной реализации стека на .net становится неактуальной благодаря среде с использованием сборщика мусора: мы не потеряем и не используем повторно (в другом потоке) ссылку на node (при доступе к node.Next в CAS) если вдруг поток № 2 раньше, чем поток № 1, выполнит операцию Pop(). В средах без управления памятью эта проблема стоит остро и данное решение не подходит.
Обходные решения
Обычное обходное решение — это добавить дополнительные биты «метки» в проверяемое значение. Например, алгоритм, использующий compare-and-swap над указателями, может использовать младшие биты адреса для проверки, сколько раз указатель был изменён. Из-за этого следующий compare-and-swap не сработает, поскольку биты меток не совпадут. Это не решает проблемы полностью, так как значение битов метки может претерпеть циклический возврат к нулю. Некоторые архитектуры предоставляют двухсловный compare-and-swap, что позволяет сделать большую метку. Обычно это называется ABA', потому что второе значение A слегка отличается от первого.
Правильный, но дорогой подход состоит в использовании промежуточных узлов, которые не являются пользовательскими данными, а обеспечивают инвариантность операций добавления и удаления. [Valois].
Другой подход — использовать один или несколько hazard pointer'ов (указателей опасности), — указателей, которые в принципе не могут появиться в структуре данных. Каждый hazard pointer обозначает промежуточное состояние структуры в процессе изменения; наличие указателей требует дальнейшей синхронизации (Даг Ли).
Некоторые архитектуры предоставляют «укрупнённые» атомарные операции, благодаря чему, например, можно атомарно изменять сразу обе ссылки, вперёд и назад, в двусвязном списке.
Некоторые архитектуры предоставляют инструкцию load linked, store conditional в которой запись в ячейку возможна, только если не было других записей в указанную ячейку. Это эффективно отделяет признак «ячейка содержит значение» от признака «ячейка была изменена». Примеры архитектур — ARM, DEC Alpha, PowerPC.
Литература
- Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup. Lock-free Dynamically Resizable Arrays
- Julian M Bucknall, Lock-free Data Structures: the stack. [1]
Ссылки
- Double checked locking
- Concurrent Data Structures — схемы решения проблемы ABA на C++ (hazard pointers, pass-the-buck, tagged pointers и другие)
 | Для улучшения этой статьи по информационным технологиям желательно: |