CAS机制

一、为什么需要CAS机制？

为什么需要CAS机制呢？我们先从一个错误现象谈起。我们经常使用volatile关键字修饰某一个变量，表明这个变量是全局共享的一个变量，同时具有了可见性和有序性。但是却没有原子性。比如说一个常见的操作a++。这个操作其实可以细分成三个步骤：

（1）从内存中读取a
（2）对a进行加1操作
（3）将a的值重新写入内存中

在单线程状态下这个操作没有一点问题，但是在多线程中就会出现各种各样的问题了。因为可能一个线程对a进行了加1操作，还没来得及写入内存，其他的线程就读取了旧值。造成了线程的不安全现象。如何去解决这个问题呢？最常见的方式就是使用AtomicInteger来修饰a。我们可以看一下代码：

public class Test3 {
    static AtomicInteger a = new AtomicInteger();

    public static void main(String[] args) {
        Test3 test3 = new Test3();
        Thread[] threads = new Thread[5];
        for (int i = 0; i < 5; i++) {
            threads[i] = new Thread(() -> {
                try {
                    for (int j = 0; j < 10; j++) {
                        System.out.println(a.incrementAndGet());

                        Thread.sleep(500);

                    }
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
            threads[i].start();
        }
    }
}

现在我们使用AtomicInteger类并且调用了incrementAndGet方法来对a进行自增操作。这个incrementAndGet是如何实现的呢？我们可以看一下AtomicInteger的源码。

 /**
     * Atomically increments by one the current value.
     * @return the updated value
     */
    public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
    }

public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
    }

底层调用的是compareAndSwapInt方法，这个compareAndSwapInt方法其实就是CAS机制。因此如果我们想搞清楚AtomicInteger的原子操作是如何实现的，我们就必须要把CAS机制搞清楚，这也是为什么我们需要掌握CAS机制的原因。

二、CAS算法理解

1、基本含义
CAS全拼又叫做compareAndSwap，从名字上的意思就知道是比较交换的意思。比较交换什么呢？
过程是这样：它包含 3 个参数 CAS（V，E，N），V表示要更新变量的值，E表示预期值，N表示新值。仅当 V值等于E值时，才会将V的值设为N，如果V值和E值不同，则说明已经有其他线程做两个更新，则当前线程则什么都不做。最后，CAS 返回当前V的真实值。
CAS 操作时抱着乐观的态度进行的，它总是认为自己可以成功完成操作。所以CAS也叫作乐观锁，那什么是悲观锁呢？悲观锁就是我们之前赫赫有名的synchronized。悲观锁的思想你可以这样理解，一个线程想要去获得这个锁但是却获取不到，必须要别人释放了才可以。

2、底层原理

image.png

CAS比较与交换的伪代码可以表示为：

do{

备份旧数据；

基于旧数据构造新数据；

}while(!CAS( 内存地址，备份的旧数据，新数据 ))

image.png

注：t1，t2线程是同时更新同一变量56的值

因为t1和t2线程都同时去访问同一变量56，所以他们会把主内存的值完全拷贝一份到自己的工作内存空间，所以t1和t2线程的预期值都为56。

假设t1在与t2线程竞争中线程t1能去更新变量的值，而其他线程都失败。（失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次发起尝试）。t1线程去更新变量值改为57，然后写到内存中。此时对于t2来说，内存值变为了57，与预期值56不一致，就操作失败了（想改的值不再是原来的值）。

（上图通俗的解释是：CPU去更新一个值，但如果想改的值不再是原来的值，操作就失败，因为很明显，有其它操作先改变了这个值。）

就是指当两者进行比较时，如果相等，则证明共享数据没有被修改，替换成新值，然后继续往下运行；如果不相等，说明共享数据已经被修改，放弃已经所做的操作，然后重新执行刚才的操作。容易看出 CAS 操作是基于共享数据不会被修改的假设，采用了类似于数据库的commit-retry 的模式。当同步冲突出现的机会很少时，这种假设能带来较大的性能提升。

3、CAS机制的优缺点
（1）优点
一开始在文中我们曾经提到过，cas是一种乐观锁，而且是一种非阻塞的轻量级的乐观锁，什么是非阻塞式的呢？其实就是一个线程想要获得锁，对方会给一个回应表示这个锁能不能获得。在资源竞争不激烈的情况下性能高，相比synchronized重量锁，synchronized会进行比较复杂的加锁，解锁和唤醒操作。

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

ABA问题

因为CAS需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。

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

• 使用版本号机制，如手动增加版本号字段

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

循环时间长开销大

自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。

解决方案：

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

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

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

当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性
解决方案：

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