CAS是什么

Compare and Swap

CAS全称是 Compate and Swap，即”比较并交换“，这个操作的伪代码是这样的：

bool CAS(int* ptr, int expected, int new_value) {
    if (*ptr == expected) {
        *ptr = new_value;
        return true;
    }
    return false;
}

其中，比较操作是为了确认操作数状态没有被改变，以确保原子性。因此CAS是一个原子操作，是一个无锁的原子操作。

CAS是乐观锁

什么是乐观锁？乐观锁的思想是假设操作过程中数据大概率不会被其他线程修改，因此不会预先加锁，而是在提交操作的时候检查数据有没有被改动。如果没被改就操作成功，反之执行错误处理机制。

与之相反的概念是悲观锁，也就是假设冲突频繁，因此操作前会通过加锁锁定资源。

CAS是无锁结构

无锁结构的含义是不依赖互斥锁，从上面的代码可以看到，CAS实现原子性的方式不是通过锁定资源，而是原子操作。 -> 需要注意的是，无锁结构和乐观锁两个概念是不冲突的。非但如此，两者还有一定的关联性。

说”CAS就是自旋锁“是不完全准确的，因为CAS是被用来实现自旋锁的，不是CAS本身就是自旋锁。

为什么需要CAS？

CAS是乐观锁+无锁结构，要理解为什么需要CAS，最好从悲观锁+有锁结构的缺点入手。

性能瓶颈

使用互斥锁Mutex，当锁获取失败时，会导致线程挂起且进行上下文切换，我们知道上下文切换是比较耗费CPU性能的。特别是在高竞争（也就是竞争激烈，多个线程同时抢夺一个资源）时，这种挂起+切换带来的性能开销是无法被忽略的。

与之相较，CAS在写入失败时不会导致线程被挂起，而是会不断重试。在竞争不激烈的场景下，重试的成本要低于线程挂起+切换的成本。

需要注意的是，这个优势会随着竞争的激烈化而减弱。假如有20个线程同时试图修改一个数据，CAS写入成功的概率是要远小于只有2个线程的情况的。在这种情况下，自旋开销可能要高于线程挂起+上下文切换的开销。

不过存在的可能性是，即使在高竞争环境下自旋开销已经显著增加，它还是比线程挂起和切换上下文的开销要小，特别是在线程数远多于CPU核心数时。

这也不难理解，如果线程有很多，自旋机制可以确保一个线程在完成任务前不会主动放弃被执行的机会，那其余线程都只能休眠，不会占用CPU性能。与之对应的是，如果使用互斥锁机制，系统为了保证公平性，会在大量线程之间切换，由此带来高额的管理成本，这个管理成本是可以大幅超越自旋成本的。更别说自旋操作通常很简单，即使成功率下降可能也不低。

死锁风险

如果使用了多个互斥锁，就存在死锁风险，即使通过规定锁定顺序+死锁检测的方法能在一定程度上解决问题，也会增加代码的复杂度。显然使用无锁结构是不存在死锁风险的。

优先级反转

优先级反转的意思是：低优先级的线程持有锁时，可能会造成高优先级的线程被阻塞，破坏系统的调度逻辑。

CAS的缺点

ABA问题

存在一种情况是，线程1将数值改成了A，随后线程2将数值改成B后又改回了A，在这之后线程1再次检查数值，会误以为没有更改。这个就是ABA问题。

常见的解决方法是增加标记，比如版本号，每次修改后自增，通过同时校验版本号和数值来确认数值是否被修改。

这里需要理解的一个关键点问题是：为什么版本号的检查是必要的？

假设线程1需要执行的操作是把数值从A改为B，而线程2需要执行的操作是把B改为A，那增加一个版本号的检查似乎毫无意义。因为不管线程2有没有修改数值，线程1只要确认数值是A，就可以成功写入了。

但只要我们增加场景的复杂度，马上就能发现为什么需要版本号。下面来说明这种情况：

初始状态：共享变量值为A，版本号为1 线程1任务：A->B 线程2任务：A->C 线程3任务：C->A

Step 1：线程1读取，得到版本号1，数值A Step 2：线程2读取，得到版本号1，数值A Step 3：线程2执行CAS，顺利将数值修改为C，版本号递增为2 Step 4：线程3读取，得到版本号2，数值C Step 5：线程3执行CAS，顺利将值改为A，版本号递增为3 Step 6：线程1执行CAS，版本号校验不通过，操作失败。

因为有版本号校验，此时数值为A，而如果没有版本号校验，此时数值为C。

只能保证单个变量的原子性

实际上CAS是一种硬件支持的原子操作，通常由CPU指令实现，指令系统可以保证CAS操作不会被其他线程打断，也限制了只能操作单个内存。也就是说，是硬件限制了CAS无法保证多个变量的原子性，而如果要在硬件层面实现多个变量的原子性需要处理更加复杂的情况。为什么这会是一个缺点呢？因为实际应用中经常需要同时更新多个变量。不过这个问题也能通过结构体（CAS操作的是一个结构体）解决，代价是增加内存开销。或者进行多个CAS操作，代价是需要复杂的逻辑保证操作的一致性。

应用

无锁计数器，比如在多线程下安全地实现自增操作。
通过CAS实现自旋锁（实现方法是只要CAS失败，就自旋等待，类型是Bool）
C++的std::atomic类型就是封装了CAS操作