Fork me on GitHub

深入分析CAS

  在JDK 5之前Java语言是靠synchronized关键字保证同步的,这会导致有锁
  锁机制存在以下问题:
  (1)在多线程竞争下,加锁、释放锁会导致比较多的上下文切换和调度延时,引起性能问题。
  (2)一个线程持有锁会导致其它所有需要此锁的线程挂起。
  (3)如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置,引起性能风险。
  volatile是不错的机制,但是volatile不能保证原子性。因此对于同步最终还是要回到锁机制上来。
  独占锁是一种 悲观锁,synchronized就是一种独占锁,会导致其它所有需要锁的线程挂起,等待持有锁的线程释放锁。
  而另一个更加有效的锁就是 乐观锁。所谓乐观锁就是,每次不加锁而是假设没有冲突而去完成某项操作,如果因为冲突失败就重试,直到成功为止。乐观锁用到的机制就是CAS,Compare and Swap。

原理分析

  CAS有3个操作数,内存值V,旧的预期值A,要修改的新值B。当且仅当预期值A和内存值V相同时,将内存值V修改为B,否则什么都不做。
  CAS的目的:利用CPU的CAS指令,同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。而整个J.U.C都是建立在CAS之上的,因此对于synchronized阻塞算法,J.U.C在性能上有了很大的提升。

非阻塞算法
  一个线程的失败或者挂起不应该影响其他线程的失败或挂起的算法。

  现代的CPU提供了特殊的指令,可以自动更新共享数据,而且能够检测到其他线程的干扰,而 compareAndSet() 就用这些代替了锁定。
  分析AtomicInteger在没有锁的情况下是如何做到数据正确性的
  1.首先毫无以为,在没有锁的机制下可能需要借助volatile原语,保证线程间的数据是可见的(共享的)。这样才获取变量的值的时候才能直接读取。

1
2
3
4
5
private volatile int value;
public final int get() {
return value;
}

  然后来看看i++是怎么做到的。

1
2
3
4
5
6
7
8
public final int getAndIncrement() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return current;
}
}

  在这里采用了CAS操作,每次从内存中读取数据然后将此数据和+1后的结果进行CAS操作,如果成功就返回结果,否则重试直到成功为止。
  2.利用compareAndSet利用JNI来完成CPU指令的操作。

1
2
3
4
5
6
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
// Unsafe类的JNI方法
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

  整体的过程就是这样子的,利用CPU的CAS指令,同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。

  3.CAS通过调用JNI的代码实现的。JNI:Java Native Interface为JAVA本地调用,允许java调用其他语言。compareAndSwapInt就是借助C来调用CPU底层指令实现的。
  下面从分析比较常用的CPU(intel x86)来解释CAS的实现原理。
  下面是sun.misc.Unsafe类的compareAndSwapInt()方法的源代码:
  public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);
  可以看到这是个本地方法调用。这个本地方法在openjdk中依次调用的c++代码为:unsafe.cpp,atomic.cpp和atomicwindowsx86.inline.hpp。

