提问人:24n8 提问时间:8/20/2020 更新时间:8/21/2020 访问量:64
使用 CAS 习惯用语时,ABA 是否与推/插入操作相关?
Is ABA relevant for push/insertion operations when using the CAS idiom?
问:
以下伪代码取自 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 问题,因为在调用 之前没有任何内容依赖于值。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;
}
}
在这里,我们加载到CAS中,然后按照预期值执行CAS。但是在 CAS 之前,我们读取 ,因此我们执行依赖于 !这就是导致 ABA 问题的原因。s->top
top
s->top
top
top->next
top
通常不可能说所有推/插入操作都没有 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 问题的影响,因为它可能会打破我们的不变性,即值是严格排序的。
此代码没有 ABA 问题,但这实际上是因为它没有做太多事情。
从根本上说,问题在于你用来确保堆栈自上次查看以来没有改变,但它并不能可靠地做到这一点。compare_and_swap(&p->next, old_next, n)
在你阅读和执行 之间,其他线程可能有:n->next
compare_and_swap
- 啪
n->next
- 推了一堆其他东西
- 重新推旧
n->next
那么即使堆栈发生了变化,你也会成功。compare_and_swap
这对你来说不是问题,因为你从不看任何字段。堆栈是否更改并不重要,因为您关心的只是指针。n->next
n->next
但是,如果您确实必须查看该对象内部,那么您的代码就会被破坏。例如,如果您添加了一个字段来原子化地跟踪堆栈大小,那么您将设置 ,如果堆栈如上所述更改,这将是错误的。stack_size
n->stack_size = old_next->stack_size+1
因此,一般而言,插入操作是 ABA 防伪的,这是不正确的。
评论