内存一致性模型(2016)

当然，计算机科学中只有两件棘手的事情：缓存失效、命名和逐个错误。但是，在计算机科学的杂草丛生中，潜藏着另一个难题：把事情看得井井有条。无论是排序、不排序，还是发推文，看事情是否井然有序，都是一个世代的挑战。

一个常见的排序挑战是内存一致性，这是定义并行线程如何观察其共享内存状态的问题。关于内存一致性的资源很多，但大多数要么是幻灯片(就像我的！)，要么是密集的大部头。我的目标是制作一本入门读物，并说明为什么内存一致性是多核系统的一个问题。有关详细信息，您当然应该参考其他优秀的参考资料。

一致性模型处理多个线程(或工作线程、节点或副本等)查看世界的方式。考虑这个运行两个线程的简单程序，其中A和B最初都为0：

要了解此程序可以输出的内容，我们应该考虑其事件发生的顺序。实际上，此程序可以按照两个明显的顺序运行：

(1)→(2)→(3)→(4)：第一个线程在第二个线程之前运行它的两个事件，因此程序打印01。

(3)→(4)→(1)→(2)：第二个线程在第一线程之前运行它的两个事件。程序仍然打印01。

还有一些不太明显的顺序，其中指令相互交错：

(1)→(3)→(2)→(4)：每个线程中的第一条指令在任一线程中的第二条指令之前运行，打印11。

(1)→(3)→(4)→(2)：运行来自第一线程的第一条指令，然后运行来自第二个线程的两条指令，然后运行来自第一线程的第二条指令。程序仍然打印11个。

直觉上，这个程序应该不可能打印00。对于要打印0的第(2)行，我们必须在第(3)行向其写入1之前打印B。我们可以用图形化的方式用一条边来表示：

从x运算到y运算的一条边表明，x必须发生在y之前，才能得到我们感兴趣的行为。类似地，对于要打印0行(4)，打印必须在行(1)将1写入A之前进行，因此让我们将其添加到图中：

当然，最后，每个线程的事件应该按顺序发生-(1)在(2)之前，(3)在(4)之前-因为这是我们对命令式程序的期望。因此，让我们也添加这些边：

但现在我们有问题了。如果我们从(1)开始，然后沿着边-到(2)，然后是(3)，然后是(4)，然后是…。(1)又来了！记住，边缘是说哪些事件必须在其他事件之前发生。因此，如果我们从(1)开始，并再次返回到(1)，则该图说明(1)必须在其本身之前发生！除非在物理学方面取得非常令人担忧的进展，否则这是不太可能的。

由于此执行需要时间扭曲，因此我们可以得出结论，此程序不能打印00。可以把它看作是一个矛盾证明：假设这个程序可以打印00。那么我们刚才展示的所有排序规则都必须成立。但是这些规则导致了一个矛盾(事件(1)发生在它自己之前)。所以这个假设是错误的。

架构师和编程语言设计人员相信我们刚才探索的规则对程序员来说是直观的。其思想是并行运行的多个线程操作单个主内存，因此所有事情都必须按顺序进行。不存在两个事件可以“同时”发生的概念，因为它们都在访问单个主内存。

请注意，此规则没有说明事件发生的顺序-只是说明它们按某种顺序发生。此直观模型的另一部分是事件按程序顺序发生：单个线程中的事件按其编写的顺序发生。这就是程序员所期待的：如果我的程序在检查钥匙是否转动之前就被允许发射导弹，那么各种不好的事情都会开始发生。

这两条规则(单个主存储器和程序顺序)共同定义了顺序一致性。定义顺序一致性是为Leslie Lamport赢得2013年图灵奖的众多成就之一。1个。

顺序一致性是我们的第一个内存一致性模型示例。内存一致性模型(我们通常简称为“内存模型”)定义了多处理器上多个线程的允许排序。例如，在上面的程序中，顺序一致性禁止任何导致打印00的排序，但允许打印01和11的某些排序。

内存一致性模型是硬件和软件之间的合同。硬件承诺只以模型允许的方式重新排序操作，作为回报，软件承认所有这样的重新排序都是可能的，并且需要考虑到它们。

考虑顺序一致性的一个很好的方法是将其视为一个开关。在每个时间步，开关选择要运行的线程，并完全运行其下一个事件。此模型保留了顺序一致性规则：事件访问单个主内存，因此按顺序发生；通过始终运行选定线程的下一个事件，每个线程的事件按程序顺序发生。

这种模式的问题是，它的速度非常慢，而且是灾难性的。我们一次只能运行一条指令，因此失去了让多个线程并行运行的大部分好处。更糟糕的是，我们必须等待每条指令完成，然后才能开始下一条指令-在当前指令的效果对其他所有线程都可见之前，不能再运行更多指令。

