多线程中ABA问题的实际案例

Question

我正在寻找一些关于ABA问题在多线程代码中造成麻烦的实际例子。

当执行一个原子的compare-and-swap指令时，ABA问题会出现在并发代码中。如果一个线程在执行compare-and-swap之前立即被中断，第二个线程可能会将compare-and-swap的目标从其初始值A更改为另一个值B。如果它然后在第一个线程恢复之前将该值改回A，则compare-and-swap将成功，尽管对目标值进行了更改。

在许多情况下，ABA不是问题。以共享引用计数为例：即使并发地更改refcount，只要我们从已经降至0的refcount中不再增加，我们就没有问题。因此，我们显然只关心目标是否与交换时的期望值匹配，而不关心它在过去是否发生了变化。

维基百科页面 有一个无锁栈实现的例子遇到了ABA问题，但我个人在生产代码中还没有遇到这个问题。我只是好奇是否有人有一些关于ABA的有趣故事可以分享。

- ComicSansMS

Answer 1

假设你想使用传统的链表实现有序列表。如果你想向列表中添加一个新值V，首先需要使用辅助指针AUX找到插入新元素的正确位置，并定位它在最后一个节点上，该节点的值小于V，同时还要保存AUX->next以进行CAS操作的比较。一旦你有了参考，就可以使NEW->next指向AUX->next，并且使用CAS将AUX->next切换到NEW，如果AUX->next仍然是你保存的相同引用。应该像这样：

AUX = list.HEAD;
WHILE( AUX->next.value < V)
    AUX = AUX->next;
OLD = AUX->next; //line 4
NEW->next = AUX->next; //line 5
IF( CAS(AUX->next, NEW, OLD)) //line 6
    Success!!!
ELSE
    Try again or whatever

这是最简单的方法。问题在于，在第4行和第5行之间，另一个线程可能已经删除了“OLD”，并插入了另一个比V小但仍大于AUX.value的元素X。如果发生这种情况，并且具有值X的节点的内存地址与原先具有OLD的地址相同，则CAS将成功，但列表将不会排序。如果第二个线程的操作发生在第5行和第6行之间，则会丢失具有值X的节点。所有这些都是由于ABA问题引起的。

- ees_cu

---

CAS(AUX->next, NEW, OLD) 应该改为 CAS(AUX->next, OLD, NEW)，对吧？ - Jason Law

这是一个听起来很好的例子，唯一的问题是ABA不是这些问题的原因。在这个单向链表中同时进行插入和删除操作已经是不安全的了。当第二个线程移除“OLD”并插入一个新值“X”，该节点地址仍然是“OLD”，这时就会发生ABA。但是ABA是不必要的——在第二个线程上删除“AUX”就足以导致数据损坏。 - Ben Voigt