Подходит ли ABA для операций вставки / вставки при использовании идиомы CAS?

Question

Следующий псевдокод взят из http://15418.courses.cs.cmu.edu/spring2013/article/46.

while (1) {
  n->next = p->next;
  Node *old_next = p->next;
  if (compare_and_swap(&p->next, old_next, n) == old_next)
    return;
}

Это pushоперация для стека без блокировки, которая использует идиому сравнения и замены, но делает это атомарно. Не похоже, что проблема ABA здесь актуальна, и мне интересно, так ли это вообще в случае операций вставки и вставки?

Answer 1

Вы правы, что эта функция не страдает от проблемы ABA, потому что нет ничего, что зависит от old_next значение до вызова compare_and_swap.

Рассмотрим (упрощенную) операцию pop:

  while (1) {
    Node *top = s->top;
    if (top == NULL)
      return NULL;
    Node *new_top = top->next;
    if (compare_and_swap(&s->top, top, new_top);
      return top;
  }
}

Здесь мы загружаем s->top в top а затем выполнить CAS на s->top с участием topкак ожидаемое значение. Но перед CAS мы читаемtop->next, поэтому мы выполняем операцию, которая зависит от top! Это то, что вызывает проблему ABA.

В целом невозможно утверждать, что все операции вставки / вставки свободны от проблемы ABA, поскольку это зависит от дополнительных деталей. В качестве несколько надуманного примера рассмотрим операцию push, которая условно перемещает значение, только если оно больше.

while (1) {
  n->next = p->next;
  Node *old_next = p->next;
  if (n->value < old_next->value)
    return;
  if (compare_and_swap(&p->next, old_next, n) == old_next)
    return;
}

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

Answer 2

В этом коде нет проблем с ABA, но это действительно потому, что он мало что делает.

Проблема в том, что вы используете compare_and_swap(&p->next, old_next, n)чтобы убедиться, что стек не изменился с тех пор, как вы в последний раз смотрели его, но это не делает этого надежно.

Между тем, когда вы читаете n->next и время, когда вы делаете compare_and_swap, другие потоки могут иметь:

1. Выскочил n->next
2. Вытолкнул кучу других вещей
3. Повторно вытолкнул старую n->next

Тогда твой compare_and_swap будет успешным, даже если стек изменился.

Для вас это не проблема, потому что вы никогда не смотрите ни в одно из полей n->next. Не имеет значения, что стек изменился, потому что все, что вас волнует, этоn->next указатель.

Если же придется искать внутри этого объекта, хотя, то ваш код будет нарушен. Например, если вы добавилиstack_size поле для атомарного отслеживания размера стека, тогда вы должны установить n->stack_size = old_next->stack_size+1, и это было бы неправильно, если бы стек изменился, как указано выше.

Так что это не правда, в общем, что вставка операции ABA-доказательство.