有时，这种等待的要求是有意义的。考虑这样一种情况，其中两个线程都想要写入另一个线程想要读取的变量A：

如果我们放弃单一主内存的想法，允许(1)和(2)并行运行，那么突然之间就不清楚应该读取事件(3)的哪个值了。单一的主存保证总会有一个“赢家”：对每个变量的最后一次写入。如果没有这个保证，在(1)和(2)都发生之后，(3)可以看到1或2，这是令人困惑的。

我们称之为一致性保证，它表示每个线程以相同的顺序看到对同一位置的所有写入。它没有规定实际的顺序((1)或(2)可能最先发生)，但确实要求每个人都看到相同的“赢家”。

没有理由执行事件(2)(从B读取)需要等待事件(1)(对A的写入)完成。它们完全不会相互干扰，因此应该允许并行运行。事件(1)特别慢，因为它是写入。这意味着对于单一的内存视图，我们不能运行(2)，直到(1)对所有其他线程都可见。在现代CPU上，由于缓存层次结构，这是一个非常昂贵的操作：

两个核心之间唯一的共享内存是一直回到L3缓存，这通常需要90个以上的周期才能访问。

我们可以将其放入存储缓冲区，而不是等待写入(1)变得可见：

那么(2)可以在将(1)放入存储缓冲器之后立即开始，而不是等待它到达L3高速缓存。由于存储缓冲区位于内核上，因此访问速度非常快。在将来的某个时候，缓存层次结构将从存储缓冲区拉出写入，并通过缓存传播它，以便其他线程可以看到它。存储缓冲区允许我们隐藏使write(1)对所有其他线程可见通常需要的写入延迟。

存储缓冲很好，因为它保留了单线程行为。例如，考虑下面这个简单的单线程程序：

读入(2)需要看到(1)为该程序写入的值，以保留预期的单线程行为。write(1)还没有进入内存-它位于内核1的存储缓冲区中-所以如果read(2)只是查看内存，它将获得一个旧值。但是，因为它在同一个CPU上运行，所以读取可以直接检查存储缓冲区，查看它是否包含对正在读取的位置的写入，并改用该值。因此，即使使用存储缓冲区，此程序也可以正确打印1。

一种允许存储缓冲的流行内存模型称为总存储排序(TSO)。除了允许使用存储缓冲区之外，TSO基本上保留了与SC相同的保证。这些缓冲区隐藏了写入延迟，大大加快了执行速度。

存储缓冲区听起来像是一个很好的性能优化，但是有一个问题：TSO允许SC不允许的行为。换句话说，在TSO硬件上运行的程序可以表现出程序员会感到惊讶的行为。

让我们看看上面相同的第一个示例，但这一次是在带有存储缓冲区的机器上运行。首先，我们执行(1)，然后执行(3)，这两个操作都将其数据放入存储缓冲区，而不是将其发送回主内存：

接下来，我们在核心1上执行(2)，它将读取B的值。它首先检查它的本地存储缓冲区，但是那里没有B的值，所以它从内存中读取B并获得值0，然后打印出来。最后，我们在内核2上执行(4)，它将读取A的值。内核2的存储缓冲区中没有A值，因此它从内存中读取并获得值0，然后打印出来。在未来某个不确定的时间点，缓存层次结构清空存储缓冲区并将更改传播到内存。

那么，在TSO下，该程序可以打印00。这是我们在上面展示的一种行为，SC明确排除了这种行为！因此，存储缓冲区会导致程序员意想不到的行为。

是否有任何架构愿意采用违背程序员直觉的优化？是!。事实证明，几乎每个现代体系结构都包含一个存储缓冲区，因此内存模型至少与TSO一样弱。

特别是，历史悠久的x86架构指定了一种非常接近TSO的内存模型。Intel(x86的发起人)和AMD(x86-64的发起人)都使用与上面的程序类似的示例石蕊测试来指定其内存模型，这些程序描述了小型测试的可观察结果。不幸的是，用几个示例来指定复杂系统的行为会留下模棱两可的空间。剑桥大学的研究人员花了大量精力将x86-TSO正式化，以明确x86的TSO实现的预期行为(特别是，它与存储缓冲概念的不同之处)。

尽管x86放弃了顺序一致性，但就其允许的疯狂行为而言，它是行为最好的体系结构之一。大多数其他架构实现的内存模型甚至更弱，这意味着它们允许更多不直观的行为。这样的模型有一个完整的范围-SPARC体系结构允许程序员在运行时在三个不同的模型之间进行选择。

