硬件内存模型 Hardware Memory Models

硬件内存模型 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,因为我们试图确定硬件允许做什么,我们假设每个线程都在自己的专用处理器上执行,并且编译器没有对线程中运行的指令进行重排:上面清单中的指令就是实际处理器执行的指令。下面的名称 r N r_N rN​ 表示线程局部寄存器,而不是局部变量,我们会问一个线程的本地寄存器的值在运行结束后是否存在某种可能。

这种关于示例程序的执行结果的问题被称为 Litmus Test, 因为它只有两种答案——结果可能或不可能, Litmus Test 给我们提供了一个清晰的方式来区分内存模型:如果一个模型允许特定的执行,另一个模型不允许,这两个模型显然是不同的,不幸的是,正如我们稍后将看到的,一个特定模型对一个特定的 Litmus 测试给出的答案往往是令人惊讶的。

如果 Litmus Test 的执行顺序是一致的,那么只有六种可能的交错:

硬件内存模型 Hardware Memory Models

因为线程交叉执行后,不存在 r1 = 1, r2 = 0 的情况,所以说这种结果是不存在的。也就是说,在顺序一致的硬件上,不存在这个程序的运行结果是 r1 = 1, r2 = 0 的情况。

理解顺序一致性一个很好的思维模型就是想象所有的处理器都连接到同一个共享内存上,而这个共享内存一次只可以为一个线程的读或写请求提供服务。我们这里暂不涉及缓存,处理器每次需要从内存读数据或需要写数据到内存时,这个请求都会被发送到共享内存中。这种一次性的共享内存使得所有对内存的访问都有了顺序:顺序一致性。

硬件内存模型 Hardware Memory Models

(本文中三个内存模型图摘自 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系统的内存模型对应于这个硬件图:

硬件内存模型 Hardware Memory Models

所有处理器还是连接到一块共享内存中,但每个处理器在自己的写队列上执行写操作,然后处理器继续执行其他指令的同时,写操作进入共享内存,一个处理器上的读取操作会在读取共享内存前会优先读本地的写队列,但这个写队列对其他处理器是不可见的,其结果就是本处理器会比其他处理器优先看倒自己的写操作。但是有一点很重要——所有处理器都必须保证写入(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 = x
    
On sequentially consistent hardware: no.
On x86 (or other TSO): no.

写队列保证线程 1 在 y 之前将 x 写入内存,并且内存写入顺序的系统级协议(TSO) 保证了线程 2 在读 y 的新值前一定能看到 x 的新值,因此,如果 r2 = x 没有看倒新的 xr1 = 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 = 1y = 1 一定会先被执行到,并且这对在其他线程中的读一定是可见的(and then the read in the other thread must observe it)所以 r1 = 0; r2 = 0 的结果是不存在的,但是在 TSO 系统中,可能发生两个线程都将写操作放入队列,并且在写操作到达内存之前从内存中读,因此两个读都可能得到 0.

这个示例可能看起来像是人为的,但是在著名的同步算法中,确实有使用两个同步变量的情况,例如 Dekker’s algorithmPeterson’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 = y
                              r2 = 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 TLO+CC 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 系统的模型概念是:每个处理器对自己的完整内存副本进行读写操作,每个读写操作都独立地传播到其他处理器,并允许在写操作传播时重新排序。

硬件内存模型 Hardware Memory Models

这里没有总存储顺序,虽然没有描述,但每个处理器都允许延迟读,直到读到它需要地结果:读可以延迟到之后地写之后。在这个宽松地模型中,目前为止我们所看到的所有 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 = y
                              r2 = 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 thread's read happen after the other thread's 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 = 1x = 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 = x
                              r2 = 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 写入了冲突的值 12 ,而线程 3 和线程 4 都读取了 x 两次。如果线程 3 看到 x = 1x = 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的写操作,然后再执行对同一个变量的读操作:

硬件内存模型 Hardware Memory Models

垂直的箭头标记了单个线程中的执行顺序:先写,再读。在这个程序中没有竞争,因为所有的东西都在一个线程中。

相比之下,在这个双线程程序中就存在一个竞争:

硬件内存模型 Hardware Memory Models

在这里,线程 2 在不与线程 1 协调的情况下写入 x。线程 2 的写与线程 1 的读写产生竞争。如果线程 2 正在读 x 而不是写 x,那么程序将只有一次竞争,即线程 1 的写操作和线程 2 的读操作之间的竞争。每个竞争至少包含一个写操作: 两个不协调的读不会相互竞争。

为了避免竞争,我们必须添加同步操作,他将强制在不同线程共享同步变量的操作上添加顺序,如果同步操作 S(a) (在变量a上同步,用虚线箭头标记) 强制线程 2 在线程 1 结束之后再写入,则消除了竞争:

硬件内存模型 Hardware Memory Models

现在线程 2 的写操作不能与线程 1 的操作同时发生。

如果线程 2 只是在读,那么我们只需要同步线程 1 的写操作。两个读取仍然可以同时进行:

硬件内存模型 Hardware Memory Models

线程可以按同步序列排序,甚至可以使用中间线程。这个程序没有竞争

硬件内存模型 Hardware Memory Models

另一方面,使用同步变量本身并不能消除竞争: 甚至可能会错误地使用它们。这个程序存在竞争:

硬件内存模型 Hardware Memory Models

线程 2 的读操作与其他线程的写操作是同步的,它肯定发生另外两个线程的写之后,但另外两个线程本身并没有同步。这个程序便不是 无数据竞争的。

Adve 和 Hill 将弱排序描述为 “ 软件和硬件之间的规约 ”,具体地说,如果软件避免了数据竞争,那么硬件的行为就应该好像它是顺序一致的,这比我们在前面几节中研究的模型更容易推理。但是,硬件如何才能履行规约呢?

Adve 和 Hill 给出了硬件 “遵循 DRF 弱排序” 的证明,这意味着它只要满足一组特定的最低要求,那么它无数据竞争的程序在其上执行时就像在顺序一致的机器上执行时一样。我不准备探讨更多细节,但重点是,在 Adve 和 Hill 的论文发表之后,硬件工程师有了一份由理论支持的菜谱:做了这些事情,您就可以断言您的硬件将与无数据竞争程序的顺序一致。事实上,假设同步操作的适当实现,大多数宽松的硬件确实是这样做的,并且还在继续这样做。Adve 和 Hill 最初关注的是 VAX,但 x86、ARM 和 POWER 肯定也能满足这些限制。这系统向无数据竞争程序保证顺序一致性的想法通常缩写为 DRF-SC。

DRF-SC 标志着硬件内存模型的一个转折点,为硬件设计人员和软件作者(至少是那些用汇编语言编写软件的人)提供了一个清晰的策略。但正如我们将在下一篇文章中看到的那样,高级编程语言的内存模型问题没有那么清晰明了的答案。

本系列中的下一个帖子是关于编程语言内存模型

译者注:

我们现在所常说的数据竞争就是在这一模型下的产物,这个模型使得硬件和软件在思考内存顺序问题时得以分离开。

致谢

这一系列的文章使我在与许多工程师的反馈和讨论中受益匪浅,我庆幸在谷歌能与他们共事。对文章中的错误和不受欢迎的观点,我将承担全部责任。

上一篇:Shiro简介及简单入门demo


下一篇:QT实现点击按钮打开和关闭窗口