深入解析 volatile 、CAS 的实现原理

忘是亡心i 2022-11-12 02:41 227阅读 0赞

在分析说明 volatile 和 CAS 的实现原理前，我们需要先了解一些预备知识，这将是对 volatile 和 CAS 有深入理解的基石。

### 预备知识 ###

缓存

现代处理器为了提高访问数据的效率，在每个CPU核心上都会有多级容量小，速度快的缓存（分别称之为L1 cache，L2 cache，多核心共享L3 cache等），用于缓存常用的数据。

缓存系统中是以缓存行(cache line)为单位存储的。缓存行是 2 的整数幂个连续字节，一般为 32-256 个字节。最常见的缓存行大小是 64个字节。

因此当CPU在执行一条读内存指令时，它是会将内存地址所在的缓存行大小的内容都加载进缓存中的。也就是说，一次加载一整个缓存行。

但写操作就比较复杂了。写操作有两种基本的模式：  
① 直写（write-through）  
直写是透过本级缓存，直接把数据写到下一级缓存（或直接到内存）中，如果对应的段被缓存了，我们同时更新缓存中的内容（甚至直接丢弃）。  
**所以，直写时缓存行永远和它对应的内存内容匹配。**  
② 回写（write-back）  
缓存不会立即把写操作传递到下一级，而是仅修改本级缓存中的数据，并且把对应的缓存段标记为“脏”段。脏段会触发回写，也就是把里面的内容写到对应的内存或下一级缓存中。回写后，脏段又变“干净”了。当一个脏段被丢弃的时候，总是先要进行一次回写。  
**也就是说，回写模式中要么缓存段的内容和内存一致（如果缓存段是干净的话）；要么缓存段中的内容最终要回写到内存中（对于脏缓存段来说）。**

缓存一致性协议

在多核处理器系统中，每个处理器核心都有它们自己的一级缓存、二级缓存等。这样一来当多个处理器核心在对共享的数据进行写操作时，就需要保证该共享数据在所有处理器核心中的可见性/一致性。  
**『 窥探技术 + MESI协议 』的出现，就是为了解决多核处理器时代，缓存不一致的问题的。**

窥探技术

“窥探”背后的基本思想是，所有内存传输都发生在一条共享的总线上，而所有的处理器都能看到这条总线：缓存本身是独立的，但是内存是共享资源，所有的内存访问都要经过仲裁（arbitrate）：同一个指令周期中，只有一个缓存可以读写内存。窥探技术的思想是，缓存不仅仅在做内存传输的时候才和总线打交道，而是不停地在窥探总线上发生的数据交换，跟踪其他缓存在做什么。所以当一个缓存代表它所属的处理器去读写内存时，其他处理器都会得到通知，它们以此来使自己的缓存保持同步。只要某个处理器一写内存，其他处理器马上就知道这块内存在它们自己的缓存中对应的缓存行已经失效。

MESI协议

我们知道，缓存系统操作的最小单位就是缓存行，而MESI是缓存行四种状态的首字母缩写，任何多核系统中的缓存行都处于这四种状态之一。  
① **失效（Invalid）缓存行**：该处理器缓存中无该缓存行，或缓存中的缓存行已经失效了。  
② **共享（Shared）缓存行**：缓存行的内容是同主内存内容保持一致的一份拷贝，在这种状态下的缓存行只能被读取，不能被写入。多组缓存可以同时拥有针对同一内存地址的共享缓存行。  
③ **独占（Exclusive）缓存行**：和S状态一样，也是和主内存内容保持一致的一份拷贝。区别在于，如果一个处理器持有了某个E状态的缓存行，那其他处理器就不能同时持该内容的缓存行，所以叫“独占”。这意味着，如果其他处理器原本也持有同一缓存行，那么它会马上变成“失效”状态（I状态）。  
④ **已修改（Modified）缓存行**：属于脏段，该缓存行已经被所属的处理器修改了。如果一个缓存行处于已修改状态，那么它在其他处理器缓存中的拷贝马上会变成失效状态，这个规律和E状态一样。此外，已修改缓存行如果被丢弃或标记为失效（即，从M状态 ——> I状态），那么先要把它的内容回写到内存中 ———— 这和回写模式下常规的脏段处理方式一样。

