本文翻译自
Memory Access Ordering – an introduction
.
该系列有 3 篇文章，其余两篇是：
Memory access ordering part 2: Barriers and the Linux kernel
， 译文：
内存访问顺序 – part2: 屏障及Linux kernel中屏障的使用
Memory access ordering part 3: Memory access ordering in the Arm Architecture
，译文：
内存访问顺序 – part3: ARM体系架构中的内存访问顺序
作者
Leif Lindholm
在 ARM 工作多年，经验丰富，虽然这篇文章发表于 2013 年，但是还是很有借鉴价值的。
我最近在
2010 年欧洲嵌入式 Linux 大会
上做了一个名为“
高性能内存系统的软件含义
”(译者注：
幻灯片
,
视频
)的报告。这个标题很成功地吸引人们参与到内存访问顺序（重排）和内存屏障的话题中来。我现在想就这个话题发表几篇博文。在本文中，我将介绍一些概念并解释背后的原因。在以后的文章中，我将继续介绍一些实际的例子。
顺序执行模型（The Sequential Execution Model）
在过去的美好时光中，计算机程序实际的行为几乎与源代码期望的行为一致：
- 事情按照程序中指定的方式发生。
-
事情按照程序中指定的
顺序
发生。 - 事情发生的次数与程序中指定的次数相同（不多也不少）。
-
事情一件一件地发生。
（译者注：串行）
在现在计算机体系结构中，上述这种怀旧幻想的方式有时被称为
顺序执行模型（Sequential Execution Model
）。为了使现有的程序和编程模型保留这种功能，即使是最极端的现代处理器也会试图在执行程序中保留顺序执行的假象。但是，在处理器外仍然有很多事情无法隐藏。美好的时光一去不复返。
现实
但是，实际情况是为了提高性能（速度和功率），在系统的不同级别上执行了很多的优化。
（译者注：理想很丰满，现实很骨感，虽然处理器架构想要极力隐藏编程模型的细节，让应用开发者感觉程序都是在按照源代码的预期顺序执行的，但是有一些例外无法隐藏，还是需要应用开发者了解其中的细节。）
编译最佳化技术（Optimizing Compilers）
优化的编译器可以大量重构代码以隐藏流水线延迟或利用微体系架构的特点来进行优化。它可以决定更早地访问内存以便在需要该值之前给它更多的时间来完成，或者推迟访问内存以平衡程序执行。实际上，在一个高度流水线化的处理器里编译器可能会重排所有类型的指令，以便在需要其结果时可以使用先前指令的结果。
下面是一个常用来解释这个问题的经典例子：
int flag = BUSY;
int data = 0;
int somefunc(void)
{
while (flag != DONE);
return data;
}
void otherfunc(void)
{
data = 42;
flag = DONE;
}
假设上述代码在两个线程中运行，线程A 调用
otherfunc()
更新变量
data
的值，并设一个完成的标志
flag
. 线程 B 调用
somefunc()
等待线程B送来的完成信号，然后返回
data
的值。在 C 语言的规范中没有任何内容可以保证
somefunc()
在开始轮询标志前不会生成读取数据
data
的代码，这意味着
somefunc()
返回 0 或者 42 都是完全合法的（
译者注：这是编译器级别的指令重排
）。虽然在代码生成过程中有一些方法可以解决此问题，但是这仍然无法阻止硬件级别的重排。
多次发射（Multi-issuing）
许多现代处理器支持每个时钟周期（
clock cycle
）发射（或执行）多条指令。即使你显式将一个汇编指令放在另一条汇编指令之后，它们也可能最终被并行发射和执行。
想象有如下一段 ARM 汇编指令序列：
在双发射（
dual-issuing
）处理器上，此序列实际上可能是这样执行的：
add
指令和
mul
指令无依赖关系，可以并行发出；
ldr
指令 和
mov
指令也无依赖关系，也可以并行发出。但是
str
指令需要依赖
sub
指令的
r1
的值，所以不能并行发出，所以在
Cycle 2
中
Issue1
没有发出任何指令。
乱序执行（Out-of-order execution）
第一个支持乱序执行的 Arm 处理器是
Arm1136J(F)-S
，它允许非依赖性的加载和存储操作彼此乱序完成。在实际应用中，只要没有数据依赖性，
cache miss
的数据访问可以被其他
cache hit
（或
cache miss
）的数据访问所取代。它还允许加载-存储指令与没有数据依赖性的数据处理指令（例如，一个加载指令为后面的加载或存储指令提供地址，这就是有数据依赖性）乱序地完成。
到了
Cortex-A9
，它支持在许多情况下对大多数非依赖指令的乱序执行。当一条指令因为在等待前面一条指令的结果而暂停时，内核可以继续执行后面的没有依赖关系的指令。
以下面的代码片段为例，在一些架构上，
mul
和
ldr
指令需要多个时钟周期，这里假设需要 2 个周期。
add r0, r0, #4
mul r2, r2, r3
str r2, [r0]
ldr r4, [r1]
sub r1, r4, r2
bx lr
如果我们在顺序处理器上执行，其执行结果如下：
但当我们在乱序处理器上执行，我们看到的结果可能如下：
因为
mul
指令需要 2 个周期，而接下来的
str
指令等待
mul
指令的结果，
ldr
指令与
mul
指令没有数据依赖关系，所以
ldr
被提前执行，当
ldr
指令执行完后，
mul
指令也已经执行完成了，
str
指令可以执行了。等
str
指令执行完，
ldr
指令也执行完成了，依赖于其结果的
sub
指令无需等待，可以立即执行。
推测（Speculation）
推测可以简单的描述为内核在知道是否应该执行某条指令之前执行或开始执行该指令。如果推测是正确的，就可以很快得到指令的结果。例如，当代码在
Arm
或
Thumb
指令集中使用通用条件执行时，或者当内核遇到条件分支指令时，内核可以推测性地执行条件指令或条件指令之后的指令。如果推测不正确，内核需要有能力消除推测不正确带来的影响，保证程序可以正常地执行。
在涉及内存加载指令的地方，推测可以更进一步。可以推测性地发出（
issue
)来自可缓存（
cacheable
)位置的负载，这可能会导致现有的缓存行（
cache line
）被驱逐，从外部存储器复制数据到该缓存行。许多现代处理器还可以监视数据访问以检测模式，在指令进入流水线之前就将模式中后续的指令加载进
cache
.
加载存储优化（Load-Store Optimizations）
高性能系统中的外部存储器访问往往具有显著的延迟。为了减少延迟，处理器很大程度上试图优化其内存访问以便通过在每个
事务
（
transaction
）中写入更多的数据来减少事务的数量。使用
突发
（
burst
）来传输仅具有单个事务延迟的较长数据流。这意味着对缓冲内存的多次写入可以合并到一个事务中。
多核 Cache 一致性
在多核处理器上，基于硬件的缓存一致性管理可以使
cache line
在核间透明地迁移。这可能导致不同的内核以不同的顺序看到缓存内存位置的更新。
举一个具体的例子：上面例子中的
somefunc()
和
othefunc()
如果在多核SMP 系统中执行还存在另一个潜在的问题。如果两个线程在不同的内核上执行，那么硬件缓存一致性管理、推测和乱序执行都会影响内核看到的内存访问的顺序，即每个内核看到的顺序可能是不同的。
简单地说，硬件缓存一致性管理意味着
cache line
可以在内核之间移动，以便在访问它们的任何地方都可以使用。
由于具有乱序能力的处理器可以在等待一个加载（或存储）的结果完成的同时从高速缓存中加载另一个内存位置，因此执行
somefunc()
的内核完全可以在
flag
更改为
DONE
之前推测性地执行加载
data
的 指令——即使这并不是程序编译出来的指令顺序。
外部内存系统（External Memory Systems）
即使您进入外部存储系统，这种复杂性仍在继续。为了在具有很多总线主控（代理）的系统中实现高性能，可能需要在多层系统中配置互连。这意味着不同的代理（或主控）到系统中各个设备（或从设备）有不同的路由。另外，像内存控制器这样的外围设备可能有多个从接口，允许多个代理同时访问它。
最后，允许缓冲的内存事务几乎可以在任何时候进行缓冲，而且可能不止一次缓冲，这可能导致来自不同主机的访问在不同的情况下需要花费不同的时间来完成。
结论
在现代计算机系统中，很多事情发生的顺序可能与人们直观地想到的顺序不同，而且系统中的每个代理看到的顺序也可能不同。在接下来的文章中，我将介绍这在实践中的含义以及您可能需要做的事情。
参考文献
Kourosh Gharachorloo –
MEMORY CONSISTENCY MODELS FOR SHARED-MEMORY MULTIPROCESSORS
(PDF)