内存避障的前世今生

相关 《内存避障：一个内存乱序实例》 《内存避障的前世今生》

0 总结

单核下的指令多队列可能造成单核无法保证顺序一致性的问题，如果单核都无法保证，那多核肯定也有一样的问题了。

（ARM架构单核无法保证顺序一致性、X86架构单核可以保证顺序一致性，因为X86单核多指令队列但会把结果重排输出，结果顺序看起来和输入一样）。

ok在单核能保证顺序一致性的前提下继续讨论（X86），在多核场景下，MESI保证了多核间缓存数据的强一致性。

（MESI其实就是一个分布式的缓存一致性策略，如果对比共享存储、多点可写的数据库架构，L1、L2等于数据库每个节点的私有缓存，L3等于共享存储） . （废话一句，多点可写的共享存储数据库如果实现出来，协议基本也就是MESI的样子，但在TP场景，性能肯定是不能接受的，但是也不能引入stroebuffer，TP数据库需要强一致性。）

但MESI严重阻塞CPU执行队列，CPU性能无法发挥，这里最大的问题就是写入，MESI写入后需要发"I"到其他核心，必须同步等待返回值，才能完成写入动作。

所以引入storebuffer，写入不再直接写入L1，而是写入stroebuffer（相当于L1的缓存），写入后不在同步等待，而是直接继续执行下一条指令。由stroebuffer发送"I"到其他核心。其他核心收到"I"后，也不会立即失效cacheline，而是将"I"放入失效队列，异步处理。

这样写的动作就变成全异步了，同时也会发生数据不一致的问题（现在是最终一致性，处理完stroebuffer、invalid queue才最终一致）。具体问题就是某core读取时没拿到最新数据，数据还在别的core的strorebuffer中、或者 数据已经失效了但本core还没来得及处理失效队列的消息。效果都是看到了旧的数据，看起来就是发生了指令乱序。

ok指令乱序发生了，我们硬件是不能自己处理的，需要软件层面增加sync语义的命令，把storebuffer和invalidqueue的缓存数据刷出，恢复MESI的强一致性，避免看到旧数据即可解决。

这里sync语义的命令就是内存避障。

1 顺序一致性是什么？

顺序一致性是我们自然而然地想到多线程程序的方式。这也是我们看待世界的方式。如果 A 发生在 B 之前，那么 B 发生在 A 之前是不正确的。如果一个处理器将 1 存储在变量 x 中，而另一个处理器将 1 存储在变量 y 中，则事件序列为：

• x → 1 and then y → 1
• y → 1 and then x → 1

（假设两者最初都为零）。

加载两个变量的第三个处理器可以观察到实际发生的序列。例如，如果它看到 x == 1 和 y == 0，它会得出结论，对 x 的写入发生在更早的时候。如果它看到 x == 0 和 y == 1，它会得出结论，对 y 的写入发生在更早的时候（如果它看到 x == y，则无法判断哪个更早）。

在顺序一致的世界中，其他处理器看到的顺序应该和第三个处理器一样，所有处理器应该都能看到一样的事件队列。

在多核处理器上，很多事情可以同时发生，除非涉及内存访问。顺序一致模型假设所有处理器和内存之间只有一个开关，并且一次只有一个处理器可以访问它。这个虚构的开关用作序列化点。

Sequential consistency wiki:

注意： x86架构多核*不*保证顺序一致性。

注意：x86架构单核保证顺序一致性。

参考上一篇中的实例内存避障fence（一）一个内存乱序实例可知，x86不提供多核场景下的顺序一致性，但保证单核的顺序一致性。

x86单核上多指令队列也是乱序执行的，为什么能保证一致性？ . 因为单核的执行结果会有指令重拍，storebuffer是严格FIFO的，虽然执行时乱序，但输出时一定有序。 注意ARM在单核上也没有顺序一致性的保证。

简单的解释是：多核之间不存在一个串行化的总线去访问内存，而是每个内核写自己的缓存，通过MESI协议做同步。

2 为什么X86多核不能提供顺序一致性？

这里背景知识比较多，这里做下总结：

需要注意的是：

• MESI本身是强一致性协议，任何数据不一致的问题都不会发生。
• 引入store buffer和invalidate queue后，MESI只负责L1、L2、L3缓存，不涉及其他缓存，所以store buffer和invalid queue会导致短时间的数据不一致的问题，强一致性 退化为 最终一致性。

