0

以下伪代码摘自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 问题无关，我想知道推送和插入操作是否通常是这种情况？

4

2 回答 2

0

You are right that this function does not suffer from the ABA problem, because there is nothing that depends on the old_next value before the call to compare_and_swap.

Consider the (simplified) pop operation:

  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;
  }
}

Here we load s->top into top and later perform a CAS on s->top with top as expected value. But before the CAS, we read top->next, so we perform an operation that depends on top! This is what causes the ABA problem.

It is not possible to generally state that all push/insert operations are free of the ABA problem, since it depends on more details. As a somewhat contrived example, consider a push operation that conditionally pushes the value only if it is greater.

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;
}

This also suffers from the ABA problem, because it might break our invariant that the values are strictly ordered.

于 2020-08-21T09:16:17.647 回答
0

这段代码不存在 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-proof 的。

于 2020-08-21T14:45:41.623 回答