[A Primer On MC and CC] 2.1 Memory Consistency 1 - 指令重排序和 SC 模型

既然我们知道了内存一致性, 那么内存不一致性体现在哪 4 大重排序?为了规范这 4 大重排序, 我们引入了哪个内存一致性模型去约束它们?Sequential Consistency的定义是什么? 这个内存一致性模型解决了这 4 大重排序中的哪些重排序呢?0 一些符号的预先说明为了方便后续的讲解, 我们先进行一些规定. 这部分在书上都有, 也有对应的图片.设:L(a)代表指令 a 的读取,S(a)代表指令 a 的写入我们把L(a)和S(a)暂时统一叫做P(a)P(a) m P(b)为 a 指令的实际退休顺序比 b 指令前面P(a) p P(b)为 a 指令的程序顺序比 b 指令前面1 四大天王: CPU 的指令重排序1.1 Load-Load 重排序首先我们先来看一张图:Woah, 是不是特别熟悉, 在哪见过? 对啦, 就在前一份随笔中我们遇见过它, 当时我稍微简略的说了, 这个就是load-load重排序. 现在我们就来仔细研究一下.这段代码的逻辑很简单, 就是 C2 在只有 flag SET 的时候, 才获取 r2 的值.为了方便说明, 假设我们的 CPU 可以对指令进行重排序, 那么我们首先来看一下 C2 的指令:; Core C2L1:2: load r1, [flag]3: cmp r1, SET4: jne L15: load r2, [data]看看这段代码,就看 C2 的代码(C1暂时先撂一边, 这很重要!), r1 和 r2 有没有关系? 回答我, look in my eyes!没关系对吧? 那我现在是一个 CPU, 我把 5 的指令排到 2 上面可不可以?当然可以!如果读取 data 的速度比读取 flag 还快的话, 咱把 5 的指令挪到 2 的上面就行了, 然后就形成了如下局面:TickC2指令2load r2, [data]3load r1, [flag]4...这重排序没有任何问题, 但是它能完成最初我们想让 CPU 干的事吗?这段代码的逻辑很简单, 就是 C2 在只有 [flag] SET 的时候, 才获取 r2 的值.不行了对不对? 程序乱了! 那这为什么不对呢? 我们来理理线索:将 C1 和 C2 连起来看, 变量 data 和变量 flag 顺序很明显是不能变的单独只看 C2, 变量 data 和变量 flag 没半毛钱关系CPU 能在保证单核心数据正确性的情况下对单核的指令进行重排序.注意: 这儿的重排序和乱序执行的区别是很大的, 但是若你理解了 SC 是抽象层/契约的话, 这个就不难理解了.前者指的是 CPU 在保证单核最终结果正确的情况下, 重新排序 CPU 的最终指令执行顺序, 也就是说, 前者直接打破了这个契约, 在程序员眼中, CPU 的指令执行顺序是不确定的.后者是 CPU 的流水线后端所干的事. CPU 完全可以维持 SC 这一契约, 也可以选择不维持. 而至于程序员眼中,CPU 是否遵循 SC,和 CPU 是否乱序执行,没有一点关系, 因为遵循 SC 的 CPU 照样可以做到乱序执行(至于怎么做到的, 下一章讲).进一步地, 我们可以继续概括出load-load触发的条件:CPU 具有单核指令重排序的功能.存在多个在局部(单个核心)无关的变量, 但是它们在全局(例如多个核心)逻辑中是有刚性的顺序要求的(上面的 data 和 flag 就是一个典型的例子).注意, 下面术语是描述此重排序不允许发生时候的定义.用书上的话/上面约定的符号:if L(a) p L(b), then L(a) m L(b)1.2 Store-Store 重排序在此之前, 我们先来粗略聊聊 CPU 的Load/Store Buffer.续接上集的 1.1, 核内缓存确实解决了一些速度问题, 但是, 这事还没完, 因为要保证多核数据一致性, 缓存加了一个Interconnection Network层, 如下图, 用来在缓存之间传递数据, 还有就是管理缓存的权限.注: 读到这, 肯定会有读者跳出来说, 你讲错了,Directory 才是 CPU 真正管理缓存权限的地方. 我知道你很急, 但你先别急, 后续会提到的.这层加进来后, 在核心数量少的时候其实也不影响啥, 但是核心数量一多, 诶, 这层的电路就越来越复杂, 但这不是最重要的. 更重要的是, 它慢啊! 你想想, 要 CPU 在执行访存指令的时候还得同步等一下缓存之间的, 那性能没救了, 直接重开吧.诶, 注意我加粗的文字, 同步! 那既然同步的性能会一言难尽, 那就改一下思路--异步!所以啊, 现在的 CPU 核心就整了一个叫做Load/Store Buffer的东西. 正好这玩意可以和 CPU 的推测执行打配合:CPU 可以先预测接下来需要读写的内存单元, 然后在Load/Store Buffer上先大笔一挥记上去, 就类似给缓存发了一个请求, 然后立刻就去乱序执行下一条预测代码.如果是读取的话,Load/Store Buffer在后台先搞到数据(如果是读的话), 然后等到 CPU 确认这条指令必须执行后, 再执行最终写入(寄存器).如果是写入的话,Load/Store Buffer会先提前申请到修改权限, 然后等到 CPU 确认这条指令必须执行后, 再执行最终写入(缓存).注: 目前我说的这些是简化的模型, 肯定有读者跳出来说, 你这模型太简单了. 我知道你很急, 但是你先别急. 目前, 我们暂时规定, 访存指令一经退休, 所执行的操作立马全局可见.我们来看一个例子, 还是上面的那张图:这段代码的逻辑很简单, 就是 C2 在只有 [flag] SET 的时候, 才获取 r2 的值,目标是获取 [data] 的新值.TickC1 指令C2 指令说明1S1: store [data], NEW-S1 进入 Store Buffer2S2: store [flag], SET-S2 进入 Store Buffer3-load r1, [flag]S2 先写入完毕退休, r1 SET4-cmp r1, SETr1 是否等于 SET?5-jne L1通过比较, 往下走6-load r2, [data]r2 [data], BOOM!7--S1 才退休, [data] NEW看到了吗? 在 Tick 6 的时刻, C2 崩了, 完美避过正确答案, 它成功获取到了data的旧值.那为什么不对呢? 我们来观察一下:S1 和 S2 的指令是单核心的, 并且指定顺序的.S1 和 S2 有顺序的进入 Store Buffer, 但是它们最终提交 (退休) 的顺序不一致.在 S1 和 S2 生效的间隙, 由于 jne 不成立, 所以有一个load指令来读取data中的内存数据.CPU 能在保证单核心数据正确性的情况下对单核的指令进行重排序(就是不按序退休).进一步地, 我们可以继续概括出store-store触发的条件:CPU 原本有多条在逻辑上强制指定顺序, 但是可以指令重排的store指令 (不管是单核心还是多核加锁变量).这些指令进入 Store Buffer 后,并没有老老实实的按进入的顺序提交最终结果.CPU 能在保证单核心数据正确性的情况下对单核的指令进行重排序(就是不按序退休).注意, 下面术语是描述此重排序不允许发生时候的定义.用书上的话/上面约定的符号:if S(a) p S(b), then S(a) m S(b)1.3 Load-Store 重排序让我们继续来看一段代码, 假设此时:[x] 0,[y] 0,NEW ! 0:C1 指令C2 指令L1: load r1, [x]L2: load r2, [y]S1: store [y], NEWS2: store [x], NEW按照我们的直觉可以得出, 上述的表格有几种可能的执行顺序:顺序结果L1-L2-S1-S2(S2-S1)r1 0,r2 0L1-S1-L2-S2r1 0,r2 NEWL2-L1-S1-S2(S2-S1)r1 0,r2 0L2-S2-L1-S1r1 NEW,r2 0but先别急, 加入Load Buffer后, 结果可能和你想的有点不一样, 我们以L1-L2-S1-S2的顺序再走一遍--注意: 下面的内存赋值语句, 例如下面表格的 [x] NEW, 它的含义是“内存值 [x] 更新为 NEW,此操作对所有 CPU 核心可见”.TickC1 指令C2 指令实际发生的我们预想的1L1: load r1, [x]-L1 进入 Load Bufferr1 [x]2-L2: load r2, [y]L2 进入 Load Bufferr2 [y]3S1: store [y], NEW-[y] 0[y] NEW4-S2: store [x], NEW[x] 0[x] NEW5--L1 退休, r1 [x]-6--L2 退休, r2 [y]-现在我们来看一下最终的结果, 容易得出:r1 NEWr2 NEW诶, 由于Load Buffer在这捣乱, 这种情况可不在上面可能执行顺序的结果内啊!问题出在哪呢? 我们概括一下:在逻辑顺序上,L1 比 S1 先执行但是在实际执行中,L1 却比 S1 后退休那我们从具体到泛化一下, 假设有一条读取指令 A, 另一条写入指令 B, 出现下面的情况:逻辑上的顺序为 A-B诶, 很不巧, 由于Load Buffer或者其他乱七八糟的因素, 实际的提交顺序却是 B-A也就是说, A 在提交值之前, B 就已经开始读取值了, 所以 B 才会读取到错误的值.这种逻辑上应该是读取指令 A 先, 写入指令 B 后, 但是实际执行顺序却是 B 先 A 后, 导致 A 读取到错误数据的情况, 我们叫做Load-Store重排序.注意, 下面术语是描述此重排序不允许发生时候的定义.用书上的话/上面约定的符号:if L(a) p S(b), then L(a) m S(b)1.4 Store-Load 重排序我们现在把 1.3 中的代码反一下, 假设此时:[x] 0,[y] 0,NEW ! 0:同上, 这张图有几种可能的执行顺序:顺序结果S1-S2-L1-L2(L2-L1)r1 NEW,r2 NEWS1-L1-S2-L2r1 0,r2 NEWS2-S1-L1-L2(L2-L2)r1 NEW,r2 NEWS2-L2-S1-L1r1 NEW,r2 0上述很符合我们的逻辑, 对吧? 毕竟按照我们人类的线性思维, 这样可再正常不过了.同上, 加入Store Buffer后, 我们以S1-S2-L1-L2的顺序再走一遍--TickC1 指令C2 指令实际发生的我们预想的1S1: store [x], NEW-S1 进入 Store Buffer[x] NEW2-S2: store [y], NEWS2 进入 Store Buffer[y] NEW3L1: load r1, [y]-r1 [y] 0r1 [y] NEW4-L1: load r2, [x]r2 [x] 0r2 [x] NEW5--S1 退休, [x] NEW-6--S2 退休, [y] NEW-现在我们来看一下最终的结果, 容易得出:r1 0r2 0原因同上, 不再赘述. 这儿直接摆出Store-Load的定义:这种逻辑上应该是写入指令 A 先, 读取指令 B 后, 但是实际执行顺序却是 B 先 A 后, 导致 B 读取到错误数据的情况, 我们叫做Store-Load重排序.注意, 下面术语是描述此重排序不允许发生时候的定义.用书上的话/上面约定的符号:if S(a) p L(b), then S(a) m L(b)还有一点小插曲--若不知道 TSO 内存一致性模型是什么的读者, 可以暂时先跳过此部分. 此部分专门讲述, 为什么 TSO 允许产生Store-Load重排序.在这个例子中, 我们可以很轻易地注意到,Store-Load重排序:并没有涉及到对指令顺序的重排序.不依靠 Store Buffer 中的记录顺序(这儿先挖个坑qwq,一种比较常见的 Store Buffer 的记录顺序叫做 FIFO, 也就是先进先出).本质是由于 Store Buffer 的延迟, 导致读取指令 A 在写入指令 B 提交之前读取数据.TSO 模型只能保证每个核心的 Store Buffer 是 FIFO 的, 从而避免了Store-Store重排序.然而, TSO 并不能保证每条读取指令都得等到另外一条写入指令最终提交后再读取值, 正如上述的例子那样.所以, TSO照样有可能产生Store-Load重排序.那有读者会问,Load-Store重排序也有上述特性, TSO 是怎么解决的呢? 答案可能让你出乎意料--TSO 中,Store Buffer在写入前有一个硬性规定, 若Load Buffer非空, 则Store Buffer不会提交, 换句话说, Store 指令必须得等 Load 指令全部提交完, 才会去提交.but, 随之而来又有一个问题---为什么 TSO 允许Store-Load而不是Load-Store?原因其实很简单, 一个字--快. 如果是Store Buffer等待Load Buffer, 那么 CPU 就可以通过Load Buffer疯狂的执行预测, 和进行下一步的计算. 要是Load Buffer等待Store Buffer的话... 好问题, 啥预测之类的全得排Store后边, 那 CPU 会慢的像蜗牛一样.并且, 要是Load指令预测错误, 就算Load退休了, 也就影响一个核心, 大不了这个核心把错误的值部扔了, 没毛病. 但是Store要是退休了... 那影响的可就不止一个核心了.2 最符合直觉的模型: SC (Sequential Consistency)2.1 抽象: 再探内存一致性模型还记得我们前一篇文章写的 3 个抽象层级吗? 现在, 我们修改一下抽象层级 1, 让它更符合程序员眼中的 CPU 的样子:抽象层级 1: 程序员眼中: 哦CPU 提供了访存指令 mov/ldr/sto,并且 CPU 执行这些指令的顺序是规定好的(有序/无序).什么意思呢? 也就是说, 在程序员的视角中, CPU 可以被抽象成一个按一定顺序执行指令的电子元器件. 但是别忘了这是在程序员的视角! 在 CPU 内部, 这些顺序执行的指令是完全可以做到乱序执行的.我们只需要保证,CPU 执行指令的所有可能的最终结果, 是按该内存一致性顺序执行后所得的所有可能的结果的其中之一(不论是 Weak Memory 模型, 还是 TSO 模型, 或者是现在的 SC), 我们就称它为遵循 SC(这儿的 SC 换成具体的名字) 模型.这句话可能有点绕, 一个最直观的例子就是上面的Load-Store, 按照我们按顺序执行指令的直觉(其实我们的直觉就是SC内存一致性模型), 不管指令按什么可能的顺序排列,r1 NEW, r2 NEW的结果都是不可能出现的, 但是它却出现了. 我们把它叫做违反 SC(这儿的 SC 换成具体的名字) 模型.所以, 内存一致性模型本质上是一套和程序员的规定, 也就是说, 内存一致性模型规定了在程序员眼中, CPU 实际到底会以怎样的顺序处理和排序他们写的指令.打个比方:例如餐厅叫号系统, 我们付钱后拿到一个排队顺序, 然后只需要等待排队就好了. 但是, 至于内部的厨师是先做 1 号顾客的菜, 还是先做 2 号顾客的菜, 我们不需要知道, 我们只需要知道, 最终的顺序是先 1 号取餐, 再轮到 2 号. 然后餐厅对外宣传:我们采用了智能叫号系统, 按顺序取餐.现在, 厨房就是CPU 流水线后端, 顾客就是指令, 海报就是内存一致性协议, 看到这个海报的人的视角就是程序员视角. 看海报的人只需要知道这个餐厅是按序取餐就好了, 没有必要知道厨房内部的具体的做饭顺序. 但是, 厨房员工采用了乱序制作的手段加快做菜速度.2.2 解决: 我们先试试 SC还记得我在 1 中讲的 3.3 部分吗? 当时, 我们讲了内存一致性模型, 它告诉 CPU 或者程序员, 该以什么样的顺序执行指令, 才能保证 CPU 最终数据的正确性. 而我们还讨论到, CPU 的乱序执行会导致数据错乱. 而导致数据错乱的原因, 主要就是上面 4 种形式的重排序.要解决这个问题, 我们必须建立一套指令之间内存读写的秩序, 并且还是用到万能的权衡大法, 以下是两个极端的方案:CPU 为了速度, 疯狂对指令重排序, 但是它提供了一系列控制指令, 程序员可以通过指令对 CPU 说:嘿, 将这条指令作为程序的分界线, 界限下面的指令不能被乱序到到界限上面去执行, 否则出大问题(这样灵活, 没得说, 并且能少用一堆逻辑门).重新设计 CPU 的执行引擎电路, 给 CPU 加点小小的魔法(好吧, 其实就是抽象层), 让程序员以为 CPU 真的在乖乖的按照程序员指定的顺序执行指令. 至于 CPU 如何实现这个魔法, 好吧, 其实程序员并不需要知道. (这样子能让程序员少掉点头发, 妙哉妙哉).现代 CPU 的内存一致性方案, 其实就是这两个方案经适当权衡之后的结果. 而这套叫Sequential Consistency(SC, 顺序执行) 的模型, 可谓对程序员是极其友好, 它就是极端方案的第二种: 程序员完全可以认为 CPU真的在按照程序员指定的顺序去执行指令, 而不会为了速度任性地重排序它们.例如在之前的例子中:L1:I2: load r1, [flag]I3: cmp r1, SETI4: jne L1I5: load r2, [data]在程序员眼中, CPU 的指令执行顺序为I2-I3-I4-I5, 那 CPU 最终给程序员呈现的结果就是正经的去执行I2-I3-I4-I5后的结果, 不会因为出现上述的四大天王重排序, 而导致乱七八糟的问题.用官方的术语定义 SC:if S(a) p S(b), then S(a) m S(b)if L(a) p L(b), then L(a) m L(b)if L(a) p S(b), then L(a) m S(b)if S(a) p L(b), then S(a) m L(b)由此可见, SC 把 4 大重排序全都干掉了. 也正因为它严格顺序执行, 所以它是程序员的福音, 能让程序员就按照他自己想的方式去写代码, 不必担心 CPU 发生指令重排.2.3 易混淆的点: 执行路径和 SC在单核心中, SC 似乎很好理解, 毕竟, SC 就是顺序执行嘛. 但是在多核心中, 情况似乎有所不同了.2.3.1 多条 SC 的合法路径敲黑板啦! 多核心下的 SC 是有很多很多条执行路径的, 就类似我们之前研究的并发编程一样. 例如之前的例子中:顺序结果S1-S2-L1-L2(L2-L1)r1 NEW,r2 NEWS1-L1-S2-L2r1 0,r2 NEWS2-S1-L1-L2(L2-L2)r1 NEW,r2 NEWS2-L2-S1-L1r1 NEW,r2 0别看这些例子看上去挺乱的不可预测, 但是它们都是符合 SC 模型的, 因为它们都是按照一定的顺序集合起来的. 但是, 如果某个时刻 CPU 计算出来的结果并不为右边的值的其中之一, 那这个 CPU 才是违反 SC的.若有一个 SC 模型的 CPU 执行你的并发代码后, 出现了一些很诡异的结果, 这个时候先别急着把 CPU 抠下来然后往地上摔(虽然这确实挺恼火的, 这是人之常情), 我建议你先喝杯咖啡冷静一下, 然后拿一张纸和一支笔, 在纸上重新推一下这段并发代码, 看看是不是某些竞争条件被遗漏了.2.3.2 SC 执行过程的偏差和执行结果的合法注意: 以下我在讨论的是执行路径, 不是CPU 本身. CPU 本身违反 SC 不假, 但是我现在在探讨的是执行路径是否违反 SC.现在, 我问一个极其刁钻的问题, 基于上述的情境, 假设有如下执行的路径:TickC1 指令C2 指令实际发生的我们预想的1S1: store [x], NEW-S1 进入 Store Buffer[x] NEW2-S2: store [y], NEWS2 进入 Store Buffer[y] NEW3L1: load r1, [y]-r1 [y] 0r1 [y] NEW4--S1 退休, [x] NEW-5--S2 退休, [y] NEW-6-L2: load r2, [x]r2 [x] NEWr2 [x] NEW问题: 我设置的这条执行路径:它存在Store-Load重排序吗它是否符合SC?(先思考 5 秒钟... 想到了吗?)答案:很明显的, 它存在Store-Load重排序, 因为指令 L1 在 S1 执行完毕之前读取了值.见下分析上述例子的执行路径, 我们可以看到, 虽然有:路径结果S1-S2-L1-L2r1 0,r2 NEW但是, 它却并不违反 SC, 为什么呢? 在此之前, 我再问一个问题:这条执行路径, 它位于我们之前所讲的抽象层级的第几层?(再思考 5 秒钟...)答案是第二层. 对, 它属于 CPU 微架构和流水线层面. 但是, 我们需要记住, 我们是站在程序员的视角下看问题的, 也就是位于抽象层级的最顶端(第一层), 我们是不知道, 也不需要知道 CPU 的微架构和流水线长什么样的.在程序员的视角下, 我们看到的是这样的指令:假设执行上述代码的 CPU 遵循 SC, 那上述执行链条, 所得到的结果有可能是r1 NEW,r2 NEWr1 0,r2 NEWr1 NEW,r2 0r1 0,r2 NEW在不在这里面? 在啊! 没毛病啊! 我们在不知道具体执行路径的情况下, 完全可以构造一条可能合理的解释路径, 去解释这个结果.换句话说, 其实看执行链是否遵循 SC, 就只需要看它结果就行了, 然后怎么推到这个结果的? 自己猜去, 天知地不知, 你不知我不知.The End