CAS（Compare-and-Swap）比较并替换

下面先简介一下CAS，再通过原子操作包引入，最后介绍一下CAS在CPU中的操作以及它的缺点。

参考文章：

https://blog.csdn.net/v123411739/article/details/79561458（原子操作类以及缺点）

https://www.jianshu.com/p/21be831e851e（CAS开销以及CPU体系结构）

https://blog.csdn.net/ustcyy91/article/details/78799793（介绍的较为完整的博文）

什么是CAS？

CAS：Compare and Swap，即比较再交换，

CAS是一种无锁算法，需要有3个操作数：内存地址V，旧的预期值A，即将要更新的目标值B。

CAS指令执行时，当且仅当内存地址V的值与预期值A相等时，将内存地址V的值修改为B，否则就什么都不做。整个比较并替换的操作是一个原子操作。

属于乐观锁的思想。（CAS 操作是基于共享数据不会被修改的假设）

JDK 5之前Java语言是靠synchronized关键字保证同步的，这是一种独占锁，也是是悲观锁。JDK1.6 中对 synchronize 进行了各种优化，为了能减少获取和释放锁带来的消耗引入了偏向锁和轻量锁【用到了CAS算法】。

要了解cas，我们先从jdk中的并发原子包开始：

CAS算法在JDK中的应用

在原子类变量中，如java.util.concurrent.atomic中的AtomicXXX，都使用了这些底层的JVM支持为数字类型的引用类型提供一种高效的CAS操作，而在java.util.concurrent中的大多数类在实现时都直接或间接的使用了这些原子变量类。之前在volatile文章中简单介绍过：https://blog.nowcoder.net/n/ebe6637ae8584e54916fb3e8103617ff

例如AtomicInteger的getAndIncrement()和incrementAndGet方法（都调用了 Unsafe 类中的 getAndAddInt（）方法，区别是：① 前者，先返回，再 +1② 后者，先+1，再返回）

我们通过getAndIncrement()来了解一下：看一下getAndIncrement()的实现：

getAndAddInt方法解析：拿到内存位置的最新值v，使用CAS尝试修将内存位置的值修改为目标值v+delta，如果修改失败，则获取该内存位置的新值v，然后继续尝试，直至修改成功。

接着继续深入探讨该方法，该方法在Unsafe中对应的源码如下。（图片引用别处）

可以看到调用了“Atomic::cmpxchg”方法，（“Atomic::cmpxchg”方法在linux_x86和windows_x86的实现写法不同。）

Atomic::cmpxchg方法解析：

mp是“os::is_MP()”的返回结果，“os::is_MP()”是一个内联函数，用来判断当前系统是否为多处理器。

如果当前系统是多处理器，该函数返回1。
否则，返回0。
LOCK_IF_MP(mp)会根据mp的值来决定是否为cmpxchg指令添加lock前缀。

如果通过mp判断当前系统是多处理器（即mp值为1），则为cmpxchg指令添加lock前缀。
否则，不加lock前缀。
这是一种优化手段，认为单处理器的环境没有必要添加lock前缀，只有在多核情况下才会添加lock前缀，因为lock会导致性能下降。cmpxchg是汇编指令，作用是比较并交换操作数。

intel手册对lock前缀的说明如下：

1、确保对内存的读-改-写操作原子执行。在Pentium及Pentium之前的处理器中，带有lock前缀的指令在执行期间会锁住总线，使得其他处理器暂时无法通过总线访问内存。很显然，这会带来昂贵的开销。从Pentium 4，Intel Xeon及P6处理器开始，intel在原有总线锁的基础上做了一个很有意义的优化：如果要访问的内存区域（area of memory）在lock前缀指令执行期间已经在处理器内部的缓存中被锁定（即包含该内存区域的缓存行当前处于独占或以修改状态），并且该内存区域被完全包含在单个缓存行（cache line）中，那么处理器将直接执行该指令。由于在指令执行期间该缓存行会一直被锁定，其它处理器无法读/写该指令要访问的内存区域，因此能保证指令执行的原子性。这个操作过程叫做缓存锁定（cache locking），缓存锁定将大大降低lock前缀指令的执行开销，但是当多处理器之间的竞争程度很高或者指令访问的内存地址未对齐时，仍然会锁住总线。

