Проблема ABA

Рассмотрим 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 в которой запись в ячейку возможна, только если не было других записей в указанную ячейку. Это эффективно отделяет признак «ячейка содержит значение» от признака «ячейка была изменена». Примеры архитектур — DEC Alpha и PowerPC.

1. Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup. Lock-free Dynamically Resizable Arrays
2. Julian M Bucknall, Lock-free Data Structures: the stack.

• Double checked locking
• Concurrent Data Structures — схемы решения проблемы ABA на C++ (hazard pointers, pass-the-buck, tagged pointers и другие)