只有当缓存行处于E或M状态时，处理器才能去写它，也就是说只有这两种状态下，处理器是独占这个缓存行的。当处理器想写某个缓存段时，如果它没有独占权，它必须先发送一条“我要独占权”的请求给总线，这会通知其他处理器，把它们拥有的同一缓存行的拷贝失效（I状态），如果它们有的话。只有在获得独占权后，处理器才能开始修改数据。并且此时，这个处理器知道，这个缓存行只有一份拷贝，在我自己的缓存里，所以不会有任何冲突。反之，如果有其他处理器想读取这个缓存行（我们马上能知道，因为我们一直在窥探总线），独占或已修改的缓存行必须先回到“共享”状态。如果是已修改的缓存段，那么还要先把内容回写到内存中。

原子操作

原子（atomic）本意是“不能被进一步分割的最小粒子”，而原子操作（atomic operation）意为“不可被中断的一个或一系列操作”。

好了，有了上面这些浅显理论基础之后，让我们开始本文主题的探讨。

### volatile的内存语义 ###

volatile变量自身具有下列特性：

① **可见性/一致性**：对一个 volatile 变量的读，总是能看到(**任意线程**)对这个 volatile 变量最后的写入。  
② **原子性**：对任意单个 volatile 变量的读/写具有原子性，但类似于 **volatile++**这种复合操作**不具有原子性**。

volatile 写-读建立的 happens before 关系

happens-before 规则中有这么一条：  
volatile变量规则：对一个volatile域的写，happens-before于任意后续对这个volatile域的读。  
  
  
happens-before的这个规则会保证volatile写-读具有如下的内存语义：

*  volatile写的内存语义：  
    当写一个 volatile 变量时，JMM 会把该线程对应的本地内存中的共享变量值刷新到主内存。
 *  volatile读的内存语义：  
    当读一个 volatile 变量时，JMM 会把该线程对应的本地内存置为无效。线程接下来将从主内存中读取共享变量。

volatile内存语义的实现原理

为了实现 volatile 的内存语义，编译器在生成字节码时，会在指令序列中插入内存屏障来禁止特定类型的处理器重排序。因为内存屏障是一组处理器指令，它并不由JVM直接暴露，因此JVM会根据不同的操作系统插入不同的指令以达成我们所要内存屏障效果。

为了保证内存可见性，java编译器在生成指令序列的适当位置会插入内存屏障指令来禁止特定类型的处理器重排序。JMM把内存屏障指令分为下列四类：

![74223b8526be7a8fef6036b5a6424d43.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NodWl4dWUyNA_size_16_color_FFFFFF_t_70][]

下面是基于保守策略的JMM内存屏障插入策略：  
在每个volatile写操作的前面插入一个StoreStore屏障。  
在每个volatile写操作的后面插入一个StoreLoad屏障。  
在每个volatile读操作的后面插入一个LoadLoad屏障。  
在每个volatile读操作的后面插入一个LoadStore屏障。

上述内存屏障插入策略非常保守，但它可以保证在任意处理器平台，任意的程序中都能得到正确的volatile内存语义。由于不同的处理器有不同“松紧度”的处理器内存模型，内存屏障的插入还可以根据具体的处理器内存模型继续优化。

在X86处理器上实现volatile的内存语义

在X86中，JMM仅需在volatile写后面插入一个StoreLoad屏障即可正确实现volatile写-读的内存语义。这是因为X86不会对读-读，读-写和写-写操作做重排序，因此在X86处理器中会省略掉这三种操作类型对应的内存屏障。

