Java并发编程-无锁CAS与Unsafe类及其并发包Atomic
一、介绍
CAS（Compare and Swap），即比较并替换，实现并发算法时常用到的一种技术，性能大大优于synchronized加锁操作，属于无锁策略。
执行函数：CAS(V,E,N)
CAS的思想很简单：三个参数，一个当前内存值V、旧的预期值E、即将更新的值N，当且仅当预期值E和内存值V相同时，将内存值修改为N并返回true，否则什么都不做，并返回false。
二、JAVA实现
CPU指令对CAS的支持（原子操作）
或许我们可能会有这样的疑问，假设存在多个线程执行CAS操作并且CAS的步骤很多，有没有可能在判断V和E相同后，正要赋值时，切换了线程，更改了值。造成了数据不一致呢？答案是否定的，因为CAS是一种系统原语，原语属于操作系统用语范畴，是由若干条指令组成的，用于完成某个功能的一个过程，并且原语的执行必须是连续的，在执行过程中不允许被中断，也就是说CAS是一条CPU的原子指令，不会造成所谓的数据不一致问题。
Unsafe
Unsafe，是CAS的核心类，由于Java方法无法直接访问底层系统，需要通过本地（native）方法来访问，Unsafe相当于一个后门，基于该类可以直接操作特定内存的数据。
CAS是一些CPU直接支持的指令，也就是我们前面分析的无锁操作，在Java中无锁操作CAS基于以下3个Unsafe类的方法实现，Atomic系列内部方法是基于下述方法的实现的
//第一个参数o为给定对象，offset为对象内存的偏移量，通过这个偏移量迅速定位字段并设置或获取该字段的值，
//expected表示期望值，x表示要设置的值，下面3个方法都通过CAS原子指令执行操作。
public final native boolean compareAndSwapObject(Object o, long offset,Object expected, Object x);
public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);
public final native boolean compareAndSwapLong(Object o, long offset,long expected,long x);
三、问题
CAS存在一个很明显的问题，即ABA问题。
问题：如果变量V初次读取的时候是A，并且在准备赋值的时候检查到它仍然是A，那能说明它的值没有被其他线程修改过了吗？如果在这段期间曾经被改成B，然后又改回A，那CAS操作就会误认为它从来没有被修改过。
针对这种情况，java并发包中提供了一个带有标记的原子引用类AtomicStampedReference，AtomicStampedReference原子类是一个带有时间戳（int类型，不一定是时间戳，也可以自定义为版本号）的对象引用，在每次修改后，AtomicStampedReference不仅会设置新值而且还会记录更改的时间。当AtomicStampedReference设置对象值时，对象值以及时间戳都必须满足期望值才能写入成功，这也就解决了反复读写时无法预知值是否已被修改。
public class AtomicStampedReference<V> {
//通过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);
}
}
另外还有类似的AtomicMarkableReference，他的内部Pair是一个boolean不标志位，可见这个类只关心变量是否有被改动过，而不关注改动的次数
private static class Pair<T> {
final T reference;
final boolean mark;
private Pair(T reference, boolean mark) {
this.reference = reference;
this.mark = mark;
}
static <T> Pair<T> of(T reference, boolean mark) {
return new Pair<T>(reference, mark);
}
}
