chapter4：TSO于X86内存模型

1、为什么需要TSO/x86

处理器内核长期以来使用write buffer来保存已提交的store指令，直到内存系统可以处理这些store请求。当store指令提交时，store请求进入write buffer，而当需要写入的缓存行在内存系统中可以保证缓存一致性时，store请求就退出write buffer。对单核处理器来说，如果在write buffer中存在对地址A的store，那么碰到对地址A的load指令时，可以直接返回即将store的值，或者也可以选择停顿load指令。write buffer的使用可以有效隐藏store的延时，并在load时通过bypassing提供写缓冲区内store的最新值。然而，在多核处理器中，写缓冲区的使用违反了SC模型，

假设一个具有有序内核的多核处理器，其中每个内核都有一个单项写入缓冲区，并按以下顺序执行上图代码

1. core1执行S1，并将NEW存放在core1的write buffer
2. 同样，core2执行S2，并将NEW存放在core2的write buffer
3. 接下来，两个core执行各自的load L1和L2，并获得旧值0
4. 最后，两个核心的write buffer将NEW值写入内存，此时x和y的值才真正发生改变。

执行完毕后，r1和r2同时为0，实际执行顺序类似于{L1,L2,S1,S2}违反了SC。

SPARC和x86的选择放弃SC，采用一种支持采用使用fifo作为write buffer的内存一致性模型。

2、TSO/x86基本思路

• Load → Load
• Load → Store
• Store → Store
• Store → Load

SC要求上述四种操作保留顺序，TSO保留前三种，不对第四种进行约束。

TSO与SC相比具有三点不同：

1. 不再维护"if S(a) <p L(b), S(a) <m L(b)"的顺序了。即允许在store未完成前可以先进行程序顺序靠后的load。这一点允许了FIFO 写缓冲区的存在。
2. 每条load从同地址的上一条store获取值(内存顺序上或程序顺序上）。这一点允许了FIFO 写缓冲区的bypassing机制。
3. 定义了FENCE来强制排序，FENCE的排序规则如下：
   load/store→FENCE; //程序顺序先于FENCE的访存都先于FENCE执行
   FENCE→load/store; //程序顺序位于FENCE之后的访存都后于FENCE执行
   FENCE→FENCE; //FENCE之间的程序顺序和内存顺序一致
   这一点允许了程序员可选择地维护Store→Load的顺序来严格按指令顺序执行。

L1通过bypass获取到S1中new的值，同样L2通过bypass获取到S2中new的值。但由于S1和S2进入write buffer，因此L2和L4获取不到x和y的更新值。

3、一点 TSO/X86 正式化方法

TSO 执行需要以下内容

1、所有核心都将它们的load和store插入到内存顺序 <m 中，考虑到它们的程序顺序，无论它们是相同还是不同的地址（即 a==b 或 a!=b）。有四种情况：

• If L(a) <p L(b) => L(a) <m L(b) /Load -> Load/
• If L(a) <p S(b) => L(a) <m S(b) /Load -> Store/
• If S(a) <p S(b) => S(a) <m S(b) /Store -> Store/
• 删除：If S(a) <p L(b) => S(a) <m L(b) /*Store -> Load*/，改为：/*Change 1: Enable FIFO Write Buffer*/

2、每个load从它之前的最后一个store中获取它的值到相同的地址：

• 删除：Value of L(a) = Value of MAX <m {S(a) | S(a) <m L(a)}，改为：/*Change 2: Need Bypassing*/
• Value of L(a) = Value of MAX <m

3、 定义 FENCE：/Change3: FENCEs Order Everything/

• If L(a) <p FENCE => L(a) <m FENCE /Load -> FENCE/
• If S(a) <p FENCE => S(a) <m FENCE /Store -> FENCE/
• If FENCE <p FENCE => FENCE <m FENCE /FENCE -> FENCE/
• If FENCE <p L(a) => FENCE <m L(a) /FENCE -> Load/
• If FENCE <p S(a) => FENCE <m S(a) /FENCE -> Store/

让TSO的FENCE作为所有内存请求的分界，这样设计比较简单，不影响正确性，且和之后更宽松的内存模型中的FENCE保持一致。

4、实现

TSO在SC的基础上允许了FIFO 写缓冲区的存在，loads/stores以程序顺序离开各个core，store的消息从buffer末尾进入，从buffer头部输出给switch。当switch选中core Ci时，进行load或者buffer头部的store。

在TSO模型中如果程序员想要store→load的memory顺序被维护，则需要显示的在store和load指令之间添加FENCE。

在多线程中，TSO的write buffer在逻辑上对每个线程都是私有的，因此在一个多线程内核中，一个线程上下文不应该从另一个线程的write buffer中通过旁路获取数据，这种逻辑上的分离可以通过每个线程实现单独的write buffer实现，或者更常见的是通过共享write buffer，但每个条目都由线程id进行标记，只有id匹配时才可以bypass。

5、TSO的atomic和fence

实现TSO的系统必须实现atomic指令和fence指令

TSO与SC的区别在于允许load bypass以及store可能写入write buffer。对于原子指令RMW可以理解为一个load紧跟着一个store。由于RMW要求是一个整体，所以load不能bypass上一个store，因此load要等上一个store退出write buffer之后才可以执行。同时，为了确保load之后可以马上store，load时需要将缓存一致性状态更新为读写状态（如M状态），而不是一般的只读状态（如S状态）。最后，为了保证原子性，在load和store之间不能更新缓存一致性状态。

6、比较SC与TSO

我们可以发现，从执行和实现的角度来说，SC都是TSO的一个子集。更一般来说，如果所有符合X模型的执行顺序也符合Y模型的执行顺序，那么Y模型比X模型更宽松（更弱），或者X模型比Y模型更严格。不过也有可能两个内存模型时不可比的，X模型允许Y模型中不允许的顺序，同时Y模型也允许一些X模型中不允许的顺序。