前言
CAS(Compare and Swap),即比较并替换,实现并发算法时常用到的一种技术,Doug lea大神在java同步器中大量使用了CAS技术,鬼斧神工的实现了多线程执行的安全性。
CAS的思想很简单:三个参数,一个当前内存值V、旧的预期值A、即将更新的值B,当且仅当预期值A和内存值V相同时,将内存值修改为B并返回true,否则什么都不做,并返回false。
问题
一个n++的问题。
public class Case { public volatile int n; public void add() { n++; } }
通过javap -verbose Case看看add方法的字节码指令
public void add(); flags: ACC_PUBLIC Code: stack=3, locals=1, args_size=1 0: aload_0 1: dup 2: getfield #2 // Field n:I 5: iconst_1 6: iadd 7: putfield #2 // Field n:I 10: return
n++被拆分成了几个指令:
- 执行getfield拿到原始n;
- 执行iadd进行加1操作;
- 执行putfield写把累加后的值写回n;
通过volatile修饰的变量可以保证线程之间的可见性,但并不能保证这3个指令的原子执行,在多线程并发执行下,无法做到线程安全,得到正确的结果,那么应该如何解决呢?
如何解决
在add方法加上synchronized修饰解决。
public class Case { public volatile int n; public synchronized void add() { n++; } }
这个方案当然可行,但是性能上差了点,还有其它方案么?
再来看一段代码
public int a = 1; public boolean compareAndSwapInt(int b) { if (a == 1) { a = b; return true; } return false; }
如果这段代码在并发下执行,会发生什么?
假设线程1和线程2都过了a==1的检测,都准备执行对a进行赋值,结果就是两个线程同时修改了变量a,显然这种结果是无法符合预期的,无法确定a的最终值。
解决方法也同样暴力,在compareAndSwapInt方法加锁同步,变成一个原子操作,同一时刻只有一个线程才能修改变量a。
除了低性能的加锁方案,我们还可以使用JDK自带的CAS方案,在CAS中,比较和替换是一组原子操作,不会被外部打断,且在性能上更占有优势。
下面以AtomicInteger的实现为例,分析一下CAS是如何实现的。
public class AtomicInteger extends Number implements java.io.Serializable { // setup to use Unsafe.compareAndSwapInt for updates private static final Unsafe unsafe = Unsafe.getUnsafe(); private static final long valueOffset; static { try { valueOffset = unsafe.objectFieldOffset (AtomicInteger.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); } } private volatile int value; public final int get() {return value;} }
- Unsafe,是CAS的核心类,由于Java方法无法直接访问底层系统,需要通过本地(native)方法来访问,Unsafe相当于一个后门,基于该类可以直接操作特定内存的数据。
- 变量valueOffset,表示该变量值在内存中的偏移地址,因为Unsafe就是根据内存偏移地址获取数据的。
- 变量value用volatile修饰,保证了多线程之间的内存可见性。
看看AtomicInteger如何实现并发下的累加操作:
public final int getAndAdd(int delta) { return unsafe.getAndAddInt(this, valueOffset, delta); } //unsafe.getAndAddInt public final int getAndAddInt(Object var1, long var2, int var4) { int var5; do { var5 = this.getIntVolatile(var1, var2); } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4)); return var5; }
假设线程A和线程B同时执行getAndAdd操作(分别跑在不同CPU上):
- AtomicInteger里面的value原始值为3,即主内存中AtomicInteger的value为3,根据Java内存模型,线程A和线程B各自持有一份value的副本,值为3。
- 线程A通过getIntVolatile(var1, var2)拿到value值3,这时线程A被挂起。
- 线程B也通过getIntVolatile(var1, var2)方法获取到value值3,运气好,线程B没有被挂起,并执行compareAndSwapInt方法比较内存值也为3,成功修改内存值为2。
- 这时线程A恢复,执行compareAndSwapInt方法比较,发现自己手里的值(3)和内存的值(2)不一致,说明该值已经被其它线程提前修改过了,那只能重新来一遍了。
- 重新获取value值,因为变量value被volatile修饰,所以其它线程对它的修改,线程A总是能够看到,线程A继续执行compareAndSwapInt进行比较替换,直到成功。
整个过程中,利用CAS保证了对于value的修改的并发安全,继续深入看看Unsafe类中的compareAndSwapInt方法实现。
public final native boolean compareAndSwapInt(Object paramObject, long paramLong, int paramInt1, int paramInt2);
Unsafe类中的compareAndSwapInt,是一个本地方法,该方法的实现位于unsafe.cpp中
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) UnsafeWrapper("Unsafe_CompareAndSwapInt"); oop p = JNIHandles::resolve(obj); jint* addr = (jint *) index_oop_fr