JDK源码——CAS实现原理

CAS的全称为Compare And Swap&＃xff0c;直译就是比较交换。是一条CPU的原子指令&＃xff0c;其作用是让CPU先进行比较两个值是否相等&＃xff0c;然后原子地更新某个位置的值&＃xff0c;其实现方式是基于硬件平台的汇编指令&＃xff0c;在intel的CPU中&＃xff0c;使用的是cmpxchg指令&＃xff0c;就是说CAS是靠硬件实现的&＃xff0c;从而在硬件层面提升效率。

利用CPU的CAS指令&＃xff0c;同时借助JNI来完成Java的非阻塞算法&＃xff0c;其它原子操作都是利用类似的特性完成的。 在 java.util.concurrent 下面的源码中&＃xff0c;Atomic, ReentrantLock 都使用了Unsafe类中的方法来保证并发的安全性。

CAS操作是原子性的&＃xff0c;所以多线程并发使用CAS更新数据时&＃xff0c;可以不使用锁&＃xff0c;JDK中大量使用了CAS来更新数据而防止加锁来保持原子更新。

CAS 操作包含三个操作数 &＃xff1a;内存偏移量位置&＃xff08;V&＃xff09;、预期原值&＃xff08;A&＃xff09;和新值(B)。 如果内存位置的值与预期原值相匹配&＃xff0c;那么处理器会自动将该位置值更新为新值 。否则&＃xff0c;处理器不做任何操作。

