• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

面试必问的CAS,了解多少?

技术杂谈 勤劳的小蚂蚁 3个月前 (01-21) 90次浏览 已收录 0个评论 扫描二维码

前言

CAS(Compare and Swap),即比较并替换,实现并发算法时常用到的一种技术,Doug lea大神在java同步器中大量使用了CAS技术,鬼斧神工的实现了多线程执行的安全性。
CAS的思想很简单:三个参数,一个当前内存值V、旧的预期值A、即将更新的值B,当且仅当预期值A和内存值V相同时,将内存值修改为B并返回true,否则什么都不做,并返回false。

问题

一个n++的问题。
  1. publicclassCase {

  2.    publicvolatileint n;

  3.    publicvoid add() {
  4.        n++;
  5.    }
  6. }
通过javap -verbose Case看看add方法的字节码指令
  1. publicvoid add();
  2.    flags: ACC_PUBLIC
  3.    Code:
  4.      stack=3, locals=1, args_size=1
  5.         0: aload_0      
  6.         1: dup          
  7.         2: getfield      #2                  // Field n:I
  8.         5: iconst_1      
  9.         6: iadd          
  10.         7: putfield      #2                  // Field n:I
  11.        10: return
n++被拆分成了几个指令:
  • 执行getfield拿到原始n;
  • 执行iadd进行加1操作;
  • 执行putfield写把累加后的值写回n;
通过volatile修饰的变量可以保证线程之间的可见性,但并不能保证这3个指令的原子执行,在多线程并发执行下,无法做到线程安全,得到正确的结果,那么应该如何解决呢?

如何解决

在add方法加上synchronized修饰解决。
  1. publicclassCase {

  2.    publicvolatileint n;

  3.    publicsynchronizedvoid add() {
  4.        n++;
  5.    }
  6. }
这个方案当然可行,但是性能上差了点,还有其它方案么?
再来看一段代码
  1. publicint a = 1;
  2. publicboolean compareAndSwapInt(int b) {
  3.    if (a == 1) {
  4.        a = b;
  5.        returntrue;
  6.    }
  7.    return f
如果这段代码在并发下执行,会发生什么?
假设线程1和线程2都过了a==1的检测,都准备执行对a进行赋值,结果就是两个线程同时修改了变量a,显然这种结果是无法符合预期的,无法确定a的最终值。
解决方法也同样暴力,在compareAndSwapInt方法加锁同步,变成一个原子操作,同一时刻只有一个线程才能修改变量a。
除了低性能的加锁方案,我们还可以使用JDK自带的CAS方案,在CAS中,比较和替换是一组原子操作,不会被外部打断,且在性能上更占有优势。
下面以AtomicInteger的实现为例,分析一下CAS是如何实现的。
  1. publicclassAtomicIntegerextendsNumberimplements java.io.Serializable {
  2.    // setup to use Unsafe.compareAndSwapInt for updates
  3.    privatestaticfinalUnsafe unsafe = Unsafe.getUnsafe();
  4.    privatestaticfinallong valueOffset;

  5.    static {
  6.        try {
  7.            valueOffset = unsafe.objectFieldOffset
  8.                (AtomicInteger.class.getDeclaredField("value"));
  9.        } catch (Exception ex) { thrownewError(ex); }
  10.    }

  11.    privatevolatileint value;
  12.    publicfinalint get() {return value;}
  13. }
  1. Unsafe,是CAS的核心类,由于Java方法无法直接访问底层系统,需要通过本地(native)方法来访问,Unsafe相当于一个后门,基于该类可以直接操作特定内存的数据。
  2. 变量valueOffset,表示该变量值在内存中的偏移地址,因为Unsafe就是根据内存偏移地址获取数据的。
  3. 变量value用volatile修饰,保证了多线程之间的内存可见性。 看看AtomicInteger如何实现并发下的累加操作:
  1. publicfinalint getAndAdd(int delta) {    
  2.    return unsafe.getAndAddInt(this, valueOffset, delta);
  3. }

  4. //unsafe.getAndAddInt
  5. publicfinalint getAndAddInt(Object var1, long var2, int var4) {
  6.    int var5;
  7.    do {
  8.        var5 = this.getIntVolatile(var1, var2);
  9.    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
  10.    return var5;
  11. }
假设线程A和线程B同时执行getAndAdd操作(分别跑在不同CPU上):
  1. AtomicInteger里面的value原始值为3,即主内存中AtomicInteger的value为3,根据Java内存模型,线程A和线程B各自持有一份value的副本,值为3。
  2. 线程A通过getIntVolatile(var1, var2)拿到value值3,这时线程A被挂起。
  3. 线程B也通过getIntVolatile(var1, var2)方法获取到value值3,运气好,线程B没有被挂起,并执行compareAndSwapInt方法比较内存值也为3,成功修改内存值为2。
  4. 这时线程A恢复,执行compareAndSwapInt方法比较,发现自己手里的值(3)和内存的值(2)不一致,说明该值已经被其它线程提前修改过了,那只能重新来一遍了。
  5. 重新获取value值,因为变量value被volatile修饰,所以其它线程对它的修改,线程A总是能够看到,线程A继续执行compareAndSwapInt进行比较替换,直到成功。
整个过程中,利用CAS保证了对于value的修改的并发安全,继续深入看看Unsafe类中的compareAndSwapInt方法实现。
  1. publicfinalnativeboolean compareAndSwapInt(Object paramObject, long paramLong, int paramInt1, int paramInt2);
Unsafe类中的compareAndSwapInt,是一个本地方法,该方法的实现位于unsafe.cpp中
  1. UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  2.  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  3.  oop p = JNIHandles::resolve(obj);
  4.  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  5.  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
  6. UNSAFE_END
  1. 先想办法拿到变量value在内存中的地址。
  2. 通过Atomic::cmpxchg实现比较替换,其中参数x是即将更新的值,参数e是原内存的值。
如果是Linux的x86,Atomic::cmpxchg方法的实现如下:
  1. inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  2.  int mp = os::is_MP();
  3.  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
  4.                    : "=a" (exchange_value)
  5.                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
  6.                    : "cc", "memory");
  7.  return exchange_value;
  8. }
看到这汇编,内心崩溃
__asm__ 表示汇编的开始 volatile 表示禁止编译器优化 LOCKIFMP 是个内联函数
  1. #define LOCK_IF_MP(mp) "cmp $0, "#mp "; je 1f; lock; 1: "
Window的x86实现如下:
  1. inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  2.    int mp = os::isMP(); //判断是否是多处理器
  3.    _asm {
  4.        mov edx, dest
  5.        mov ecx, exchange_value
  6.        mov eax, compare_value
  7.        LOCK_IF_MP(mp)
  8.        cmpxchg dword ptr [edx], ecx
  9.    }
  10. }

  11. // Adding a lock prefix to an instruction on MP machine
  12. // VC++ doesn't like the lock prefix to be on a single line
  13. // so we can't insert a label after the lock prefix.
  14. // By emitting a lock prefix, we can define a label after it.
  15. #define LOCK_IF_MP(mp) __asm cmp mp, 0  
  16.                       __asm je L0      
  17.                       __asm _emit 0xF0
  18.                       __asm L0:
LOCKIFMP根据当前系统是否为多核处理器决定是否为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的正确性。

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:面试必问的CAS,了解多少?
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00