14

我正在寻找一些在多线程代码中引起问题的ABA 问题的真实示例。

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

在许多情况下,ABA 不是问题。以共享引用计数为例:即使 refcount 并发改变我们也没有问题,只要我们从不从已经下降到 0 的 refcount 增加。所以我们显然只关心目标是否匹配交换时的期望值,而不是过去是否发生变化。

维基百科页面有一个受 ABA 影响的无锁堆栈实现示例,但到目前为止,我个人还没有在生产代码中遇到过这个问题。我只是好奇是否有人有一些关于 ABA 的好战争故事要分享。

4

1 回答 1

12

假设您想使用传统的链表实现有序列表。假设您想在列表中添加一个新值 V。首先,你要找到合适的位置,使用辅助指针AUX插入新元素,并将其定位在最后一个值小于V的节点,同时保存AUX->next,以便在CAS操作中进行比较。一旦有了引用,您将 NEW->next 指向 AUX->next,然后使用 CAS,如果 AUX->next 仍然是您保存的相同引用,则将 AUX->next 切换为 NEW。它应该是这样的:

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

于 2013-01-28T00:36:10.320 回答