使用 CAS 习惯用语时,ABA 是否与推/插入操作相关?

Is ABA relevant for push/insertion operations when using the CAS idiom?

提问人:24n8 提问时间:8/20/2020 更新时间:8/21/2020 访问量:64

问:

以下伪代码取自 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;
}

这是使用比较和交换习惯用语的无锁堆栈的操作,但以原子方式执行。ABA 问题似乎与此处无关,我想知道推送和插入操作是否通常如此?push

多线程与 语言无关的比较 和交换 ABA

评论


答:

1赞 mpoeter 8/21/2020 #1

您说得对,此函数不会遇到 ABA 问题,因为在调用 之前没有任何内容依赖于值。old_nextcompare_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;
  }
}

在这里,我们加载到CAS中,然后按照预期值执行CAS。但是在 CAS 之前,我们读取 ,因此我们执行依赖于 !这就是导致 ABA 问题的原因。s->toptops->toptoptop->nexttop

通常不可能说所有推/插入操作都没有 ABA 问题,因为它取决于更多细节。举一个有点人为的示例,考虑一个推送操作,该操作仅在值大于时才有条件地推送该值。

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 问题的影响,因为它可能会打破我们的不变性,即值是严格排序的。

0赞 Matt Timmermans 8/21/2020 #2

此代码没有 ABA 问题,但这实际上是因为它没有做太多事情。

从根本上说,问题在于你用来确保堆栈自上次查看以来没有改变,但它并不能可靠地做到这一点。compare_and_swap(&p->next, old_next, n)

在你阅读和执行 之间,其他线程可能有:n->nextcompare_and_swap

  1. n->next
  2. 推了一堆其他东西
  3. 重新推旧n->next

那么即使堆栈发生了变化,你也会成功。compare_and_swap

这对你来说不是问题,因为你从不看任何字段。堆栈是否更改并不重要,因为您关心的只是指针。n->nextn->next

但是,如果您确实必须查看该对象内部,那么您的代码就会被破坏。例如,如果您添加了一个字段来原子化地跟踪堆栈大小,那么您将设置 ,如果堆栈如上所述更改,这将是错误的stack_sizen->stack_size = old_next->stack_size+1

因此,一般而言,插入操作是 ABA 防伪的,这是不正确的。