2、禁止该指令与之前和之后的读和写指令重排序。

3、把写缓冲区中的所有数据刷新到内存中。

上面的第1点保证了CAS操作是一个原子操作，第2点和第3点所具有的内存屏障效果，保证了CAS同时具有volatile读和volatile写的内存语义。

CAS在CPU中的操作

（开销例子请看参考文章）

此处了解不详，只做简单介绍。前面说到了lock前缀的作用。这里要介绍一下CPU的硬件体系结构：

CAS（比较并交换）是CPU指令级的操作，只有一步原子操作，所以非常快。而且CAS避免了请求操作系统来裁定锁的问题，不用麻烦操作系统，直接在CPU内部就搞定了。但CAS就没有开销了吗？不！有cache miss的情况。

上图是一个8核CPU计算机系统，每个CPU有cache（CPU内部的高速缓存，寄存器），管芯内还带有一个互联模块，使管芯内的两个核可以互相通信。在图中央的系统互联模块可以让四个管芯相互通信，并且将管芯与主存（内存）连接起来。数据以“缓存线”为单位在系统中传输，“缓存线”对应于内存中一个 2 的幂大小的字节块，大小通常为 32 到 256 字节之间。当 CPU 从内存中读取一个变量到它的寄存器中时，必须首先将包含了该变量的缓存线读取到 CPU 高速缓存。同样地，CPU 将寄存器中的一个值存储到内存时，不仅必须将包含了该值的缓存线读到 CPU 高速缓存，还必须确保没有其他 CPU 拥有该缓存线的拷贝。

假设CPU0负责执行CAS赋值，而CPU7的高数缓存中还存在着该值，值要通过各种通道（此处开销），最终把值传到CPU0中的高数缓存中。

总结上面两部分：为什么CAS存入之前需要进行比较和替换这些多步操作，却还能保证原子性？【面试题】

CAS是基于硬件层面的，系统在硬件层面保证了比较并交换操作的原子性，处理器使用基于对缓存或总线加锁的方式实现多处理器之间的原子操作。

在前期的CPU中，是通过总线锁，对于多核处理器，会标记lock前缀，带有lock前缀的指令在执行期间会锁住总线，使得其他处理器暂时无法通过总线访问内存。也就是当某个cpu在进行CAS操作时，其他cpu暂停访问内存。【数据最终都是存储在内存里的，cpu主要是运算】

后来CPU优化，做到缓存锁，当要执行CAS操作时，先经过操作使得确保只有一个高速缓存持有该变量，然后锁住该缓存，由改缓存的CPU进行修改，其他高速缓存都不能持有该值，执行完成后解锁继续其他操作。

CAS的缺点：

CAS虽然很高效的解决了原子操作问题，但是CAS仍然存在三大问题。

1、循环时间长开销很大：
我们可以看到getAndAddInt方法执行时，如果CAS失败，会一直进行尝试。如果CAS长时间一直不成功，可能会给CPU带来很大的开销。

2、只能保证一个共享变量的原子操作：
只能保证一个共享变量的原子操作。当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。

3、ABA问题？ABA问题怎么解决？
如果内存地址V初次读取的值是A，并且在准备赋值的时候检查到它的值仍然为A，那我们就能说它的值没有被其他线程改变过了吗？

如果在这段期间它的值曾经被改成了B，后来又被改回为A，那CAS操作就会误认为它从来没有被改变过。这个漏洞称为CAS操作的“ABA”问题。Java并发包为了解决这个问题，从Java1.5开始JDK的atomic包里提供了一个带有标记的原子引用类“AtomicStampedReference”，（这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。），它可以通过控制变量值的版本来保证CAS的正确性。因此，在使用CAS前要考虑清楚“ABA”问题是否会影响程序并发的正确性，如果需要解决ABA问题，改用传统的互斥同步可能会比原子类更高效。