c语言一维数组怎么快速排列
242
2022-12-01
说透缓存一致性与内存屏障
说透缓存一致性与内存屏障
故事还得从一个矛盾说起。
摩尔定律告诉我们：大约每18个月会将芯片的性能提高一倍。芯片的这种飞速发展直接导致了芯片的指令执行速度与内存读取速度之间的巨大鸿沟。
举个例子，CPU在1纳秒之内可以执行几十条指令，但是从内存中读取一条数据就需要花费几十纳秒。这种数量级的差异便是计算机中的一个主要矛盾：
CPU日益增长的对数据快速读取的需要和I/O设备读取速度不平衡不充分的发展之间的矛盾
而CPU运行所需要的指令和数据都存储在低速的内存中，人们无法容忍让CPU这样宝贵的高速设备进行漫长的等待。
计算机科学领域的任何问题都可以通过增加一个中间层来解决。所以需要一个比内存更快的存取设备做缓冲，尽量做到和CPU一样快，这样就不需要每次都从低速的内存中获取数据了。
于是引入了高速缓存。
1. 高速缓存
我们已经知道为什么需要高速缓存了。那么什么是高速缓存？它为什么就比内存快？既然这么快，为什么不直接当成内存用？
别急，我一点点解释。
1.1. 什么是高速缓存Cache
我们最熟悉的内存是一种动态随机访问存储器（Dynamic RAM,DRAM） ，存储器中每个存储单元由配对出现的晶体管和电容器构成，每隔一段时间，固定要对DRAM刷新充电一次，否则内部的数据就会消失。
而高速缓存是一种静态随机访问存储器（Static RAM,SRAM） ，不需要刷新电路就能保存它内部存储的数据，这就是静态的含义，因此SRAM的存储性能非常高！工作速度在纳秒级别，勉强能跟得上CPU的运算速度。
但是SRAM的缺点就是集成度低，相同容量的内存可以设计成较小的体积，但是SRAM却需要更大的体积；而且，SRAM这玩意儿巨贵！这就是不能直接把它当内存用的原因。
越靠近CPU核心地带的设备越需要强悍的性能，可是容量如果太小又帮不上太大的忙。如果一个中间层（一层高速缓存）不能高效解决问题，那就多来几个中间层。目前CPU的解决思路一般是以量取胜，比如同时设置L1、L2、L3三级缓存。
在缓存容量上，通常是内存 > L3 > L2 > L1，容量越小速度越快。其中L1和L2是由每个CPU核心独享的，L3缓存是由所有CPU核心共享的。CPU的架构见下图：
需要特别说明的是，L1缓存又分为了L1d数据缓存（L1 Data）和L1i指令缓存（L1 Instruct），上图为了完整性一并画出了，本文中的高速缓存一律指数据缓存。
为了接下来方便讲解，我们把三级缓存模型简化为一级缓存模型，毕竟道理都是相通的嘛。看一下简化之后的图。
简化的高速缓存架构
1.2. 缓存行
说完了什么是Cache，接下来我们来看看Cache里装的到底是什么？
这不是废话嘛，肯定装的是数据啊。没错，是从内存中获取到的数据，但是数据的单位呢？CPU每次只把需要的数据从内存中读取到Cache就行了吗？肯定不是，我们想一下，只把需要的一个数据从内存中读到Cache，CPU再从Cache中继续读这个数据进行处理，Cache的存在完全就是多此一举，还不如直接从内存读数据呢。
所以要想让Cache充分发挥作用，必须让它做点“多余”的事情。因此从内存中获取数据的时候，我们把包含目标数据的一整块内存数据都放入Cache中。别小看这个动作，它有个科学的解释，叫做空间局部性。
位置相邻的数据常常会在相近的时间内被访问
根据空间局部性原理，如果目标数据相邻的数据被访问，CPU就不需要再从内存中获取了，这种直接从Cache中获取到目标数据的行为叫做“缓存命中”，极大地提高了CPU的工作效率。如果Cache里边没有，就称为Cache Miss，CPU需要再等待几十个指令周期从内存中把这一整块内存数据读入Cache。
给存储“一整块内存数据”的地方起个名字，叫「缓存行」（Cache Line）。
Cache是由缓存行组成的，缓存行是CPU高速缓存和内存交互的最小单元。在X86架构中，缓存行的大小是64个字节，大小和CPU具体型号有关。本文只关注缓存行的抽象概念，不涉及具体的缓存行大小。
接下来，终于要进入本文的正式部分了。
我一直认为，计算机的演进就是一部在挖坑和填坑之间反复横跳的发展史。对这一点的理解会随着本文的后续讲述逐渐加深。比如高速缓存Cache很好地解决了CPU与内存的速度矛盾，但是也为计算机系统带来了更高的复杂度，我来举个例子。
2. 伪共享问题
我们到目前为止说的都是CPU从Cache中read数据，但是总得有write的时候吧。既然有了Cache，肯定就得先把值write到Cache中，再更新到内存里啊。那么，问题来了。
2.1. 什么是伪共享
数据X、Y、Z同处于一个缓存行内，Core0和Core1同时加载了该缓存行到Cache中，此时Core0修改了该缓存行中的X为X1，如果此时Core1也想修改Y为Y1该怎么办呢？
由于缓存行是Cache和内存之间交互的最小单元，所以Core0根本不知道Core1修改的是缓存中的Y还是X，所以为了防止造成并发问题，最好的办法就是让Core1中的该缓存行失效，重新加载。这就是伪共享问题。
伪共享问题的定义：当多核心修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。
2.2. 解决伪共享
既然问题是由多个变量共享一个缓存行导致的，那就让Y变量独享一个缓存行就好了。
最简单的方法就是通过代码手动进行字节填充，拿早期的LinkedTransferQueue中的部分源码举个例子，注意看注释内容：
static final class PaddedAtomicReference
此外，JDK 8开始，提供了一个sun.misc.Contended注解来解决伪共享问题，加上这个注解的类会自动补齐缓存行。
稍微扯远了一些，我们回到上方的动图。Core0修改了缓存行中的X，我们说当前最合适的处理办法就是让Core1中的缓存行失效，否则就会出现缓存一致性问题。伪共享问题其实就是解决缓存一致性问题的副作用。只不过本文中我单独把这个问题列了出来。
为了解决缓存一致性问题，CPU天然支持了总线锁的功能。
3. 总线锁
顾名思义就是，锁住Bus总线。通过处理器发出lock指令，总线接受到指令后，其他处理器的请求就会被阻塞，直到此处理器执行完成。这样，处理器就可以独占共享内存的使用。
但是，总线锁有一个非常大的缺点，一旦某个处理器获取总线锁，其他处理器都只能阻塞等待，多处理器的优势就无法发挥。
于是，经过发展、优化，又产生了缓存锁。
4. 缓存锁
缓存锁：不需锁定总线，维护本处理器内部缓存和其他处理器缓存的一致性。相比总线锁，会提高cpu利用率。
但是缓存锁也不是万能，有些场景和情况依然必须通过总线锁才能完成。
缓存锁其实是一种实现的效果，它是通过缓存一致性协议来实现的，可能有的读者也听说过Snoopy嗅探协议，我举个例子帮助大家理解这三个概念。
总线锁&缓存锁&嗅探协议
假如村里有一个单人公厕，一条蜿蜒大道与公厕相连，大道旁边住着A、B、C、D四个人，每个人要上厕所必须经过主干道。
我们再设置一点前提，假设每个人都不想到了厕所门口的时候才知道厕所已经被人占用了。
为了合理使用厕所，保证每次只有一个人进入厕所，并且不会出现其他人在厕所门口等待的情况，ABCD四个人聚在一起开会讨论，协商出了一条约定。
当有人去上厕所的时候，其他人在家老实呆着，不要去上厕所！
四个人纷纷拍着自己大腿叫绝。他们商议出来了一个听起来确实能解决问题，但是实际上内容非常空洞的一个协议。
因为他们不知道现在有谁正在占用厕所，更不知道谁正在前往厕所的路上。
其中A灵机一动，想出了一个办法。可以在每家和主干道的岔路口设置一个监测设备，当有人上厕所经过岔路口的时候监测设备就提醒其他三个人已经有人去厕所了，老实在家等着吧。
如此一来，就达成了一种给厕所添加锁的一种效果，这种效果就相当于上文提到的缓存锁。4人商议出来的协议就相当于缓存一致性协议，A提出来的方法实现了协议，相当于Snoopy嗅探。
如果大家读到这里在思考例子中的厕所究竟表示内存还是缓存行，我劝大家赶紧止住。在生活中找到和计算机科学中非常贴切的例子是非常非常困难的。这个例子只是简单说明一下缓存锁和锁存一致性协议以及Snoopy嗅探协议之间的关系罢了，不要深究！
自然，缓存一致性协议就是我们接下来的主角了。
5. 缓存一致性协议
每个处理器共享同一个主内存，并且都有自己的高速缓存。如果多个处理器都对同一块主内存区域进行更改，将导致各自的的缓存数据不一致。那同步到主内存时该以谁的缓存数据为准呢？
缓存一致性协议就是为了解决这个问题提出的，这类协议有MSI、MESI和MOSI等。
我们以应用最广泛的MESI为例进行介绍。
5.1. MESI
MESI是Modified、Exclusive、Shared、Invalid四个单词的首字母缩写，表示缓存行的4种状态。
Modified
缓存行被对应的CPU核心修改之后就会处于Modified状态，并且保证该缓存行不会出现在任何其他CPU的缓存中。即使有，也是Invalid状态，需要从内存或其他Cache中重新读取。
因此，处于Modified状态的缓存行可以说是被相应CPU核心独占的。由于该缓存行拥有该数据的唯一最新副本，因此该缓存行最终负责将其写回内存或将其传递给其他CPU。
Modified的缓存行
Exclusive
Exclusive状态就非常好理解了，意味着独占、排他，和Modified状态非常类似。唯一不同的一点就是这个缓存行还没有被CPU核心修改，这也说明内存中的内容依然是最新的。即便如此，一旦某个缓存行处于该状态，就意味着其他CPU核心不能拥有该缓存行的副本。
Exclusive缓存行
Shared
处于Shared状态的缓存行意味着同时出现在了一个或多个CPU Cache中，且多个CPU Cache的缓存行和内存中的数据一致。CPU核心不能在未与其他核心“协商”的情况下，修改其Cache中的该缓存行。至于什么是“协商”，下文会讲到。
Shared缓存行
Invalid
处于Invalid状态的缓存行不包含任何数据，只是被打上了Invalid状态的标签而已。其他CPU修改了缓存行，就会导致本CPU中的该缓存行失效为Invalid状态。当有新数据被放入Cache中时，会被优先放入Invalid状态的缓存行中，避免置换出其他有用的缓存导致Cache Miss。
Invalid缓存行
以上4种状态之间的跃迁离不开各个CPU核心之间的协作，比如某个数据被同时缓存在多个CPU核心的Cache中，此时这些缓存行的状态是Shared，假如Core0对缓存行做了write操作，为了避免缓存数据的不一致性，其他CPU核心需要将对应的缓存行状态设置为Invalid状态。那么其他CPU核心是怎么知道Core0修改了缓存行呢？换个问法，Core0怎么让其他核心知道自己修改了缓存行呢？
人有人言，兽有兽语。CPU核心之间的沟通也有自己的一套“黑话”，称为缓存一致性消息。
5.2. CPU之间的“黑话”
消息分为请求和响应两类。
处理器在进行数据读写的时候会往总线（Bus）中发请求消息，同时每个处理器核心还会嗅探（Snoop）总线中由其他处理器发出的请求消息并在一定条件下往总线中回复响应消息。
Read
Read消息表示要读取某个缓存行，同时会携带目标缓存行对应的物理地址。
Read Response
是对Read消息的反馈，反馈的内容就是发送Read消息的CPU核心请求的目标缓存行。Read Response可能来自于内存，也可能来自其他CPU核心。
比如，如果被请求的目标缓存行不存在于任何CPU Cache中，那么只能从内存中获取；如果被请求的目标缓存行恰好被其中一个CPU修改，此时该缓存行为Modified状态，意味着该缓存行目前是最新数据，那么理应让其他同样需要该缓存行的CPU核心获取到该最新数据，更进一步，自然理应由该CPU核心把该缓存行的内容反馈给发出Read消息的CPU核心。
Invalidate
Invalidate的含义是使某个缓存行失效，拥有该缓存行的其他CPU核心需要删除该缓存行中的数据，并对发出Invalidate消息的核心做出反馈。
Invalidate Acknowledge
这就是上面提到的Invalidate消息的反馈，意味着发出此消息的CPU核心已经将Invalidate消息的目标缓存行中的数据清除。
如果有多个CPU同时发出Invalidate消息怎么办？答案是总线裁决。首先占用消息总线的CPU核心获胜，其他核心只能乖乖清空自己的缓存行，并向其发出Invalidate Acknowledge反馈。
Read Invalidate
Read Invalidate相当于Read + Invalidate，既要读取某个缓存行信息，又要让属于其他CPU核心的此缓存行失效。同样，Read Invalidate也需要收到反馈，只不过此反馈既包含1条Read Response，又包含多条（如果其他CPU核心也拥有目标缓存行的话）Invalidate Acknowledge。
Writeback
Writeback消息包含要写回内存的地址和数据，通常指的是Modified状态的数据，这样Cache就可以根据需要弹出处于Modified状态的缓存行，以便为其他数据腾出空间。
这俩消息很简单，就不画图浪费你们的流量了。。。
5.3. MESI状态跃迁示例
CPU之间通过缓存一致性消息的传递，才有了缓存行在MESI四种状态之间的跃迁。
如上图，每两个状态之间都可能会发生状态越迁，是不是感觉很复杂？
如果之前的内容我给你解释地很清楚的话，就很容易想明白每个状态之间的跃迁场景了。为了不影响接下来的讲解，我把每种场景解释放在了文章最后（见附录1），需要的读者读完文章之后可以翻阅一下（即使不看也不会影响接下来的阅读哦）。
还有一个在线的网站可以帮助你更好地理解MESI协议（见附录2），你可以站在CPU的角度发出指令，网站以动态方式展示缓存行的状态变换，强烈建议阅读完文章之后大家试一下。
截至目前，文章都是围绕Cache展开的，高速缓存的引入极大地提高了计算机的整体运行效率。但在某些特殊情况下，CPU的性能表现却是非常糟糕。
6. 不能让CPU闲着
考虑这么一个场景，CPU 0 和CPU 1 同时拥有某个缓存行，两个缓存行都处于Shared状态，CPU 0想对自己的缓存行执行write操作，必须先发送Invalidate消息让CPU 1中的缓存行失效。如下图所示：
由于CPU 0必须等到CPU 1反馈了Invalidate Acknowledge之后才能确保自己可以操作缓存行，所以从发出Invalidate直到收到Invalidate Acknowledge的这段时间，CPU 0一直处于闲置状态。
CPU是何等宝贵的资源，让它闲着是不可能的，绝对不可能的！
硬件工程师为了解决这个问题，引入了Store Buffers。
6.1. 引入Store Buffers
工程师在CPU和Cache之间添加了一个中间层——Store Buffer。当CPU 0想执行write指令时，先把想要write的值写入到Store Buffer中，然后再继续执行其他任务，无需傻傻地等待CPU 1。直到CPU 1传回反馈之后，CPU 0再将Store Buffer中的最新值写入到缓存行中。
计算机的发展就是不断挖坑、填坑的过程。Store Buffers的引入解决了CPU闲置的问题，如果事情发展到现在就完美了该有多好，然而又引出了3个新问题。
6.2. Store Buffers引起的问题1
看一下上图左侧的代码，其中a和b的初始值为0，在大多数时候，最后的断言会为True。
之所以说大多数时候，因为左侧的代码在某个场景下可能会出现不符合我们预期的情况（断言为False）。如果要证明，我们只需要举出一个反例即可，因此我们进一步假设含有变量a的缓存行已经存在于CPU 1的Cache中，含有变量b的缓存行已经存在于CPU 0的Cache中。
下面我们根据引入Store Buffers之后的CPU架构来执行上面的代码，CPU 0 和CPU 1 的操作顺序如下图所示：
CPU 0 执行a = 1;CPU 0 首先从自己的Cache中查找a，发现没有；CPU 0 发送Read Invalidate消息来获取含有a的缓存行，并通知其他CPU，“老子要用，你们都给我销毁！”；CPU 0 在Store Buffer中记录下自己想赋给a的值，即a = 1。此时CPU 0并不会阻塞，会继续向下执行，但是在时间线的发展上，紧接着是CPU 1的操作，见第5步；CPU 1收到来自CPU 0的Read Invalidate消息，于是把自己包含a的缓存行返回给CPU 0，并且把自己的缓存行状态设置为Invalid；CPU 0 开始执行b = a + 1；CPU 0 收到来自CPU 1 的缓存行，并放到自己的缓存行中，其中a的值为0；此时CPU 0 的缓存行中的a和b的状态都是Exclusive，因为这些缓存行都由CPU 0 独占；CPU 0 从缓存行中读取a，此时值为0；CPU 0 根据自己之前在Store Buffer中存放的a = 1来更新自己Cache中的a，设置为1；CPU 0 在第8步获取的a值的基础上+ 1（这一步不需要重新从缓存行中读取数据，因为读取的动作在第8步中已经做了），并更新自己缓存行中的b；此时包含b的缓存行的状态为Modified；CPU 0 执行断言操作，发现断言为False。
再给大家补充一个动图：
这确实是一件非常违反直觉的事情，我们本来以为CPU就是完全按照代码的顺序执行的（至少最终结果应该表现地像CPU是完全按照代码的顺序执行的一样），我们认为b的最终结果就应该是2。
出现这个问题的原因是CPU 0 运行过程中出现了a的两份数据拷贝，一份是在Store Buffer中，一份是在Cache中。为了不让软件工程师疯掉，继续保持软件代码的直观性，硬件工程师又引入了Store Forwarding来解决这个问题。
6.3. 引入Store Forwarding
每个CPU在执行数据加载操作时都直接使用Store Buffer中的内容，而无需从Cache中获取，如下图所示。
请注意上图和原来图片的区别，上图中的Store Buffer中的数据可以直接被CPU读取。对应到上面的CPU 0 的操作步骤，就是第8步直接从Store Buffer中读取最新的a，而不是从Cache中读取，这样整个程序的最终断言结果就是True！
总之，引发的第1个问题，硬件工程师通过引入Store Forwarding为我们解决了。
6.4. Store Buffers引起的问题2
在多个CPU并发处理情况下也可能会导致代码运行出现问题。
同样也是举一个极端一点的例子。见下图左侧的代码，其中a和b的初始值为0，进一步假设含有变量a的缓存行已经存在于CPU 1的Cache中，含有变量b的缓存行已经存在于CPU 0的Cache中。CPU 0 执行foo方法，CPU 1 执行bar方法。正常情况下，bar方法中的断言结果应该为True。
然而，我们按照下图中的执行顺序操作一遍之后，断言却是False！
CPU 0 执行a = 1，首先从自己的Cache查找啊，发现没有；CPU 0 将a的新值1写入到自己的Store Buffer中；CPU 0 发送Read Invalidate消息（从发出这个消息到CPU 1 接收到，期间又运行了非常多的步骤，见下方GIF图）；CPU 1 执行while (b == 0) continue，发现b不在自己的Cache中，于是发送Read消息；CPU 0 执行b = 1，由于b已经存在于自己的Cache中了，所以直接将Cache中的b修改为1，并修改包含b的缓存行的状态为Modified；CPU 0 收到来自第4步CPU 1 发出的Read消息，由于当前自己拥有的b是最新版本的，所以CPU 0 把含有b的缓存行返回给CPU 1，同时修改自己的缓存行状态为Shared；CPU 1 收到来自CPU 0 的b缓存行数据，放到自己的Cache中，并设置为Shared状态；CPU 1 结束while循环，因为此时的b值已经是1了；CPU 1 执行assert(a == 1)，由于Cache中的a值是0（此时还没收到来自CPU 0 的Read Invalidate消息，因此CPU 1 有理由认为自己的数据就是合法的），因此断言结果为False；CPU 1 终于收到来自CPU 0 的Read Invalidate消息了，虽然已经晚了（当然CPU压根不知道自己的这个消息接收的时机并不合适），但是还得按照约定把自己的a设置为Invalid状态，并且给CPU 0 发送Invalidate Acknowledge以及Read Response反馈；CPU 0 收到CPU 1 的反馈，利用Store Buffer中的值更新a。
至此，流程全部结束，再送给大家一个GIF。
我们分析一下结果不符合我们预期的原因。
Store Buffer的加入导致Read Invalidate的发送是一个异步操作，异步可能导致的结果就是CPU 1 接收到CPU 0 的Read Invalidate消息太晚了，导致在Cache中的实际操作顺序是b = 1，最后才是a = 1，就好像写操作被重排序了一样，这就是CPU的乱序执行。
如果没有看懂上面一段就再看一下图片中的CPU 0 Cache的时间线演化。
很多人看到「乱序执行」唯恐避之不及，它当初可是为了提高CPU的工作效率而诞生的，而且在大多数情况下并不会导致什么错误，只是在多处理器（smp）并发执行的时候可能会出现问题，于是便有了下文。
也就是说，如果在第5步CPU 0 修改b之前，我们强制让CPU 0先完成对a的修改就可以了。
为了解决这样的问题，CPU提供了一些操作指令，来帮助我们避免这样的问题，就是大名鼎鼎的内存屏障（Memory Barrier,mb）。
6.5. 内存屏障
我们稍微修改一下foo方法，在b = 1之前添加一条内存屏障指令smp_mb()。
内存屏障
多说一点，smp的全称是Symmetrical Multi-Processing（对称多处理）技术，是指在一个计算机上汇集了一组处理器(多CPU)，各CPU之间共享内存子系统以及总线结构。
为什么要特意加上smp呢？因为即便现代处理器会乱序执行，但在单个CPU上，指令能通过指令队列顺序获取指令并执行，结果利用队列顺序返回寄存器，这使得程序执行时所有的内存访问操作看起来像是按程序代码编写的顺序执行的，因此没必要使用内存屏障（前提是不考虑编译器的优化的情况）。
内存屏障听起来很高大上，但是对于软件开发者而言其实非常简单，总结一句话就是：
在内存屏障语句之后的所有针对Cache的写操作开始之前，必须先把Store Buffer中的数据全部刷新到Cache中。
如果你看明白了我上面说的Store Buffer，这句话是不是贼好懂呢？换个角度再翻译一下，就是一定要保证存到Store Buffer中的数据有序地刷新到Cache中，这样就可以避免发生指令重排序了。
如何保证有序呢？
最简单的方式就是让CPU傻等，CPU 0 在执行第5步之前必须等着CPU 1给出反馈，直到清空自己的Store Buffer，然后才能继续向下执行。
啥？又让CPU闲着？一切让CPU闲置的方法都是馊主意！
还有一个办法就是让数据在Store Buffer中排队，谁先进入就必须先刷新谁，后边的必须等着！
这样一来，本来可以直接写入Cache的操作（比如待操作的数据已经存在于自己的Cache中了）也必须先存到Store Buffer，然后依序进行刷新。
应用内存屏障之后的操作步骤就不给大家再写一遍了，相信大家能够想清楚。
总之，引发的第2个问题，我们通过使用内存屏障解决了。
6.6. Store Buffers引起的问题3
Store Buffer的容量通常很小，如果CPU此时需要对多个数据执行write操作，碰巧这些数据都不在该CPU的Cache中，那么该CPU只能发送对应的Read Invalidate指令了，同时新数据写入Store Buffer，非常容易导致Store Buffer空间被占满。
一旦Store Buffer被占满，CPU就只能干等着目标CPU完成Read Invalidate操作，并且返给自己Invalidate Acknowledge，当前CPU才能逐步将Store Buffer中的值刷新到Cache，腾出空间，然后继续执行。
CPU又又又闲下来了！所以我们肯定又得找个办法来解决这个问题。
出现这个问题的主要原因在于Invalidate Acknowledge的反馈速度太慢了！
因为CPU太老实了，它只有在确认自己的缓存行被设置为Invalid状态之后才会发送Invalidate Acknowledge。如果Cache的其他操作太频繁，“设置缓存行为Invalid状态”这个动作本身都会被延迟执行，更何况Invalidate Acknowledge的反馈动作呢，得等到猴年马月啊！
上面的GIF图中为了表现出「反馈慢」这种情况，我特意把Invalidate消息的发送速度设置地很慢，其实消息地发送速度非常快，只是CPU处理Invalidate消息的速度太慢了而已，望悉知。
如果不想等，想直接获取操作结果，你想到了什么？
没错，是异步！
实现方式就是再加一层消息队列——Invalidate Queues。
6.7. 引入Invalidate Queues
如下图，我们的硬件架构又升级了。在每个CPU的Cache之上，又设置了一个Invalidate Queue。
这样一来，收到Invalidate消息的CPU核心会把Invalidate消息直接存储到Invalidate Queue中，然后立即返回Invalidate Acknowledge，不需要再等着缓存行被实际设置成Invalid状态再发送，极大地提高了反馈速度。
你可能会问，万一Invalidate Queues中的Invalidate消息最终执行失败，但是Acknowledge消息已经返回了，这该怎么办呢？
好问题！答案是，我不知道。我们就当作硬件工程师绝对不会留下这个bug就是了。
Invalidate Queue填了Store Buffer容量太小的坑，接下来看看它自己又挖了什么坑吧。
6.7.1. Invalidate Queue引发的问题
这个坑比较严重，很有可能直接干翻缓存屏障，再次引发乱序执行的问题。
老样子，还是先准备一下翻车的环境。如下图，我们假设变量a被CPU 0 和CPU 1 共享，为Shared状态；变量b被CPU 0 独占，为Exclusive状态；CPU 0 和CPU 1 分别执行foo和bar方法。
我们按照下图中的执行顺序操作一遍。
CPU 0 执行a = 1，因为CPU 0 的Cache中已经有a了，状态为Shared，因此不能直接修改，需要发送Invalidate（不是Read Invalidate，因为自己有a）消息使其他缓存行失效；CPU 0 把试图修改的a的最新值1放入Store Buffer；CPU 0 发送Invalidate消息；CPU 1 执行while(b == 0) continue;发现b不在自己的Cache中，于是发送Read消息来获取b；CPU 1 收到来自CPU 0 的Invalidate消息，把该消息放入Invalidate Queue中（并没有立即让a失效），等候处理，然后立刻返回Anknowledge；CPU 0 收到Acknowledge消息，认为CPU 1 已经把a值设置为Invalid了，于是放心地把Store Buffer中的数据刷新到自己的Cache中，此时CPU 0 Cache中的a为1，状态为Modified；然后就可以直接越过smp_mb()内存屏障，因为现在Store Buffer中的数据已经空了，满足内存屏障的约束条件。CPU 0 执行b = 1，因为其独占了b，所以可以直接在Cache中修改b的值，此时b缓存行的状态为Modified；CPU 0 收到来自CPU 1 的Read消息，将修改之后的b缓存行返回，并修改自己Cache中的b缓存行的状态为Shared；CPU 1 收到包含b的缓存行数据，放在自己的Cache中，此时CPU 1 的Cache同时拥有了a和b；CPU 1 结束执行while(b == 0) continue;因为此时CPU 1 读到的b已经是1了；CPU 1 开始执行assert(a == 1)，CPU 1 从自己的Cache读到a为0，断言为False。CPU 1 开始处理Invalidate Queue队列，令Cache中的a失效，但是为时已晚！
至此流程全部结束，再上个GIF。
问题很明显出在第11步，这就是臭名昭著著名的可见性问题。CPU 0 修改了a的值，CPU 1 却不知道或者说知道的太晚！如果在第11步读取a的值之前就赶紧刷新Invalidate Queue中的消息，让a失效就好了，这样CPU 1 就不得不重新Read，得到的结果自然就是1了。
原因搞明白了，怎么解决呢？内存屏障再一次闪亮登场！
6.7.2. 内存屏障的另一个功能
上文已经解释了内存屏障的功能，再抄一遍加深印象：
1.在内存屏障语句之后的所有针对Cache的写操作开始之前，必须先把Store Buffer中的数据全部刷新到Cache中。
其实内存屏障还有另一个功能：
2.在内存屏障语句之后的所有针对Cache的读操作开始之前，必须先把Invalidate Queue中的数据全部作用到Cache中。
使用缓存屏障之后的代码就变成了这个样子：
bar方法在assert之前添加了内存屏障，意味着在获取a的值之前，所有在Invalidate Queue中的Invalidate消息必须作用到Cache中。
至此，我们再次用内存屏障解决了可见性问题。
问题还没有结束......
7. 读内存屏障 & 写内存屏障
内存屏障有两个功能，在foo方法中实际发挥作用的是功能1，功能2并没有派上用场；同理，在bar方法中实际发挥作用的是功能2，功能1并没有派上用场。于是很多不同型号的CPU架构（不是所有）将内存屏障功能分为了读内存屏障和写内存屏障，具体如下。
smp_mb（全内存屏障，包含读和写全部功能）smp_rmb（read memory barrier，仅包含功能2）smp_wmb（write memory barrier，仅包含功能1）
上文已经解释地挺清楚了，因此就不再重复介绍smp_rmb和smp_wmb的作用了。直接看修改之后的代码吧。
8. 总结
计算机的演进就是一部反复挖坑、填坑的发展史。
为了解决内存和CPU之间速度差异过大的问题，引入了高速缓存Cache，结果导致了缓存一致性问题；
为了达到缓存一致的效果，CPU之间需要沟通啊，于是又设计了各种消息传递，结果消息传递导致了CPU的偶尔闲置；
为了不让CPU停下来，硬件工程师加入了写缓冲——Store Buffer，这一下子带来了3个问题！
第一个问题比较简单，通过引入Store Forwarding解决了；
第二个问题是操作重排序问题，我们又引入了内存屏障的第一个大招；
第三个问题是由于Store Buffer空间限制导致CPU又闲下来了，于是又设计了Invalidate Queues，然后又导致了乱序执行和可见性问题；
通过使用内存屏障的全部大招终于解决了乱序执行和可见性问题，又引出了大招伤害性过强的问题，于是又拆分成了更细粒度的读屏障和写屏障。。。。。。
9. 后记
问题其实还有很多，比如各种不同CPU结构是怎么实现内存屏障的？可想而知，每个人都有每个人的想法，不同CPU的实现指定也不一样，甚至可能拆分地更细或者更粗。不过这些与大部分软件开发者（包括我）都没有什么关系了，更多问题还是留给芯片开发者以及操作系统开发者吧。
不要纠结于具体的实现细节，把文章中的大部分搞懂已经能帮助我们理解很多问题了。如果还想知道的更多，可以看看附录3中的第1篇文章。
10. 附录1——MESI跃迁场景解析
(a)：通过Writeback消息把被修改过的缓存行刷新至内存，但是CPU的Cache仍然保留该数据；
(b)：CPU修改了只保存在当前Cache中的缓存行；
(c)：CPU收到了Read Invalidate消息，该消息的目标正是当前处于M状态（被修改了）的缓存行。CPU不得不使自己的缓存行失效，并把该缓存行数据携同Read Response以及Invalidate Acknowledge消息返回；
(d)：CPU执行了一个原子操作，该操作包含读和写两个子操作，并且不可分割。CPU首先发送Read Invalidate消息，收到Read Response消息之后立刻对数据进行更新，至此便完成了该原子操作。
(e)：和d大致相同。CPU执行了一个原子操作，该操作包含读和写两个子操作，并且不可分割。CPU首先发送Invalidate消息，收到Invalidate Acknowledge消息之后立刻对数据进行更新，至此便完成了该原子操作。
(f)：当前CPU修改了一个缓存行数据，接着其他CPU核心对当前CPU的该缓存行发出Read消息，当前CPU将该缓存行数据随Read Response消息反馈给其他CPU核心。至于该过程会不会涉及到缓存行数据刷新到内存，那就不一定了。
(g)：当前CPU独占了一个未经修改的缓存行，其他CPU对当前CPU的该缓存行发出Read消息，当前CPU将该缓存行随Read Response消息反馈给其他CPU，并将缓存行的状态由Exclusive改为Shared；
(h)：多个CPU共享某个缓存行，其中一个CPU对其他CPU发出Invalidate消息，该CPU收到其他所有拥有该缓存行的CPU的Invalidate Acknowledge消息之后，将该缓存行状态切换为Exclusive；或者其他CPU自己清空了该缓存行（比如为其他数据腾出空间）导致该CPU独占该缓存行，同样会发生这种状态转换。
(i)：其他CPU对当前CPU独占的一个缓存行发出一个Read Invalidate消息，当前CPU将该缓存行设置为Invalid，并发送Read Response以及Invalidate Acknowledge反馈；
(j)：CPU对不在自己Cache的一个数据进行写操作，因此发出Read Invalidate消息，收到一条Read Response（可能来自其他Cache，也可能来自内存）以及所有拥有该缓存行的CPU的Invalidate Acknowledge反馈（可能压根没有）之后，缓存行被当前CPU独占；
(k)：CPU读取某个自己Cache中不存在的数据，于是发出Read消息，收到Read Response（该消息一定来自于其他CPU）之后，缓存行的状态由Invalid变为了Shared；
(l)：当前CPU和其他CPU共享了一个缓存行，突然有一个其他CPU向当前CPU发来一条Invalidate消息，当前缓存行只能默默把自己的缓存行设置为Invalidate，并回复Invalidate Acknowledge。
11. 附录2——MESI在线网站使用
地址：scss.tcd.ie/Jeremy.Jone…
见上图，网站主要分为3部分
内存数据
内存中保存了4个数据，初始值为0，地址分别为a0、a1、a2、a3。
高速缓存
显示 CPU 缓存的变量数据和 MESI 协议状态。该高速缓存能容纳2个缓存行数据，所有缓存行的初始状态为I（Invalid）。
CPU核心
共有3个 CPU，每个 CPU 都有各自的 Cache，CPU 操作分为「读」和「写」，这部分是我们可以手动操作的部分。
举个例子：
CPU0执行read a0，于是通过各种bus总线将内存中地址为a0的数据读入缓存行内，由于目前只有CPU0独占该缓存行，所以状态变为Exclusive；CPU1执行read a0，又通过各种bus总线将a0的数据读到自己的缓存行内，此时CPU0和CPU1的缓存行都变为Shared状态；CPU1执行write a0，将地址为a0的数据+1后写回内存，同时向CPU0发出Invalidate信号，导致CPU0将其缓存行置为Invalid状态；此时CPU1独占缓存行，因此缓存行为Exclusive状态；CPU1执行read a1，类似第1步，通过各种bus总线将内存中地址为a1的数据读入缓存行内，由于目前只有CPU1独占该缓存行，所以状态为Exclusive；此时CPU1的Cache被占满；最后CPU1执行read a2，由于CPU1的Cache已经被占满了，只能弹出a0，存入a2，此时a2状态为Exclusive。
12. 附录3——参考文献
[1] Paul E. McKenney. Memory Barriers: a Hardware View for Software Hackers.
[2] barrier和smp_mb
[3] 内存屏障和volatile语义
[4] 解密内存屏障
[5] MESI在线网站
[6] 看懂这篇，才能说了解并发底层技术
[7] Why Memory Barriers中文翻译（下）
[8] MESI与内存屏障
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
相关文章
发表评论
暂时没有评论，来抢沙发吧~