CAS
CAS(CompareAndSet)是保证并发安全性的一条CPU底层原子指令，它的功能是判断某个值是否为预期值，如果是的话，就改为新值，在CAS过程中不会被中断。
compareAndSet 在JNI(Java Naive Interface)中实现，位于unsafe.cpp文件，关键的语句是 cmpxchg(x, addr, e)，其中x指的是旧值，addr是要和oldValue一致的内存位置，而e是要变为的新值。执行该原子语句时，将oldValue和从addr取出的值进行比较，相等的话才设置addr位置的值为新值e。
ABA
但CAS存在一个ABA问题，举例来说，假设线程1和线程2拥有同一个引用p，p指向对象A。某个时刻，线程1想要利用CAS把p指向的对象换成C，此时被线程2中断，线程2将p指向的对象换成B后再换成A，然后线程1继续运行，发现p确实仍然指向对象A，因此执行CAS将A换成C。但线程1并不知道在它中断的这段时间内，p指向的引用经历了从A到B在到A的过程，这个bug就称为ABA问题。对于普通场景来说，ABA问题似乎不会造成什么危害，但我们来考虑下面这种场景。
ABA的危害
下面是一段伪代码，将就着看一下。场景是用链表来实现一个栈，初始化向栈中压入B、A两个元素，栈顶head指向A元素。
在某个时刻，线程1试图将栈顶换成B，但它获取栈顶的oldValue(为A)后，被线程2中断了。线程2依次将A、B弹出，然后压入C、D、A。然后换线程1继续运行，线程1执行compareAndSet发现head指向的元素确实与oldValue一致，都是A，所以就将head指向B了。但是，注意我标黄的那行代码，线程2在弹出B的时候，将B的next置为null了，因此在线程1将head指向B后，栈中只剩了一个孤零零的元素B。但按预期来说，栈中应该放的是B → A → D → C。
Node head;
head=B;
A.next=head;
head=A;
Thread thread1= newThread(->{
oldValue=head;
sleep(3秒);
compareAndSet(oldValue, B);
}
);
Thread thread2= newThread(->{//弹出A
newHead =head.next;
head.next= null; //即A.next = null;
head =newHead;//弹出B
newHead =head.next;
head.next= null; //即B.next = null;
head = newHead; //此时head为null//压入C
head =C;//压入D
D.next =head;
head=D;//压入A
A.next =D;
head=A;
}
);
thread1.start();
thread2.start();
如有错误，敬请指正 >。<