北京最好白癜风医院 http://www.znlvye.com/Abstract
/p>
如今大数据，云计算，分布式系统等对算力要求高的方向如火如荼。提升计算机算力的一个低成本方法是增加CPU核心，而不是提高单个硬件工作效率。
这就要求软件开发者们能准确，熟悉地运用高级语言编写出能够充分利用多核心CPU的软件，同时程序在高并发环境下要准确无误地工作，尤其是在商用环境下。
但是做为软件工程师，实际上不太可能花大量的时间精力去研究CPU硬件上的同步工作机制。
退而求其次的方法是总结出一套比较通用的内存模型，并且运用到并发编程中去。
本文结合对CPU的黑盒测试，介绍一个能够通用于x86系列CPU的并发编程的内存模型。
此内存模型被测试在AMD与x86系列CPU上具有可行性，正确性。
本文章节：
1.关于各型号CPU的说明书规定或模型规定
2.官方发布的黑盒测试及它们可复现/不可复现的CPU型号
3.指令重排的发生
4.根据黑盒测试定义抽象内存模型x86-TSO
5.ARigorousandUsableProgrammer’sModelforx86Multiprocessors的发布团队在AMD/Intel系列CPU上进行的一系列黑盒测试及它们与x86-TSO模型结构的关系
6.扩展
6.1通过Hotspot源码分析javavolatile关键字的语意及其与x86-TSO/普通TSO内存模型的关系
6.2Linux内存屏障宏定义与x86-TSO模型的关系
7.总结
8.参考文献
1.各个型号CPU的规定
CPU相关的模型或规定：
x86-CC模型（出自Thesemanticsofx86-CCmultiprocessormachinecode.InProc.POPL,Jan.）
IWP(IntelWhitePaper，英特尔在年8月发布的一篇CPU模型准则，内容给出了P1~P8共8条规则，并且用10个在CPU上的黑盒测试
来支持这8条规则)
IntelSDM(继承IWP的Intel模型)
AMD3.14说明手册对CPU的规定
2.官方黑盒测试
下面的可在...观察到，不可在...观察到，都是针对最后的State而言，亦即Proc0:EAX=0^...语句表示的最终状态
其中倒着的V是且的意思
以下提到的StoreBuffer即CPU核心暂时缓存写入操作的物理部件，StoreBuffer中的写入操作会在任意时刻被刷入共享存储（主存/缓存），前提是总线没被锁/缓存行没被锁
以下提到的StoreFowarding指的是CPU核心在读取内存单元时会去StoreBuffer中寻找该变量，如果找到了就读取，以便得到该内存单元在本核心上最新的版本
1.测试SB:可在现代IntelCPU和AMDx86中观察到
核心0和核心1各有自己的StoreBuffer，会造成上述情况。
核心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:在IntelCore2上可以观察到，但却是被X86-CC模型和IWP说明禁止的
核心0和核心1有各自的StoreBuffer
核心0将x=1缓存在自己的StoreBuffer中，并且根据StoreForwarding原则,核心0读取x到EAX的时候
会读取自己的StoreBuffer，读取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和IntelSDM中好像是可以被允许的，也就是上面的ForbiddenFinalState被许可，但实际上不能
ARigorousandUsableProgrammer’sModelforx86Multiprocessors中作者原话：However,theprinciplesstatedinrevisions29–34oftheIntelSDMappear,presumablyunintentionally,toallowthem.TheAMD3.14Vol.2,§7.2texttakenalonewouldallowthem,buttheimpliedcoherencefromelsewhereintheAMDmanualwouldforbidthem
实际上是概念模型如果从局部描述，没有办法说确切，但是从整体上看，整个模型的说明很多地方都禁止了n5和n4b的发生，可见想描述一个松散执行顺序的CPU模型是多么难的一件事。软件开发者也没办法花大量的时间精力去钻研硬件的结构组成和工作原理，只能依靠硬件厂商提供的概念模型去理解硬件的行为
在AMD3.15的模型说明中，语言清晰地禁止了IRIW，而不是模棱两可的否定。
以下表格总结了上述的黑盒测试在不同CPU模型中的观察结果（3..15是AMD不同版本的模型，29~34是IntelSDM在这个版本范围的模型）
3.指令重排的发生
上述的黑盒测试的解释中，提到了重排的概念，让我们看一下从软件层面的指令到硬件上，哪些地方可能出现重排序：
CPU接收二进制指令流，流水线设计的CPU会依照流水线的方式串行地执行每条指令的各个阶段
举例描述：一个餐厅里每个人的就餐需要三个阶段：盛饭，打汤，拿餐具。有三个员工，每人各负责一个阶段，显然每个员工只能同时处理一个客人，也就是同一时刻，同一阶段只能有一个客人，也就是任何时刻不可能出现两位客人同时打汤的情况，当然也不可能出现两个员工同时服务一个客人。能形成一条有条不紊的进餐流水线，不用等一个客人一口气完成3个阶段其他客人才能开始盛饭。
对于CPU也是，指令的执行分为取指，译码，取操作数，写回内存等阶段，每个阶段只能有一条指令在执行。
CPU应当有取值工作模块，译码工作模块，等等模块来执行指令。每种模块同一时刻只能服务一条指令，对于CPU来说，流水线式地执行指令，是串行的，没有CPU聪明到给指令重排序一说，如果指令在CPU内部的执行顺序和高级语言的语义顺序不一样，那么很可能是编译器优化重排，导致CPU接受到的指令
本来就是编译器重排过的。
真正的指令重排出现在StoreBuffer的不可见上，缓存一致性已经保证了CPU间的缓存一致性。具体重拍的例子就是第一个黑盒测试SB/p>
初值：x=0,y=0
在我们常规的并发编程思维中，会为这4条语句排列组合（按我们的认知，1一定在2之前，3一定在4之前），并且认为无论线程怎么切换，这四条语句的排列组合（1在2前，3在4前的组合）一定有一条符合最后的实际运行结果。假如按照这样的组合来执行，那么最后EAX=1,EBX=1，或者这样的顺序来执行，最后EAX=0且EBX=1，怎么都不可能EAX=0,EBX=0
但实际上SB测试可以在Intel系列上观察到，从软件开发者的角度上看，就好像按照的顺序执行了一样，如同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.在IntelSDM和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写入数据，在一些英文文献中会表示为：Bufferedwritesto变量名，也就是对变量的写会被缓存在StoreBuffer，暂时不会被其他CPU观察到
绿色:CPU核心将缓存的写操作刷入共享存储，除了有其他核心占有锁的情况(因为其他核心占有锁的话，锁住了缓存行或总线，则当前核心不能修改这个缓存行或访问共享存储)，任何情况下，StoreBuffer都可以被刷入共享存储
蓝色：如果要读取的变量不在StoreBuffer中，则去共享存储读取（缓存或主存）
5.ARigorousandUsableProgrammer’sModelforx86Multiprocessors的发布团队在AMD/Intel系列CPU上进行的一系列黑盒测试及它们与x86-TSO模型结构的关系
在ARigorousandUsableProgrammer’sModelforx86Multiprocessors一文中，作者为了验证x86-TSO模型的正确性，在普遍流行的AMD和Intel处理器上使用嵌入汇编的C程序进行测试。
并且使用memevents工具监视内存并且查看最终结果,并且用HOL4监控指令执行前后寄存器和内存的状态，最后进行验证，共进行了次试验。
结果如下：
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.对于单个核心来说，因为StoreForwarding原则，同一个内存单元之前的写操作必对之后的读操作可见
解释：对一个核心而言，自己的写入是能马上为自己所见的
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源码分析javavolatile关键字的语意及其与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屏障
遵循StoreForwarding，所以对于本核心，本核心的写操作对后续的读操作可见。这三点已经十分符合本文的x86-TSO模型。
有一点没有呈现，就是单个CPU核心中，是否禁止读延迟，也就是写操作不能跨越到读操作之前，根据上面的只有StoreLoad屏障有操作，其他屏障，包括LoadStore屏障无操作可以推断
普通的TSO模型也是遵循禁止读延迟原则的
6.2Linux内存屏障宏定义与x86-TSO模型的关系
Linux的内存屏障宏定义
在Linux下定义的具有全功能的内存屏障，是有实际操作的，和JVM的storeLoad如出一辙
读屏障是空操作，写屏障只是简单的禁止编译器重排序，防止CPU接收的指令流被编译器重排序。
只要编译器能编译出符合我们高级语言程序语意顺序的二进制流给CPU，根据TSO模型的，CPU执行这些指令流的中的写操作对外部呈现出来的（刷入共享存储被所有CPU观察到）就是FIFO顺序
读操作不涉及任何状态变更，所以不需要内存屏障（也许只有在x86上才不需要，在其他有InvaildQueue的CPU结构中或许需要）
7.总结
本文总结：
x86-TSO模型的特点总结：
因为缓存有MESI协议保证一致性，所以缓存可以和主存合并抽象成共享存储
x86-TSO的写操作严格遵循FIFO
CPU流水线式地执行指令会使得CPU对接受到的指令流顺序执行
x86-TSO中唯一重排的地方在于StoreBuffer，因为StoreBuffer的存在，核心的写入操作被缓存，无法马上刷新到共享存储中被其他核心观察到，所以就有了“写”比“读”晚执行的直观感受，也可以说是读操作提前了，排到了写操作前
阻止这种重排的方法是使用带lock前缀的指令或者XCHG指令，或MFENCE指令，将StoreBuffer中的内容刷入到共享存储，以便被其他核心观察到
8.本文参考文献
参考文献/p>
《Linux内核源代码情景分析》：毛德操
x86-TSO:ARigorousandUsableProgrammer’sModelforx86Multiprocessors
MemoryBarriers:aHardwareViewforSoftwareHackers
