AtomicStampReference：CAS中的ABA问题

问题分析

CAS算法实现一个重要前提：需要取出内存中某时刻的数据，而在下时刻比较并替换，那么在这个时间差类会导致数据的变化。

举一个例子：
现有一个用单向链表实现的堆栈，栈顶为A，这时线程T1已经知道A.next为B，然后希望用CAS将栈顶替换为B：进行head.compareAndSet(A,B)，在T1执行上面这条指令之前，线程T2介入，将A、B出栈，再pushD、C、A，而对象B此时正处于游离状态；若此时轮到线程T1执行CAS操作，检测发现栈顶仍为A，所以CAS成功，栈顶变为B，但实际上B.next为null。结果现在堆栈中只有B一个元素，C和D组成的链表不再存在于堆栈中，此时C、D平白无故被弄丢了。

其实还有另外一种情况：

A最开始的内存地址是X，然后失效了，有分配了B，恰好内存地址是X，这时候通过CAS操作也成功了，但是在像Java这种有GC机制的语言中，若A失效就被GC处理了，不会发生这种情况。若是在像C/C++没有GC机制的语言中是有可能出现的。

解决方案：

像各种乐观锁的实现中通常都会用版本戳version(保持递增加一规则)来对记录或对象标记，在CAS时加上对该版本戳的比较。
在Java语言中，AtomicStampedReference也是使用类似的机制做解决方案。

其核心方法为：

/**
 * Atomically sets the value of both the reference and stamp
 * to the given update values if the
 * current reference is {@code ==} to the expected reference
 * and the current stamp is equal to the expected stamp.
 *
 * @param expectedReference the expected value of the reference
 * @param newReference the new value for the reference
 * @param expectedStamp the expected value of the stamp
 * @param newStamp the new value for the stamp
 * @return {@code true} if successful
 */
public boolean compareAndSet(V   expectedReference,
                             V   newReference,
                             int expectedStamp,
                             int newStamp) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedStamp == current.stamp &&
        ((newReference == current.reference &&
          newStamp == current.stamp) ||
         casPair(current, Pair.of(newReference, newStamp)));
}

其中设定stamp值的原子性方法为：由于是非阻塞方法，即使两个参数对应，请求也会不合逻辑地失败。但最终当没有其他线程请求时就会成功。推荐阅读

/**
 * Atomically sets the value of the stamp to the given update value
 * if the current reference is {@code ==} to the expected
 * reference.  Any given invocation of this operation may fail
 * (return {@code false}) spuriously, but repeated invocation
 * when the current value holds the expected value and no other
 * thread is also attempting to set the value will eventually
 * succeed.
 *
 * @param expectedReference the expected value of the reference
 * @param newStamp the new value for the stamp
 * @return {@code true} if successful
 */
public boolean attemptStamp(V expectedReference, int newStamp) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        (newStamp == current.stamp ||
         casPair(current, Pair.of(expectedReference, newStamp)));
}

上面都用到unsafe的原子性方法compareAndSwapObject(xxxx)：

1
2
3

private boolean casPair(Pair<V> cmp, Pair<V> val) {
    return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}