CAS 原理介绍

女爷i 2023-07-13 12:28 10阅读 0赞

## **概述** ##

CAS（Compare-and-Swap），即比较并替换，是一种实现并发算法时常用到的技术，Java并发包中的很多类都使用了CAS技术。CAS也是现在面试经常问的问题，本文将深入的介绍CAS的原理。

## **案例** ##

介绍CAS之前，我们先来看一个例子。

/**
     * @author joonwhee
     * @date 2019/7/6
     */
    public class VolatileTest {
        
        public static volatile int race = 0;
     
        private static final int THREADS_COUNT = 20;
        
        public static void increase() {
            race++;
        }
     
        public static void main(String[] args) throws InterruptedException {
            Thread[] threads = new Thread[THREADS_COUNT];
            for (int i = 0; i < THREADS_COUNT; i++) {
                threads[i] = new Thread(new Runnable() {
                    @Override
                    public void run() {
                        for (int i = 0; i < 10000; i++) {
                            increase();
                        }
                    }
                });
                threads[i].start();
            }
     
            while (Thread.activeCount() > 1) {
                Thread.yield();
            }
            System.out.println(race);
        }
    }

这个例子有些网友反馈会进入死循环，我后面也发现了，在IDEA的RUN模式下确实会陷入死循环，通过 Thread.currentThread().getThreadGroup().list(); 代码可以打印出当前的线程情况如下：

java.lang.ThreadGroup[name=main,maxpri=10]
        Thread[main,5,main]
        Thread[Monitor Ctrl-Break,5,main]

可以看到，除了Main方法线程后，还有一个Monitor Ctrl-Break线程，这个线程是IDEA用来监控Ctrl-Break中断信号的线程。

解决死循环的办法：如果是IDEA，可以使用DEBUG模式运行就可以，或者使用下面这段代码。

import java.util.concurrent.CountDownLatch;
     
    /**
     * @author joonwhee
     * @date 2019/7/6
     */
    public class VolatileTest {
        
        public static volatile int race = 0;
     
        private static final int THREADS_COUNT = 20;
     
        private static CountDownLatch countDownLatch = new CountDownLatch(THREADS_COUNT);
     
        public static void increase() {
            race++;
        }
     
        public static void main(String[] args) throws InterruptedException {
            Thread[] threads = new Thread[THREADS_COUNT];
            for (int i = 0; i < THREADS_COUNT; i++) {
                threads[i] = new Thread(new Runnable() {
                    @Override
                    public void run() {
                        for (int i = 0; i < 10000; i++) {
                            increase();
                        }
                        countDownLatch.countDown();
                    }
                });
                threads[i].start();
            }
            countDownLatch.await();
            System.out.println(race);
        }
    }

上面这个例子在[volatile关键字详解][volatile]文中用过，我们知道，运行完这段代码之后，并不会获得期望的结果，而且会发现每次运行程序，输出的结果都不一样，都是一个小于200000的数字。

通过分析字节码我们知道，这是因为volatile只能保证可见性，无法保证原子性，而自增操作并不是一个原子操作（如下图所示），在并发的情况下，putstatic指令可能把较小的race值同步回主内存之中，导致我们每次都无法获得想要的结果。那么，应该怎么解决这个问题了？

![format_png][]

**解决方法：**

首先我们想到的是用synchronized来修饰increase方法。

![format_png 1][]

使用synchronized修饰后，increase方法变成了一个原子操作，因此是肯定能得到正确的结果。但是，我们知道，每次自增都进行加锁，性能可能会稍微差了点，有更好的方案吗？

答案当然是有的，这个时候我们可以使用Java并发包原子操作类（Atomic开头），例如以下代码。

![format_png 2][]

我们将例子中的代码稍做修改：race改成使用AtomicInteger定义，“race++”改成使用“race.getAndIncrement()”，AtomicInteger.getAndIncrement()是原子操作，因此我们可以确保每次都可以获得正确的结果，并且在性能上有不错的提升（针对本例子，在JDK1.8.0\_151下运行）。

