CAS原理

CAS介绍

Cas的全拼是 Compare and Swap ，翻译过来是比较和交换，这是一种思想、一种算法，也被称之为无锁更新。

Cas是一种非常常见的算法，也是面试中的常客，同时也是原子类和乐观锁的底层原理。

在多线程的情况下，访问一个共享资源是线程不安全的，通常我们会使用互斥锁，即一个时刻只能有一个线程访问共享资源。但是，互斥锁由于需要CPU切换上下文线程，进而导致性能低下。

而CAS另辟蹊径，没有通过互斥锁，而是当多个线程同时使用CAS算法去更新共享资源时，只会有一个线程能够成功更新，而其他线程都会更新失败，不过与互斥锁不同的是，更新失败的线程并不会阻塞，而是告知此次操作竞争失败，但是还可以再次尝试。

就比如，sql中的条件更新一样：update set id=3 from table where id=2。因为单条sql执行具有原子性，如果有多个线程同时执行此sql语句，只有一条能更新成功。

CAS的思路

在大多数的处理器中，都会实现CAS相关的指令，这一条指令就能够实现比较和交换的操作。

也正是由于这一条CPU指令，所以CAS相关的操作是具备原子性的，这个操作再执行期间不会被打算，这样能够保证并发的安全性。而这个原子性是由CPU进行提供，在使用时无需程序猿来操心。

CAS有三个操作数，内存值V，预期值A，要修改的值B。

处理逻辑是，当预期值和内存值相同时，才会将内存值修改为B。在执行CAS的时候，如果内存中的V正好等于传入的A，则会把V的值修改成B；如果内存中的V和传入的A不相等，则说明A的值已经被其他线程修改过，那么本次的CAS修改失败。

JDK中大量使用了CAS来更新数据而防止加锁(synchronized 重量级锁)来保持原子更新。

使用示例

如果不使用CAS，在高并发下，多线程同时修改一个变量的值我们需要synchronized加锁(可能有人说可以用Lock加锁，Lock底层的AQS也是基于CAS进行获取锁的)。

public class Test {
    private int i=0;
    public synchronized int add(){
        return i++;
    }
}
    

java中为我们提供了AtomicInteger 原子类(底层基于CAS进行更新数据的)，不需要加锁就在多线程并发场景下实现数据的一致性。

public class Test {
    private  AtomicInteger i = new AtomicInteger(0);
    public int add(){
        return i.addAndGet(1);
    }
}    

CAS的问题

ABA问题

有一种情况，原本的值是A变成了B然后又变成了A，CAS在检查这种情况的时候，会认为值没有发送变化，实际上是已经发生了变化。

ABA解决的方案就是每次更新就加上版本号,1A->2B-3A。

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

循环时间长开销大

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

如果JVM能支持处理器提供的pause指令，那么效率会有一定的提升。

pause指令有两个作用：

• 第一，它可以延迟流水线执行命令(de-pipeline)，使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零；
• 第二，它可以避免在退出循环的时候因内存顺序冲突(Memory Order Violation)而引起CPU流水线被清空(CPU Pipeline Flush)，从而提高CPU的执行效率。

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

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

还有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如，有两个共享变量i = 2，j = a，合并一下ij = 2a，然后用CAS来操作ij。

从Java 1.5开始，JDK提供了AtomicReference类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行CAS操作。