其中一个值得一提的架构是ARM，它可能为你的智能手机提供动力。ARM内存模型是出了名的不够详细，但本质上是一种弱排序形式，提供的保证很少。弱排序允许对几乎任何操作进行重新排序，这实现了各种硬件优化，但在最低级别编程也是一场噩梦。

幸运的是，所有现代架构都包含同步操作，以便在必要时控制其宽松的内存模型。最常见的此类操作是栅栏(或栅栏)。屏障指令强制其之前的所有内存操作在其可以开始之后的任何内存操作之前完成。也就是说，屏障指令在程序执行中的特定点有效地恢复顺序一致性。

当然，这正是我们试图通过引入存储缓冲区和其他优化来避免的行为。障碍物是一种可以节省使用的逃生舱口：它们可能需要数百次循环。正确使用它们也非常微妙，特别是在与模棱两可的内存模型定义结合使用时。还有一些更有用的原语，比如原子比较和交换，但是确实应该避免直接使用低级同步。一个真正的同步库将使您省去痛苦的世界。

不仅仅是硬件对内存操作进行重新排序-编译器一直都在这样做。请考虑以下计划：

此程序始终打印100个1的字符串。当然，在循环内写入X是多余的，因为没有其他代码更改X的值。标准的循环不变代码运动编译器传递将把写入移出循环以避免重复，然后死存储消除将删除X=0，留下：

这两个程序完全相等，因为它们都将产生相同的输出。2个。

但是现在假设有另一个线程与我们的程序并行运行，并且它对X执行一次写入：

在这两个线程并行运行的情况下，第一个程序的行为发生了变化：现在，只要只有一个0(因为它将在下一次迭代中重置X=1)，它就可以打印像11101111这样的字符串。第二个程序的行为也发生了变化：它现在可以打印像11100000这样的字符串，一旦它开始打印0，它就再也不会回到1了。

但这两个更改行为对这两个程序并不常见：第一个程序永远不能打印11100000……第二个程序也不能打印11101111……这意味着在存在并行性的情况下，编译器优化不再生成等价的程序！

这个例子暗示的是，在程序级别上也有一个内存一致性的概念。这里的编译器优化实际上是一种重新排序：它以程序员可能看不见的方式重新排列(和删除)内存访问。因此，为了保留直观的行为，编程语言需要它们自己的内存模型，为程序员提供关于如何重新排序其内存操作的契约。这种想法在语言设计社区变得越来越普遍。例如，最新版本的C++和Java都有严格定义的内存模型来管理它们的操作。

所有这些重新排序看起来非常疯狂，人类不可能保持一切正常。另一方面，如果您反思您的编程经验，内存一致性可能不是您经常遇到的问题(除非您是一个低级内核黑客)。我如何协调这两个极端呢？

诀窍在于，我在这里提到的每个示例都涉及数据竞争。数据竞争是对同一内存位置的两次访问，其中至少一个是写操作，并且没有同步引起的排序。如果没有数据竞争，则重新排序行为无关紧要，因为所有不直观的重新排序都将被同步阻止。请注意，这并不意味着无竞争的程序是确定性的：不同的线程可以在每次执行时赢得竞争。

事实上，像C++和Java这样的语言为无数据争用的程序(或时髦的版本，“SC for DRF”)提供了一种称为顺序一致性的保证。这个保证说，如果你的程序没有数据争用，编译器将插入所有必要的栅栏来保持顺序一致性的外观。然而，如果你的程序有数据争用，那么所有的赌注都是无效的，编译器可以自由地做它想做的任何事情。直觉是，有数据争用的程序很可能是有错误的，而且就是这样。如果你的程序有数据争用，那么编译器就可以自由地做它想做的任何事情。直觉是，有数据争用的程序很可能有错误，就是这样。如果程序有故意的数据竞争，程序员很可能无论如何都知道他们在做什么，因此可以自己负责内存排序问题。

既然您已经看到了所有这些乱七八糟的东西，那么最重要的一课就是您应该使用同步库。它将为您解决难看的重新排序问题。操作系统也进行了相当大的优化，以便只在特定平台上进行必要的同步。但是现在您知道了，当这些库和内核处理微妙的同步问题时，幕后会发生什么。

如果出于某种原因，你想更多地了解计算机体系结构给世界带来的各种令人讨厌的记忆模型，摩根和克莱普尔关于计算机体系结构的综合讲座有一篇关于内存一致性和连贯性的好文章。

虽然兰波特最初写的是多处理器，但他后来的工作转向了分布式系统。在现代分布式系统环境中，“顺序一致性”的含义与架构师的意图略有不同(且更弱)。架构师所说的“顺序一致性”更像是分布式系统人员所说的“线性化”。--↩。

让我们暂且不信，假设编译器还不够聪明，无法将此程序优化为一个打印调用。--↩