前言事情是这样的，一位读者看了我的一篇文章，不同意我文章中的观点，于是就有了交流后。也许是我发的狗头表情让这位读者觉得我不尊重他。于是，这位读者一气之下删了我，让我先回家种地再删好友。说实话，我承认你说我做饭，但你要我回家种地，我不懂。为什么要回家种地？养猪不是比种地更赚钱吗？我想了半天也没明白。突然，看到新闻，顿时明白了读者们的用心良苦。因此，我决定写这篇文章来分析读者提出的几个问题。读者观点读者的几个观点：volatile关键字的底层实现是lock指令。lock指令触发缓存一致性协议JMM，由缓存一致性协议保证。先说下我的看法：第一点我觉得是的，这个我在volatile的文章里也说过了。volatile的底层实现是锁前缀指令。第二点我认为是错误的。第三点我认为是错误的。至于我为什么这么想，我给你讲道理，毕竟我们都是有理性的人不是吗？读者的观点围绕着“缓存一致性协议”展开，OK，那我们就从缓存一致性协议说起吧！从字面上看，缓存一致性协议是“用来解决CPU的缓存不一致问题的协议”。拆开这句话，有几个问题：为什么CPU在运行时需要缓存？为什么缓存不一致？有哪些方法可以解决缓存不一致的问题？让我们一一分析。为什么需要缓存CPU是一个运算单元，主要负责计算；内存是一种存储介质，负责存储数据和指令；在没有缓存的时代，CPU和内存是这样协同工作的：一句话概括就是：CPU运行速度很高，但是取数据的速度很慢，严重浪费CPU性能。那我们该怎么办呢？在工程上，解决速度不匹配的方法主要有两种，即物理适配和空间缓冲。物理适配很好理解，多级机械齿轮就是物理适配的典型例子。至于空间缓冲区，更多的是用在软件和硬件上，CPU多级缓存就是一个经典的代表。什么是CPU多级缓存？简单来说，就是基于时间=距离/速度的公式。通过在CPU和内存之间设置多层缓存，减少取数据的距离，可以更好的适配CPU和内存的速度。由于缓存离CPU更近，结构更合理，缩短了CPU取数据的速度，从而提高了CPU的利用率。同时，由于CPU取数据和指令满足时间局部性和空间局部性，有了缓存后，当对同一个数据进行多次操作时，中间进程可以使用缓存来暂存数据，进一步分配时间=距离/速度距离，更好的CPU利用率。时间局部性：如果正在访问一个信息项，则很可能在不久的将来再次访问它。空间局部性：如果引用了一个内存位置，那么它附近的位置将来也会被引用。为什么缓存不一致？CPU利用率的出现有了很大的提高。在单核时代，CPU既享受了缓存带来的便利，又不用担心数据不一致的问题。但这一切的前提都是建立在“单核”之上。多核时代的到来打破了这种平衡。进入多核时代后，首先需要面对的问题是：多个CPU是共享一组缓存还是各自拥有一组缓存？答案是“每个都有一组缓存”。为什么？我们不妨做一个假设，假设多个CPU共享一组缓存，会发生什么情况？如果共享一组缓存，由于低级缓存（靠近CPU的缓存）的空间很小，多个CPU的时间将花费在等待使用低级缓存上，这意味着多个CPU变成串行工作，如果变成串行，就失去了多核并行的本质意义。我们用反证来证明，多个CPU共享一套缓存是不可行的，所以只能让多个CPU各自拥有一套私有缓存。于是，多CPU的缓存结构就变成了这样（多级缓存简化）：这种设计虽然解决了多处理器抢占缓存的问题，但是也带来了一个新的问题，很头疼的数据一致性问题：具体来说，如果多个CPU同时使用某个数据，由于多组缓存的存在，数据可能会不一致。我们可以看下面的例子：假设内存中存入了age=1，CPU0执行age+1操作，CPU1也执行age+1操作。CPU同时给age=1加1。由于多组缓存，CPU之间无法感知到彼此的修改，导致数据不一致，导致最终结果不是预期值。数据一致性问题在没有缓存的情况下也会发生，但在有缓存的情况下会变得尤为严重。数据不一致的问题对程序来说是致命的。所以需要有一个协议，可以让多组缓存看起来像只有一组缓存。于是，缓存一致性协议诞生了。缓存一致性协议缓存一致性协议就是为了解决缓存一致性问题而诞生的。它旨在通过维护多个缓存空间中缓存行的一致视图来管理数据一致性。先补充一下cacheline的概念：cacheline是cache读取的最小单位，cacheline是2个连续字节的整数次方，一般为32-256字节，最常见的cacheline大小为64字节。在Linux系统中，可以使用cat/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size命令查看缓存行大小。Mac系统可以通过sysctlhw.cachelinesize查看缓存行大小。缓存行也是缓存一致性协议管理的最小单元。实现高速缓存一致性协议有两种主要机制，基于目录和总线嗅探。基于目录什么是基于目录？说白了就是用一个目录来记录cacheline的使用情况，然后当CPU要使用某个cacheline的时候，先通过查看目录获取cacheline的使用情况，这样保证数据一致性。目录有六种格式：Fullbitvectorformat、Coarsebitvectorformat、Sparsedirectoryformat、Number-balancedbinarytreeformat、ChaineddirectoryFormat（链式目录格式）有限指针格式（Limitedpointerformat）这些目录的名称是花哨的，但实际上它们并没有那么复杂，只是数据结构和优化方法不同而已。比如全位向量格式，就是用bit来记录每条cacheline是否被某个CPU缓存。后一种格式的目录无非是在存储和可伸缩性方面做了一些优化。记录目录比直接消息通信更耗时，因此基于目录机制实现的缓存一致性协议会有比较高的延迟。但也有一个优点。第三方目录的存在简化了通信过程，通信占用的总线带宽会比较小。因此，基于目录适用于具有大量CPU内核的大型系统。基于总线嗅探的目录依赖实现的缓存一致性协议虽然带宽占用小，但延迟高，不适合作为小型系统的缓存一致性方案。小型系统通常使用基于总线嗅探的缓存一致性。协议。总线是CPU与内存地址和数据交互的桥梁。总线嗅探就是监视这个交互桥梁，及时感知数据的变化。当CPU修改私有缓存中的数据时，它会向总线发送一个事件消息，告诉总线上的其他监听器数据被修改了。当其他CPU感知到它们的私有缓存中有数据的修改副本时，它们可以更新缓存副本或使缓存副本无效。更新缓存副本会产生巨大的总线流量，影响系统的正常运行。因此，当监测到更新事件时，更有可能使私有缓存副本失效，即丢弃数据副本。这种使修改后的数据副本失效的方法有一个专业术语，叫做“write-invalidate”。基于“write-invalidation”的缓存一致性协议称为“write-invalidation”协议。常见MSI、MESI、MOSI、MOESI和MESIF协议都属于此类。MESIMESI协议是一种基于失效的缓存一致性协议。它是支持回写缓存的最常用协议。它也是使用最广泛的缓存一致性协议。它是基于总线嗅探实现的，使用额外的两个位标记每个缓存行的状态，并保持状态的切换，以达到缓存一致性的目的。MESI状态MESI是四个字的缩写，每个字代表缓存行的一个状态：M：修改，已修改。高速缓存行具有与主存储器不同的值。如果其他CPU核心要从主存中读取这块数据，就必须将缓存行写回主存，状态变为共享态（S）。E：排他性的，排他性的。缓存行只在当前缓存中，但与主存数据一致。当其他缓存读取它时，状态变为共享状态；当前写入数据时，它变为已修改(M)。S：共享，共享。缓存行也存在于其他缓存中并且是干净的。缓存行可以随时丢弃。我：无效，无效。缓存行无效。MESI消息在MESI协议中，缓存行状态的切换依赖于消息的传输。MESI有以下几种消息类型：读取：读取某个地址的数据。读取响应：对读取消息的响应。Invalidate：请求其他CPU无效地址对应的cacheline。InvalidateAcknowledge：对Invalidate消息的响应。读取无效：读取+无效消息的组合消息。回写：该消息包含要写回内存的地址和数据。MESI通过消息传递维护一个缓存状态机，实现共享内存。至于具体细节，这里就不多说了。如果你不知道MESI，建议你去这个网站动手实验，可以模拟各种场景，实时生成动画，更容易理解。如果打不开本站，别着急，源码都给你扒了，回复“MESI”自行获取，解压本地运行即可。下面用这个网站来演示一个简单的例子：CPU0读a0CPU1写a0简单分析一下：CPU0读a0，读到Cache0后，因为排他性，缓存行的状态为E。CPU2写a0，先读a0到Cache2，因为是共享的，所以状态为S。然后修改a0的值，cacheline的状态变为E，最后通知CPU0将a0所在的cacheline作废。MESI的存在保证了缓存的一致性，使多核CPU能够更好地与数据进行交互。那是不是CPU被压榨到了极致？答案是否定的，让我们继续。文章的后半部分依赖于上一篇文章中的知识点。如果我的陈述没有让你理解前半部分的知识点，你可以直接翻到总结部分，我在这里准备了一个思路总结。如果你准备好了，让我们继续开车，看看我们还能如何挤压CPU。StoreBuffer由上可知：如果CPU写入了某个数据，而该数据不在私有缓存中，那么CPU会发送ReadInvalidate消息读取相应的数据，并使其他缓存副本失效。但是有一个问题大家想过，就是从发送一条消息到接收到所有的响应消息，中间的等待过程对于CPU来说是漫长的。它能减少CPU等待消息的时间吗？有能力的！存储缓冲区就是为此而生的。你是怎么做到的？存储缓冲区是CPU和缓存之间的结构。CPU写入时，可以直接写入storebuffer，无需等待其他CPU的响应报文。收到响应报文后，将storebuffer中的数据写入cacheline。CPU读取数据时，会先判断storebuffer中是否有数据。如果存在，则首先使用storebuffer中的数据（这种机制称为“storeforwarding”）。这样既提高了CPU的利用率，又保证了读写都可以在同一个CPU上顺序进行。注意这里的读写顺序执行指的是同一个CPU，为什么要强调相同呢？因为，storebuffer的引入并不能保证多个CPU的全局顺序执行。让我们看下面的例子：//CPU0执行voidfoo(){a=1;b=1;}//CPU1执行voidbar(){while(b==0)continue;断言（a==1）；}假设CPU0执行了foo方法，CPU1执行了bar方法，如果在执行前，缓存情况如下：CPU0缓存了b，由于独占状态为E。CPU1缓存了a，因为是独占的，所以状态为E。那么，storebuffer可用后，可能会出现这种情况（简化与内存交互的过程）：换句话说：CPU0执行a=1，因为a不在CPU0的缓存中，有storebuffer，Write直接将a=1写入storebuffer，同时发送readinvalidate报文。CPU1执行while(b==1)，因为b不在CPU1的缓存中，所以CPU1发送一个读报文去读。CPU0收到CPU1的读报文，知道CPU1要读b，于是返回读响应报文，并将对应缓存行的状态变为S。CPU1收到读响应报文，知道b=1，于是将b=1放入缓存中，同时结束while循环。CPU1执行assert(a==1)，从缓存中获取a=0，执行失败。我们从不同的角度来分析分析：从CPU0的角度来看自己：a=1先于b=1，所以当b=1时，a一定已经等于1。从CPU0的角度来看CPU1：因为ab=1时一定等于1，所以当CPU1因为b==1跳出循环后，接下来执行assert肯定是成功的，但实际上失败了，也就是说，站在CPU0的角度来看，CPU1被重新排序。那么如何解决storebuffer的引入带来的全局顺序问题呢？硬件设计者为开发者提供内存屏障（memory-barrier）指令。我们只需要使用内存屏障修改代码，在a=1之后添加smp_mb()即可消除引入storebuffer的影响。.//CPU0执行voidfoo(){a=1;smp_mb();b=1;}//CPU1执行voidbar(){while(b==0)continue;assert(a==1);}memorybarrier是如何实现全局秩序的？有两种方式，等待storebuffer生效和进入storebuffer队列。等待storebuffer生效意味着后续写入内存屏障必须等待storebuffer中的值接收到相应的响应消息并写入cacheline。排队进入storebuffer排队进入storebuffer是指后面的memorybarrier写入直接写入storebuffer并排队，等待storebuffer前面的写入全部写入cacheline。从动画可以看出，两种方法都需要等待，但是等待storebuffer生效是在CPU中，进入storebuffer队列是进入storebuffer等等。因此，排队进入storebuffer会比较高效，大多数系统也采用这种方式。InvalidateQueue内存屏障可以解决storebuffer带来的全局顺序性问题。但是有一个问题，storebuffer的容量很小，如果在其他CPU繁忙的时候响应消息的速度变慢，storebuffer很容易被填满，直接影响CPU的运行效率。怎么做？这个问题的根源是由于消息响应慢导致storebuffer被填满，那么消息响应速度能不能提高呢？有能力的！出现无效队列。invalidatequeue的主要作用是提高invalidate消息的响应速度。有了invalidatequeue，当CPU收到invalidate消息时，可以将消息放入invalidate队列，而不是使对应的cacheline失效，并立即返回InvalidateAcknowledge消息，然后检查是否有Invalidate消息invalidate队列中的cacheline，如果有，此时会处理Invalidate消息。invalidatequeue虽然可以加快invalidate消息的响应速度，但是也带来了一个全局的时序问题，类似于storebuffer带来的全局问题。看下面的例子：//CPU0执行voidfoo(){a=1;smp_mb();b=1;}//CPU1执行voidbar(){while(b==0)continue;assert(a==1);}上面的代码还是假设CPU0执行foo方法，CPU1执行bar方法。如果执行前缓存情况是这样的：那么，创建invalidate队列后，可能会出现这种执行情况：CPU0执行a=1。相应的缓存行在cpu0的缓存中是只读的，因此cpu0将新值a=1放入其存储缓冲区，并发送一条无效消息以从cpu1的缓存中刷新相应的缓存行。当(b==0)继续执行时，CPU1执行，但是包含b的缓存行不在它的缓存中。因此，它发送一条已读消息。CPU0执行b=1。因为这个cacheline已经被缓存了，所以直接更新cacheline，b=0更新为b=1。CPU0收到read消息，将包含b的cacheline发送给CPU1，b所在的cacheline状态变为S。CPU1收到a的invalidate消息，放入自己的invalidate队列，发送一个向CPU0发送无效确认消息。请注意，原始值“a”仍存储在CPU1的缓存中。CPU1收到包含b的缓存行并将其写入其缓存。CPU1现在可以在(b==0)继续时完成执行，因为它发现b的值为1，所以继续执行下一条语句。CPU1执行assert(a==1)，由于原来的值a还在CPU1的缓存中，所以断言失败。cpu1处理队列中的invalidate消息，并从它自己的缓存中使包含a的缓存行无效。但为时已晚。从这个例子可以看出，引入invalidatequeue后，全局顺序又不能保证了。如何解决，解决方法同storebuffer，使用内存屏障改造代码：//CPU0executesvoidfoo(){a=1;smp_mb();b=1;}//CPU1执行voidbar(){while(b==0)continue;smp_mb();assert(a==1);}改造后的运行过程就不过多描述了，总结一下，内存屏障可以解决invalidatequeue带来的全局有序性问题。内存屏障和Lock指令内存屏障由上文可知，内存屏障有两个作用，处理storebuffer和invalidatequeue，维护全局顺序。但是在很多情况下，只需要处理storebuffer和invalidatequeue中的一个，所以很多系统将内存屏障细分为读内存屏障和写内存屏障。读屏障用于处理无效队列，而写屏障用于处理存储缓冲区。场景的X86架构下，不同内存屏障对应的指令有：读屏障：lfence写屏障：sfence读写屏障：mfenceLock指令我们再回顾一下。在之前关于volatile的文章中，我提到volatile关键字的底层实现是lock前缀指令。锁前缀指令和内存屏障有什么关系？我不认为这与它有任何关系。只是lock前缀指令的部分功能可以达到内存屏障的效果。这一点也可以在《IA-32 架构软件开发人员手册》上的对应描述中找到。手册中对锁前缀指令的定义是总线锁，即锁前缀指令通过锁定总线来保证可见性，禁止指令重排序。虽然“总线锁”这个词太老了，但今天的系统更多的是“锁定缓存行”。但我想表达的是，锁前缀指令的核心思想仍然是“锁”，这与内存屏障有着根本的区别。复习题复习一下读者的这两个观点：读者：lock指令触发了缓存一致性协议读者：JMM是由缓存一致性协议保证的。cacheline可以起到和read-writebarrier一样的作用，read-writebarrier解决的问题是storebuffer和invalidatequeue带来的全局顺序性问题。缓存一致性问题用于解决多核系统下的缓存一致性问题。由硬件保证，对软件透明。它是多核系统中客观存在的东西，不需要触发。对于第二种观点，我的看法是：JMM是一种虚拟内存模型，将JVM的运行机制抽象出来，让Java开发者更好的理解JVM的运行机制。它封装了CPU的底层实现，让Java开发者可以更好的进行开发而不用被底层实现细节所折磨。JMM想表达的是，在某种程度上，你可以通过一些Java关键字让Java的内存模型达到强一致性。所以JMM与缓存一致性协议没有联系，本质上与之无关。比如你不能因为你单身就说刘亦菲单身，因为她在等你刘亦菲也单身。综上所述，对于一些没有基础的同学来说，理解起来会有些吃力，所以总结一下全文的思路，应付一般的面试是没有问题的。因为内存的速度跟CPU不匹配，所以在内存和CPU之间加入了多级缓存。独占使用单核CPU不会有数据不一致的问题，但是多核的情况下会有缓存一致性问题。缓存一致性协议是为了解决多组缓存带来的缓存一致性问题。缓存一致性协议有两种实现方式，一种基于目录，另一种基于总线嗅探。基于目录的方式延迟高，但占用总线流量小，适用于CPU核数多的系统。基于总线嗅探的方法延迟低，但占用总线流量大，适用于CPU核数较少的系统。常见的MESI协议是基于总线嗅探实现的。MESI解决了缓存一致性问题，但依然无法将CPU性能压榨到极致。为了进一步压榨CPU，引入了storebuffer和invalidatequeue。storebuffer和invalidatequeue的引入导致全局顺序不满足，所以需要writebarrier和readbarrier。X86架构下读屏障指令为lfenc，写屏障指令为sfence，读写屏障指令为mfence。lock前缀指令直接锁定cacheline，也可以达到内存屏障的效果。x86架构下，volatile的底层实现是锁前缀指令。JMM是一种模型，一种便于Java开发人员开发的抽象模型。缓存一致性协议是为了解决CPU多核系统下的数据一致性问题。它是客观的东西，不需要触发。JMM与缓存一致性协议无关。JMM和MESI没有任何关系。写在上一篇，我主要参考了维基百科和Linux内核大师PaulE.McKenney的论文和书籍。如果想对并发编程底层有更深入的研究，PaulE.McKenney的论文和书籍非常值得。看一下，需要的话后台会回复“MESI”来接。由于作者水平有限，文章中难免有错误。如果你找到了，请指出来！好了，今天的文章到此结束，我是小王，我们下期见！欢迎关注我的个人：CoderW参考资料《深入理解并行编程》《IA-32+架构软件开发人员手册》《Memory Barriers: a Hardware View for Software Hackers》《Is Parallel Programming Hard, And, If So, What Can You Do About It?》
