为什么自动垃圾回收可以消除 ABA 问题？

Question

我在维基百科的实践书中调查了并发中的 ABA 问题，并且我阅读了以下内容 post

据我所知，ABA 问题的根本原因是在算法中我们检查的状态与之前相同，但算法暗示状态未被触及。

具有堆栈数据结构的示例：

要将元素添加到堆栈，我们使用以下算法：

create new stack node(save to `newNode` variable)

while(true) {
    oldHead = stack.get();
    newNode.next = oldHead; // point_1
    if(stack.compareAndSet(oldhead, newNode)) { // atomically replace head if now head same as was in start of iteration
        break;
    }    
}

导致ABA问题的步骤：
初始状态

a->b->c  // a-head, c- tail.

Thread_1 尝试将值 d 添加到堆栈并且 OS 在 compareAndSet 操作之前挂起线程（point_1）
Thread_2然后执行pop（Thread_1仍然挂起）
```
b->c  // b-head, c- tail.
```
Thread_3然后执行pop（Thread_1仍然挂起）
```
c // c-head, c- tail.
```
Thread_4然后执行push a(Thread_1仍然暂停)
```
a->c // a-head, c- tail.
```
Thread_1 唤醒并且 cas 操作成功执行，尽管在某些情况下可能不受欢迎。

虽然this answer被接受我不明白为什么自动垃圾收集消除了这个问题。

虽然我不是 C 专家，但我知道在 C 中你不能为两个不同的对象分配一个内存范围。

能说清楚点吗？

Answer 1

你的部分困惑可能来自于你混淆了数据结构本身和内容。

在 'proper' 实现中，您将有堆栈节点包含数据，而不是数据本身。所以，你最终得到的是 Node(a)、Node(b) 等——所以当某个线程将 c 压入堆栈时，它会传递 c，但实际上被压入的是 Node(c)。

这意味着，在这样的环境中，在第 4 步进入堆栈的东西将不仅仅是 a，而是 new Node(a)，这将是 不同的指针 来自 Node(a)，其他线程在步骤 1 中看到了这些对象。这些对象在业务方面可能非常平等（例如，在 java 中，它们等于方法将 return true)，但指针比较会有所不同。在这里，我们将讨论自动 GC 的不同之处。第 1 步中的阻塞线程仍然持有对 stack/registers 上 Node(a) 的旧实例的引用，即使它后来从堆栈中删除并且在堆中的任何地方都没有对它的强引用。这可以防止该节点被删除和内存地址被重用，这会欺骗 CAS。

请注意，如果您在线程 1 仍处于临界区时删除（内存方面）原始节点 (a)，那么您在此处提到的糟糕情况只会发生在非 GC 语言中。这是非常棘手的——你让线程带有指向已释放内存块的指针，并且需要非常、非常确定它不会在以后的任何时候被取消引用，因为它最终会导致比 ABA 更糟糕的结果（你可以阅读来自释放块的任何垃圾）。

如果您不以 Node(x) 的形式实现间接层，而只是让客户端直接调用 push/pop/modify 内部节点，那么所有的选择都将失败 - 客户端只需将同一个节点推送两次例如，稍后会导致无限循环。在你的例子中，它会先删除然后重新插入同一个节点，但这假设数据结构和客户端代码之间存在大量泄漏状态 - 在多线程环境中做这件事非常危险，特别是如果你想尝试无锁结构.

总而言之，自动 GC 并不能避免所有 ABA 情况。它防止非常特殊的 ABA 情况，与 malloc 的内存重用相关，用于积极优化的无锁代码，其中包含对死对象的引用。

为什么自动垃圾回收可以消除 ABA 问题？

Why does automatic garbage collection eliminate ABA problems?

java

concurrency

lock-free

aba