建网站电脑版和手机版怎么做,长沙生活信息网,南京seo推广,wordpress 媒体库 七牛硬件内存模型 Hardware Memory Models
(Memory Models, Part 1)
Posted on Tuesday, June 29, 2021.
简介#xff1a;童话的终结
很久以前#xff0c;当人们还在写单线程程序的时候#xff0c;让程序跑的更快的一个最有效的办法就是什么也不做#xff0c;因为下一代硬件…硬件内存模型 Hardware Memory Models
(Memory Models, Part 1)
Posted on Tuesday, June 29, 2021.
简介童话的终结
很久以前当人们还在写单线程程序的时候让程序跑的更快的一个最有效的办法就是什么也不做因为下一代硬件和编译器的优化会使得程序更快但行为不发生改变。在这个童话般的时代区分优化是否有效有一个简单的测试方法如果程序员无法区分一个正确程序经过优化和未经优化的版本之间的运行结果差异除速度更快外那么优化就是有效的也就是说正确的优化不会改变程序的行为。
但是多年前的某一天硬件工程师们发现让单个处理器越来越快的魔法消失了与此同时他们发现了一种新的魔法这能使得他们创造出拥有越来越多处理器的计算机。操作系统将这种硬件并行性抽象成线程 Threads 暴露给开发者。这种通过操作系统线程提供多处理器能力的魔法对硬件工程师很友好但它给语言设计师、编译器作者和程序员带来了严重的问题。
之前许多在单线程程序中不可见因此有效的硬件和编译器优化在多线程程序中变得可见。如果我们说有效的优化不会改变正确程序的行为那么现在来看只能要么说这些优化是无效的要么说程序是错误的我们改如何抉择呢
下面是一个用类 C 语言编写的简单示例程序。在这个程序以及我们将要考虑的所有程序中所有变量的初始值都被设为零。
// Thread 1 // Thread 2
x 1; while (done 0) { /* loop */ }
done 1; print(x);如果线程 1 和线程 2 都运行在自己的特定的处理器上并且都运行到结束那么这个程序可能输出0 吗直接逐行翻译成运行在 x86 平台上的汇编后它总是输出 1但是直接翻译成运行在 ARM 或 POWER 多处理器上的汇编后却可以输出 0。此外不管底层硬件是什么标准的编译器优化都可以使这个程序输出 0 或进入无限循环。
这得视情况而定。因为它既取决于硬件也取决于编译器。直接逐行转换到运行在x86多处理器上的汇编总是输出1。但是直接逐行转换到在ARM或POWER多处理器上运行的汇编程序可以输出0。此外无论底层硬件是什么标准的编译器优化都可以使这个程序输出0或进入无限循环。
“视情况而定” 这似乎不是一个令人愉快的结局程序员需要一个明确的答案来确定一个程序是否能在新的硬件或新的编译器下继续工作同时硬件设计师和编译器开发者也需要一个明确的答案来确定在执行一个给定的程序时硬件和编译后的代码可以有多精确。因为这里主要涉及的问题是内存中数据更改的可见性和一致性所以这个契约被称为内存一致性模型或简称内存模型。
最初硬件模型的目标是定义对编写汇编的程序员来说硬件能提供什么保证在这种定义中是不包含编译器的。25 年前人们尝试修改内存模型用来定义对使用像 Java 或 C 这种高级语言的程序员来说编译器能提供什么保证在内存模型中加入编译器会使得定义一个合理的模型的工作变得更加复杂。
这是硬件和编译器内存模型系列的第一篇我写这篇文章的目的在于为后面讨论我们可能想要在 Go 的内存模型中做出的潜在改变建立背景。但在理解 Go 的发展方向和我们的目标之前我们必须先了解目前其他硬件内存模型和语言内存模型的发展方向以及它们实现这一目标的坎坷道路。
这篇文章是关于硬件的。让我们假设我们正在为多处理器计算机编写汇编语言。为了写出正确的程序你需要从计算机硬件中得到什么保证? 四十多年来计算机科学家一直在寻找这个问题的答案。
顺序一致性模型
Leslie Lamport 在1979年的论文 How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs如何使多处理器计算机正确执行多进程程序 中引入了顺序一致性的概念 The customary approach to designing and proving the correctness of multiprocess algorithms for such a computer assumes that the following condition is satisfied: the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. A multiprocessor satisfying this condition will be called sequentially consistent. 为这类计算机设计和证明多进程算法正确性的通常方法假定满足以下条件所有的执行结果都是一致的就像在处理器上的所有操作都按某种顺序执行的一样并且每个处理器的操作都是按程序指定的顺序出现的。满足这一条件的多处理器系统将被称为顺序一致的 今天我们不仅仅讨论计算机硬件也将讨论满足顺序一致性的编程语言一个程序唯一可能的执行方式对应于将多个线程的操作交错为顺序执行。顺序一致性模型通常被认为是最理想的模型也是程序员使用起来最自然的模型它允许你可以假定程序是按您页面上显示的顺序执行的并且单个线程的执行只是以某种顺序进行交错但未以其他方式重新排列。
有人可能会质疑顺序一致性是不是一个理想的模型但这超出了本文的讨论范围。我只注意到像 1979 年那样考虑线程交错执行的所有可能性对于 Leslie Lamport 提出的 “the customary approach to designing and proving the correctness of multiprocess algorithms” 四十年时间内还没人能取代他。
早些时候我问这个程序能不能输出 0
// Thread 1 // Thread 2
x 1; while(done 0) { /* loop */ }
done 1; print(x);为了让程序更易于分析让我们删除循环和打印并思考读取共享变量的可能结果
Litmus Test: Message Passing
Can this program see r1 1, r2 0?// Thread 1 // Thread 2
x 1 r1 y
y 1 r2 x我们假设每个示例开始时所有变量的初始值都被设为 0因为我们试图确定硬件允许做什么我们假设每个线程都在自己的专用处理器上执行并且编译器没有对线程中运行的指令进行重排上面清单中的指令就是实际处理器执行的指令。下面的名称 rNr_NrN 表示线程局部寄存器而不是局部变量我们会问一个线程的本地寄存器的值在运行结束后是否存在某种可能。
这种关于示例程序的执行结果的问题被称为 Litmus Test, 因为它只有两种答案——结果可能或不可能, Litmus Test 给我们提供了一个清晰的方式来区分内存模型如果一个模型允许特定的执行另一个模型不允许这两个模型显然是不同的不幸的是正如我们稍后将看到的一个特定模型对一个特定的 Litmus 测试给出的答案往往是令人惊讶的。
如果 Litmus Test 的执行顺序是一致的那么只有六种可能的交错 因为线程交叉执行后不存在 r1 1, r2 0 的情况所以说这种结果是不存在的。也就是说在顺序一致的硬件上不存在这个程序的运行结果是 r1 1, r2 0 的情况。
理解顺序一致性一个很好的思维模型就是想象所有的处理器都连接到同一个共享内存上而这个共享内存一次只可以为一个线程的读或写请求提供服务。我们这里暂不涉及缓存处理器每次需要从内存读数据或需要写数据到内存时这个请求都会被发送到共享内存中。这种一次性的共享内存使得所有对内存的访问都有了顺序顺序一致性。 (本文中三个内存模型图摘自 Maranget et al. [“A Tutorial Introduction to the ARM and POWER Relaxed Memory Models.”](https://colobu.com/2021/06/30/hwmm/A Tutorial Introduction to the ARM and POWER Relaxed Memory Models))
上图展示了一个序列一致的机器的模型而不是构建它的唯一方法实际上可以使用多个共享内存模块和高速缓存构建一个顺序一致的计算机以帮助预测从内存读的结果但保证顺序一致就以为着机器的行为必须与上图模型一致如果我们只是试图了解顺序一致的执行方式我们就可以忽略所有具体的复杂实现方式只考虑这个模型。
不幸的是对于程序员来说放弃严格的顺序一致性可以让硬件更快地执行程序因此所有现代硬件都在以各种方式偏离顺序一致性。准确定义具体的硬件偏离是相当困难的。本文以当今广泛使用的硬件中的两种内存模型为例: x86、ARM 和 POWER 处理器系列。
x86 Total Store Order (x86-TSO)
现代x86系统的内存模型对应于这个硬件图 所有处理器还是连接到一块共享内存中但每个处理器在自己的写队列上执行写操作然后处理器继续执行其他指令的同时写操作进入共享内存一个处理器上的读取操作会在读取共享内存前会优先读本地的写队列但这个写队列对其他处理器是不可见的其结果就是本处理器会比其他处理器优先看倒自己的写操作。但是有一点很重要——所有处理器都必须保证写入stores到共享内存时的总顺序这也是这种内存模型 TSO(总存储有序) 名字的来源。一旦一个值被写入到共享内存以后所有处理器都将看到并使用这个值直到它被本地写操作覆盖或被来自其他处理器的缓冲写操作覆盖。
本地写队列是一个标准的先进先出的队列内存写操作将会根据处理器执行他们的顺序作用于共享内存因为写操作的顺序由写队列保存而且由于其他处理器可以立刻看倒对共享内存的写操作所以前面我们考虑的 Litmus 测试的结果中 r1 1; r2 0 的情况依然不存在。
Litmus Test: Message Passing
Can this program see r1 1, r2 0?// Thread 1 // Thread 2
x 1 r1 y
y 1 r2 xOn sequentially consistent hardware: no.
On x86 (or other TSO): no.写队列保证线程 1 在 y 之前将 x 写入内存并且内存写入顺序的系统级协议TSO 保证了线程 2 在读 y 的新值前一定能看到 x 的新值因此如果 r2 x 没有看倒新的 x 那 r1 y 就不可能看到新的 y, 在这里存储顺序是至关重要的线程 1 在 y 之前写 x, 所以在写 x 之前线程 2 不可能看到新写的 y 的内容。
在这种情况下顺序一致性和 TSO 模型是一致的但是他们在其他 litmus 测试的结果上并不一致例如这是区分两种型号的常用示例:
Litmus Test: Write Queue (also called Store Buffer)
Can this program see r1 0, r2 0?// Thread 1 // Thread 2
x 1 y 1
r1 y r2 x
On sequentially consistent hardware: no.
On x86 (or other TSO): yes!任何一个顺序一致的系统中x 1 或 y 1 一定会先被执行到并且这对在其他线程中的读一定是可见的and then the read in the other thread must observe it所以 r1 0; r2 0 的结果是不存在的但是在 TSO 系统中可能发生两个线程都将写操作放入队列并且在写操作到达内存之前从内存中读因此两个读都可能得到 0.
这个示例可能看起来像是人为的但是在著名的同步算法中确实有使用两个同步变量的情况例如 Dekker’s algorithm 或 Peterson’s algorithm 和一些其他的方案。如果一个线程没有看到来自另一个线程的所有写操作它们就会中断。
为了修复这些依赖于更强内存顺序的算法非顺序一致性的硬件提供了显式的指令称为内存屏障可以用他们来控制顺序我们可以添加一个内存屏障保证线程在开始读之前将之前所有的写操作刷入到内存中
// Thread 1 // Thread 2
x 1 y 1
barrier barrier
r1 y r2 x随着屏障的添加 r1 0; r2 0 的情况将不复存在Dekker 和 Petersion 的算法也可以正常工作了。内存屏障有很多不同的类型具体情况因系统而异这已经超出了本文的范围关键问题在于存在这样一种内存屏障技术他为程序员或语言实现者提供了一种在关键时刻保证强一致性的方法。
最后一个例子说明这个模式为什么被称为 TSO在这种模式下有本地写队列但在读的路径上没有缓存一旦一个写操作到达内存所有处理器不仅都认同该值在内存存在而且还认同它相对于来自其他处理器写操作的先后顺序。考虑一下 Litmus 测试
Litmus Test: Independent Reads of Independent Writes (IRIW)
Can this program see r1 1, r2 0, r3 1, r4 0?
(Can Threads 3 and 4 see x and y change in different orders?)// Thread 1 // Thread 2 // Thread 3 // Thread 4
x 1 y 1 r1 x r3 yr2 y r4 x
On sequentially consistent hardware: no.
On x86 (or other TSO): no.如果线程 3 看到 y 先于 x 改变那线程 4 也可以看到 y 先于 x 改变吗在 x86 或其他的 TSO 机器上答案是不能对主存的所有写入操作都有一个统一的顺序所有的处理器都认可这个顺序但前提是每个处理器在它们到达主存之前都知道了他们的写入。 译者注 顺序一致性模型可以理解为一种完全互斥模型共享内存同时只允许一个线程操作所以一定不会有问题。 TSO 有点像读写锁它能保证写顺序在此之上的内存屏障可以提供更强的一致性。 x86-TSO 之路
x86-TSO 现在看起来相当清晰明了但它一路走来却充满了坎坷和错误的弯路20 世纪 90 年代第一代x86多处理器的手册中几乎没有提到硬件提供的内存模型。
作为该问题的一个例子Plan 9 是第一款真正运行在 x86 上的多处理器操作系统没有全局内核锁。在 1997 年将它移植到奔腾 Pro 处理器上时开发人员被归结为写队列 Litmus 测试的行为困扰在一段微妙的同步代码中按假设 r1 0; r2 0 是不可能存在的但它却确实发生了更糟糕的是英特尔手册对内存模型详细的信息介绍地含糊不清。
有邮件列表建议it’s better to be conservative with locks than to trust hardware designers to do what we expect宁可使用更保守地锁也不要期望硬件设计师能做我们所期望的事对此一名 Plan 9 的开发者很好的解释到 (explained the problem well) I certainly agree. We are going to encounter more relaxed ordering in multiprocessors. The question is, what do the hardware designers consider conservative? Forcing an interlock at both the beginning and end of a locked section seems to be pretty conservative to me, but I clearly am not imaginative enough. The Pro manuals go into excruciating detail in describing the caches and what keeps them coherent but don’t seem to care to say anything detailed about execution or read ordering. The truth is that we have no way of knowing whether we’re conservative enough. 我当然同意我们会在多处理器中遇到更宽松的顺序但问题在于在硬件设计师眼中什么是保守的强制在需要锁定的部分临界区的首尾加锁对我来说应该是相当保守的了但我显然没有足够的想象力。奔腾 Pro 的手册在描述缓存以及如何保证他们的一致性时给出了相当详细的细节但对执行或读取顺序的细节只字不提以此导致的就是我们根本无法知道自己做的是否足够保守。 在讨论期间一名英特尔的架构师也对内存模型做出了非正式的解释他指出即使是在使用 486 多处理器的奔腾系统中也会出现 r1 0; r2 0 的情况只是奔腾 Pro 更大的流水线和写队列让这种问题更容易暴露。
这名英特尔架构师还写到 Loosely speaking, this means the ordering of events originating from any one processor in the system, as observed by other processors, is always the same. However, different observers are allowed to disagree on the interleaving of events from two or more processors. Future Intel processors will implement the same memory ordering model. 粗略来说内存模型这意味着从系统中任何一个处理器产生的事件的顺序对在其他处理器上的观察者来说始终是相同的。但是允许观察者对来自两个或多个处理器的事件持不同意见。注保证单个处理器上的事件顺序允许不同处理器的事件乱序执行 未来英特尔也将实现相同的内存模型。 对于 “different observers are allowed to disagree on the interleaving of events from two or more processors” 的说法意味着 IRIW 的 Litmus 测试的结果在 x86 上是肯定的尽管在前一节中我们看到 x86 的答案是否定的这怎么可能呢
答案似乎是英特尔处理器从未对这个 Litmus 测试做出 yes 的回答而当时这位英特尔的架构师也不愿意尾未来的处理器做出任何保证。且体系结构手册中仅有的少量文本几乎没有做出任何保证这使得对它们编程非常困难。
Plan 9 的讨论并不是孤立的事件Linux 内核开发人员在 1999 年 11 月下旬 开始有一百多封邮件讨论类似英特尔内存保证的问题。
在接下来的十年里越来越多的人遇到了这些困难英特尔的一组架构师承担了为当前和未来处理器编写有用的处理器行为保证的任务。其第一个成果是 2007 年 8 月发布的 《英特尔 64 架构内存顺序白皮书Intel 64 Architecture Memory Ordering White Paper》,其目的在于帮助软件开发者清楚地理解不同顺序的内存访问指令可能产生的结果同年晚些时候 AMD 在 [AMD64 架构程序员参考手册 3.14 版本AMD64 Architecture Programmer’s Manual revision 3.14](https://courses.cs.washington.edu/courses/cse351/12wi/supp-docs/AMD Vol 1.pdf)中发布了类似的描述。这些描述基于一个名为 “总锁顺序 因果一致性TLO CC” 的模型故顺序性比 TSO 要弱在公开的谈话中英特尔的架构师讲到 TLO CC 如同要求的那样强大但还不是足够将大的(as strong as required but no stronger.) 特别的是该模型保留了 x86 处理器对 IRIW 的 Litmus 测试做出肯定回答的权力。不幸的是内存屏障的定义还没强大到重新建立顺序一致性的内存语义即便在每条指令之后都加一个屏障。更糟糕的是研究人员发现英特尔 x86 的硬件实际上违反了 TLO CC 模型例如
Litmus Test: n6 (Paul Loewenstein)
Can this program end with r1 1, r2 0, x 1?// Thread 1 // Thread 2
x 1 y 1
r1 x x 2
r2 y
On sequentially consistent hardware: no.
On x86 TLOCC model (2007): no.
On actual x86 hardware: yes!
On x86 TSO model: yes! (Example from x86-TSO paper.)2008 年晚些的时候英特尔和 AMD 修订了规范保证了对 IRIW case 的否决并增强了内存屏障但仍然允许一些似乎在任何合理的硬件上都不应该出现的意外行为例如
Litmus Test: n5
Can this program end with r1 2, r2 1?// Thread 1 // Thread 2
x 1 x 2
r1 x r2 x
On sequentially consistent hardware: no.
On x86 specification (2008): yes!
On actual x86 hardware: no.
On x86 TSO model: no. (Example from x86-TSO paper.)为了解决这些问题欧文斯等人提出了 x86-TSO 模型 ,它基于早期的 SPARCv8 TSO 模型当时它们声称“据我们所知x86-TSO 是可靠的足够强大的可以进行以上编程并且大体上符合供应商的意图” 几个月后英特尔和 AMD发布了广泛使用这种模式的新手册。
看起来英特尔处理器从一开始就实现了 x86-TSO, 实际上英特尔花了十年时间才决定致力于此回顾过去显然英特尔和 AMD 的架构师曾为如何编写一个内存模型而苦苦挣扎这个模型既要为未来的处理器优化留下空间还要为编译器作者和汇编语言程序员提供有用的保证。“As strong as required but no stronger” 是一种艰难的平衡行为。
ARM/POWER 宽松的内存模型 Relaxed Memory Model
现在让我们看看一个更宽松的内存模型ARM 和 POWER 处理器上的内存模型在实现层面这两个系统有诸多不同但保证内存一致性的模型被证明是大致相似的而且相比 x86-TSO 甚至是 x86-TLO-CC 要弱一些。
ARM 和POWER 系统的模型概念是每个处理器对自己的完整内存副本进行读写操作每个读写操作都独立地传播到其他处理器并允许在写操作传播时重新排序。 这里没有总存储顺序虽然没有描述但每个处理器都允许延迟读直到读到它需要地结果读可以延迟到之后地写之后。在这个宽松地模型中目前为止我们所看到的所有 Litmus 测试地结果都是肯定地这确实有可能发生。
对于通过 Litmus 测试的原始消息单个处理器的写入重新排序意味着其他线程以相同的顺序无法观察到线程 1 的写入
Litmus Test: Message Passing
Can this program see r1 1, r2 0?// Thread 1 // Thread 2
x 1 r1 y
y 1 r2 x
On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: yes!在 ARM/POWER 模型中我们可以认为线程 1 和线程 2 都有各自单独的内存副本写操作以任何可能的顺序在内存之间传播。如果线程 1 在发送 x 的更新之前将 y 的更新发送给线程 2 并且线程 2 在这两个更新之间执行它确实会看到 r1 1, r2 0 的结果。
该结果表明ARM/POWER 模型比 TSO 更弱对硬件的要求更低。ARM/POWER 模型仍承认 TSO所做的各种重排序:
Litmus Test: Store Buffering
Can this program see r1 0, r2 0?// Thread 1 // Thread 2
x 1 y 1
r1 y r2 x
On sequentially consistent hardware: no.
On x86 (or other TSO): yes!
On ARM/POWER: yes!在 ARM/POWER 上对 X 和 Y 的写入可能会在本地存储器进行但如果在相反的线程上读取时可能写操作还没有传播开。
下面是一个 Litmus test它展示了 x86 拥有的总存储顺序意味着什么:
Litmus Test: Independent Reads of Independent Writes (IRIW)
Can this program see r1 1, r2 0, r3 1, r4 0?
(Can Threads 3 and 4 see x and y change in different orders?)// Thread 1 // Thread 2 // Thread 3 // Thread 4
x 1 y 1 r1 x r3 yr2 y r4 x
On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: yes!在 ARM/POWER 中不同的线程可能以不同的顺序观察到不同的写操作它们不能保证到达主存时总写入顺序是一致的所以线程 3 可以看到 x 在 y 之前发生变化而线程 4 也可能看到 y 在 x 之前发生变化。
作为另一个例子ARM/POWER 系统具有内存读取的可见缓冲或重新排序如下面 Litmus 测试所见
Litmus Test: Load Buffering
Can this program see r1 1, r2 1?
(Can each threads read happen after the other threads write?)// Thread 1 // Thread 2
r1 x r2 y
y 1 x 1
On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: yes!在任何顺序一致性的机器上交错执行必然是从线程 1 的 r1 x 或线程 2 的 r2 y 开始的读到的一定是 0因此不可能得到 r1 1, r2 1 的结果然而在 ARM/POWER 模型中处理器被允许延迟读操作直到指令流后面的写操作完成这样在两次读之前 y 1 和 x 1 其实已经被执行了。
尽管 ARM 和 POWER 的内存模型都允许这个结果但 Maranget 等人在 2012 年的这篇报告中 还是讲到只能在 ARM 上得到复现POWER 上从来没有出现过。在这里模型和现实之间的分歧开始发挥作用正如我们在英特尔 x86 中所做的那样硬件实现了比技术上的保证更强的模型我们鼓励程序依赖于更强的行为这代表着将来较弱的硬件将会会破坏程序行为不管其是否有效。
如同 TSO 系统 ARM 和 POWER 也有一些屏障我们可以在上面的例子中插入这些屏障来保证强顺序一致的行为。但一个显而易见的问题是一个没有使用屏障的 ARM/POWER 是否排除了任何行为难道所有 Litmus 测试的结果都是 “不这不可能发生”。当我们关注于单一的内存位置时它可以 译者注 这里说的其实是如果 ARM/POWER 不使用屏障技术那它的顺序是否是完全不可控的体现在 Litmus 测试上就是难道所有的情况都可能发生 这里有一个 Litmus 测试它可以测试即视在 ARM/POWER 上也不会发生的事情
Litmus Test: Coherence
Can this program see r1 1, r2 2, r3 2, r4 1?
(Can Thread 3 see x 1 before x 2 while Thread 4 sees the reverse?)// Thread 1 // Thread 2 // Thread 3 // Thread 4
x 1 x 2 r1 x r3 xr2 x r4 x
On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: no.这个 Litmus 测试与前一个类似只不过现在两个线程 1 2 都在写同一个变量 x 而不是不同的变量 x 和 y 。线程 1 和线程 2 向 x 写入了冲突的值 1 和 2 而线程 3 和线程 4 都读取了 x 两次。如果线程 3 看到 x 1 被 x 2 覆盖那么线程 4 是否可以看到相反的结果呢
答案是 no 即使在 ARM/POWER 上系统中的线程必须就写入单个内存位置的总顺序达成一致。也就是说线程必须同意哪个写会覆盖其他写。这种性值叫做 相干性 coherence, 没有相干性处理器要么不同意内存的最终结果要么报告内存位置从一个值切换到另一个值然后返回到第一个值。编写这样一个系统的程序是非常困难的。 译者注 相关性是说不管多个值读写的顺序能不能保证有序如果多个线程并发修改同一内存位置的值修改的结果落实到主从上时对所有观察者来说一定是有唯一顺序的不可能存在观察者 A 观察到 x 先被线程 1 修改观察者 B 观察到 x 先被线程 2 修改的情况。 我故意忽略了ARM 和 POWER 弱内存模型中的许多细微之处。更详细的内容可以参考 Peter Sewell 关于该主题的论文, 此外ARMv8 通过使多副本原子化来增强内存模型但我在这里不打算详细解释这意味着什么。
有两点值得注意, 首先这里的微妙之处令人难以置信这是一个由非常执着、非常聪明的人进行了超过十年的学术研究的课题。我并没有说我自己能完全理解。这不是我们应该希望向普通程序员解释的东西也不是我们在调试普通程序时希望保持清晰的东西。其次允许的情况和观察到的情况之间的差距造成了不幸的未来的 “惊喜”。如果当前的硬件没有显示所有允许的行为特别是当很难解释什么是允许的时候, 然后不可避免地程序会意外地依赖于实际硬件的更受限制的行为。如果一个新芯片的该行为不受限制那么硬件内存模型在技术上允许这种新行为破坏你的程序也就是说从技术上来说这个 bug 是你的错这一点也不能安慰你。这不是写程序的方法。 译者注 第二点是说你不要去过度依赖这种由具体硬件所保障的行为否则如果换一个芯片你不就麻了吗 弱排序与无数据竞争序列一致性 Weak Ordering and Data-Race-Free Sequential Consistency
到目前为止我希望您明确硬件的细节是复杂的且微妙的但却并不是你每次编写代码时都需要考虑的东西相反你只需要明确“如果遵循这些简单的规则您的程序将会向顺序执行的那样产生确定的结果”我们任然在讨论硬件所以我们讨论的依然是交错执行的独立的汇编指令
Sarita Adve 和 Mark Hill 在 1990 年的论文 “Weak Ordering – A New Definition(《弱排序——一种新的定义》)” 提出了这个方法他们对 “弱排序 Weak Ordering” 的定义如下 Let a synchronization model be a set of constraints on memory accesses that specify how and when synchronization needs to be done. 假设同步模型是对内存访问的一组约束这些约束指定了如何以及何时完成同步。 Hardware is weakly ordered with respect to a synchronization model if and only if it appears sequentially consistent to all software that obey the synchronization model. 当且仅当硬件看起来与所有遵循同步模型的软件顺序一致时硬件相对于该同步模型是弱排序的。 虽然他们的论文聚焦于当时的额硬件并不是 x86 ARM 或 POWER 但是这种将讨论提升到具体设计之上的想法使得这篇论文与今天的话题相关。
我之前说过有效的优化不会改变有效程序的行为这些规则首先定义了有哪些有效的手段然后所有硬件的优化都必须使得遵循这些规则这些程序像是在顺序一致的机器上执行的那样。当然更有趣的细节是这些规则本身即定义程序有效含义的约束条件。 译者注 硬件的细节是复杂且微妙的但这并不是我们每次写程序都需要考虑的问题我们应该关注的是这样一组规则它定义了什么样的程序是有效的硬件的优化应该保证遵循这组规则的程序的行为。 Adve 和 Hill 提出了一个同步模型他们将其称之为无数据竞争data-race-free DRF,该模型假设硬件的内存同步操作是与普通的内存读写操作分开的。 普通内存读写可以在同步操作之间重新排序但普通读写不会跨越它们硬件内存同步也就是说同步操作成为了成为了重排序的 “屏障”。对于所有理想化的顺序一致的执行如果来自不同线程的两个对普通内存的访问操作要么都是读要么被同步操作分割开这些同步操作强制一个发生在另一个之前那么这个程序就是五数据竞争的 DRF。
让我们看一些来自 Adve 和 Hill 论文中的例子经过重新绘制下面是一个线程它执行对变量x的写操作然后再执行对同一个变量的读操作 垂直的箭头标记了单个线程中的执行顺序:先写再读。在这个程序中没有竞争因为所有的东西都在一个线程中。
相比之下在这个双线程程序中就存在一个竞争 在这里线程 2 在不与线程 1 协调的情况下写入 x。线程 2 的写与线程 1 的读写产生竞争。如果线程 2 正在读 x 而不是写 x那么程序将只有一次竞争即线程 1 的写操作和线程 2 的读操作之间的竞争。每个竞争至少包含一个写操作: 两个不协调的读不会相互竞争。
为了避免竞争我们必须添加同步操作他将强制在不同线程共享同步变量的操作上添加顺序如果同步操作 S(a) (在变量a上同步用虚线箭头标记) 强制线程 2 在线程 1 结束之后再写入则消除了竞争 现在线程 2 的写操作不能与线程 1 的操作同时发生。
如果线程 2 只是在读那么我们只需要同步线程 1 的写操作。两个读取仍然可以同时进行 线程可以按同步序列排序甚至可以使用中间线程。这个程序没有竞争 另一方面使用同步变量本身并不能消除竞争: 甚至可能会错误地使用它们。这个程序存在竞争 线程 2 的读操作与其他线程的写操作是同步的它肯定发生另外两个线程的写之后但另外两个线程本身并没有同步。这个程序便不是 无数据竞争的。
Adve 和 Hill 将弱排序描述为 “ 软件和硬件之间的规约 ”具体地说如果软件避免了数据竞争那么硬件的行为就应该好像它是顺序一致的这比我们在前面几节中研究的模型更容易推理。但是硬件如何才能履行规约呢
Adve 和 Hill 给出了硬件 “遵循 DRF 弱排序” 的证明这意味着它只要满足一组特定的最低要求那么它无数据竞争的程序在其上执行时就像在顺序一致的机器上执行时一样。我不准备探讨更多细节但重点是在 Adve 和 Hill 的论文发表之后硬件工程师有了一份由理论支持的菜谱做了这些事情您就可以断言您的硬件将与无数据竞争程序的顺序一致。事实上假设同步操作的适当实现大多数宽松的硬件确实是这样做的并且还在继续这样做。Adve 和 Hill 最初关注的是 VAX但 x86、ARM 和 POWER 肯定也能满足这些限制。这系统向无数据竞争程序保证顺序一致性的想法通常缩写为 DRF-SC。
DRF-SC 标志着硬件内存模型的一个转折点为硬件设计人员和软件作者(至少是那些用汇编语言编写软件的人)提供了一个清晰的策略。但正如我们将在下一篇文章中看到的那样高级编程语言的内存模型问题没有那么清晰明了的答案。
本系列中的下一个帖子是关于编程语言内存模型。 译者注 我们现在所常说的数据竞争就是在这一模型下的产物这个模型使得硬件和软件在思考内存顺序问题时得以分离开。 致谢
这一系列的文章使我在与许多工程师的反馈和讨论中受益匪浅我庆幸在谷歌能与他们共事。对文章中的错误和不受欢迎的观点我将承担全部责任。