关于CPU的锁有如下3种:
  3.1 处理器自动保证基本内存操作的原子性
  首先处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存当中读取或者写入一个字节是原子的,意思是当一个处理器读取一个字节时,其他处理器不能访问这个字节的内存地址。奔腾6和最新的处理器能自动保证单处理器对同一个缓存行里进行16/32/64位的操作是原子的,但是复杂的内存操作处理器不能自动保证其原子性,比如跨总线宽度,跨多个缓存行,跨页表的访问。但是处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性。
  3.2 使用总线锁保证原子性
  第一个机制是通过总线锁保证原子性。如果多个处理器同时对共享变量进行读改写(i++就是经典的读改写操作)操作,那么共享变量就会被多个处理器同时进行操作,这样读改写操作就不是原子的,操作完之后共享变量的值会和期望的不一致,举个例子:如果i=1,我们进行两次i++操作,我们期望的结果是3,但是有可能结果是2。如下图

  原因是有可能多个处理器同时从各自的缓存中读取变量i,分别进行加一操作,然后分别写入系统内存当中。那么想要保证读改写共享变量的操作是原子的,就必须保证CPU1读改写共享变量的时候,CPU2不能操作缓存了该共享变量内存地址的缓存。
  处理器使用总线锁就是来解决这个问题的。所谓总线锁就是使用处理器提供的一个LOCK#信号,当一个处理器在总线上输出此信号时,其他处理器的请求将被阻塞住,那么该处理器可以独占使用共享内存。
  3.3 使用缓存锁保证原子性
  第二个机制是通过缓存锁定保证原子性。在同一时刻我们只需保证对某个内存地址的操作是原子性即可,但总线锁定把CPU和内存之间通信锁住了,这使得锁定期间,其他处理器不能操作其他内存地址的数据,所以总线锁定的开销比较大,最近的处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。
  频繁使用的内存会缓存在处理器的L1,L2和L3高速缓存里,那么原子操作就可以直接在处理器内部缓存中进行,并不需要声明总线锁,在奔腾6和最近的处理器中可以使用“缓存锁定”的方式来实现复杂的原子性。所谓“缓存锁定”就是如果缓存在处理器缓存行中内存区域在LOCK操作期间被锁定,当它执行锁操作回写内存时,处理器不在总线上声言LOCK#信号,而是修改内部的内存地址,并允许它的缓存一致性机制来保证操作的原子性,因为缓存一致性机制会阻止同时修改被两个以上处理器缓存的内存区域数据,当其他处理器回写已被锁定的缓存行的数据时会起缓存行无效,在例1中,当CPU1修改缓存行中的i时使用缓存锁定,那么CPU2就不能同时缓存了i的缓存行。
  但是有两种情况下处理器不会使用缓存锁定。第一种情况是:当操作的数据不能被缓存在处理器内部,或操作的数据跨多个缓存行(cache line),则处理器会调用总线锁定。第二种情况是:有些处理器不支持缓存锁定。对于Inter486和奔腾处理器,就算锁定的内存区域在处理器的缓存行中也会调用总线锁定。
  以上两个机制我们可以通过Inter处理器提供了很多LOCK前缀的指令来实现。比如位测试和修改指令BTS,BTR,BTC,交换指令XADD,CMPXCHG和其他一些操作数和逻辑指令,比如ADD(加),OR(或)等,被这些指令操作的内存区域就会加锁,导致其他处理器不能同时访问它。

CAS存在的问题

  CAS虽然很高效的解决原子操作,但是CAS仍然存在三大问题。
1.ABA问题
  因为CAS需要在操作值的时候检查下值有没有发生变化,如果没有发生变化则更新,但是 如果一个值原来是A,变成了B,又变成了A ,那么使用CAS进行检查时会发现它的值没有发生变化,但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号,每次变量更新的时候把版本号加一,那么A-B-A 就会变成1A-2B-3A。
  从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用,并且当前标志是否等于预期标志,如果全部相等,则以原子方式将该引用和该标志的值设置为给定的更新值。
  关于ABA问题参考文档

2.循环时间长开销大
  自旋CAS如果长时间不成功,会给CPU带来非常大的执行开销。如果JVM能支持处理器提供的pause指令那么效率会有一定的提升,pause指令有两个作用,第一它可以延迟流水线执行指令(de-pipeline),使CPU不会消耗过多的执行资源,延迟的时间取决于具体实现的版本,在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突(memory order violation)而引起CPU流水线被清空(CPU pipeline flush),从而提高CPU的执行效率。

3.只能保证一个共享变量的原子操作
  当对一个共享变量执行操作时,我们可以使用循环CAS的方式来保证原子操作,但是对多个共享变量操作时,循环CAS就无法保证操作的原子性,这个时候就可以用锁,或者有一个取巧的办法,就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i=2,j=a,合并一下ij=2a,然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性,你可以把多个变量放在一个对象里来进行CAS操作。

应用

java.util.concurrent包

  java.util.concurrent包完全建立在CAS之上的,没有CAS就不会有此包。可见CAS的重要性。
  java.util.concurrent包中借助CAS实现了区别于synchronouse同步锁的一种乐观锁。

