多线程中ABA的真实示例

Question

我正在寻找一些很好的实际例子,说明ABA问题导致多线程代码出现问题.

执行原子比较和交换指令时,并发代码中会出现ABA问题.如果线程在执行比较和交换之前立即中断,则第二个线程可能会更改比较和交换的目标从其初始值A更改为不同的值B.如果它然后将值更改回A在第一个线程恢复之前,尽管目标值发生了变化,但compare-and-swap仍会成功.

在许多情况下,ABA不是问题.以共享引用计数为例:即使refcount同时更改,我们也没有问题,只要我们永远不会从已经下降到0的refcount增加.所以我们显然只对目标是否匹配感兴趣交换时的预期价值,而不是过去的变化.

在维基百科页面具有从ABA遭受无锁栈实现的例子,但我个人没有碰上在生产代码的问题为止.我只是好奇是否有人有一些很好的战争故事来分享ABA.

Answer 1

假设您要使用传统链接列表实现有序列表.假设您要将新值V添加到列表中.首先,您必须找到使用辅助指针AUX插入新元素的正确位置,并将其定位在最后一个节点中,其值小于V,并且还要保存AUX-> next以在CAS操作中进行比较.一旦你有了参考,你可以使用NEW->下一个指向AUX-> next然后使用CAS,如果AUX-> next仍然是你保存的参考,你可以在NEW旁边切换AUX->.它应该是这样的:

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问题.