这里需要再次强调说明的是，内存屏障是一组处理器指令，而上面的四种内存屏障（StoreStore、StoreLoad、LoadLoad、LoadStore）这是JMM内存屏障的一种分类，在不同的处理器中，会转换成相应处理器对应的该内存屏障类型的指令。比如，同样是StoreLoad屏障，在SPARC中的指令是membar、在Xeon中的指令是mfence、在Itanium中的指令是mf。

在X86处理器上执行volatile写操作时会插入一个带有lock前缀（汇编指令）来实现volatile的内存语义的。如，『0x01a3de24: lock addl $0x0,(%esp);』  
至于lock前缀是如何保证volatile的内存语义（包括volatile自身的特定以及volatile 写-读建立的 happens before 的内存语义），将在下面介绍CAS时对lock前缀进行一个详细的说明。

### CAS ———— compareAndSet ###

/**
      * Atomically sets the field of the given object managed by this updater
      * to the given updated value if the current value {@code ==} the
      * expected value. This method is guaranteed to be atomic with respect to
      * other calls to {@code compareAndSet} and {@code set}, but not
      * necessarily with respect to other changes in the field.
      *
      * @param obj An object whose field to conditionally set
      * @param expect the expected value
      * @param update the new value
      * @return {@code true} if successful
      * @throws ClassCastException if {@code obj} is not an instance
      * of the class possessing the field established in the constructor
    */
    public abstract boolean compareAndSet(T obj, int expect, int update);

以原子的方式更新这个更新器所管理的对象(obj)的成员变量，并且将这个成员变量更新为给定的更新后的值(update)如果当前值等于期望值(expect)时。  
当存在其他使用‘compareAndSet’或者’set’的情况下，这个方法可以确保是原子的，但如果你用其他的方式去改变这个成员变量时(如，使用直接赋值的方式 field=newField)，那么它是不会遵循这个原子性的。同时，该操作具有volatile 读和写的内存语义。

前面我们已经介绍了原子操作的概念，所以这里CAS涉及的两步：a) 只有field的值为expect时；b) 将field的值修改为update的值；将视为一个原子操作。

处理器如何实现原子操作

首先处理器会自动保证基本的内存操作的原子性。同时，处理器提供**总线锁定**和**缓存锁定**两个机制来保证复杂内存操作的原子性。  
① 使用总线锁保证原子性  
所谓总线锁就是使用处理器提供的一个LOCK＃信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住,那么该处理器可以独占使用共享内存。

② 使用缓存锁保证原子性  
在同一时刻我们只需保证对某个内存地址的操作是原子性即可，但总线锁定把CPU和内存之间通信锁住了，这使得锁定期间，其他处理器不能操作其他内存地址的数据，所以总线锁定的开销比较大，最近的处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。  
在奔腾6和最近的处理器中可以使用“缓存锁定”的方式来实现复杂的原子性。所谓“缓存锁定”就是如果缓存在处理器缓存行中内存区域在LOCK操作期间被锁定，当它执行锁操作回写内存时，处理器不在总线上声言LOCK＃信号，而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改被两个以上处理器缓存的内存区域数据，当其他处理器回写已被锁定的缓存行的数据时会起缓存行无效。

在JDK 8，Linux操作系统，X86处理器环境下，CAS的源码如下：

// Adding a lock prefix to an instruction on MP machine
    #define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "
    
    inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
      int mp = os::is_MP();
      __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                        : "=a" (exchange_value)
                        : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                        : "cc", "memory");
      return exchange_value;
    }

程序会根据当前处理器的类型来决定是否为cmpxchg指令添加lock前缀。如果程序是在多处理器上运行，就为cmpxchg指令加上lock前缀（lock cmpxchg）。反之，如果程序是在单处理器上运行，就省略lock前缀（单处理器自身会维护单处理器内的顺序一致性，不需要lock前缀提供的内存屏障效果）。