3 Store Buffer和Invalidate Queue实例解析

3.1 MESI

3.2 Store Bufferes 缓存存储

当处理器需要把修改写入缓存时，然后在写入内存这个过程时处理器不需要等待了。只需要把指数据写入Store Bufferes，然后发生Invalidate消息给其它CPU，然后本CPU就可以去执行其它指令了，等到我们都收所有回复确认Invalidate Acknowledge消息，在把Store Bufferes消息写回缓存修改状态为（M），如果有其它CPU来读，就会刷新到内存，状态变为S。

Store Bufferes 的作用是让 CPU 需要写的时候仅仅将其操作交给 Store Buffere，然后继续执行下去，Store Bufferes 在某个时刻就会完成一系列的同步行为。

3.3 Invalidate Queues 无效队列

修改数据时需要使其它处理器数据失效，这其实也是一系列的写操作，如果我们这些消息都交给Store Bufferes处理，Store Bufferes速度快，但是容量很小，所以就设计出了Invalidate Queues，当别的CPU收到Invalidate消息时，把这个操作加入无效队列，然后快速返回Invalidate Acknowledge消息，让发起者做后续操作，然后Invalidate并不是马上处理，而只是加入了队列，也就是说其实不是立刻让本CPU的缓存数据失效，而是等CPU处理无效队列里的无效消息时再失效。

3.4 实例：问题如何发生

int *result = 0;  // point to shared memory
int *flat = 0;    // point to shared memory

/* processor #1 */
int write()
{
    *result = 213;
    *flag = 1;
}

/* processor #2 */
int check()
{
    while(*flag)
    {
        printf("%d\n", *result);
    }
}

两核心并发，processor1执行write()、processor2执行check()

p2检查*result时可能拿到两个值，因为p1的storebuffer可能还没刷，或者p1的storebuffer已经刷了，但p2还没处理自己的无效队列。

3.5 实例：加入内存屏障解决问题

硬件 level 上很难揣度软件上这种前后数据依赖关系，因此往往无法通过某种手段自动的避免这种问题，因而只有通过软件的手段表示（对应也需要硬件提供某种指令来支持这种语义），这个就是 Memory Barrier（内存屏障）。

• Store Memory Barrier是一条告诉处理器在执行这之后的指令之前，应用所有已经在存储缓存（store buffer）中的保存的指令。
• Load Memory Barrier是一条告诉处理器在执行任何的加载前，先应用所有已经在失效队列中的失效操作的指令。

解决：

int *result = 0;  // point to shared memory
int *flat = 0;    // point to shared memory

/* processor #1 */
int write()
{
    *result = 213;
    [ Store Memory Barrier ]
    *flag = 1;
}

/* processor #2 */
int check()
{
    while(*flag)
    {
        [ Load Memory Barrier ]
        printf("%d\n", *result);
    }
}

• [ Store Memory Barrier ]的必要性：写避障保证了数据从storebuffer刷到L3中，能被其他核看到。
• [ Load Memory Barrier ]的必要性：读避障保证了其他核去L3中拿最新的数据，而不是从自己的缓存里面拿旧数据。

所以当前场景下，上述两个避障缺一不可。

3.6 X86的内存避障

1. Store Memory Barrier

- 写屏障，等同于前文的StoreStore Barriers
- 告诉处理器在执行这之后的指令之前，执行所有已经在存储缓存（store buffer）中的修改（M）指令。
- 即：所有store barrier之前的修改（M）指令都是对之后的指令可见。
- **即：把storebuffer中保存的异步的写指令，全部刷出到L3中。**Load Memory Barrier：读屏障，等同于前文的LoadLoad Barriers

- 告诉处理器在执行任何的加载前，执行所有已经在失效队列（Invalidte Queues）中的失效（I）指令。
- 即：所有load barrier之前的store指令对之后（本核心和其他核心）的指令都是可见的。
- **即：把失效队列中的，别的core发过来的失效信息全部处理掉，避免以为自己数据是最新的，不去L3中拿。**Full Barrier：万能屏障，即Full barrier作用等同于以上二者之和。

- 即所有store barrier之前的store指令对之后的指令都是可见的，之后（本核心和其他核心）的指令也都是可见的，完全保证了数据的强一致性。