在聊聊高并发（101）实现几种自旋锁（5）中使用了java.util.concurrent.atomic.AtomicStampedReference原子变量指向工作队列的队尾，为什么使用AtomicStampedReference原子变量而不是使用AtomicReference是由于这个实现中等待队列的同1个节点具有不同的状态，而同1个节点会屡次进出工作队列，这就有可能出现出现ABA问题。
熟习并发编程的同学应当知道CAS操作存在ABA问题。我们先看下CAS操作。
CAS(Compare and Swap) 比较并交换操作是1个3元操作: 目标地址的值T(arget)，期望值E(xpected)，实际值R(eal)，
1. 只有当目标值T == 期望值E时，才会把目标值T设置为实际值R，否则不改变目标值
2. 不管目标值是不是改变，都返回之前的目标值T
类似以下的逻辑:
package com.zc.lock;
public class CAS {
private int value;
public synchronized int get(){
return value;
}
public synchronized int compareAndSwap(int expected, int real){
int oldValue = value;
if(value == expected){
value = real;
}
return oldValue;
}
public synchronized boolean compareAndSet(int expected, int real){
return (expected == compareAndSwap(expected, real));
}
}
CAS只比较期望值和目标值是不是相当，相当就设置新值。那末ABA问题就来了：
1. 由于CAS只是值比较，比如目标是A, 期望值也是A, 那末CAS操作会成功。但是这时候候目标A可能不是原来的那个A了，它多是A变成了B，再变成了A。所以叫ABA问题，很形象。ABA问题可能会使程序出错，比如限时有界队列锁中的节点有几个状态，虽然援用值是A，但是可能对象的状态已变了，这时候候的A实际已不是原来的A了
2. 需要注意的是ABA问题不是说CAS操作的进程中A变成了ABA，CAS操作是原子操作，不会被打断。ABA问题场景以下：
先获得了A的值，然后再CAS(A, R), 这时候候CAS中的A实际指向的对象的状态可能和它刚取得的时候的状态已发送了改变。
</pre><pre name="code" class="java">A a = ref.get();
// 根据a的状态做1些操作
// do something
// CAS,这时候候会出现ABA问题，a指向的对象可能已变了
ref.compareAndSet(a, b)
解决ABA问题方法就是给状态设置时间戳，这是并发中加乐观锁的常见做法，如果状态的时间戳产生了改变，证明已不是原来的对象了，所以操作失败
// 用int做时间戳
AtomicStampedReference<QNode> tail = new AtomicStampedReference<CompositeLock.QNode>(null, 0);
int[] currentStamp = new int[1];
// currentStamp中返回了时间戳信息
QNode tailNode = tail.get(currentStamp);
tail.compareAndSet(tailNode, null, currentStamp[0], currentStamp[0] + 1)
下面我们来看1下java.util.concurrent.atomic.AtomicStampedReference的源代码是如何实现的。
下面代码来自JDK1.7，条理很清晰，实现有几个要点:
1. 创建1个Pair类来记录对象援用和时间戳信息,采取int作为时间戳，实际使用的时候时间戳信息要做成自增的，否则时间戳如果重复，还会出现ABA的问题。这个Pair对象是不可变对象，所有的属性都是final的， of方法每次返回1个新的不可变对象
2. 使用1个volatile类型的援用指向当前的Pair对象，1旦volatile援用产生变化，变化对所有线程可见
3. set方法时，当要设置的对象和当前Pair对象不1样时，新建1个不可变的Pair对象
4. compareAndSet方法中，只有期望对象的援用和版本号和目标对象的援用和版本好都1样时，才会新建1个Pair对象，然后用新建的Pair对象和原理的Pair对象做CAS操作
5. 实际的CAS操作比较的是当前的pair对象和新建的pair对象，pair对象封装了援用和时间戳信息
private static class Pair<T> {
final T reference;
final int stamp;
private Pair(T reference, int stamp) {
this.reference = reference;
this.stamp = stamp;
}
static <T> Pair<T> of(T reference, int stamp) {
return new Pair<T>(reference, stamp);
}
}
private volatile Pair<V> pair;
public AtomicStampedReference(V initialRef, int initialStamp) {
pair = Pair.of(initialRef, initialStamp);
}
public void set(V newReference, int newStamp) {
Pair<V> current = pair;
if (newReference != current.reference || newStamp != current.stamp)
this.pair = Pair.of(newReference, newStamp);
}
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)));
}
private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
private static final long pairOffset =
objectFieldOffset(UNSAFE, "pair", AtomicStampedReference.class);
private boolean casPair(Pair<V> cmp, Pair<V> val) {
return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}