cmpxchgl的详细执行过程：  
首先，输入是"r" (exchange\_value), "a" (compare\_value), "r" (dest), "r" (mp)，表示compare\_value存入eax寄存器，而exchange\_value、dest、mp的值存入任意的通用寄存器。嵌入式汇编规定把输出和输入寄存器按统一顺序编号，顺序是从输出寄存器序列从左到右从上到下以“%0”开始，分别记为%0、%1···%9。也就是说，输出的eax是%0，输入的exchange\_value、compare\_value、dest、mp分别是%1、%2、%3、%4。  
因此，cmpxchgl %1,(%3)实际上表示cmpxchgl exchange\_value,(dest)，此处(dest)表示dest地址所存的值。需要注意的是cmpxchgl有个隐含操作数eax，其实际过程是先比较eax的值(也就是compare\_value)和dest地址所存的值是否相等，如果相等则把exchange\_value的值写入dest指向的地址。如果不相等则把dest地址所存的值存入eax中。  
输出是"=a" (exchange\_value)，表示把eax中存的值写入exchange\_value变量中。  
Atomic::cmpxchg这个函数最终返回值是exchange\_value，也就是说，如果cmpxchgl执行时compare\_value和dest指针指向内存值相等则会使得dest指针指向内存值变成exchange\_value，最终eax存的compare\_value赋值给了exchange\_value变量，即函数最终返回的值是原先的compare\_value。此时Unsafe\_CompareAndSwapInt的返回值(jint)(Atomic::cmpxchg(x, addr, e)) == e就是true，表明CAS成功。如果cmpxchgl执行时compare\_value和(dest)不等则会把当前dest指针指向内存的值写入eax，最终输出时赋值给exchange\_value变量作为返回值，导致(jint)(Atomic::cmpxchg(x, addr, e)) == e得到false，表明CAS失败。

lock前缀

lock前缀的指令的说明：  
① **保证指令的执行的原子性**  
带有lock前缀的指令在执行期间会锁住总线，使得其他处理器暂时无法通过总线访问内存。很显然，这会带来昂贵的开销。从Pentium 4，Intel Xeon及P6处理器开始，intel在原有总线锁的基础上做了一个很有意义的优化：如果要访问的内存区域（area of memory）在lock前缀指令执行期间已经在处理器内部的缓存中被锁定（即包含该内存区域的缓存行当前处于独占或以修改状态），并且该内存区域被完全包含在单个缓存行（cache line）中，那么处理器将直接执行该指令。由于在指令执行期间该缓存行会一直被锁定，其它处理器无法读/写该指令要访问的内存区域，因此能保证指令执行的原子性。  
② **禁止该指令与之前和之后的读和写指令重排序**  
在AI-32架构软件开发者手册第8中内存排序中，有说明LOCK前缀会禁止指令与之前和之后的读和写指令重排序。这相当于JMM中定义的StoreLoad内存屏障的效果。也正是因为这个内存屏障的效果，会使得线程把其写缓冲区中的所有数据刷新到内存中。注意，这里不是单单被修改的数据会被回写到主内存，而是写缓存中所有的数据都回写到主内存。  
而将写缓冲区的数据回写到内存时，就会通过缓存一致性协议（如，MESI协议）和窥探技术来保证写入的数据被其他处理器的缓存可见。  
而这就相当于实现了volatile的内存语义。是的，上面我们为说明的lock前缀是如何实现volatile的内存语义就是这么保证的。

所以，我们可以知道CAS的指令的原子性，以及内存语义就是通过lock前缀指令来完成的。

### 解惑 ###

怎么说了，由于笔者对操作系统以及C++的一无所知，以至于在看《Java 并发编程的艺术》以及相关的一些文章，要么会漏掉一些细节，要么就是独立的概念看着好像都懂，但串起来就蒙圈了。。。 这里，暂且记录一些笔者非常粗浅的认知。

① 处理器上有一套完整的协议，来保证Cache一致性。比较经典的Cache一致性协议当属MESI协议。也就是说，MESI协议是处理器自身会遵循的一个缓冲一致性协议。

