欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

面试官:你知道什么是 CAS 吗?

程序员文章站 2022-10-03 16:22:56
你知道什么是 CAS 吗?文章目录你知道什么是 CAS 吗?前言1.CAS 是什么?2.CAS 的思路3.图解4.CAS 的语义5.代码演示6.总结7.参考前言CAS 其实是我们面试中的常客,因为它是原子类的底层原理,同时也是乐观锁的原理,所以当你去面试的时候,经常会遇到这样的问题“你知道哪些类型的锁”?你可能会回答“悲观锁和乐观锁”,那么下一个问题很有可能是问乐观锁的原理,也就是和 CAS 相关的问题,当然也有可能会继续深入问你 CAS 的应用场景或者是缺点等问题。1.CAS 是什么?首先我们来...

你知道什么是 CAS 吗?

前言

CAS 其实是我们面试中的常客,因为它是原子类的底层原理,同时也是乐观锁的原理,所以当你去面试的时候,经常会遇到这样的问题“你知道哪些类型的锁”?你可能会回答“悲观锁和乐观锁”,那么下一个问题很有可能是问乐观锁的原理,也就是和 CAS 相关的问题,当然也有可能会继续深入问你 CAS 的应用场景或者是缺点等问题。

项目环境

1.CAS 是什么?

首先我们来看一下 CAS 是什么,它的英文全称是 Compare-And-Swap,中文叫做“比较并交换”,它是一种思想、一种算法。

在多线程的情况下,各个代码的执行顺序是不能确定的,所以为了保证并发安全,我们可以使用互斥锁。而 CAS 的特点是避免使用互斥锁,当多个线程同时使用 CAS 更新同一个变量时,只有其中一个线程能够操作成功,而其他线程都会更新失败。不过和同步互斥锁不同的是,更新失败的线程并不会被阻塞,而是被告知这次由于竞争而导致的操作失败,但还可以再次尝试。

CAS 被广泛应用在并发编程领域中,以实现那些不会被打断的数据交换操作,从而就实现了无锁的线程安全。

2.CAS 的思路

在大多数处理器的指令中,都会实现 CAS 相关的指令,这一条指令就可以完成“比较并交换”的操作,也正是由于这是一条(而不是多条)CPU 指令,所以 CAS 相关的指令是具备原子性的,这个组合操作在执行期间不会被打断,这样就能保证并发安全。由于这个原子性是由 CPU 保证的,所以无需我们程序员来操心。

CAS 有三个操作数:内存值 V、预期值 A、要修改的值 B。CAS 最核心的思路就是,仅当预期值 A 和当前的内存值 V 相同时,才将内存值修改为 B。

我们对此展开描述一下:CAS 会提前假定当前内存值 V 应该等于值 A,而值 A 往往是之前读取到当时的内存值 V。在执行 CAS 时,如果发现当前的内存值 V 恰好是值 A 的话,那 CAS 就会把内存值 V 改成值 B,而值 B 往往是在拿到值 A 后,在值 A 的基础上经过计算而得到的。如果执行 CAS 时发现此时内存值 V 不等于值 A,则说明在刚才计算 B 的期间内,内存值已经被其他线程修改过了,那么本次 CAS 就不应该再修改了,可以避免多人同时修改导致出错。这就是 CAS 的主要思路和流程。

JDK 正是利用了这些 CAS 指令,可以实现并发的数据结构,比如 AtomicInteger 等原子类。

利用 CAS 实现的无锁算法,就像我们谈判的时候,用一种非常乐观的方式去协商,彼此之间很友好,这次没谈成,还可以重试。CAS 的思路和之前的互斥锁是两种完全不同的思路,如果是互斥锁,不存在协商机制,大家都会尝试抢占资源,如果抢到了,在操作完成前,会把这个资源牢牢的攥在自己的手里。当然,利用 CAS 和利用互斥锁,都可以保证并发安全,它们是实现同一目标的不同手段。

3.图解

假设有两个线程同时来操作共享变量,利用 CAS 来改变 x 的值,过程如下:
面试官:你知道什么是 CAS 吗?
首先,线程1执行,它期望当前的值是 100,并且想将其改成 150。在执行的时候,它会去检查当前的值是不是 100,发现真的是 100,所以可以改动成功,而当改完之后,x 的值就会从 100 变成 150。

当线程1执行完成之后,线程2开始执行,同样它的期望值也是 100,想修改为 200,但是它检查发现当前的值已经被修改并不是 100,所以并不会执行后续操作将 100 改成 200,也就是说整个操作都是没有效果的,此次没有修改成功,CAS 操作失败。

当然,接下来线程 2 还可以有其他的操作,这需要根据业务需求来决定,比如重试、报错或者干脆跳过执行。