1.java.util.concurrent.atomic包的实现
  如AtomicInteger类
  由于java的CAS同时具有 volatile 读和volatile写的内存语义,因此Java线程之间的通信现在有了下面四种方式:
   1.A线程写volatile变量,随后B线程读这个volatile变量。
   2.A线程写volatile变量,随后B线程用CAS更新这个volatile变量。
   3.A线程用CAS更新一个volatile变量,随后B线程用CAS更新这个volatile变量。
   4.A线程用CAS更新一个volatile变量,随后B线程读这个volatile变量。
  Java的CAS会使用现代处理器上提供的高效机器级别原子指令,这些原子指令以原子方式对内存执行读-改-写操作,这是在多处理器中实现同步的关键(从本质上来说,能够支持原子性读-改-写指令的计算机器,是顺序计算图灵机的异步等价机器,因此任何现代的多处理器都会去支持某种能对内存执行原子性读-改-写操作的原子指令)。同时,volatile变量的读/写和CAS可以实现线程之间的通信。把这些特性整合在一起,就形成了整个concurrent包得以实现的基石。如果我们仔细分析concurrent包的源代码实现,会发现一个通用化的实现模式:
   1.首先,声明共享变量为volatile;
   2.然后,使用CAS的原子条件更新来实现线程之间的同步;
   3.同时,配合以volatile的读/写和CAS所具有的volatile读和写的内存语义来实现线程之间的通信。
  AQS,非阻塞数据结构和原子变量类(java.util.concurrent.atomic包中的类),这些concurrent包中的基础类都是使用这种模式来实现的,而concurrent包中的高层类又是依赖于这些基础类来实现的。从整体来看,concurrent包的实现示意图如下:

2.跳跃表java.util.concurrent.ConcurrentSkipListMap
  ConcurrentSkipListMap采用典型的空间换取时间策略,它是一个有序的,支持高并发的Map.
  实现原理参见 Java多线程(四)之ConcurrentSkipListMap深入分析
  它对节点的操作都是CAS机制实现的
3.无锁队列java.util.concurrent.ConcurrentLinkedQueue
  实现原理参见 聊聊并发(六)ConcurrentLinkedQueue的实现原理分析

高性能内存队列disruptor中的CAS

  实现原理参考并发编程网 并发框架Disruptor

堆中对象的分配

  我们都知道java调用new object()会创建一个对象,这个对象会被分配到JVM的堆中。那么这个对象到底是怎么在堆中保存的呢?
  首先,new object()执行的时候,这个对象需要多大的空间,其实是已经确定的,因为java中的各种数据类型,占用多大的空间都是固定的(对其原理不清楚的请自行Google)。那么接下来的工作就是在堆中找出那么一块空间用于存放这个对象。
  在单线程的情况下,一般有两种分配策略:
  1.指针碰撞: 适用于内存是绝对规整的(内存是否规整取决于内存回收策略),分配空间的工作只是将指针像空闲内存一侧移动对象大小的距离即可。
  2.空闲列表: 适用于内存非规整的情况,该情况下JVM会维护一个内存列表,记录哪些内存区域是空闲的,大小是多少。给对象分配空间的时候去空闲列表里查询到合适的区域然后进行分配即可

  但是JVM不可能一直在单线程状态下运行,那样效率太差了。由于再给一个对象分配内存的时候不是原子性的操作,至少需要以下几步:查找空闲列表、分配内存、修改空闲列表等等,这是不安全的。解决并发时的安全问题也有两种策略:
  1.CAS: 实际上虚拟机采用CAS配合上失败重试的方式保证更新操作的原子性,原理和上面讲的一样。
  2.TLAB: 如果使用CAS其实对性能还是会有影响的,所以JVM又提出了一种更高级的优化策略:每个线程在Java堆中预先分配一小块内存,称为本地线程分配缓冲区(TLAB),线程内部需要分配内存时直接在TLAB上分配就行,避免了线程冲突。只有当缓冲区的内存用光需要重新分配内存的时候才会进行CAS操作分配更大的内存空间。虚拟机是否使用TLAB,可以通过-XX:+/-UseTLAB参数来进行配置(jdk5及以后的版本默认是启用TLAB的)。


参考文章
  JAVA CAS原理深度分析
  java高并发:CAS无锁原理及广泛应用

-----------------本文结束,感谢您的阅读-----------------