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

Question

我已经在练习书和维基百科中调查了并发中的 ABA 问题，我已经阅读了以下帖子

据我了解，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. 线程_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 操作成功执行，尽管在某些情况下它可能是不受欢迎的。

虽然这个答案被接受了，但我不明白为什么自动垃圾收集会消除这个问题。

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

你能说得更清楚吗？

Answer 1

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

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

这意味着，在这样的环境中，在步骤4进入堆栈的东西会不会只是a，这将是new Node(a)，这将是不同的指针从Node(a)哪个其他线程已经看到在步骤1中这些对象可能是很好等于商业智慧（例如，在 java 中，它们的 equals 方法将返回 true），但指针比较会有所不同。在这里，我们来到了自动 GC 发挥作用的部分。步骤 1 中的阻塞线程仍然持有对堆栈/寄存器上 Node(a) 旧实例的引用，即使它稍后从堆栈中删除并且在堆中的任何地方都没有对它的强引用。这可以防止该节点被删除和内存地址被重用，这会欺骗 CAS。

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

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

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