CAS原理
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