JAVA concurrent 实现基础-CAS

2018-11-21 21:23

JAVA concurrent 实现基础-CAS



  CAS是指的计算机中的一种值替换操作。CAS 操作包含三个操作数-内存地址(V),原来的预期值(A)和需要修改的新值(B)。当且仅当预期值A和内存值V相同时,将内存值V修改为B,否则什么都不做。CAS操作原理图如下:

JAVA concurrent 实现基础-CAS

  在多线程高并发环境中为了保证对象访问的安全性,通常的做法是加锁,将并行化的操作变为串行化。锁住对象访问的资源确实可以保证对象的安全性,但是在实际生产环境中,会大大影响系统的吞吐量。这种策略被称为悲观策略,java 中的 synchronized 就是这种实现方式。

  既然锁的方式会存在性能问题,是否可以用无锁的方式来保证对象访问的安全性呢。无锁策略就使用了比较交换-CAS来判断多个线程访问对象是否会产生冲突,一旦检测冲突,就会不断重试,直到没有冲突为止。

  相对于锁的实现而言,CAS的处理方式更加优雅,得益于其优越的性能优势和天然免疫死锁(没有锁,不会有线程一直阻塞),更为重要的是,使用无锁的方式没有锁竞争带来的开销,也没有线程间频繁调度带来的开销,它比基于锁的方式有更优越的性能,所以在目前被广泛应用。

  下面是unsafe.cpp文件中的源代码 ,该文件位于opnjdk的路径:

  CompareAndSetInt的大致意思为:先获取对象的变量的内存地址,然后再调用atomic的cmpxchg函数:

JAVA concurrent 实现基础-CAS

  其中在atomic.hpp 的cmpxchg函数实现的过程通过do-while循环来实现数据值的更新替换。首先先去获取一次结果值, 如果结果和现在不同,就直接返回,因为有其他人修改了;否则会一直尝试去修改。直到成功。

JAVA concurrent 实现基础-CAS

  上面是CAS的C++实现代码,我们可以看到使用了内存交换指令cmpxchg。那么cmpxchg是如何保证操作原子性的呢。这里就需要引入CPU上的锁机制,这里使用经典的i++来举例:

JAVA concurrent 实现基础-CAS

  在双核CPU的机器上CPU1和CPU2执行i++命令,如果没有内存锁,CPU1和CPU2都可以访问i的内存地址,计算的结果就没法准确预测,i的结果可能是2也可能是3。如果需要得到准确的结果值,就必须对CPU的内存操作加锁。对于内存加锁的方式有两种:

  1、总线锁方式,就是针对内存总线加锁,总线锁的实现就是使用的处理器提供一个LOCK # 信号。当该CPU在访问锁定的内存资源的时候,其他处理器的请求会被阻塞,从而该处理器则独占该内存资源。

  2、缓存锁方式,CPU上会有L1,L2,L3高速缓存来保证内存的频繁使用,而无需和内存总线做大量通信,如果要保证内存数据操作的原子性,在CPU上的高速缓存加锁是一个比在内存总线上面加锁更划算的一种方式。所谓“缓存锁定”就是如果缓存在处理器缓存行中内存区域在LOCK操作期间被锁定,当它执行锁操作回写内存时,处理器不在总线上声言LOCK#信号,而是修改内部的内存地址,并允许它的缓存一致性机制(MESI协议)来保证操作的原子性,因为缓存一致性机制会阻止同时修改被两个以上处理器缓存的内存区域数据,当其他处理器回写已被锁定的缓存行的数据时会起缓存行无效。

  MESI 是指4中状态的首字母。每个Cache line(缓存存储数据的单元。)有4个状态,可用2个bit表示,它们分别是:

JAVA concurrent 实现基础-CAS

JAVA concurrent 实现基础-CAS

  然后开始开始修改数据(这里以CPU1作为说明),CPU1执行i++指令计算后发现需要将i的值改为2,CPU1将i的状态修改为M(修改)并通知缓存了i的CPU2,CPU2将cache2中的i的状态设置为I(无效),然后CPU1修改i的值为2.

JAVA concurrent 实现基础-CAS

  最后CPU2发出数据读取指令。CPU2通知CPU1,CPU1将修改的i值同步到内存总线的时候将i的状态从M(修改)-E(独享)。CPU1同步CPU2中的i,将cache1和同步后的cache2中的i改为S(共享)。

JAVA concurrent 实现基础-CAS

  从上面两种加锁方式可以看出缓存锁方式的实现更加合理,该种实现方式只会锁定CPU自身的高速缓存行,而不会对内存总线加锁,不会阻碍其他CPU和缓存总线的通信。但是如果操作的数据不能被缓存在在CPU的缓存行上或者跨越了多个缓存行,则只能使用总线锁的方式来实现原子性。另外在一部分早期版本的处理器上,即便锁定了缓存行也同时会锁定内存总线。

  CAS操作会检查值是否发生变化,如果原值没有发生变化则更新,但是如果一个值原来是A,然后变成了B,最后又变成了A。如果CAS单纯依赖值执法变化来判断就无法分辨出这种情况。解决的办法和ORACLE数据表的乐观锁的实现机制类似,额外增加版本控制,每次更新值需要同时更新一次版本(累加1),比较的时候不仅需要比较值也需要比较版本,比如1A-2B-3A这种就可以分辨出来值是否发生过变化。这个问题在java 1.5 之后的jdk包提供了AtomicStampedRefrence来解决ABA问题,该类中compareAndSet()会先检查当然对象的引用是否等于预期引用,且当前标志是否等于预期标志,如果都满足,则通过原子操作来实现值的更新。

  这个问题主要是CAS的操作机制导致,自旋CAS如果长时间不成功,会导致CPU的大量执行开销。好在JVM虚拟机对于自旋这种情况有一定干预,会设置自旋次数,当超过该次数,就会将线程挂起,让出CPU资源。

  PS:自旋,就是假设线程可能会在将来一段时间获取到锁,JVM会让需要获取锁的几个线程做空循环,经过多次循环,如果线程获取到锁,则进入到临界区域。如果超过一定次数还是无法获取锁,JVM会将改线程挂起。

  说到自旋就不得不提到自旋锁,自旋锁是SMP架构中一种low-level的同步方式。自旋锁的建立只需要少部分资源;当线程被block的时候,它可以重复检查锁是否被占用,这是一种busy-waiting的模式,自旋锁在等待过程中会一直消耗CPU时间。当线程进入自旋状态的时候,其实并没做实际的操作,它可以是执行几次for循环也可以执行几条空的汇编指令,一直在占着CPU不放,等待获取锁的机会。

JAVA concurrent 实现基础-CAS

  CAS作为底层的原子操作和volatile作为底层的可见性实现,构成了juc包实现多线程并发安全机制基础。juc很多常见的结构底层也来自于它们。组成结构图如下所示: