CAS（比较与交换）

1.什么是CAS

CAS 是 compare and swap 的缩写，即我们所说的比较与交换。CAS 操作包含三个操作数，分别是内存位置（V）、预期原值（A）和新值(B)。当且仅当内存位置的V值和预期原值A相等的时候，那么就将内存里面的值V更新成新值B。其实现方式是通过C++调用CPU指令完成的，所以效率较高。基于乐观锁操作，通过某种方式不加锁来处理资源，比如通过给记录加上version来获取数据，性能较悲观锁有很大提高。

当多个线程同时使用CAS 操作一个变量时，只有一个线程会胜出，并成功更新，其余线程均会失败。但是失败的线程不会挂起，仅是被告知失败，并且允许再次尝试，当然也允许实现的线程放弃操作。基于这样的原理，CAS 操作即使没有锁，也可以发现其他线程对当前线程的干扰。

与锁相比，使用CAS会使程序看起来更加复杂一些，但由于其非阻塞的，它对死锁问题天生免疫，并且，线程间的相互影响也非常小。更为重要的是，使用无锁的方式完全没有锁竞争带来的系统开销，也没有线程间频繁调度带来的开销，因此，他要比基于锁的方式拥有更优越的性能。

2.CAS的底层原理

实际上，我们可以使用同步将这两个操作变成原子的，但是这么做就没有意义了。所以我们只能靠硬件来完成，硬件可以保证一个从语义上看起来需要多次操作的行为只通过一条处理器指令就能完成。这类指令常用的有：

1.测试并设置（Tetst-and-Set）

2.获取并增加（Fetch-and-Increment）

3.交换（Swap）

4.比较并交换（Compare-and-Swap）

5.加载链接/条件存储（Load-Linked/Store-Conditional）

CPU 实现原子指令有2种方式：

1.通过总线加锁来保证原子性。

其实就是处理器使用了总线锁，所谓总线锁就是使用处理器提供的一个 LOCK# 信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占共享内存。但是该方法成本太大。因此有了下面的方式。

2、通过缓存锁定来保证原子性。

指内存区域如果被缓存在处理器的缓存行中，并且在Lock 操作期间被锁定，那么当他执行锁操作写回到内存时，处理器不在总线上声言 LOCK# 信号，而时修改内部的内存地址，并允许他的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改两个以上处理器缓存的内存区域数据（这里和 volatile 的可见性原理相同），当其他处理器回写已被锁定的缓存行的数据时，会使缓存行无效。

注意：有两种情况下处理器不会使用缓存锁定。

1.、当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行时，则处理器会调用总线锁定。

2.、有些处理器不支持缓存锁定，对于 Intel 486 和 Pentium 处理器，就是锁定的内存区域在处理器的缓存行也会调用总线锁定。

3.CAS的缺点

CAS虽然高效地解决了原子操作，但是还是存在一些缺陷的，主要表现在三个方法：循环时间太长、只能保证一个共享变量原子操作、ABA问题。（ABA问题：CAS需要检查操作值有没有发生改变，如果没有发生改变则更新。但是存在这样一种情况：如果一个值原来是A，变成了B，然后又变成了A，那么在CAS检查的时候会发现没有改变，但是实质上它已经发生了改变，这就是所谓的ABA问题。对于ABA问题其解决方案是加上版本号，即在每个变量都加上一个版本号，每次改变时加1，即A —> B —> A，变成1A —> 2B —> 3A）