[A Primer Of CC and MC] 1. 对于 Memory Consistency 和 Cache Coherence 及其关系的一点思考

最近在自制 OS 内核自然而然的搞到了并发结果很快就被-O2优化教做人了。遂不服气开始研究 CC (Cache Coherence) 和 MC(Memory Consistency), 势必要搞出点名头。1 缓存和乱序执行1.1 缓存的诞生很久很久以前CPU想获取或者写入数据都是直接控制总线读写内存。诶这多方便多直接不是吗但是很快架构师就发现这 DRAM 的速度相对于cpu的寄存器而言可实在是慢得不敢恭维啊。那怎么办?于是我们不得不请出那句计算机界的至理名言(好吧其实是冷笑话)了:所有的问题都可以通过加一层抽象层来解决如果加一层解决不掉那就--再加一层!(记住这句话后面讲 MC 和 CC 的关系的时候要考!)所以经研究决定我们决定给 CPU 加一层抽象--缓存。对加一块容量比寄存器稍微大一点但是速度又比内存快得多的SRAM。我们将所有常用的数据集成在缓存中需要的时候快速取就好。这不就解决了速度问题了吗但是如果程序员在写汇编代码的时候还得管缓存的话那可就麻烦死了。所以我们必须保证程序员在写汇编代码的时候脑子中只有CPU和内存而没有缓存这样才不至于让程序员在写代码的时候由于脑子过载而死机。由此我们可以引出缓存的一个特点那就是透明性。1.2 CPU 的乱序执行还是在很久很久以前那会 CPU 非常的呆看到内存中的指令只会 FDEMW 这多符合直觉呀。但是很快架构师就发现诶我只需要略施小计对指令进行重排列就可以加快执行速度呢所以后续的 CPU 就引入了一个新技术 --乱序执行它能够对指令进行重排列在保证最终结果一致的前提下更换指令的顺序。这个最终结果一致说人话就是重新排列该核心中数条彼此无关的指令的执行顺序。例如mov eax,1 ; Instruction Amov ebx,2 ; Ins B这两条指令彼此之间是无关的所以可以重新排序先执行 Ins B 和先执行 Ins A 的结果是一样的所以 CPU 为了速度可能会先执行 Ins B 再执行 Ins A. 这就是重排列。而若是mov [eax],1mov ebx,[eax]这样子的话那就不能重排列了因为两条指令是相关的.由此我们就可以成功通过让 CPU 对指令重排序从而加快 CPU 的执行速度。2 问题: 缓存不一致和内存执行顺序的不一致2.1 CPU 乱序执行在多核心下的不一致性乱序执行后CPU 单核性能确实提上来了。然而工程师设计之初可没想到有多核 -- 它只保证单核心最终的结果正确。我们来看另外一个情况, 就是书中的 3.2:此时此刻C2 核心中的r1和r2变量可没有什么关系啊那我把 L2 移动到 L1 前面可不可以? 在只有 C2 的情况下这可一点问题都没有啊!但是问题是我们将 C1 核心和 C2 核心连起来看诶很显然把 L2 丢上面是违背我们原来想要的逻辑的。所以L1 和 L2 顺序是不能换的。而这个情境其实就是后续会涉及到的Load-Load重排序在此先提前涉及一下。那如何解决这个问题呢我们必须建立起一套秩序尽量减少甚至杜绝这类问题。2.2 缓存带来的不一致性既然都提到缓存了那就展示一下书上所写的缓存的架构吧。我们可以看到科学家远比我们想象的要丧心病狂他们给 CPU 加了很多很多的缓存。我们也可以看到每个核心都会有一个私有缓存。[!IMPORTANT]在接下来的文章中我们只关注私有缓存部分我们将 LLC(L3 Cache) 和内存块看作一个东西不加以区分。而前面讲到了我们实现缓存的目的有两个:让缓存相对于程序员透明。提升CPU访问主存的速度。当然书中有句老话说得好:所以我们也必须得保证它的确定性。现在每个核心都有一个私有缓存那每个核心之间的私有变量肯定是会出现不同步的。但是不同步就意味着会出错连正确性都无法保证。还有就是如果缓存必须和内存保持强一致性的话那不就和主存访问一样了吗那第二个目的就搞不定了缓存增加了个寂寞。所以我们必须建立一套协议能够实现这两个目的的同时又可以保证正确3 解决: 内存一致性(MC)和缓存一致性(SC)3.1 抽象: CPU 一致性读写模型在解决 2 的两个问题之前我们先尝试对 CPU 一致性做一个抽象建模。在 1.1 中我们可以知道CPU 是乱序执行的。那么我们可以尝试建立如下的抽象层每一层都对上一层暴露了几个接口:抽象层级 1: 程序员眼中: 哦CPU 提供了访存指令 mov/ldr/sto抽象层级 2: CPU 核心译码器眼中: 现在我有一堆指令, 我需要调用指令重排, 加快速度。至于具体怎么访存交给下一层的控制器吧。抽象层级 3: CPU 核心缓存控制器眼中: 我现在收到了一堆对于单个内存的读写指令。我需要确定这个内存是在我自己的Private D-Cache 中还是在别的核间缓存里或者是在主存中然后获取数据。(后续抽象层级省略)现在我们有了一个模型: CPU的译码器负责重排列访存指令而访存指令访问缓存控制器用它获取数据。3.2 抽象层级 3 实现: 缓存一致性协议(CC)既然我们的目的是对 抽象层级 2 的接口进行设计那么我们就首先提供两个接口:这个其实可以继续简化成read和write两个接口。那我们必须得考虑, 如何实现这两个接口, 让它相对于抽象层级 2 透明?3.2.1 第一次尝试: 增加一个传输层现在让我们考虑如下情境:Thread 1/CPU 1:mov [ripvar1], rax ; 私有缓存命中Thread 2/CPU 2:mov rbx, [ripvar1] ; 问题: 这b是在 C1 的私有缓存中啊! 它长啥样我不到啊! 怎么办?我们尝试加一个层级这个层级可以让 C2 访问由 C1 修改的但是目前未同步到主存的内存。对其实直接把在 C1 存储缓存的值给拿过来。这样就可以让 C2 获取 C1 的值这样就可以保证数据的正确性。3.2.2 第二次尝试: 同时进行读和写首先我们来看一个场景:;CPU 1:Tick 1: mov [ripvar1], rax;CPU 2:Tick 2: mov rbx, [ripvar1];CPU 3:Tick 2: mov rcx, [ripvar1]我们来看一下这个好像没毛病! 就算有两个 CPU 在 Tick 2 对内存同时进行了读取但是没有任何数据是读错的!而且这个还能很明显的加快 CPU 读写内存的速度毕竟缓存的速度比内存快多了 (至于具体的速度这个涉及到后续两个折磨死人的东西一个叫做MESI另一个叫做Store Buffer)。所以我们可以得出一个结论:在一个 Tick 中, 很多个 CPU 可以同时读取多个数据.那再来看一个场景:;CPU 1:Tick 1: mov [ripvar1], rax ;L1;CPU 2:Tick 1: mov [ripvar1], rbx ;L2诶这下出问题了! 我变量 var1 的值到底是 C1 的 rax 还是 C2 的 rbx 啊? 我不到啊! 由此可见,多个 CPU 不能在同一 Tick 写同一块内存.所以我们必须加一个硬件仲裁器强制对 L1 和 L2 的写入顺序进行排序确保 L1 和 L2 有先后顺序这样 CPU 就可以正常的写入数据了。而至于怎么定义先后顺序来保证数据的正确性... 这个说来话长, 后续讲吧反正现阶段只需要知道这样可以保证正确性就好了。3.2.3 最终结论: SWMR 和缓存一致性总之现在所有的问题都解决了数据的正确性透明性还有速度(多个 CPU 可以一起读同一片缓存而缓存的速度比主存快得多。同时)。所以我们可以得出几个结论:在一个 Tick 中, 很多个 CPU 可以同时读取多个数据多个 CPU 不能在同一 Tick 写同一块内存这就是 SWMR(Single Writer, Multi Reader) 的总结, 它可以很好的保证缓存的一致性(即正确性)同时兼顾速度和透明性。3.3 对抽象层级 2 的接口实现: 内存一致性协议(MC)这方面的话要是在此详细讲开的话太重了所以我就一笔带过详细讲的话就需要在后续的好几篇 Blog 讲了。解决了缓存一致性的问题后这个层级的目的其实和上个层级的一样:如何设计一套方案让 CPU 在加快速度的同时又尽力减少对程序员的影响?前面讲到了 CPU 的乱序执行我们把它摆出来。但是正如 2.1 所说它数据乱了!!!由此我们有两个方案:既然解决不了问题那就建立一套规范让提出问题的人闭嘴自己遵守去。我们可以通过改 CPU 的乱序执行的步骤尽量在 CPU 内部就能遵守 1 的规范来搞定这些问题。而这些规范就是内存一致性协议至于如何平衡 CPU 和程序员之间的工作那就又回到我们前几期讨论的经典命题了--权衡(Trade Off)。这个的话在此就不细讲了因为不同 CPU 采取的方案不同(例如 ARM 等 CPU 就倾向于方案 1哈哈心疼 ARM 嵌入式程序员三秒钟)后续讲内存模型的时候再详细扯。总而言之内存一致性协议其实目的就是加快 CPU 乱序执行速度的同时如何保证 CPU 最终数据的正确性。The End内存一致性协议(MC)的目的是加快 CPU 乱序执行速度的同时如何保证 CPU 最终执行结果的正确性它是宏观层面下的是针对整个程序而言换句话说它关注的是一堆指令的顺序。缓存一致性协议(CC)的目的是通过追加缓存在加快 CPU单条指令的执行速度(敲黑板啦单条指令不