java - 为什么自动垃圾回收可以消除 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.

1. Thread_1 尝试将值 d 添加到堆栈，操作系统在 compareAndSet 操作之前挂起线程 (point_1)

2. Thread_2 然后执行 pop(Thread_1 仍然挂起)

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

3. Thread_3 然后执行 pop(Thread_1 仍然挂起)

   c // c-head, c- tail.
   

4. Thread_4 然后执行 push a(Thread_1 仍然挂起)

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

5. Thread_1 被唤醒，并且 cas 操作成功执行，尽管在某些情况下可能不受欢迎。

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

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

你能说清楚点吗？

Answer 1

您的部分困惑可能来自于您将数据结构本身与内容混为一谈。

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

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

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

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

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