java aba问题_JAVA与ABA问题

在《JAVA并发编程实战》的第15.4.4节中看到了一些关于ABA问题的描述。有一篇文章摘录了书里的内容。

书中有一段内容为：

如果在算法中采用自己的方式来管理节点对象的内存，那么可能出现ABA问题。在这种情况下，即使链表的头结点仍然只想之前观察到的节点，那么也不足以说明链表的内容没有发生变化。如果通过垃圾回收器来管理链表节点仍然无法避免ABA问题，那么还有一个相对简单的解决方法：不是只是更新某个引用的值，而是更新两个值，包含一个引用和一个版本号。

这一段说到了“如果采用自己的方式管理节点对象的内存，可能出现ABA问题”，又说通过垃圾回收器来管理链表节点可能避免ABA问题。但是这些表述太简略，让我有些困惑。具体怎么样管理内存，会出现ABA问题？GC会什么可能会避免ABA问题？为什么只是“可能会避免”？

在JDK的ConcurrentLinkedQueue的源码注释中，有以下说法：

* This is a modification of the Michael & Scott algorithm,

* adapted for a garbage-collected environment, with support for

* interior node deletion (to support remove(Object)). For

* explanation, read the paper.

*

* Note that like most non-blocking algorithms in this package,

* this implementation relies on the fact that in garbage

* collected systems, there is no possibility of ABA problems due

* to recycled nodes, so there is no need to use “counted

* pointers” or related techniques seen in versions used in

* non-GC’ed settings.

里边有两点要注意的：

说这个类的实现是对”Michael & Scott”算法的一个修改，这个修改是基于ConcurrentLinkedList的实现存在于“垃圾回收的环境”。

说这个类的实现依赖于“在GC系统中，there is no possibility of ABA problems due to recycled nodes”。问题在于，什么叫”recycled nodes”？

好吧，那么在JAVA中怎么操作可能会现ABA问题呢？

假如有一个Queue(先别管它怎么实现)，那么在以下情况下会出现ABA问题：

我们在CAS中比较对节点的引用 & 我们复用节点。假如queue初始的状态是A -> E。在变化后的状态是A -> X -> E。那么我们在CAS中比较对A的引用时，就无法看出状态的变化。“复用”，就是像这个例子一样，把同一个节点再次加个队列。

我们在CAS中比较对节点的引用 & 某个new出来的节点A2的地址恰好和A1的地址相同。

第一种情况不管GC环境还是非GC环境，都会造成ABA问题。所以GC只是可能会避免ABA问题，就像《JAVA并发编程实战》中说的一样。

GC环境和无GC的环境(如C++)的不同在于第二种情况。即，在JAVA中第，第二种情况是不可能发生的。原因在于，在我们用CAS比较A1和A2这两个引用时，暗含着的事实是——这两个引用存在，所以它们所引用的对象都是GC root可达的。那么在A1引用的对象还未被GC时，一个新new的对象是不可能和A1的对象有相同的地址的。所以A1 != A2。

所以，在JAVA的GC环境中，如果两个引用在CAS中被判断为相等，它们引用的肯定是同一个对象。但是，这种描述对于非GC环境不成立。

例如，在C++中，我们对指针(类比于JAVA中的引用)采用CAS操作，那么即使两个指针相同，他们也未必引用同一个对象，有可能是第一个指针所指向的内存被释放后，第二个对象恰好分配在相同地址的内存。

在维基百科上，给出了上面提到的第一种情况在C++中的一个例子。在这个例子中，复用节点的行为，可能会导致使用一个悬垂指针。

同时，维基百科也对第二种情况给出了描述：

A common case of the ABA problem is encountered when implementing a lock-free data structure. If an item is removed from the list, deleted, and then a new item is allocated and added to the list, it is common for the allocated object to be at the same location as the deleted object due to optimization. A pointer to the new item is thus sometimes equal to a pointer to the old item which is an ABA problem.

在ConcurrentLinkedList的实现中，并不存在复用节点的行为。在这个类的实现内部，以及它提供给用户的API，都无法使得节点被复用，而且这是JAVA环境中。所以ConcurrentLinkedList的实现中直接对node的引用进行CAS操作，而不必担心ABA问题。

例如，在offer的实现中(JDK1.7)

public boolean offer(E e) {

checkNotNull(e);

final Node newNode = new Node(e);

for (Node t = tail, p = t;;) {

Node q = p.next;

if (q == null) {

// p is last node

if (p.casNext(null, newNode)) {

// Successful CAS is the linearization point

// for e to become an element of this queue,

// and for newNode to become “live”.

if (p != t) // hop two nodes at a time

casTail(t, newNode); // Failure is OK.

return true;

}

// Lost CAS race to another thread; re-read next

}

else if (p == q)

// We have fallen off list. If tail is unchanged, it

// will also be off-list, in which case we need to

// jump to head, from which all live nodes are always

// reachable. Else the new tail is a better bet.

p = (t != (t = tail)) ? t : head;

else

// Check for tail updates after two hops.

p = (p != t && t != (t = tail)) ? t : q;

}

}

用if (p.casNext(null, newNode))来确保只有p是尾节点时，才将新结点链接在p的后边。