x86-TSO : 适用于x86体系架构并发编程的内存模型
Abstract :html
现在大数据，云计算，分布式系统等对算力要求高的方向如火如荼。提高计算机算力的一个低成本方法是增长CPU核心，而不是提升单个硬件工做效率。java
这就要求软件开发者们能准确，熟悉地运用高级语言编写出可以充分利用多核心CPU的软件，同时程序在高并发环境下要准确无误地工做，尤为是在商用环境下。node
可是作为软件工程师，实际上不太可能花大量的时间精力去研究CPU硬件上的同步工做机制。linux
退而求其次的方法是总结出一套比较通用的内存模型，而且运用到并发编程中去。编程
本文结合对CPU的黑盒测试，介绍一个可以通用于 x86 系列CPU的并发编程的内存模型。缓存
此内存模型 被测试在 AMD 与 x86 系列CPU上具备可行性，正确性。架构
本文章节：并发
1.关于各型号CPU的说明书规定或模型规定app
2.官方发布的黑盒测试及它们可复现/不可复现的CPU型号分布式
3.指令重排的发生
4.根据黑盒测试定义抽象内存模型 x86-TSO
5.A Rigorous and Usable Programmer’s Model for x86 Multiprocessors 的发布团队在AMD/Intel系列CPU上进行的一系列黑盒测试及它们与x86-TSO模型结构的关系
6.扩展
6.1 经过Hotspot源码分析 java volatile 关键字的语意及其与x86-TSO/普通TSO内存模型的关系
6.2 Linux内存屏障宏定义 与 x86-TSO 模型的关系
7.总结
8.参考文献
1.各个型号CPU的规定
CPU相关的模型或规定：
x86-CC 模型（出自 The semantics of x86-CC multiprocessor machine code. In Proc. POPL 2009, Jan. 2009）
IWP (Intel White Paper，英特尔在2007年8月发布的一篇CPU模型准则，内容给出了P1~P8共8条规则，而且用10个在CPU上的黑盒测试
来支持这8条规则)
Intel SDM (继承IWP的Intel 模型)
AMD3.14 说明手册对CPU的规定
2.官方黑盒测试
下面的可在...观察到，不可在...观察到，都是针对 最后的 State 而言，亦即 Proc 0: EAX = 0 ^ ... 语句表示的最终状态
其中倒着的V是且的意思
如下提到的StoreBuffer即CPU核心暂时缓存写入操做的物理部件，StoreBuffer中的写入操做会在任意时刻被刷入共享存储（主存/缓存），前提是总线没被锁/缓存行没被锁
如下提到的Store Fowarding 指的是CPU核心在读取内存单元时 会去 StoreBuffer中寻找该变量，若是找到了就读取，以便获得该内存单元在本核心上最新的版本
1.测试SB : 可在现代Intel CPU 和 AMD x86 中观察到
核心0 和 核心1 各有本身的Store Buffer，会形成上述状况。
核心0将 x = 1 缓存在本身的StoreBuffer里，而且从共享内存中获取 y = 0，之因此见不到 y = 1 是由于 核心1 将 y = 1 的操做缓存在本身的StoreBuffer里
核心1将 y = 1 缓存在本身的StoreBuffer里，而且从共享内存中获取 x = 0，没法见到 x = 1 与上述同理
2.测试IRIW : 实际上不容许在任何CPU上观察到，可是有的CPU模型的描述可能让该测试发生
若是 核心0 和 核心2 共享 StoreBuffer，由于读取时会先去 StoreBuffer 读取修改，因此 核心0 执行的 x = 1 会被 CPU2 读取，故 EAX = 1 , 由于核心1 和 核心2 不共享StoreBuffer，核心1 的 y = 1 操做缓存在本身和核心3的共享StoreBuffer中
因此 EBX = 0 ， CPU3的寄存器状态同理
3.测试n6 : 在 Intel Core 2 上能够观察到，但倒是被X86-CC模型和IWP说明禁止的
核心0 和 核心1 有各自的Store Buffer
核心0将 x = 1 缓存在本身的Store Buffer 中，而且根据 Store Forwarding 原则 , 核心0 读取 x 到 EAX 的时候
会读取本身的Store Buffer，读取x 的值是 1，故EAX = x = 1
同理，核心1也会缓存本身的写操做， 即缓存 y = 2 和 x = 2 到本身的 StoreBuffer，所以 y = 2 这个操做不会被
核心0 观察到，核心0 从主内存中加载 y 。故 EBX = y = 0
4.测试n5 / n4b ：实际上不能在任何CPU上观察到
n5和n4b是一样类型的测试，假如 核心0和 核心1都有本身的StoreBuffer
对于n5，核心0的EAX若是等于2，那么说明 核心1的StoreBuffer刷入到 共享的主存中, 那么 EAX = x 必然=执行于 x = 2
以后，一位 x = 1 对 EAX = x 来讲是有影响的，EAX = x 和 x = 1 禁止重排，那么 x = 1 必然不能出如今 x = 2 以前，
更不可能出如今 ECX = x 以前 （x = 2 对 ECX = x 也是有影响的，语义上严禁重排）
对于n4b，若是EAX = 2 ，说明 核心1的 x = 2 操做已经刷入主存被 核心0 观察到，那么对于 核心0来讲 x = 2 先于 EAX = x 执行
同上理，ECX = x 和 x = 2 也是严禁重排的，故 ECX = x 要先于 EAX = x 执行，更先于 x = 1 执行
n5 和 n4b 测试在AMD3.14 和Intel SDM 中好像是能够被容许的，也就是上面的 Forbidden Final State 被许可，但实际上不能
A Rigorous and Usable Programmer’s Model for x86 Multiprocessors 中做者原话 ： However, the principles stated in revisions 29–34 of the Intel SDM appear, presumably unintentionally, to allow them. The AMD3.14 Vol. 2, §7.2 text taken alone would allow them, but the implied coherence from elsewhere in the AMD manual would forbid them
其实是概念模型若是从局部描述，没有办法说确切，可是从总体上看，整个模型的说明不少地方都禁止了n5和n4b的发生，可见想描述一个松散执行顺序的CPU模型是多么难的一件事。软件开发者也没办法花大量的时间精力去钻研硬件的结构组成和工做原理，只能依靠硬件厂商提供的概念模型去理解硬件的行为
在AMD3.15的模型说明中，语言清晰地禁止了IRIW，而不是模棱两可的否认。
如下表格总结了上述的黑盒测试在不一样CPU模型中的观察结果（3.14 3.15是AMD不一样版本的模型，29~34是Intel SDM在这个版本范围的模型）
3.指令重排的发生
上述的黑盒测试的解释中，提到了重排的概念，让咱们看一下从软件层面的指令到硬件上，哪些地方可能出现 重排序：
CPU接收二进制指令流，流水线设计的CPU会依照流水线的方式串行地执行每条指令的各个阶段
举例描述：一个餐厅里 每一个人的就餐须要三个阶段：盛饭，打汤，拿餐具。有三个员工，每人各负责一个阶段，显然每一个员工只能同时处理一个客人，也就是同一时刻，同一阶段只能有一个客人，也就是任什么时候刻不可能出现两位客人同时打汤的状况，固然也不可能出现两个员工同时服务一个客人。能造成一条有条不紊的进餐流水线，不用等一个客人一口气完成3个阶段其余客人才能开始盛饭。
对于CPU也是，指令的执行分为 取指，译码，取操做数，写回内存 等阶段，每一个阶段只能有一条指令在执行。
CPU应当有 取值工做模块，译码工做模块，等等模块来执行指令。每种模块同一时刻只能服务一条指令，对于CPU来讲，流水线式地执行指令，是串行的，没有CPU聪明到给指令重排序一说，若是指令在CPU内部的执行顺序和高级语言的语义顺序不同，那么极可能是编译器优化重排，致使CPU接受到的指令
原本就是编译器重排过的。
真正的指令重排出如今StoreBuffer的不可见上，缓存一致性已经保证了CPU间的缓存一致性。具体重拍的例子就是第一个黑盒测试SB:
初值：x = 0, y = 0
在咱们常规的并发编程思惟中，会为这4条语句排列组合（按咱们的认知，1必定在2以前，3必定在4以前），而且认为不管线程怎么切换，这四条语句的排列组合（1在2前，3在4前的组合）必定有一条符合最后的实际运行结果。假如按照 1 3 2 4 这样的组合来执行，那么最后 EAX = 1 , EBX = 1，或者 1 2 3 4 这样的顺序来执行，最后 EAX = 0 且 EBX = 1，怎么都不可能 EAX = 0, EBX = 0
但实际上SB测试能够在Intel系列上观察到，从软件开发者的角度上看，就好像 按照 2 4 1 3 的顺序执行了同样，如同 2 被排在1 以前，3 被排在4 以前，是所谓 指令重排 的一种状况
实际上，是由于StoreBuffer的存在，才致使了上述的指令重排。
试想一下，CPU0将 x = 1 指令的执行缓存在了本身的StoreBuffer里，CPU1也把 y = 1 的执行缓存在本身的StoreBuffer里，这样的话当二者执行各自的读取操做的时候，亦即CPU0执行 EAX = y
CPU1执行 EBX = x , 都会直接去缓存或主存中读取，而缓存又MESI协议保证一致，可是不保证StoreBuffer一致，因此二者没法互相见到对方的StoreBuffer中对变量的修改，因而读到x, y都是初值 0
4.根据黑盒测试定义抽象内存模型 x86-TSO
从以上的试验没法总结出一套通用的内存模型，由于每一个CPU的实现不一样，可是咱们能够总结出一个合理的关于x86的内存模型
而且这个模型适合软件开发者参考，而且符合CPU厂商的意图
首先是关于StoreBuffer的设计：
1.在Intel SDM 和 AMD3.15模型中，IRIW黑盒测试是明文禁止的，而IRIW测试意味着某些CPU能够共享StoreBuffer因此咱们想创造的合理内存模型不能让CPU共享StoreBuffer
2.可是在上述黑盒测试中，好比n6和SB，都证实了，StoreBuffer确实存在
总结:StoreBuffer存在且每一个CPU独占本身的StoreBuffer
上述的黑盒测试代表，除了StoreBuffer形成的CPU写不能立刻被其余CPU观察到，各个CPU对主存的观察应该都是一致的，能够忽略掉缓存行，由于MESI协议会保证各个CPU的缓存行之间的一致性，可是没法保证StoreBuffer中的内容的一致性，由于MESI是缓存一致性协议，每一个字母对应缓存（cache）的一种状态，保证的只是缓存行的一致性。
总结一下：咱们想构造的x86模型的特色：
1. 在硬件上必然是有StoreBuffer存在的，设计时须要考虑进去
2. 缓存方面由于MESI协议，各个CPU的缓存之间不存在不一致问题，因此缓存和主存能够抽象为一个共享的内存
3. 额外的一个特色是 总线锁，x86提供了 lock 前缀 ，lock前缀能够修饰一些指令来达到 read-modify-write 原子性的效果，好比最多见的 read-modify-write 指令 ADD，CPU须要从内存中取出变量，
加一后再写回内存，lock前缀可让当前CPU锁住总线，让其余CPU没法访问内存，从而保证要修改的变量不会在修改中途被其余CPU访问，从而达到原子性 ADD 的效果。在x86中还有其余的指令自带
lock 前缀的效果，好比XCHG指令。带锁缓存行的指令在锁释放的时候会把StoreBuffer刷入共享存储
最后能够获得以下模型：
其中各颜色线段的含义：
红色：CPU的各个核心能够争夺总线锁，占有总线锁的CPU能够将本身的storeBuffer刷入到共享存储中（其实总线锁不是真的必定要锁总线，也能够锁缓存行，若是要锁的目标不仅一个缓存行，则锁总线），占有期间其余CPU没法将本身的storeBuffer刷入共享存储
橙色：根据StoreFowarding原则，CPU核心读取内存单元时，首先去StoreBuffer读取最近的修改，而且x86的StoreBuffer是遵循FIFO的队列，x86不容许CPU直接修改缓存行，因此StoreStore内存屏障在x86上是空操做，由于对于一个核心来讲，写操做都是FIFO的，写操做不会重排序。x86不容许直接修改缓存行也是缓存和主存能抽象成一体的缘由。
紫色: 核心向StoreBuffer写入数据，在一些英文文献中会表示为：Buffered writes to 变量名，也就是对变量的写会被缓存在StoreBuffer，暂时不会被其余CPU观察到
绿色: CPU核心将缓存的写操做刷入共享存储，除了有其余核心占有锁的状况 (由于其余核心占有锁的话，锁住了缓存行或总线，则当前核心不能修改这个缓存行或访问共享存储)，任何状况下，StoreBuffer均可以被刷入共享存储
蓝色：若是要读取的变量不在StoreBuffer中，则去共享存储读取（缓存或主存）
5.A Rigorous and Usable Programmer’s Model for x86 Multiprocessors 的发布团队在AMD/Intel系列CPU上进行的一系列黑盒测试及它们与x86-TSO模型结构的关系
在A Rigorous and Usable Programmer’s Model for x86 Multiprocessors 一文中，做者为了验证x86-TSO模型的正确性，在广泛流行的 AMD和 Intel 处理器上使用嵌入汇编的C程序进行测试。
而且使用memevents工具监视内存而且查看最终结果,而且用HOL4监控指令执行先后寄存器和内存的状态，最后进行验证，共进行了4600次试验。
结果以下：
1.写操做不容许重排序，不管是对其余核心来讲仍是本身来讲
解释：
从核心1 的角度看 核心0，x 和 y 的写入顺序不能颠倒
从x86-TSO模型的物理构件角度解释就是，写操做会按照 FIFO 的规则 进入 StoreBuffer，而且按照FIFO的顺序刷入共享存储，因此 写操做没法重排序。
因此 x = 1 写操做先入StoreBuffer队列，接着 y = 1 入，刷入共享存储的时候， x = 1 先刷入，y = 1 再刷入， 因此若是 y 读到 1 的话，x 必定不能是 0
2.读操做不能延迟 ：对于其余核心来讲，对于本身来讲若是不是同一个内存单元，是否重排可有可无，（由于读不能通知写，只有写改变了某些状态才能通知读去作些什么， 好比 x = 1; if (x == 1); ）
解释：
从核心1的角度观察，若是EBX = 1 , 那么说明 核心0的 y = 1 操做已经从 StoreBuffer中刷入到共享存储，以前说过，CPU流水线执行指令在物理上是不能对指令流进行重排的，因此 EAX = x 的操做 在 y = 1 以前执行
同理，EBX = y 这个读操做也不能延后到 x = 1 以后执行，因此 EAX = x 先于 y = 1 ，y = 1 先于 EBX = y , EBX = y 先于 x = 1 , 因此 EAX 不可能接受到 x = 1 的结果
3.读操做能够提早：上述2是读操做不能延后，可是能够提早，而且是从其余核心的角度观察到的
例子是 上面的 SB测试，
若是忽视StoreBuffer，从核心1的角度看，EBX = 0，说明 x = 1 未执行，那么 EBX = x 应该在 x = 1 以前执行，又由于 y = 1 在 EBX = x 以前，那么 y = 1 应该在 x = 1 以前，EAX = y 在 x = 1 以后，理应在 y = 1 以后
那么EAX 理应 = 1。
可是最后状态能够二者均为0.。就好像 读取的指令被从新排到前面（下面是一种重排状况）
在x86-TSO模型中，写操做是容许被提早的，从物理硬件的角度解释以下：
假设核心0是左边的核心，核心1是右边的核心，若是二者都把 写操做缓存在 StoreBuffer中，而且读操做执行以前，StoreBuffer没有同步回共享存储，那么二者读到的 x 和 y 都来自共享存储，而且都是 0。
4.对于单个核心来讲，由于Store Forwarding 原则，同一个内存单元 以前的写操做必对以后的读操做可见
解释：对一个核心而言，本身的写入是能立刻为本身所见的
5.写操做的可见性是传递的，这一点与 happens-before 原则的传递性相似，若是 A 能 看到 B 的动做，B能看到 C 的动做，那么 A必定能看到C 的动做
解释： 对于核心1，若是EAX = 1 ，那么说明核心1已经见到了 核心0的动做，对于核心2，EBX = 1，说明核心2已经见到了 核心1的动做，又根据以前的 读操做不能延后，EAX = x 不能延迟到 y = 1 以后，
因此 核心2 必能见到 核心0 的动做，因此 ECX = x 不能为 0
6.共享存储的状态对全部核心来讲都是一致的
上面的IRIW测试就是违反共享内存一致性的例子：
核心2 和 核心3 观察到 核心0 和 核心1 的行为，那么他们的行为应该都是同样的，由于都刷入到共享存储中了
7.带lock前缀的指令或者 XCHG指令，会清空StoreBuffer，使得以前的写操做立刻被其余核心观察到
解释：EAX一开始是1，将EAX的值写入 x ，核心0 的 XCHD会把StoreBuffer清空，亦即将 x = EAX (1) 刷入共享存储，核心1若是看到 x = 0 (EDX = 0 )，说明 x = EAX 在后面才执行。推得y = ECX 在 x = EAX 以前执行
y = ECX 也会立刻刷入共享存储，必然对 核心 0 可见，因此 最后不可能 x = 0, y = 0
MFENCE指令在x86-TSO模型上也能达到刷StoreBuffer的效果。
总结：在x86-TSO模型上，惟一可能重排序的清空是 读被提早了（从多个CPU的视角看），其实是 StoreBuffer缓存了写操做，致使写操做没写出来。
6.扩展：
6.1 经过Hotspot源码分析 java volatile 关键字的语意及其与x86-TSO/普通TSO内存模型的关系
Java 的 volatile语意：Hotspot实现
在JVM的字节码解释器中，若是putstatic字节码或putfield字节码的变量是java层面的volatile关键字修饰的，就会在指令执行的最后插入一道 storeLoad 屏障，前文已经说过，在x86中
惟一可能重排的是 读操做提早到 写操做以前，这里的storeLoad操做作的就是阻止重排
在os_cpu/linux_x86下的实现以下：
其实只是执行了一条带lock前缀的空操做嵌入汇编指令（栈顶指针+0是空操做），实现的效果就是把StoreBuffer中的内容刷入到 共享存储中
其实还有一层增强， __ asm __ 后面的volatile关键字 会阻止编译器对本条指令先后的指令重排序优化，这保证了CPU获得的指令流是符合咱们程序的语意的
在模板解释器中：
一开始我惊讶于此，这句话没有为不一样平台实现选择不一样的实现方法，而是简单检查若是不是须要 storeLoad 屏障就跳过。
其实做者注解已经说的很明白，如今大部分RISC的SPARC架构的CPU的实现都知足TSO模型，因此只须要StoreLoad屏障而已
我在新南威尔斯大学的网站上找到了关于TSO的比较正宗的解释：
下面的讨论中，是否须要重排序是根据CPU最后的行为是否符合咱们高级语言程序的语意顺序决定的，若是相同则不须要，不相同则须要。
也就是单个核心中，写操做之间是顺序的，会按二进制指令流的写入顺序刷到共享存储，不须要考虑重排的状况，因此不须要StoreStore屏障
遵循Store Forwarding，因此对于本核心，本核心的写操做对后续的读操做可见。这三点已经十分符合本文的x86-TSO模型。
有一点没有呈现，就是单个CPU核心中，是否禁止读延迟，也就是写操做不能跨越到读操做以前，根据上面的 只有StoreLoad 屏障有操做，其余屏障，包括LoadStore屏障无操做能够推断
普通的TSO模型也是遵循禁止读延迟原则的
6.2 Linux内存屏障宏定义 与 x86-TSO 模型的关系
Linux 的内存屏障宏定义
在Linux下定义的具备全功能的内存屏障，是有实际操做的，和JVM的storeLoad一模一样
读屏障是空操做，写屏障只是简单的禁止编译器重排序，防止CPU接收的指令流被编译器重排序。
只要编译器能编译出符合咱们高级语言程序语意顺序的二进制流给CPU，根据TSO模型的，CPU执行这些指令流的中的写操做对外部呈现出来的（刷入共享存储被全部CPU观察到）就是FIFO顺序
读操做不涉及任何状态变动，因此不须要内存屏障（也许只有在x86上才不须要，在其余有Invaild Queue的CPU结构中或许须要）
7.总结
本文总结：
x86-TSO模型的特色总结：
由于缓存有MESI协议保证一致性，因此缓存能够和主存合并抽象成共享存储
x86-TSO的写操做严格遵循FIFO
CPU流水线式地执行指令会使得CPU对接受到的指令流顺序执行
x86-TSO中惟一重排的地方在于StoreBuffer，由于StoreBuffer的存在，核心的写入操做被缓存，没法立刻刷新到共享存储中被其余核心观察到，因此就有了 “ 写 ” 比 “读” 晚执行的直观感觉，也能够说是读操做提早了，排到了写操做前
阻止这种重排的方法是 使用带 lock 前缀的指令或者XCHG指令，或MFENCE指令，将StoreBuffer中的内容刷入到共享存储，以便被其余核心观察到
8.本文参考文献
参考文献:
《Linux内核源代码情景分析》：毛德操
x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors