CAS原理

1 CAS初认识

Synchronized是通过对象内部的一个叫做监视器锁（monitor）来实现的，监视器锁本质又是依赖于底层的操作系统的Mutex Lock（互斥锁）来实现的。而操作系统实现线程之间的切换需要从用户态转换到核心态，这个成本非常高，状态之间的转换需要相对比较长的时间，这就是为什么Synchronized效率低的原因。因此，这种依赖于操作系统Mutex Lock所实现的锁我们称之为“重量级锁”。

而CAS是在硬件层面保证了比较并交换操作的原子性

CAS(Compare And Swap)，即比较并交换。是解决多线程并行情况下使用锁造成性能损耗的一种机制，CAS操作包含三个操作数——内存位置(V)、预期原值(A)和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。无论哪种情况，它都会在CAS指令之前返回该位置的值。CAS有效地说明了“我认为位置V应该包含值A；如果包含该值，则将B放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。
在JAVA中，sun.misc.Unsafe 类提供了硬件级别的原子操作来实现这个CAS。 java.util.concurrent 包下的大量类都使用了这个 Unsafe.java 类的CAS操作。

CAS的全称为Compare-And-Swap ,它是一条CPU并发原语。它的功能是判断内存某个位置的值是否为预期值,如果是则更新为新的值,这个过程是原子的。

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

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。 如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该位置的值。

2 CAS的目的

利用CPU的CAS指令，同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。而整个J.U.C都是建立在CAS之上的，因此相比synchronized阻塞算法，J.U.C在性能上有了很大的提升。

3 CAS存在的问题

问题描述：当你获得对象当前数据后，在准备修改为新值前，对象的值被其他线程连续修改了两次，而经过两次修改后，对象的值又恢复为旧值，这样当前线程无法正确判断这个对象是否修改过。
解决办法：JDK1.5可以利用AtomicStampedReference类来解决这个问题，AtomicStampedReference内部不仅维护了对象值，还维护了一个时间戳。当AtomicStampedReference对应的数值被修改时，除了更新数据本身外，还必须要更新时间戳，对象值和时间戳都必须满足期望值，写入才会成功

在Java中，AtomicStampedReference也实现了这个作用，它通过包装[E,Integer]的元组来对对象标记版本戳stamp，从而避免ABA问题，例如下面的代码分别用AtomicInteger和AtomicStampedReference来对初始值为100的原子整型变量进行更新，AtomicInteger会成功执行CAS操作，而加上版本戳的AtomicStampedReference对于ABA问题会执行CAS失败。

public class AtomicStampedReferenceDemo {
    private static AtomicStampedReference atomicStampedReference = new AtomicStampedReference(100, 1);

    public static void main(String[] args) throws InterruptedException {

        Thread thread1 = new Thread(new Runnable() {
            @Override
            public void run() {
            int stamp = atomicStampedReference.getStamp();

            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            atomicStampedReference.compareAndSet(100, 110, stamp, stamp + 1);
            atomicStampedReference.compareAndSet(110, 100, stamp, stamp + 1);
            }
        });


        Thread thread2 = new Thread(new Runnable() {
            @Override
            public void run() {
            int stamp = atomicStampedReference.getStamp();

            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("AtomicStampedReference compareAndSet : " + atomicStampedReference.compareAndSet(100, 120, stamp, stamp + 1));
            }
        });

        thread1.start();
        thread2.start();

        thread1.join();
        thread2.join();
    }
}

这里，阅读下 AtomicStampedReference 类的源码。其中，compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) 方法有四个参数，分别表示：预期引用，更新后的引用，预期标志，更新后的标志。它的作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

4 底层原理

想要弄清楚其底层原理，深入到源码是最好的方式，在上面我们已经通过源码看到了其实就是Usafe的方法来完成的，在这个方法中使用了compareAndSwapInt这个CAS机制。因此，现在我们有必要进一步深入进去看看：

我们可以看到这里面主要有四个参数，第一个参数就是我们操作的对象a，第二个参数是对象a的地址偏移量，第三个参数表示我们期待这个a是什么值，第四个参数表示的是a的实际值。

不过这里我们会发现这个compareAndSwapInt是一个native方法，也就是说再往下走就是C语言代码，如果我们保持好奇心，可以继续深入进去看看。

上面的代码我们解读一下：首先使用jint计算了value的地址，然后根据这个地址，使用了Atomic的cmpxchg方法进行比较交换。现在问题又抛给了这个cmpxchg，真实实现的是这个函数。我们再进一步深入看看，真相已经离我们不远了。

皮球又一次被完美的踢走了，现在在不同的操作系统下会调用不同的cmpxchg重载函数，我现在用的是win10系统，所以我们看看这个平台下的实现，别着急再往下走走：

这块的代码就有点涉及到汇编指令相关的代码了，到这一步就彻底接近真相了，首先三个move指令表示的是将后面的值移动到前面的寄存器上。然后调用了LOCK_IF_MP和下面cmpxchg汇编指令进行了比较交换。现在我们不知道这个LOCK_IF_MP和cmpxchg是如何交换的，没关系我们最后再深入一下。

最终是由操作系统的汇编指令完成的。

windows_x86底层实现
hotspot\src\os_cpu\windows_x86\vmatomic_linux_x86.inline.hpp
inline jint   Atomic::cmpxchg  (jint   exchange_value, volatile jint*   dest, jint   compare_value) {
 // alternative for InterlockedCompareExchange
 int mp = os::is_MP();
 __asm {
  mov edx, dest
  mov ecx, exchange_value
  mov eax, compare_value
  LOCK_IF_MP(mp)
  cmpxchg dword ptr [edx], ecx
 }
}

Atomic 原子类

对于这种的count++类的操作，我们完全可以换一种做法，java并发包下面提供了一系列的Atomic原子类，比如说AtomicInteger

多个线程可以并发的执行 AtomicInteger 的 incrementAndGet() 方法，意思就是给我把count的值累加1，接着返回累加后最新的值。实际上，Atomic原子类底层用的不是传统意义的锁机制，而是无锁化的CAS机制，通过CAS机制保证多线程修改一个数值的安全性。

假如说有3个线程并发的要修改一个AtomicInteger的值，他们底层的机制如下：

首先，每个线程都会先获取当前的值。接着走一个原子的CAS操作，原子的意思就是这个CAS操作一定是自己完整执行完的，不会被别人打断。
然后CAS操作里，会比较一下，现在你的值是不是刚才我获取到的那个值。如果是，说明没人改过这个值，那你给我设置成累加1之后的一个值。
同理，如果有人在执行CAS的时候，发现自己之前获取的值跟当前的值不一样，会导致CAS失败，失败之后，进入一个无限循环，再次获取值，接着执行CAS操作。

CAS性能优化
从上面的流程图其实可以看出来，比如说大量的线程同时并发修改一个 AtomicInteger，可能有很多线程会不停的自旋，进入一个无限重复的循环中。
这些线程不停地获取值，然后发起CAS操作，但是发现这个值被别人改过了，于是再次进入下一个循环，获取值，发起CAS操作又失败了，再次进入下一个循环。
在大量线程高并发更新 AtomicInteger 的时候，这种问题可能会比较明显，导致大量线程空循环，自旋转，性能和效率都不是特别好。那么如何优化呢？

Java 8有一个新的类，LongAdder，他就是尝试使用分段CAS以及自动分段迁移的方式来大幅度提升多线程高并发执行CAS操作的性能，这个类具体是如何优化性能的呢？如图：

LongAdder核心思想就是热点分离，这一点和ConcurrentHashMap的设计思想相似。
就是将value值分离成一个数组，当多线程访问时，通过hash算法映射到其中的一个数字进行计数。
而最终的结果，就是这些数组的求和累加。这样一来，就减小了锁的粒度。

参考链接

http://blog.sina.com.cn/s/blog_73b4b91f0102y53t.html

https://zhuanlan.zhihu.com/p/44871583

https://blog.csdn.net/lixinkuan328/article/details/94319775

https://baijiahao.baidu.com/s?id=1647620168550407271&wfr=spider&for=pc