// 使用 unsafe 类的原子操作方式
private static final Unsafe unsafe &＃61; Unsafe.getUnsafe();
private static final long valueOffset;static {try {//计算变量 value 在类对象中的偏移量valueOffset &＃61; unsafe.objectFieldOffset(AtomicInteger.class.getDeclaredField("value"));} catch (Exception ex) { throw new Error(ex); }
}

关于偏移量

Unsafe 调用C 语言可以通过偏移量对变量进行操作

//volatile变量value
private volatile int value;/*** 创建具有给定初始值的新 AtomicInteger** &＃64;param initialValue 初始值*/
public AtomicInteger(int initialValue) {value &＃61; initialValue;
}//返回当前的值
public final int get() {return value;
}
//原子更新为新值并返回旧值
public final int getAndSet(int newValue) {return unsafe.getAndSetInt(this, valueOffset, newValue);
}
//最终会设置成新值
public final void lazySet(int newValue) {unsafe.putOrderedInt(this, valueOffset, newValue);
}
//如果输入的值等于预期值&＃xff0c;则以原子方式更新为新值
public final boolean compareAndSet(int expect, int update) {return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}//方法相当于原子性的 &＃43;&＃43;i
public final int getAndIncrement() {//三个参数&＃xff0c;1、当前的实例 2、value实例变量的偏移量 3、递增的值。return unsafe.getAndAddInt(this, valueOffset, 1);
}
//方法相当于原子性的 --i
public final int getAndDecrement() {//三个参数&＃xff0c;1、当前的实例 2、value实例变量的偏移量 3、递减的值。return unsafe.getAndAddInt(this, valueOffset, -1);
}
Unsafe 源码解析

在JDK8中追踪可见sun.misc.Unsafe这个类是无法看见源码的&＃xff0c;打开openjdk8源码看

文件&＃xff1a;openjdk-8-src-b132-03_mar_2014.zip

目录&＃xff1a;openjdk\jdk\src\share\classes\sun\misc\Unsafe.java

通常我们最好也不要使用Unsafe类&＃xff0c;除非有明确的目的&＃xff0c;并且也要对它有深入的了解才行。要想使用Unsafe类需要用一些比较tricky的办法。Unsafe类使用了单例模式&＃xff0c;需要通过一个静态方法getUnsafe()来获取。但Unsafe类做了限制&＃xff0c;如果是普通的调用的话&＃xff0c;它会抛出一个SecurityException异常&＃xff1b;只有由主类加载器加载的类才能调用这个方法。


//获取Unsafe实例静态方法
&＃64;CallerSensitive
public static Unsafe getUnsafe() {Class caller &＃61; Reflection.getCallerClass();if (!VM.isSystemDomainLoader(caller.getClassLoader()))throw new SecurityException("Unsafe");return theUnsafe;
}


//native硬件级别的原子操作//类似的有compareAndSwapInt,compareAndSwapLong,compareAndSwapBoolean,compareAndSwapChar等等。public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);//内部使用自旋的方式进行CAS更新&＃xff08;while循环进行CAS更新&＃xff0c;如果更新失败&＃xff0c;则循环再次重试&＃xff09;public final int getAndAddInt(Object o, long offset, int delta) {int v;do {//获取对象内存地址偏移量上的数值vv &＃61; getIntVolatile(o, offset);//如果现在还是v,设置为 v &＃43; delta,否则返回false,继续循环再次重试.} while (!compareAndSwapInt(o, offset, v, v &＃43; delta));return v;}


利用 Unsafe 类的 JNI compareAndSwapInt 方法实现&＃xff0c;使用CAS实现一个原子操作更新&＃xff0c;compareAndSwapInt 四个参数&＃xff1a;1、当前的实例 2、实例变量的内存地址偏移量 3、预期的旧值 4、要更新的值。

到这里 CAS 的实现过程就讲了&＃xff0c;CAS 的实现离不开处理器的支持。可以发现AtomicInteger原子类的内部几乎是基于前面分析过Unsafe类中的CAS相关操作的方法实现的&＃xff0c;这也同时证明AtomicInteger getAndIncrement自增操作实现过程,是基于无锁实现的。

假设这样一种场景&＃xff0c;当第一个线程执行CAS(V,E,U)操作。在获取到当前变量V&＃xff0c;准备修改为新值U前&＃xff0c;另外两个线程已连续修改了两次变量V的值&＃xff0c;使得该值又恢复为旧值&＃xff0c;这样的话&＃xff0c;我们就无法正确判断这个变量是否已被修改过&＃xff0c;如下图&＃xff1a;

这就是典型的CAS的ABA问题&＃xff0c;一般情况这种情况发现的概率比较小&＃xff0c;可能发生了也不会造成什么问题&＃xff0c;比如说我们对某个做加减法&＃xff0c;不关心数字的过程&＃xff0c;那么发生ABA问题也没啥关系。但是在某些情况下还是需要防止的&＃xff0c;那么该如何解决呢&＃xff1f;在Java中解决ABA问题&＃xff0c;我们可以使用以下原子类

AtomicStampedReference原子类是一个带有时间戳的对象引用&＃xff0c;在每次修改后&＃xff0c;AtomicStampedReference不仅会设置新值而且还会记录更改的时间。当AtomicStampedReference设置对象值时&＃xff0c;对象值以及时间戳都必须满足期望值才能写入成功&＃xff0c;这也就解决了反复读写时&＃xff0c;无法预知值是否已被修改的窘境。底层实现为&＃xff1a; 通过Pair私有内部类存储数据和时间戳, 并构造volatile修饰的私有实例。

接着看 java.util.concurrent.atomic.AtomicStampedReference类的compareAndSet&＃xff08;&＃xff09;方法的实现&＃xff1a;

private static class Pair {final T reference;final int stamp;//最好不要重复的一个数据,决定数据是否能设置成功,时间戳会重复private Pair(T reference, int stamp) {this.reference &＃61; reference;this.stamp &＃61; stamp;}static Pair of(T reference, int stamp) {return new Pair(reference, stamp);}
}

同时对当前数据和当前时间进行比较&＃xff0c;只有两者都相等是才会执行casPair()方法&＃xff0c;单从该方法的名称就可知是一个CAS方法&＃xff0c;最终调用的还是Unsafe类中的compareAndSwapObject方法到这我们就很清晰AtomicStampedReference的内部实现思想了&＃xff0c;通过一个键值对Pair存储数据和时间戳&＃xff0c;在更新时对数据和时间戳进行比较&＃xff0c;只有两者都符合预期才会调用Unsafe的compareAndSwapObject方法执行数值和时间戳替换&＃xff0c;也就避免了ABA的问题。

/*** 原子更新带有版本号的引用类型。* 该类将整数值与引用关联起来&＃xff0c;可用于原子的更数据和数据的版本号。* 可以解决使用CAS进行原子更新时&＃xff0c;可能出现的ABA问题。*/
public class AtomicStampedReference {//静态内部类Pair将对应的引用类型和版本号stamp作为它的成员private static class Pair {//最好不要重复的一个数据,决定数据是否能设置成功,建议时间戳final T reference;final int stamp;private Pair(T reference, int stamp) {this.reference &＃61; reference;this.stamp &＃61; stamp;}//根据reference和stamp来生成一个Pair的实例static Pair of(T reference, int stamp) {return new Pair(reference, stamp);}}//作为一个整体的pair变量被volatile修饰private volatile Pair pair;//构造方法&＃xff0c;参数分别是初始引用变量的值和初始版本号public AtomicStampedReference(V initialRef, int initialStamp) {pair &＃61; Pair.of(initialRef, initialStamp);}....private static final sun.misc.Unsafe UNSAFE &＃61; sun.misc.Unsafe.getUnsafe();private static final long pairOffset &＃61; objectFieldOffset(UNSAFE, "pair", AtomicStampedReference.class);//获取pair成员的偏移地址static long objectFieldOffset(sun.misc.Unsafe UNSAFE,String field, Class klazz) {try {return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));} catch (NoSuchFieldException e) {NoSuchFieldError error &＃61; new NoSuchFieldError(field);error.initCause(e);throw error;}}
}

/*** &＃64;param 期望(老的)引用* &＃64;param (新的)引用数据* &＃64;param 期望(老的)标志stamp(时间戳)值* &＃64;param (新的)标志stamp(时间戳)值* &＃64;return 是否成功*/
public boolean compareAndSet(V expectedReference,V newReference,int expectedStamp,int newStamp) {Pair current &＃61; pair;return// 期望(老的)引用 &＃61;&＃61; 当前引用expectedReference &＃61;&＃61; current.reference &&// 期望(老的)标志stamp(时间戳)值 &＃61;&＃61; 当前标志stamp(时间戳)值expectedStamp &＃61;&＃61; current.stamp &&// (新的)引用数据 &＃61;&＃61; 当前引用数据 并且 (新的)标志stamp(时间戳)值 &＃61;&＃61;当前标志stamp(时间戳)值((newReference &＃61;&＃61; current.reference && newStamp &＃61;&＃61; current.stamp) ||#原子更新值casPair(current, Pair.of(newReference, newStamp)));}//当引用类型的值与期望的一致的时候&＃xff0c;原子的更改版本号为新的值。该方法只修改版本号&＃xff0c;不修改引用变量的值&＃xff0c;成功返回true
public boolean attemptStamp(V expectedReference, int newStamp) {Pair current &＃61; pair;returnexpectedReference &＃61;&＃61; current.reference &&(newStamp &＃61;&＃61; current.stamp ||casPair(current, Pair.of(expectedReference, newStamp)));
}/*** CAS真正实现方法*/
private boolean casPair(Pair cmp, Pair val) {return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}

期望 Pair cmp&＃xff08;A&＃xff09; &＃61;&＃61; 当前内存存偏移量位置 Pair&＃xff08;V&＃xff09;&＃xff0c;就更新值 Pair val&＃xff08;B&＃xff09;成功返回true 否则 false。

public static void main(String[] args) {AtomicStampedReference num &＃61; new AtomicStampedReference(1, 0);Integer i &＃61; num.getReference();int stamped &＃61; num.getStamp();if (num.compareAndSet(i, i &＃43; 1, stamped, stamped &＃43; 1)) {System.out.println("测试成功");}
}

通过以上原子更新方法&＃xff0c;可见 AtomicStampedReference就是利用了Unsafe的CAS方法&＃43;Volatile关键字对存储实际的引用变量和int的版本号的Pair实例进行更新