精讲java中的CAS

一、CAS概述

CAS（Compare And Swap）指比较并交换。CAS算法CAS(V, E, N)包含3个参数，V表示要更新的变量，E表示预期的值，N表示新值。在且仅在V值等于 E值时，才会将V值设为 N，如果 V值和 E值不同，则说明已经有其他线程做了更新，当前线程什么都不做。最后，CAS返回当前V的真实值。

二、CAS的特性

CAS操作采用了乐观锁的思想，总是认为自己可以成功完成操作。在有多个线程同时使用CAS操作一个变量时，只有一个会胜出并成功更新，其余均会失败。失败的线程不会被挂起，仅被告知失败，并且允许再次尝试，当然，也允许失败的线程放弃操作。基于这样的原理，CAS操作即使没有锁，也可以发现其他线程对当前线程的干扰，并进行恰当的处理。

三、CAS的自旋等待

在JDK的原子包java.util.concurrent.atomic里面提供了一组原子类，这些原子类的基本特性就是在多线程环境下，在有多个线程同时执行这些类的实例包含的方法时，会有排他性。其内部便是基于CAS算法实现的，即在某个线程进入方法中执行其中的指令时，不会被其他线程打断；而别的线程就像自旋锁一样，一直等到该方法执行完成才由JVM从等待的队列中选择另一个线程进入。

相对于synchronized阻塞算法，CAS是非阻塞算法的一种常见实现。由于CPU的切换比CPU指令集的操作更加耗时，所以CAS的自旋操作在性能上有了很大的提升。JDK具体的实现源码如下：

public  class  AtomicInteger  extends  Number  implements  java.io.Serializable  {

    private  volatile  int  value;

	public  final  int  get()  {

          return  value;

    }

    public  final  int  getAndIncrement()  {

      for (; ; ) {  CAS自旋，一直尝试，直到成功

          int  current  =  get();

          int  next  =  current  +  1;

          if  (compareAndSet(current,  next))

              return  current;

      }

    }

    public  final  boolean  compareAndSet(int  expect,  int  update)  {

      return  unsafe.compareAndSwapInt(this,  valueOffset,  expect,  update);

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

在以上代码中，getAndIncrement采用了CAS操作，每次都从内存中读取数据然后将此数据和加1后的结果进行CAS操作，如果成功，则返回结果，否则重试直到成功为止。

四、源码

// 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); }
    }
/**
     * Atomically sets the value to the given updated value
     * if the current value {@code ==} the expected value.
     *
     * @param expect the expected value
     * @param update the new value
     * @return {@code true} if successful. False return indicates that
     * the actual value was not equal to the expected value.
     */
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 参数1：表示当前对象
• 参数2：表示内存偏移量
• 参数3：表示预期值
• 参数4：表示修改值

五、ABA问题

对CAS算法的实现有一个重要的前提：需要取出内存中某时刻的数据，然后在下一时刻进行比较、替换，在这个时间差内可能数据已经发生了变化，导致产生ABA问题。

ABA问题原因：

• ABA问题指第1个线程从内存的V位置取出A，这时第2个线程也从内存中取出A，并将V位置的数据首先修改为B，接着又将V位置的数据修改为A，这时第1个线程在进行CAS操作时会发现在内存中仍然是A，然后第1个线程操作成功。尽管从第1个线程的角度来说，CAS操作是成功的，但在该过程中其实V位置的数据发生了变化，只是第1个线程没有感知到罢了，这在某些应用场景下可能出现过程数据不一致的问题。
  ABA问题解决方案：
• 部分乐观锁是通过版本号（version）来解决ABA问题的，具体的操作是乐观锁每次在执行数据的修改操作时都会带上一个版本号，在预期的版本号和数据的版本号一致时就可以执行修改操作，并对版本号执行加1操作，否则执行失败。因为每次操作的版本号都会随之增加，所以不会出现ABA问题，因为版本号只会增加，不会减少。（版本号可以用AtomicStampedReference来定义）

---

总结

CAS并发原语体现在JAVA语言中就是sun.misc.Unsafe类中的各个方法。调用UnSafe类中的CAS方法，JVM会帮我们实现出CAS汇编指令。这是一种完全依赖于硬件的功能，通过它实现了原子操作。再次强调，由于CAS是一种系统原语，原语属于操作系统用语范畴，是由若干条指令组成的，用于完成某个功能的一个过程，并且原语的执行必须是连续的，在执行过程中不允许被中断，也就是说CAS是一条CPU的原子指令，不会造成所谓的数据不一致问题。