1、什么是CAS？

CAS：Compare and Swap，即比较再交换。
jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。JDK 5之前Java语言是靠synchronized关键字保证同步的，这是一种独占锁，也是是悲观锁。

2、CAS的作用？

在多线程编程的时候，为了保证多个线程对一个对象可以安全进行访问时,我们需要加同步锁，如synchronized,保证对象的在使用时的正确性，synchronized是一种独占锁，它会导致所有需要此锁的线程挂起，等待锁的释放。
加锁会导致一下问题：

  1. 加多线程竞争下，加锁和释放锁会导致较多的上下文切换，引起性能问题。
  2. 多线程可以导致死锁的问题。
  3. 多线程持有的锁会导致其他需要此锁的线程挂起。

而乐观锁却是不加锁，那不加锁如何确保某一变量的操作没有被其他线程修改过？
这里就需要CAS操作（Compare And Swap）来实现。

3、CAS算法理解

对CAS的理解，CAS是一种无锁算法，CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。
7.3 CAS算法实现原理 - 图1
image.png
CAS比较与交换的伪代码可以表示为：
do{ 备份旧数据； 基于旧数据构造新数据； }while(!CAS( 内存地址，备份的旧数据，新数据 ))
7.3 CAS算法实现原理 - 图3
注：t1，t2线程是同时更新同一变量56的值
因为t1和t2线程都同时去访问同一变量56，所以他们会把主内存的值完全拷贝一份到自己的工作内存空间，所以t1和t2线程的预期值都为56。
假设t1在与t2线程竞争中线程t1能去更新变量的值，而其他线程都失败。（失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次发起尝试）。t1线程去更新变量值改为57，然后写到内存中。此时对于t2来说，内存值变为了57，与预期值56不一致，就操作失败了（想改的值不再是原来的值）。
（上图通俗的解释是：CPU去更新一个值，但如果想改的值不再是原来的值，操作就失败，因为很明显，有其它操作先改变了这个值。）
就是指当两者进行比较时，如果相等，则证明共享数据没有被修改，替换成新值，然后继续往下运行；如果不相等，说明共享数据已经被修改，放弃已经所做的操作，然后重新执行刚才的操作。容易看出 CAS 操作是基于共享数据不会被修改的假设，采用了类似于数据库的commit-retry 的模式。当同步冲突出现的机会很少时，这种假设能带来较大的性能提升。

4、CAS缺点

CAS虽然很高效的解决原子操作，但是CAS仍然存在三大问题。ABA问题，循环时间长开销大和只能保证一个共享变量的原子操作。

3.1、ABA问题

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

  1. public class ABASample {
  2.     static AtomicInteger atomicIntegerMoney = new AtomicInteger(1);
  3.     public static void main(String[] args) throws InterruptedException {
  4.         Thread laoWang = new Thread(new Runnable() {
  5.             @Override
  6.             public void run() {
  7.                 System.out.println("------------------线程1.老王查账户余额------------------");
  8.                 System.out.println(atomicIntegerMoney.get());
  9.                 //停顿模拟老王在存钱时撩妹耽误时间了
  10.                 try {
  11.                     Thread.sleep(3000);
  12.                 } catch (InterruptedException e) {
  13.                     e.printStackTrace();
  14.                 }
  15.                 System.out.println("------------------线程1.老王撩完妹墨墨迹迹地存入1万,老王此时的账户余额------------------");
  16.                 atomicIntegerMoney.getAndIncrement();
  17.                 System.out.println(atomicIntegerMoney.get());
  18.                 System.out.println("------------------线程1.结果是对的,但过程老王并不知道自己的钱被转走过,这就是所谓的ABA问题------------------");
  19.             }
  20.         });
  21.         Thread zhangShan = new Thread(new Runnable() {
  22.             @Override
  23.             public void run() {
  24.                 System.out.println("------------------线程2.张三趁老王撩妹的时间转走老王的1万去炒股了,老王此时的账户余额------------------");
  25.                 atomicIntegerMoney.decrementAndGet();
  26.                 System.out.println(atomicIntegerMoney.get());
  27.                 try {
  28.                     //停顿模拟张三快速炒股赚钱的时间
  29.                     Thread.sleep(1000);
  30.                 } catch (InterruptedException e) {
  31.                     e.printStackTrace();
  32.                 }
  33.                 System.out.println("------------------线程2.张三拿老王的1万炒股赚了1万并往老王的账户转回1万,老王此时的账户余额------------------");
  34.                 atomicIntegerMoney.getAndIncrement();
  35.                 System.out.println(atomicIntegerMoney.get());
  36.             }
  37.         });
  38.         laoWang.start();
  39.         Thread.sleep(1000);
  40.         zhangShan.start();
  41.     }
  42. }

image.png
解决方案
CAS类似于乐观锁，即每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据。因此解决方案也可以跟乐观锁一样：

  • 使用版本号机制，如手动增加版本号字段
  • Java 1.5开始，JDK的Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前的标志是否等于预期标志，如果全部相等，则以原子方式将该应用和该标志的值设置为给定的更新值。