通过方法调用，我们可以发现，getAndIncrement方法调用getAndAddInt方法，最后调用的是compareAndSwapInt方法，即本文的主角CAS，接下来我们开始介绍CAS。

![format_png 3][]

![format_png 4][]

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

## **CAS是什么？** ##

CAS是英文单词**CompareAndSwap**的缩写，中文意思是：比较并替换。CAS需要有3个操作数：内存地址V，旧的预期值A，即将要更新的目标值B。

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

**源码分析**

上面源码分析时，提到最后调用了compareAndSwapInt方法，接着继续深入探讨该方法，该方法在Unsafe中对应的源码如下。

![format_png 5][]

可以看到调用了“Atomic::cmpxchg”方法，“Atomic::cmpxchg”方法在linux\_x86和windows\_x86的实现如下。

**linux\_x86的实现：**

![format_png 6][]

**windows\_x86的实现：**

![format_png 7][]

**Atomic::cmpxchg方法解析**：

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

1.  如果当前系统是多处理器，该函数返回1。
2.  否则，返回0。

**LOCK\_IF\_MP(mp)**会根据mp的值来决定是否为cmpxchg指令添加lock前缀。

1.  如果通过mp判断当前系统是多处理器（即mp值为1），则为cmpxchg指令添加lock前缀。
2.  否则，不加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的缺点：** ##

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

1.  循环时间长开销很大。
2.  只能保证一个共享变量的原子操作。
3.  ABA问题。

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

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

**什么是ABA问题？ABA问题怎么解决？**

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

如果在这段期间它的值曾经被改成了B，后来又被改回为A，那CAS操作就会误认为它从来没有被改变过。这个漏洞称为CAS操作的“ABA”问题。Java并发包为了解决这个问题，提供了一个带有标记的原子引用类“AtomicStampedReference”，它可以通过控制变量值的版本来保证CAS的正确性。因此，在使用CAS前要考虑清楚“ABA”问题是否会影响程序并发的正确性，如果需要解决ABA问题，改用传统的互斥同步可能会比原子类更高效。

[volatile]: https://zhuanlan.zhihu.com/p/34362413
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMzLnpoaW1nLmNvbS84MC92Mi05Y2YyMmU5YzgzYWI3MjQ0MjU4ZTIxYTAxOTVkYTE3Nl83MjB3LmpwZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMyLnpoaW1nLmNvbS84MC92Mi05NWZiMGRjMWQ0YTQ0NDQyOWVmOTdhNmRhZDI4MjNiMV83MjB3LmpwZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWM0LnpoaW1nLmNvbS84MC92Mi1jZTc1NGIxMTFkODIxZmZlN2ExNTRhZTk1MzAyMjIxYl83MjB3LmpwZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMxLnpoaW1nLmNvbS84MC92Mi1hNmUxMTc4OTE0NzU2ZjIxZDk4OTA1MjE2MTM5Njc5MF83MjB3LmpwZw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMzLnpoaW1nLmNvbS84MC92Mi1jNDEzZGZmNWM5ODJkYWE3ZGM1ODVmMjY1OWFlMDY1YV83MjB3LmpwZw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMzLnpoaW1nLmNvbS84MC92Mi1lNjYyMWNlOTk3OWE4NjQ2M2UzNTI5YzI3ZGVmNDgzYV83MjB3LmpwZw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMxLnpoaW1nLmNvbS84MC92Mi05MTgxMDFkZjc0N2JhOWQwMzgxNWNlZmZmMzk1NWQ3NF83MjB3LmpwZw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMyLnpoaW1nLmNvbS84MC92Mi1jZDI0MTI5YTJiOGYxMDZlYzMxNzkwODNkM2U4Y2ZkMV83MjB3LmpwZw?x-oss-process=image/format,png