② lock前缀 本身带有全屏障的效应，所以不会在lock前缀指令后再插入内存屏障指令

③ Q：既然处理器本身已经维护了缓存的一致性，那为什么还会出现多线程操作两个共享变量时出现“预期之外”的结果了？（这里共享变量不带有volatile，并且操作不加锁以及序列化流程控制）  
比如：  
简单说，初始时x=0, y=0  
p0处理器做  
x = 1  
r1 = x  
r2 = y  
p1处理器做  
y = 1  
r3 = y  
r4 = x  
最后结果可以出现r2 = 0且r4 = 0的情况。

A：是这样的，线程的本地内存是JMM的一个抽象概念，并不真实存在。它涵盖了缓存，写缓冲区，寄存器以及其他的硬件和编译器优化。同时，现代的处理器使用写缓冲区来临时保存向内存写入的数据。写缓冲区可以保证指令流水线持续运行，它可以避免由于处理器停顿下来等待向内存写入数据而产生的延迟。  
所以说，如果在没加锁的话，p0处理器可能在将\[\_x\]=1写到了写缓冲区后就接着执行后面的指令了，这就使得『\[\_x\]=1』操作并未真的写到主内存中，那么p1处理器就无法看到真实的值。但如果使用锁的话，p0处理器会确保『\[\_x\]=1』操作是已经将数据写到主内存后才往下执行的，同时p1处理器也是保证『\[\_y\]=1』操作是将数据写到主内存了才会往下执行下面的指令。这样一来p0就能看到正确的y值，p1就能看到正确的x值了。

后记

笔者是个计算机基础方面的小白，如果文章有错不吝指教 :)

参考

《Java 并发编程的艺术》  
[http://www.infoq.com/cn/articles/cache-coherency-primer][http_www.infoq.com_cn_articles_cache-coherency-primer]  
[http://blog.csdn.net/prstaxy/article/details/51802220][http_blog.csdn.net_prstaxy_article_details_51802220]  
[https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf][https_www.intel.com_content_dam_www_public_us_en_documents_manuals_64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf]  
[https://www.zhihu.com/question/26848513][https_www.zhihu.com_question_26848513]  
[https://stackoverflow.com/questions/4232660/which-is-a-better-write-barrier-on-x86-lockaddl-or-xchgl][https_stackoverflow.com_questions_4232660_which-is-a-better-write-barrier-on-x86-lockaddl-or-xchgl]

[74223b8526be7a8fef6036b5a6424d43.png]: /images/20221022/eee2a35e29284b1ab526e46fd4d27ab7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NodWl4dWUyNA_size_16_color_FFFFFF_t_70]: /images/20221022/ace40a32e49c4fdc91a9af63bd6cb60f.png
[http_www.infoq.com_cn_articles_cache-coherency-primer]: https://link.jianshu.com?t=http%3A%2F%2Fwww.infoq.com%2Fcn%2Farticles%2Fcache-coherency-primer
[http_blog.csdn.net_prstaxy_article_details_51802220]: https://link.jianshu.com?t=http%3A%2F%2Fblog.csdn.net%2Fprstaxy%2Farticle%2Fdetails%2F51802220
[https_www.intel.com_content_dam_www_public_us_en_documents_manuals_64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf]: https://link.jianshu.com?t=https%3A%2F%2Fwww.intel.com%2Fcontent%2Fdam%2Fwww%2Fpublic%2Fus%2Fen%2Fdocuments%2Fmanuals%2F64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf
[https_www.zhihu.com_question_26848513]: https://link.jianshu.com?t=https%3A%2F%2Fwww.zhihu.com%2Fquestion%2F26848513
[https_stackoverflow.com_questions_4232660_which-is-a-better-write-barrier-on-x86-lockaddl-or-xchgl]: https://link.jianshu.com?t=https%3A%2F%2Fstackoverflow.com%2Fquestions%2F4232660%2Fwhich-is-a-better-write-barrier-on-x86-lockaddl-or-xchgl