【并发基础】CAS（Compare And Swap）操作的底层原理以及应用详解
目录
一、锁机制存在的问题
在JDK 5之前Java语言是靠synchronized关键字保证同步的，这会导致有锁
锁机制存在以下问题：
（1）在多线程竞争下，加锁、释放锁会导致比较多的上下文切换和调度延时，引起性能问题。
（2）一个线程持有锁会导致其它所有需要此锁的线程挂起。
（3）如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置，引起性能风险。
volatile是不错的机制，它是通过汇编语言中的LOCK指令实现的，但是volatile不能保证原子性。因此对于同步最终还是要回到锁机制上来。
独占锁是一种悲观锁，synchronized就是一种独占锁，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。
而另一个更加有效的锁就是乐观锁。所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。乐观锁的缺点是不能解决脏读的问题。乐观锁用到的机制就是CAS，Compare and Swap。
二、什么是CAS
CAS的全称为Compare And Swap，直译就是比较交换。是一条CPU的原子指令，其作用是让CPU先进行比较两个值是否相等，然后原子地更新某个位置的值，其实现方式是基于硬件平台的汇编指令，在intel的CPU中，使用的是cmpxchg指令，就是说CAS是靠硬件实现的，从而在硬件层面提升效率。
它是一个无锁的原子算法。所以它就是一个乐观锁，也就是不加锁。无锁也就没有加锁和解锁的过程，不存在阻塞，也就提高了效率，提高了CPU的吞吐量（单位时间内执行完成的操作条数就多了）
它就是CPU的一条原子指令。过程是这样：它包含 3 个参数内存位置（V）、预期原值（A）和新值(B)。V表示要更新变量的值，E表示预期值，N表示新值。仅当V值等于E值时，才会将V的值设为N，如果V值和E值不同，则说明已经有其他线程做两个更新，则当前线程则什么都不做。最后，CAS 返回当前V的真实值（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前 值）。CAS 操作时抱着乐观的态度进行的，它总是认为自己可以成功完成操作。
当多个线程同时使用CAS 操作一个变量时，只有一个会胜出，并成功更新，其余均会失败。失败的线程不会挂起，仅是被告知失败，并且允许再次尝试，当然也允许实现的线程放弃操作。基于这样的原理，CAS 操作即使没有锁，也可以发现其他线程对当前线程的干扰。
与锁相比，使用CAS会使程序看起来更加复杂一些，但由于其非阻塞的，它对死锁问题天生免疫，并且，线程间的相互影响也非常小。更为重要的是，使用无锁的方式完全没有锁竞争带来的系统开销，也没有线程间频繁调度带来的开销，因此，它要比基于锁的方式拥有更优越的性能。
简单的说，CAS 需要你额外给出一个期望值，也就是你认为这个变量现在应该是什么样子的。如果变量不是你想象的那样，那说明它已经被别人修改过了。你就需要重新读取，再次尝试修改就好了。
三、CAS的应用
利用CPU的CAS指令，同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。而整个J.U.C都是建立在CAS之上的，因此对于synchronized阻塞算法，J.U.C在性能上有了很大的提升。
3.1 非阻塞算法 （nonblocking algorithms）
非阻塞算法就是一个线程的失败或者挂起不应该影响其他线程的失败或挂起的算法。非阻塞算法就需要借助CAS操作来实现，这也是CAS的一个主要应用方向。
现代的CPU提供了特殊的指令，可以自动更新共享数据，而且能够检测到其他线程的干扰，而 compareAndSet() 就用这些CPU提供的特殊指令代替了锁定。
我们来看一下AtomicInteger类在没有锁的情况下是如何做到数据正确性的。
public class AtomicInteger extends Number implements java.io.Serializable {
private volatile int value;
public final int get() {
return value;
}
public final int getAndIncrement() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return current;
}
}
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
}
首先毫无疑问，在没有锁的机制下可能需要借助volatile原语，保证线程间的数据是可见的（共享的）。
private volatile int value; 这样才获取变量的值的时候才能直接读取。
public final int get() {
return value;
} 然后来看看++i是怎么做到的。
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
}
incrementAndGet()采用了CAS操作，每次从内存中读取数据然后将此数据和+1后的结果进行CAS操作，如果成功就返回结果，否则重试直到成功为止。
incrementAndGet()方法中的compareAndSet()方法则是利用JNI来完成CPU指令的操作。通过判断当前的值this还是不是等于一开始的值expect，如果还等于expect，就说明期间没有其他线程对该数据进行了修改，不会出现并发一场，那么就将this改成update更新后的数据。
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update); // 仔细注意传进来的参数，理解该方法的作用
}
整体的过程就是这样子的，通过JNI（Java本地调用）来调用C语言代码，然后C语言代码来调用CPU的CAS指令来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。
其中
unsafe.compareAndSwapInt(this, valueOffset, expect, update); 类似：
if (this == expect) {
this = update
return true;
} else {
return false;
} Unsafe 是 CAS 的核心类， Java 无法直接访问底层操作系统，而是通过本地（ native ）方法来访问。不过尽管如此， JVM 还是开了一个后门： Unsafe ，它提供了硬件级别的原子操作， 这里的 compareAndSwapInt () 就是 Unsafe 类提供的硬件原子操作之一 。
那么问题就来了，成功过程中需要2个步骤：比较this == expect，替换this = update，compareAndSwapInt如何这两个步骤的原子性呢？ 参考CAS的原理。
四、CAS底层原理
归功于硬件指令集的发展，实际上，我们可以使用同步将这两个操作变成原子的，但是这么做就没有意义了。所以我们只能靠硬件来完成，硬件保证一个从语义上看起来需要多次操作的行为只通过一条处理器指令就能完成。这类指令常用的有：
- 测试并设置（Tetst-and-Set）
- 获取并增加（Fetch-and-Increment）
- 交换（Swap）
- 比较并交换（Compare-and-Swap）
- 加载链接/条件存储（Load-Linked/Store-Conditional）
<figcaption> SMP（对称多处理器）架构图 </figcaption> - BUS：总线
- 每一个CPU都共用一根总线，与主内存相互交互。每一个CPU都有一个自己私有的Cache
CPU 实现原子指令有3种方式：
4.1 处理器自动保证基本内存操作的原子性
首先处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存当中读取或者写入一个字节是原子的，意思是当一个处理器读取一个字节时，其他处理器不能访问这个字节的内存地址。奔腾6和最新的处理器能自动保证单处理器对同一个缓存行里进行16/32/64位的操作是原子的，但是复杂的内存操作处理器不能自动保证其原子性，比如跨总线宽度，跨多个缓存行，跨页表的访问。但是处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性。
4.2 通过总线锁定来保证原子性
总线锁定其实就是处理器使用了总线锁，所谓总线锁就是使用处理器提供的一个 LOCK# 信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占共享内存。但是该方法成本太大。因此有了下面的方式。
4.3 通过缓存锁定来保证原子性
在同一时刻我们只需保证对某个内存地址的操作是原子性即可，但总线锁定把CPU和内存之间通信锁住了，这使得锁定期间，其他处理器不能操作其他内存地址的数据，所以总线锁定的开销比较大，最近的处理器在某些场合下使用缓存锁定代替总线锁定。
所谓缓存锁定 是指内存区域如果被缓存在处理器的缓存行中，并且在Lock 操作期间被锁定，那么当它执行操作写回到内存时，处理器不在总线上输出 LOCK# 信号，而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改两个以上处理器缓存的内存区域数据（这里和 volatile 的可见性原理相同），当其他处理器回写已被锁定的缓存行的数据时，会使缓存行无效。
注意：有两种情况下处理器不会使用缓存锁定
- 当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行时，则处理器会调用总线锁定。
- 有些处理器不支持缓存锁定，对于 Intel 486 和 Pentium 处理器，就是锁定的内存区域在处理器的缓存行也会调用总线锁定。
4.4 总结：
锁总线是通过LOCK#信号实现的，锁缓存是通过缓存一致性协议实现的。
五、CAS存在的问题
CAS虽然高效地解决了原子操作，但是还是存在一些缺陷的，主要表现在三个方面：循环时间太长、只能保证一个共享变量原子操作、ABA问题。
5.1 循环时间太长
如果CAS一直不成功呢？这种情况绝对有可能发生，如果自旋CAS长时间地不成功，则会给CPU带来非常大的开销。在JUC中有些地方就限制了CAS自旋的次数，例如BlockingQueue的SynchronousQueue。
5.2 只能保证一个共享变量原子操作
看了CAS的实现就知道这只能针对一个共享变量，如果是多个共享变量就只能使用锁了，当然如果你有办法把多个变量整成一个变量，利用CAS也不错。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。
5.3 ABA问题
CAS需要检查操作值有没有发生改变，如果没有发生改变则更新。但是存在这样一种情况：如果一个值原来是A，变成了B，然后又变成了A，那么在CAS检查的时候会发现没有改变，但是实质上它已经发生了改变，这就是所谓的ABA问题。对于ABA问题其解决方案是加上版本号，即在每个变量都加上一个版本号，每次改变时加1，即A —> B —> A，变成1A —> 2B —> 3A。
从Java1.5 开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。其实就类似于引入了版本概念，给每一个数据都有一个它唯一的版本号，通关检查版本号来判断数据是否被修改。
5.4 CAS造成Cache一致性流量过大
现在几乎所有的锁都是可重入的，即已经获得锁的线程可以多次锁住/解锁监视对象，按照之前的HotSpot设计，每次加锁/解锁都会涉及到一些CAS操作（比如对等待队列的CAS操作），CAS操作会延迟本地调用(使本地调用不是那么及时)，因此偏向锁的想法是 一旦线程第一次获得了监视对象，之后让监视对象“偏向”这个线程，之后的多次调用则可以避免CAS操作，说白了就是置个变量，如果发现为true则无需再走各种加锁/解锁流程。轻量级锁就是基于CAS操作的
CAS为什么会引入本地延迟？这要从SMP（对称多处理器）架构说起，下图大概表明了SMP的结构：
<figcaption> SMP（对称多处理器）架构 </figcaption>
其意思是 所有的CPU会共享一条系统总线（BUS），靠此总线连接主存。每个核都有自己的一级缓存，各核相对于BUS对称分布，因此这种结构称为“对称多处理器”。
而CAS的全称为Compare-And-Swap，是一条CPU的原子指令，其作用是让CPU比较后原子地更新某个位置的值，其实现方式是基于硬件平台的汇编指令，就是说CAS是靠硬件实现的，JVM只是封装了汇编调用，那些AtomicInteger类便是使用了这些封装后的接口。
例如：Core1和Core2可能会同时把主存中某个位置的值Load到自己的L1 Cache中，当Core1在自己的L1 Cache中修改这个位置的值时，会通过总线，使Core2中L1 Cache对应的值“失效”，而Core2一旦发现自己L1 Cache中的值失效（称为Cache命中缺失）则会通过总线从内存中加载该地址最新的值，大家通过总线的来回通信称为“Cache一致性流量”，因为总线被设计为固定的“通信能力”，如果Cache一致性流量过大，总线将成为瓶颈。而当Core1和Core2中的值再次一致时，称为“Cache一致性”，从这个层面来说，锁设计的终极目标便是减少Cache一致性流量。
而CAS恰好会导致Cache一致性流量，如果有很多线程都共享同一个对象，当某个Core CAS成功时必然会引起总线风暴，这就是所谓的本地延迟，本质上偏向锁就是为了消除CAS，降低Cache一致性流量。
相关参考：
Cache一致性：
上面提到Cache一致性，其实是有协议支持的，现在通用的协议是MESI（最早由Intel开始支持），具体参考：http://en.wikipedia.org/wiki/MESI_protocol。Cache一致性流量的例外情况：
其实也不是所有的CAS都会导致总线风暴，这跟Cache一致性协议有关，具体参考：http://blogs.oracle.com/dave/entry/biased_locking_in_hotspotNUMA(Non Uniform Memory Access Achitecture）架构：
与SMP对应还有非对称多处理器架构，现在主要应用在一些高端处理器上，主要特点是没有总线，没有公用主存，每个Core有自己的内存，针对这种结构此处不做讨论。
六、concurrent包的实现
由于java的CAS同时具有 volatile 读和volatile写的内存语义，因此Java线程之间的通信现在有了下面四种方式：
- A线程写volatile变量，随后B线程读这个volatile变量。
- A线程写volatile变量，随后B线程用CAS更新这个volatile变量。
- A线程用CAS更新一个volatile变量，随后B线程用CAS更新这个volatile变量。
- A线程用CAS更新一个volatile变量，随后B线程读这个volatile变量。
Java的CAS会使用现代处理器上提供的高效机器级别原子指令，这些原子指令以原子方式对内存执行读-改-写操作，这是在多处理器中实现同步的关键（从本质上来说，能够支持原子性读-改-写指令的计算机器，是顺序计算图灵机的异步等价机器，因此任何现代的多处理器都会去支持某种能对内存执行原子性读-改-写操作的原子指令）。同时，volatile变量的读/写和CAS可以实现线程之间的通信。把这些特性整合在一起，就形成了整个concurrent包得以实现的基石。如果我们仔细分析concurrent包的源代码实现，会发现一个通用化的实现模式：
- 首先，声明共享变量为volatile；
- 然后，使用CAS的原子条件更新来实现线程之间的同步；
- 同时，配合以volatile的读/写和CAS所具有的volatile读和写的内存语义来实现线程之间的通信。
AQS和非阻塞数据结构和原子变量类（java.util.concurrent.atomic包中的类），这些concurrent包中的基础类都是使用这种模式来实现的，而concurrent包中的高层类又是依赖于这些基础类来实现的。从整体来看，concurrent包的实现示意图如下：
6.1 Atomic类
Atomic类并不使用同步锁，而是采用CAS操作，每次对值进行修改时，先判断其预期值与内存值是否相同，若相同则修改，否则不修改
优点 不加锁，性能较快
缺点 高并发情况下，出错概率越大，长时间CAS不成功，导致CPU消耗过大
注：此种方法是乐观锁，即操作前认为此次操作不会出现竞态，不加锁，只在最后写入主存时进行判断
警：ABA问题，当一个值原来是A，被某个线程改成B，又被另个线程改成A，此时CAS操作判断不出已经发生变化，java中使用版本号来解决此问题。
其他相关文章：【并发编程】volatile关键字最全详解，看这一篇就够了
【Java内存模型】Java内存模型（JMM）详解以及并发编程的三个重要特性（原子性，可见性，有序性）
【并发基础】AQS（Abstract Queued Synchronizer）框架的使用和实现原理详解
【并发编程】synchronized关键字最全详解，看这一篇就够了
【并发编程】线程安全和线程不安全的定义以及实现线程安全的方法有哪些
华为工作强度 847人发布
