无锁算法中的ABA问题

Question

我理解 ABA 问题。但是我不明白的是：他们说在拥有自动垃圾回收的语言中，它可能不会出现。所以我的问题是：

• 自动垃圾回收如何防止ABA问题的发生？
• 在Java中是否可能发生ABA问题，如果可以，如何避免？
• 是否可以防止ABA问题的发生？

- Trying

Answer 1

• 当启用自动垃圾回收时，两个对象不能使用相同的引用同时存在，这是因为只要有一个引用计数大于0，该引用本身就不会被释放和重复使用。

  因此，在某人仍持有旧引用时，您无法将引用内容“切换”为指向不同的对象。

- shaydel

Answer 2

ABA问题与垃圾回收无关。例如，应用程序可以将对象从链表移动到空闲列表，然后立即将其重新使用。因此，在重新使用之前，对象实际上从未被释放。 尽管如此，ABA问题可能会以以下方式发生：

Thread1:
    prevHead = head;

Thread2:
    prevHead = head;
    newHead = getFromFreeList();
    if (cas(&head, prevHead, newHead)) addToFreeList(prevHead);

Thread3:
    prevHead = head;
    newHead = getFromFreeList(); // Get the same object 'released' by Thread2
    cas(&head, prevHead, newHead) // succeeds and put back what was removed by Thread2

Thread1:
    newHead = getFromFreeList();
    if (cas(&head, prevHead, newHead)) addToFreeList(prevHead);
    // CAS will succeed although it shouldn't since there were
    // a modification on the head done by 'Thread3' in between.

- Rogério Ramos

Answer 3

在《多处理器编程的艺术》一书中，作者讨论了程序员可能想要在Java中实现自己的资源池（例如，一个列表节点池）的情况。然后，直接管理资源池的程序员绕过垃圾回收，从而提高性能。尽管如此，必须注意避免ABA问题。

以下是Java内存管理的核心代码：

ThreadLocal<Node> freeList = new ThreadLocal<Node>() {
    protected Node initialValue() { return null; };
};

LockFreeQueueRecycle.java的完整代码可以在此处找到：

http://booksite.elsevier.com/9780123705914/exercises/07~Chapter_10.zip

请查看第10章的幻灯片和代码：

http://booksite.elsevier.com/9780123705914/?ISBN=9780123705914

- Daniel S.

Answer 4

如何通过自动垃圾回收来防止ABA问题的发生？ 参见Herlihy Shavit的《多处理器编程的艺术》。引用：它（ABA问题）经常出现，特别是在动态内存算法中。 因此，在Java中当然可以出现ABA问题，但由于在大多数情况下该问题出现在动态内存算法中，并且您不经常在Java中实现此类算法，因此您不会经常看到此错误。

Java是否可能出现ABA问题？如果是，如何解决？ 《多处理器编程的艺术》一书给出了一个与锁无关的并发队列的内存回收问题的Java示例。

是否可能防止ABA问题的发生？引用：避免ABA问题的方法是测试值是否在两个时间点相同，而是测试值是否在这些时间点之间已更改。其中一种方法是使用AtomicStampedReference。

- Thomas Krieger

---

请在此处提供书中的文字，以便每个人都可以跟随。您可以将该网址作为参考。 - Trying

@gstackoverflow，“读这本书”不仅是礼貌，而且非常有力和慷慨的回答。它给了你发展自己实力的手段。可惜你无法欣赏并表现出如此的不感激。如果你读了这本书却发现它并不好，我也能理解，但即便如此，我们也应该欣赏提供详细、权威处理意见的精神。请阅读、学习并表示尊重。 - Lew Bloch

@Lew Bloch，如果我没有这本书，我就没有其他方法得到答案了吗？如果一个人正确理解了这本书，他可以解释书中所讲的主题。 - gstackoverflow