关于CAS交换算法的理解

闲来无事，特意看了几页java并发编程的艺术，感触很多，发现大神写的文章解惑了之前许多问题，憋说话，直接进入主题！

一、基础知识（必备）

参考文章：https://blog.csdn.net/weixin_43618070/article/details/89206134?utm_source=po_vip
1.0计算机存储体系

在多CPU的计算机中，每个CPU都对应自己的寄存器。现代处理器，一般将cache分为2~3级，L1, L2, L3。L1一般为CPU专有，不在多个CPU*享。L2 cache一般是多个CPU共享的。L1 cache, L2 cache, L3 cache,级别越低，离cpu越近

2.0 缓存cache的逻辑结构

内存地址的简单结构

一个cache被分为S个组，每个组有E个cacheline，而一个cacheline中，有B个存储单元，现代处理器中，这个存储单元一般是以字节(通常8个位)为单位的，也是最小的寻址单元。因此，在一个内存地址中，中间的s位决定了该单元被映射到哪一组，而最低的b位决定了该单元在cacheline中的偏移量。valid通常是一位，代表该cacheline是否是有效的(当该cacheline不存在内存映射时，当然是无效的)。tag就是内存地址的高t位，因为可能会有多个内存地址映射到同一个cacheline中，所以该位是用来校验该cacheline是否是CPU要访问的内存单元。

当tag和valid校验成功是，我们称为cache命中，这时只要将cache中的单元取出，放入CPU寄存器中即可。

当tag或valid校验失败的时候，就说明要访问的内存单元(也可能是连续的一些单元，如int占4个字节，double占8个字节)并不在cache中，这时就需要去内存中取了，这就是cache不命中的情况(cache miss)。当不命中的情况发生时，系统就会从内存中取得该单元，将其装入cache中，与此同时也放入CPU寄存器中，等待下一步处理。

2.0 CPU简单的工作原理

1、取指令：CPU的控制器从内存读取一条指令并放入指令寄存器。指令的格式一般是这个样子滴：

操作码就是汇编语言里的mov,add,jmp等符号码；操作数地址说明该指令需要的操作数所在的地方，是在内存里还是在CPU的内部寄存器里。
2、指令译码：指令寄存器中的指令经过译码，决定该指令应进行何种操作(就是指令里的操作码)、操作数在哪里(操作数的地址)。
3、 执行指令，分两个阶段“取操作数”和“进行运算”。
4、 修改指令计数器，决定下一条指令的地址。
详细了解可以自己百度！

二、主题（CAS算法理解—乐观锁）

参考文章：https://blog.csdn.net/qq_42370146/article/details/105559575?utm_source=po_vip

标准的解释：
它包含 3 个参数 CAS（V，E，N），V表示要更新变量的值，E表示预期值，N表示新值。仅当 V值等于E值时，才会将V的值设为N，如果V值和E值不同，则说明已经有其他线程完成更新，则当前线程则什么都不做，最后CAS 返回当前V的真实值。

理解：
刚才基础知识里面就介绍了关于缓存的基础知识了。上面的V就是多个线程共享的变量值，是保存在主存（内存）上的，而E就是每个线程自己保留的副本（注意：每个线程都有自己的独立内存的），N就是线程要准备更新的值。线程先比较自己的副本是不是跟主存的一致，一致的话就会将自己要更新的N值刷新到主存中去，不一致就刷新失败。

当多个线程同时使用CAS 操作一个变量时，最多只有一个会胜出，并成功更新，其余均会失败。失败的线程不会挂起，仅是被告知失败，并且允许再次尝试（自旋），当然也允许实现的线程放弃操作。基于这样的原理，CAS 操作即使没有锁，也可以避免其他线程对当前线程的干扰。
举例：
假设有一个大黑板（主内存），大黑板原先是贴着小王的照片，在某一个时刻，有小李，小明，以及小可爱同时来到黑板前，他们每个人口袋都有小王的照片，现在他们都想去把小王的照片换下来，然而是小可爱先抢到黑板的使用权，他拿出口袋里面原先小王的照片，发现跟黑板的小王照片一模一样，于是他确定这个黑板的照片还没有被人改过，他马上撤下小王的照片，换上自己小可爱的照片，这样，小可爱就成功换上了自己的照片并走开了，这个时后小李以及小明就发现照片被人修改了，暂时改不了拉，只能将原先下王的照片换成小可爱的照片，然后继续抢占黑板的使用权。

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

深入理解：
我们都说CAS其实归于硬件层面实现的一致性的，那么到底是怎么实现的呢。在java中有这样一个类Unsafe，里面有一个本地方法：
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
其实就是这个CAS的算法实现，这个本地方法看不了，要想看，只能去虚拟机的源码中看了，这个我就百度了下他的具体源码，如下：

我们发现有一条cmpxchg这条汇编语言命令，他是可以直接操作内存进行数据交换，实现CAS最终目的。

（一条汇编指令对应一条CPU指令，是单步操作，自然是原子性的，因此CAS实现是在硬件层面上的）

这么说了这么一大堆，其实好像还没有怎么用到上面的缓存，其实CAS的实现最主要还是利用了缓存一致性的原理去实现的（比如Intel64处理器使用MESI（修改，独占，共享，无效）控制协议去维护内部缓存和其他处理器缓存一致性）。在多核处理器系统中进行操作的时候，Intel64处理器是能察觉到其他处理器访问系统内存和他们的内部缓存的。处理器使用嗅探技术保证他的内部缓存、系统缓存和其他处理器的缓存的数据在总线上是一致的。

关于 cmpxchg()函数的源码：

这个lock前缀指令作用在《java并发编程的艺术》里面就有介绍他的作用：
Lock在这里的作用：
1、在cmpxchg执行期间，锁住内存地址，其他处理器不能访问该内存，保证原子性。
（这个就是保证CAS原子性的关键所在）
2、写内存屏障，保证每个线程的本地空间与主存一致。
3、禁止cmpxchg与前后任何指令重排序，防止指令重排序

最后说说他的缺点：
CAS虽然高效地解决了原子操作，但是还是存在一些缺陷的，主要表现在三个方面：

1.自旋时间太长

如果CAS一直不成功呢？这种情况绝对有可能发生，如果自旋CAS长时间地不成功，则会给CPU带来非常大的开销。在JUC中有些地方就限制了CAS自旋的次数，例如BlockingQueue的SynchronousQueue。

2.只能保证一个共享变量原子操作
看了CAS的实现就知道这只能针对一个共享变量，如果是多个共享变量就只能使用锁了，当然如果你有办法把多个变量整成一个变量，利用CAS也不错。例如读写锁中state的高低位。（https://www.cnblogs.com/wait-pigblog/p/9350569.html）