网站建设电销,手表网站欧米茄报价,响应式WordPress企业主题,模板式自助建站转载自 面试必问的 CAS #xff0c;要多了解前言
CAS#xff08;Compare and Swap#xff09;#xff0c;即比较并替换#xff0c;实现并发算法时常用到的一种技术#xff0c;Doug lea大神在java同步器中大量使用了CAS技术#xff0c;鬼斧神工的实现了多线程执行的安全性…转载自 面试必问的 CAS 要多了解前言
CASCompare and Swap即比较并替换实现并发算法时常用到的一种技术Doug lea大神在java同步器中大量使用了CAS技术鬼斧神工的实现了多线程执行的安全性。
CAS的思想很简单三个参数一个当前内存值V、旧的预期值A、即将更新的值B当且仅当预期值A和内存值V相同时将内存值修改为B并返回true否则什么都不做并返回false。
问题
一个n的问题。
12345678publicclass Case { publicvolatile int n; publicvoid add() { n; }}通过javap -verbose Case看看add方法的字节码指令
1234567891011publicvoid add(); flags: ACC_PUBLIC Code: stack3, locals1, args_size1 0: aload_0 1: dup 2: getfield #2 // Field n:I 5: iconst_1 6: iadd 7: putfield #2 // Field n:I 10:returnn被拆分成了几个指令
执行getfield拿到原始n执行iadd进行加1操作执行putfield写把累加后的值写回n
通过volatile修饰的变量可以保证线程之间的可见性但并不能保证这3个指令的原子执行在多线程并发执行下无法做到线程安全得到正确的结果那么应该如何解决呢
如何解决
在add方法加上synchronized修饰解决。
12345678publicclass Case { publicvolatile int n; publicsynchronized void add() { n; }}这个方案当然可行但是性能上差了点还有其它方案么
再来看一段代码
12345678publicint a 1;publicboolean compareAndSwapInt(intb) { if(a 1) { a b; returntrue; } returnfalse;}如果这段代码在并发下执行会发生什么
假设线程1和线程2都过了a1的检测都准备执行对a进行赋值结果就是两个线程同时修改了变量a显然这种结果是无法符合预期的无法确定a的最终值。
解决方法也同样暴力在compareAndSwapInt方法加锁同步变成一个原子操作同一时刻只有一个线程才能修改变量a。
除了低性能的加锁方案我们还可以使用JDK自带的CAS方案在CAS中比较和替换是一组原子操作不会被外部打断且在性能上更占有优势。
下面以AtomicInteger的实现为例分析一下CAS是如何实现的。
123456789101112131415publicclass AtomicInteger extendsNumber implementsjava.io.Serializable { // setup to use Unsafe.compareAndSwapInt for updates privatestatic final Unsafe unsafe Unsafe.getUnsafe(); privatestatic final long valueOffset; static{ try{ valueOffset unsafe.objectFieldOffset (AtomicInteger.class.getDeclaredField(value)); }catch(Exception ex) { thrownew Error(ex); } } privatevolatile int value; publicfinal int get() {returnvalue;}}Unsafe是CAS的核心类由于Java方法无法直接访问底层系统需要通过本地native方法来访问Unsafe相当于一个后门基于该类可以直接操作特定内存的数据。变量valueOffset表示该变量值在内存中的偏移地址因为Unsafe就是根据内存偏移地址获取数据的。变量value用volatile修饰保证了多线程之间的内存可见性。
看看AtomicInteger如何实现并发下的累加操作
123456789101112publicfinal int getAndAdd(intdelta) { returnunsafe.getAndAddInt(this, valueOffset, delta);}//unsafe.getAndAddIntpublicfinal int getAndAddInt(Object var1, longvar2, intvar4) { intvar5; do{ var5 this.getIntVolatile(var1, var2); }while(!this.compareAndSwapInt(var1, var2, var5, var5 var4)); returnvar5;}假设线程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方法实现。
1publicfinal native boolean compareAndSwapInt(Object paramObject, longparamLong, intparamInt1, intparamInt2);Unsafe类中的compareAndSwapInt是一个本地方法该方法的实现位于unsafe.cpp中
123456UNSAFE_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_from_field_offset_long(p, offset); return(jint)(Atomic::cmpxchg(x, addr, e)) e;UNSAFE_END先想办法拿到变量value在内存中的地址。通过Atomic::cmpxchg实现比较替换其中参数x是即将更新的值参数e是原内存的值。
如果是Linux的x86Atomic::cmpxchg方法的实现如下
12345678inline jint Atomic::cmpxchg (jint exchange_value, volatilejint* dest, jint compare_value) { intmp os::is_MP(); __asm__volatile(LOCK_IF_MP(%4)cmpxchgl %1,(%3) :a(exchange_value) :r(exchange_value), a(compare_value), r(dest), r(mp) :cc,memory); returnexchange_value;}看到这汇编内心崩溃
__asm__表示汇编的开始volatile表示禁止编译器优化LOCK_IF_MP是个内联函数
1#define LOCK_IF_MP(mp) cmp $0, #mp ; je 1f; lock; 1: Window的x86实现如下
12345678910111213141516171819inline jint Atomic::cmpxchg (jint exchange_value, volatilejint* dest, jint compare_value) { intmp os::isMP(); //判断是否是多处理器 _asm { mov edx, dest mov ecx, exchange_value mov eax, compare_value LOCK_IF_MP(mp) cmpxchg dword ptr [edx], ecx }}// Adding a lock prefix to an instruction on MP machine// VC doesnt like the lock prefix to be on a single line// so we cant insert a label after the lock prefix.// By emitting a lock prefix, we can define a label after it.#define LOCK_IF_MP(mp) __asm cmp mp, 0 \ __asm je L0 \ __asm _emit 0xF0\ __asm L0:LOCK_IF_MP根据当前系统是否为多核处理器决定是否为cmpxchg指令添加lock前缀。
如果是多处理器为cmpxchg指令添加lock前缀。反之就省略lock前缀。单处理器会不需要lock前缀提供的内存屏障效果
intel手册对lock前缀的说明如下
确保后续指令执行的原子性。在Pentium及之前的处理器中带有lock前缀的指令在执行期间会锁住总线使得其它处理器暂时无法通过总线访问内存很显然这个开销很大。在新的处理器中Intel使用缓存锁定来保证指令执行的原子性缓存锁定将大大降低lock前缀指令的执行开销。禁止该指令与前面和后面的读写指令重排序。把写缓冲区的所有数据刷新到内存中。
上面的第2点和第3点所具有的内存屏障效果保证了CAS同时具有volatile读和volatile写的内存语义。
CAS缺点
CAS存在一个很明显的问题即ABA问题。
问题如果变量V初次读取的时候是A并且在准备赋值的时候检查到它仍然是A那能说明它的值没有被其他线程修改过了吗
如果在这段期间曾经被改成B然后又改回A那CAS操作就会误认为它从来没有被修改过。针对这种情况java并发包中提供了一个带有标记的原子引用类AtomicStampedReference它可以通过控制变量值的版本来保证CAS的正确性。