如下面的代码：

  1. public class ABASample2 {
  2.     private static AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(1, 0);
  3.     public static void main(String[] args) throws InterruptedException {
  4.         Thread laoWang = new Thread(new Runnable() {
  5.             @SneakyThrows
  6.             @Override
  7.             public void run() {
  8.                 int cur_stamp = atomicStampedReference.getStamp();
  9.                 int new_stamp = cur_stamp+1;
  10.                 System.out.println("------------------"+Thread.currentThread().getName()+".老王查账户的余额-------------------");
  11.                 System.out.println(atomicStampedReference.getReference());
  12.                 Thread.sleep(3000);
  13.                 boolean addResult = atomicStampedReference.compareAndSet(1,2,cur_stamp,new_stamp);
  14.                 if(addResult){
  15.                     System.out.println("------------------"+Thread.currentThread().getName()+".老王存钱成功,账户的余额-------------------");
  16.                 }else{
  17.                     System.out.println("------------------"+Thread.currentThread().getName()+".老王存钱失败,账户的余额-------------------");
  18.                 }
  19.                 System.out.println(atomicStampedReference.getReference());
  20.                 System.out.println("------------------"+Thread.currentThread().getName()+".所以通过AtomicStampedReference的stamp可以解决ABA的问题-------------------");
  21.             }
  22.         },"线程1");
  23.         Thread zhangShan = new Thread(new Runnable() {
  24.             @SneakyThrows
  25.             @Override
  26.             public void run() {
  27.                 int cur_stamp = atomicStampedReference.getStamp();
  28.                 int new_stamp = cur_stamp+1;
  30.                 System.out.println("------------------"+Thread.currentThread().getName()+".张三趁老王撩妹的时间转走老王的1万去炒股了,老王此时的账户余额------------------");
  31.                 atomicStampedReference.compareAndSet(1,0,cur_stamp,new_stamp);
  32.                 System.out.println(atomicStampedReference.getReference());
  33.                 Thread.sleep(1000);
  34.                 System.out.println("------------------"+Thread.currentThread().getName()+".张三拿老王的1万炒股赚了1万并往老王的账户转回1万,老王此时的账户余额------------------");
  35.                 cur_stamp = atomicStampedReference.getStamp();
  36.                 new_stamp = cur_stamp+1;
  37.                 atomicStampedReference.compareAndSet(0,1,cur_stamp,new_stamp);
  38.                 System.out.println(atomicStampedReference.getReference());
  39.             }
  40.         },"线程2");
  41.         laoWang.start();
  42.         Thread.sleep(1000);
  43.         zhangShan.start();
  44.     }
  45. }

image.png
当然，我们一般只关心结果，不关心过程，所以我们一般情况下用AtomicReference就可以了，如果特定场景下一定要关心过程是否有变化的话那就要用AtomicStampedReference了。

3.2、循环时间长开销大

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

  • 破坏掉for死循环，当超过一定时间或者一定次数时，return退出。JDK8新增的LongAddr,和ConcurrentHashMap类似的方法。当多个线程竞争时，将粒度变小，将一个变量拆分为多个变量，达到多个线程访问多个资源的效果，最后再调用sum把它合起来。

  • 如果JVM能支持处理器提供的pause指令，那么效率会有一定的提升。pause指令有两个作用：第一，它可以延迟流水线执行指令（de-pipeline），使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零；第二，它可以避免在循环的时候因内存顺序冲突（Memory Order Violation）而引起CPU流水线被清空，从而提高CPU的实行效率。

    3.3、只能保证一个共享变量的原子操作

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

  • 用锁

  • 把多个共享变量合并成一个共享变量来操作。比如，有两个共享变量i=2,j=a,合并一下ji=2a,然后用CAS来操作ij。
  • 封装成对象。注：从Java 1.5开始，JDK提供了AtomicReference类来保证引用对象之前的原子性，可以把多个变量放在一个对象里来进行CAS操作。

    3.4、比较花费CPU资源，即使没有任何争用也会做一些无用功。

    3.5、会增加程序测试的复杂度，稍不注意就会出现问题。

    5、CAS算法在JDK中的应用

    在原子类变量中，如java.util.concurrent.atomic中的AtomicXXX，都使用了这些底层的JVM支持为数字类型的引用类型提供一种高效的CAS操作，而在java.util.concurrent中的大多数类在实现时都直接或间接的使用了这些原子变量类。
    Java 1.7中AtomicInteger.incrementAndGet()的实现源码为：
    7.3 CAS算法实现原理 - 图6
    7.3 CAS算法实现原理 - 图7
    由此可见，AtomicInteger.incrementAndGet的实现用了乐观锁技术，调用了类sun.misc.Unsafe库里面的 CAS算法，用CPU指令来实现无锁自增。所以，AtomicInteger.incrementAndGet的自增比用synchronized的锁效率倍增。