multithreading - ABA 在多线程中的真实示例

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




8年前关闭。




我正在寻找一些在多线程代码中导致麻烦的 ABA 问题的真实示例。

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

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

wikipedia page有一个受 ABA 影响的无锁堆栈实现示例，但我个人到目前为止还没有在生产代码中遇到这个问题。我只是好奇是否有人有一些关于 ABA 的精彩 war 故事可以分享。

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 将成功，但不会对列表进行排序。如果第二个线程的 Action 发生在第 5 行和第 6 行之间，您将丢失值为 X 的节点。所有这些都是因为 ABA 问题。