一分钟带你搞懂CAS算法是如何保证线程安全的。

程序员牛肉

发布于 2024-09-26 13:16:14

610

发布于 2024-09-26 13:16:14

文章被收录于专栏：小牛肉带你学Java

大家好，我是程序员牛肉。

你可以试想这样一个场景：一家电影院要对外进行售票，但他们采用的是朴素的手工记账方式。有一个唯一账本，售货员每卖出一张票就要手动去修改这个账本中的电影票余量。

有一天，电影院只剩下最后一张票了，客户在售货员A处购买这张票之后，就在A还没来得及修改账本的时候，另一名客户又在售货员B处购买这张票，由于售货员A还没修改账本，售货员B认为当前还是有余票的，就有把这张票卖出去了。

这下坏了，电影院的座位是有限的。我们竟然把票买超了。

当我们尝试把这个购票模式转移到网上的时候，也同样会有把票买超的情况。有可能我们的一个线程（售票员）还没来得及修改数据库（账本），就被另一个线程（售票员）把票卖出去了。

我们来看看这样一个买票请求应该会经历哪些步骤：

检查票的余额
如果还有余票，进行售卖
修改票的余额

那么为什么会出现超卖问题呢？用最朴素的想法来想，那就应该是因为售票操作不连续，是可以打断的。

在理想情况下，我们认为售票业务应该是这样的：

可是在高并发业务下，售票业务可能会变为这样了：

由于这两个线程并没有按照我们预想的方式对影票余额进行修改，我们就认为这两个线程是不安全的。

我们最朴素的想法是：直接使用synchronized关键字锁定这块代码。可是这样做的话，效率实在是太低了。

Java的线程是直接映射到操作系统的线程的，我们每一次对Java线程的阻塞和唤醒都需要操作系统从用户态转化到内核态。这种状态转换是及其浪费时间的，甚至有的时候会比执行业务代码还要耗时。

那有没有一种方法，既可以控制多线程下的共享资源安全性，又可以不阻塞Java线程呢？

答案呼之欲出，就是CAS算法。

CAS（Compare-And-Swap）是一种用于实现无锁并发算法的技术。它是一种乐观锁的实现方式。

所谓的乐观锁，就是乐观的认为多个线程之间不会引发共享资源的异常。

核心思想是通过比较当前需要修改的值与预期原来的值，如果两者相等，则将当前值更新为新值，这一过程是原子性的。CAS操作包含三个关键参数：内存位置（V）、预期数值（E）和新数值（N）。当内存位置的数值等于预期数值时，将内存位置的值替换为新数值；如果不相等，则不做任何操作，通常意味着有其他线程已经修改了该值

我们可以用图来表示CAS的操作：

A和B就代表两条线程，而C就代表此时A和B争抢的资源文件，如果A线程运气好抢到了资源C，他将会把自身的old value 与C进行对比，如果一致，就把C的状态改为1，并且获得对C的操作权。

而此时B再与C进行比较，0！=1，因此B就会放弃swap操作，但是在实际操作中，B并不会就直接放弃，而是让其进行自旋，所谓的自旋就是不断进行CAS操作，假如C的状态后面变为0，B就又会重新进行比较和交换操作

我们可以用代码表示这段逻辑：

int cas(long * addr ,long oldvalue,long newvalue)
{
    if(*addr != old)
        return 0;
    *addr= new ;
    return 1;

这段代码展示了CAS的核心思想：对比并交换。但是不要想当然的认为这段代码中的操作是原子性的。

这不就回到先有鸡还是先有蛋的问题了？

不过我们不用担心这个，CAS一般都是在硬件上实现的，天生具备原子性。在Java中，CAS被放到了Unsafe这个类下：

在JUC包下，大量的锁的底层实现都用到了CAS操作，比如Reentrantlock的公平锁：

当你了解CAS的机制后，我们就可以自己设计一个简单的锁：

public class MyLocks {
    int statue =0;
    public void lock()
    {
        while ( statue!=0)
        {
            System.out.println(Thread.currentThread().getName()+"等待锁");
        }
        statue=1;
    }
    public void unlock()
    {
        statue=0;
    }
}

让我们替换这个类中加锁lock方法中的CAS操作为原子性CAS:

public class LiLock {
    private static Unsafe unsafe;
    volatile  int statue =0;
 
    static {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            unsafe = (Unsafe) field.get(null);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    long objectOffset = unsafe.objectFieldOffset(LiLock.class.getDeclaredField("statue"));
 
    public LiLock() throws NoSuchFieldException {
 
    }
 
    public void lock() throws NoSuchFieldException {
 
        while (!unsafe.compareAndSwapInt(this, objectOffset, 0, 1))
        {
            System.out.println(Thread.currentThread().getName()+" is waiting");
        }
    }
    public void unlock() {
        statue=0;
    }
}

但CAS并不是一个完美的算法，他也有自己的问题。那就是ABA问题。

所谓的ABA问题，就是说CAS在修改的时候，只会比较内存位置的数值是否等于预期数值，并不会关心数值变化的过程。

这就会造成一个问题：