4.CAS 的语义

我们来看一看 CAS 的语义,有了下面的等价代码之后,理解起来会比前面的图示和文字更加容易,因为代码实际上是一目了然的。接下来我们把 CAS 拆开,看看它内部究竟做了哪些事情。CAS 的等价语义的代码,如下所示:

public class SimulatedCAS {

    private int value;// 共享变量 x 的值

    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        int oldValue = value;// 旧值
        if (oldValue == expectedValue) {// 比较:如果旧值等于预期值
            value = newValue;// 交换:设置共享变量 x = 新值
        }
        return newValue;
    }
}

在这段代码中有一个 compareAndSwap 方法,在这个方法里有两个入参,第 1 个入参期望值 expectedValue,第 2 个入参是 newValue,它就是我们计算好的新的值,我们希望把这个新的值去更新到变量上去。

你一定注意到了, compareAndSwap 方法是被 synchronized 修饰的,我们用同步方法为 CAS 的等价代码保证了原子性。

接下来我将讲解,在 compareAndSwap 方法里都做了哪些事情。需要先拿到变量的当前值,所以代码里用就会用 int oldValue = value 把变量的当前值拿到。

  • 然后就是 compare,也就是比较,所以此时会用 if (oldValue == expectedValue) 把当前值和期望值进行比较;
  • 如果它们是相等的话,那就意味着现在的值正好就是我们所期望的值,满足条件,说明此时可以进行 swap,也就是交换,所以就把 value 的值修改成 newValue,最后再返回 oldValue,完成了整个 CAS 过程。

CAS 最核心的思想就在上面这个流程中体现了,可以看出,compare 指的就是 if 里的比较,比较 oldValue 是否等于 expectedValue;同样,swap 实际上就是把 value 改成 newValue,并且返回 oldValue。所以这整个 compareAndSwap 方法就还原了 CAS 的语义,也象征了 CAS 指令在背后所做的工作。

5.代码演示

我们写一段代码来演示第三小节中两个线程 CAS 的过程,代码如下:

public class CASDemo {

    private volatile int value = 100;// 共享变量 x 的值

    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        int oldValue = value;// 旧值
        if (oldValue == expectedValue) {// 比较:如果旧值等于预期值
            value = newValue;// 交换:设置共享变量 x = 新值
        }
        return newValue;
    }

    static class CASTask implements Runnable {

        private CASDemo casDemo;
        private int expectedValue;
        private int newValue;

        public CASTask(CASDemo casDemo, int expectedValue, int newValue) {
            this.casDemo = casDemo;
            this.expectedValue = expectedValue;
            this.newValue = newValue;
        }

        @Override
        public void run() {
            casDemo.compareAndSwap(expectedValue, newValue);
        }
    }

    public static void main(String[] args) throws InterruptedException {
        CASDemo casDemo = new CASDemo();
        Thread t1 = new Thread(new CASTask(casDemo, 100, 150), "Thread-1");
        Thread t2 = new Thread(new CASTask(casDemo, 100, 200), "Thread-2");
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println("CAS 之后 value 的值:" + casDemo.value);
    }
}

这里的 compareAndSwap 方法就是刚才所讲过的 CAS 的等价语义的代码。在 main() 方法里面,新建两个线程 Thread t1 和 Thread t2,分别设置 CAS(100,150), CAS(100,200),然后启动线程,并且主线程等待两个线程执行完毕之后,打印出最后 value 的值。

执行结果如下:

线程[Thread-1] CAS 成功,value[100]->[150] 
线程[Thread-2] CAS 失败 
CAS 之后 value 的值:150

结果符合预期,线程1 先获取到锁,判断预期值 100 和共享变量 value 的旧值一样,替换共享变量 value 值为 150,释放锁。然后线程2 开始执行,获取到锁,但是此时预期值100 != 150,CAS 失败,最后返回的结果为 150。

代码调试

断点打在 14 行,选择 Thread 模式。
面试官:你知道什么是 CAS 吗?
线程1 进来,可以看到 oldValue = expectedValue = 100,进入到 if 代码中
面试官:你知道什么是 CAS 吗?
继续往下,CAS成功,打印 线程[Thread-1] CAS 成功,value[100]->[150]
面试官:你知道什么是 CAS 吗?
Resume Program F9 直接进入到线程2,可以看到 oldValue != expectedValue,CAS 失败。
面试官:你知道什么是 CAS 吗?

6.总结

CAS 的核心思想是通过将内存中的值与指定数据进行比较,当这两个数值一样时,才将内存中的数据替换为新的值,整个过程是具备原子性的。

7.参考

  • 《Java 并发编程 78 讲》- 徐隆曦

本文地址:https://blog.csdn.net/xiewenfeng520/article/details/107594693