4

我在维基百科的实践书中调查了并发中的 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. 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 操作成功执行，尽管在某些情况下它可能是不可取的。

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

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

你能更清楚地澄清它吗？

4

1 回答 1

5

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

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

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

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

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

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

于 2017-03-17T10:43:43.470 回答