Linux内核中的内存屏障(1)

larmbr | 2014-02-14 | Tags: Linux内核, 内存管理

概览

SMP这种并行架构相比传统的单处理器带来相当可观的性能提升。一个不可避免的问题是并行架构的处理器间的交互问题。一种可能的解决方案是,每个CPU都有自己唯一可访问内存,处理器间通过消息传递进行通信。这种架构的问题是带给程序员(尤其是系统程序员)巨大的编程负担,因为需要处理数据分隔与传递。相反,被广泛应用的另一种架构是,多处理器间共享一个共享的内存地址空间。这种架构下每个处理器依然可能有自己的本地内存,但不同的是所有的内存对所有的处理器都是可以访问的,只存在访问效率的问题。本文也针对这种架构进行讨论。

共享的内存空间允许每个处理器都进行对任意内存位置的访问(access)操作,这会引起在单处器上没有的问题。考虑这种情况(此图示和例子来源于内核文档Documentation/memory-barriers.txt):

                :                :
    +-------+   :   +--------+   :   +-------+
    |       |   :   |        |   :   |       |
    | CPU 1 |<----->| Memory |<----->| CPU 2 |
    |       |   :   |        |   :   |       |
    +-------+   :   +--------+   :   +-------+
        ^       :       ^        :       ^
        |       :       |        :       |
        |       :       v        :       |
        |       :   +--------+   :       |
        |       :   |        |   :       |
        +---------->| Device |<----------+
                :   |        |   :
                :   +--------+   :

在如图的这种系统模型中,假设存在如下的内存访问操作:

CPU 1           CPU 2
=============== ===============
{ A == 1; B == 2 }
A = 3;          x = A;
B = 4;          y = B;

由于处理器出于效率而引入的乱序执行(out-of-order execution)和缓存的关系, 对于内存来说, 最后x和y的值可以有如下组合:

     x == 1, y == 2 
     x == 1, y == 4 
     x == 3, y == 2 
     x == 3, y == 4 

因此,对于在操作系统这一层次编程的程序员来说,他们需要一个内存模型,以协调处理器间正确地使用共享内存,这个模型叫做内存一致性模型(memory consistency model)或简称内存模型(memory model)

另外有一点需要明确的是,计算机是一个层层抽象的机器,最底层是裸机,再往上是能理解汇编程序的虚拟机,再往上是能理解更高层级编程语言(如C/C++,Java)的更高层级虚拟机。在高级层级编程语言这一层次,编程语言以及运行环境定义了这个层次的内存模型, 如C++, Java规范中分别定义了各自的内存模型。不过,本文主要着眼的是处理器架构层次定义的内存模型

一种直观的内存模型叫做顺序一致性模型(sequential consistency model), 简单讲,顺序一致性模型保证两件事:

每个处理器(或线程)的执行顺序是按照最后汇编的二进制程序中指令的顺序来执行的,
对于每个处理器(或线程),所有其他处理器(或线程)看到的执行顺序跟它的实际执行顺序一样。

由上两点就可以推出: 整个程序依照着一种有序的执行顺序执行。这种模型是非常直观的,运行在此架构下的程序的执行顺序跟一个不明白内存模型是何物的程序员他所期待的执行顺序一样。

不过,这种模型的效率低下,因为它阻止了处理器发挥乱序执行的能力以最大化并行度,因此在商用的处理器架构中,没有人使用这种模型。取而代之的是更弱的内存一致性模型

比如,耳熟能详的x86及其后续的兼容于它的x86_64架构,采用的是一种叫流程一致性(process consistency)的模型,简言之:

对于某个处理器的`写操作`,它可以按照其意愿重排执行顺序,但对于所有其它处理器,他们看到的顺序,就是它实际执行的顺序。也许这点很难理解,但很重要,后文详述。

还有更松散的弱内存模型, 给予处理器非常自由的重排指令的能力。因此,需要程序员(尤指系统程序员)采取必要的措施进行限制,以保证想要的结果。这就是本文的主题。实际上,这种处理器典型的就是DEC ALPHA, 因此,Linux的通用内存模型是基于它之上构建的。后文详述。

在继续之前,有三个概念要澄清。

`程序顺序(program order)`: 指给定的处理器上,程序最终编译后的二进制程序中的内存访问指令的顺序,因为编译器的优化可能会重排源程序中的指令顺序。
`执行顺序(execution order)`: 指给定的处理器上,内存访问指令的实际执行顺序。这可能由于处理器的乱序执行而与程序顺序不同。
`观察顺序(perceived order)`: 指给定的处理器上,其观察到的所有其他处理器的内存访问指令的实际执行顺序。这可能由于处理器的缓存及处理器间内存同步的优化而与执行顺序不同。

前面的几种内存模型的描述中,其实就用到了这几种顺序的等价描述。

何谓内存屏障

上文已经粗略描述了多处理架构下,为了提高并行度,充分挖掘处理器效率的做法会导致的一些与程序员期待的不同的执行结果的情况。本节更详细地描述这种情况, 即为何顺序一致性的模型难以保持的原因。

总的来说,在系统程序员关注的操作系统层面,会重排程序指令执行顺序的两个主要的来源是处理器优化编译器优化

处理器优化

共享内存的多处理架构的典型结构图如下:

图片

如图,共享内存的涵义其实是每个处理器拥有自己本地内存, 但所有的非本地内存亦可访问,但显然存在速度的差别。此外,每个处理器还拥有自己的本地缓存系统; 所有的处理器通过一个网络来通信。

显然,这种架构下的内存操作会有巨大的延时问题。为了缓解这些问题,处理器会采取一些优化措施, 而导致程序顺序被破坏。

  • 情景一: 设想某处理器发出一条某内存位置读的指令,恰好这个内存位置在远端内存,而且处理器本地缓存也没有命中。于是,为了等待这个值,处理器需要空转(stall)。这显然是效率的极大浪费,事实现代的处理器都有乱序执行引擎, 指令并不是直接被执行,而是放到等待队列里,等待操作数到位后才执行,而这期间处理器优先处理其他指令。也就是出于效率考虑,处理器会重排指令, 这就违背了程序顺序

  • 情景二: 设想有一个热点全局变量,那么在程序运行一段时间后,很可能很多个处理器的本地缓存都有该变量的一份拷贝。再设想现在有处理器A修改这个全局变量,这个修改会发布一条消息能过网络通知所有其他处理器更新该变量缓存。由于路径的问题,消息不会同时到达所有处理器,那么存在一种可能性,某处理器此时仍观察到旧的值,而采取一些基于该旧值的动作。也就是,执行顺序观察顺序不同,这可能导致出人意表的程序行为。

编译器优化

编译器的优化操作,如寄存器分配(register allocation), 循环不变里代码移动(loop-invariant code motion), 共同子表达式(common sub-expression elimination), 等等,都有可能导致内存访问操作被重排,甚至消除。因此,编译器优化也会影响指令重排。

另外,还有一种情况需要单独说明。一些设备会把它们的控制接口映射到程序的进程空间,对这种设备的访问叫做内存映射IO(Memory Mapped IO, MMIO), 对设备的地址寄存器与数据寄存器等寄存器的访问就如同读写内存一样方便。一般的访问模式是先传访问端口到地址寄存器AR, 再从数据寄存器DR中访问数据, 其代码顺序为:

*AR = 1;
x = *DR;

这种顺序可能会被编译器颠倒,结果自然是错误的程序行为。

综上,内存屏障就是在处理器/设备交互过程中,显式加入的一些干预措施,以防止处理器优化或编译优化,以保持想要的内存指令访问顺序

内存屏障的种类

Linux内核实现的屏障种类有以下几种:

写屏障(write barriers)

  • 定义: 在写屏障之前的所有写操作指令都会在写屏障之后的所有写操作指令更早发生。

  • 注意1: 这种顺序性是相对这些动作的承接者,即内存来说。也就是说,在一个处理器上加入写屏障不能保证别的处理器上看到的就是这种顺序,也就是观察顺序执行顺序无关。

  • 注意2: 写屏障不保证屏障之前的所有写操作在屏障指令结束前结束。也就是说,写屏障序列化了写操作的发生顺序,却没保证操作结果发生的序列化。

读屏障(write barriers)

  • 定义: 在读屏障之前的所有读操作指令都会在读屏障之后的所有读操作指令更早发生。另外,它还包含后文描述的数据依赖屏障的功能

  • 注意1: 这种顺序性是相对这些动作的承接者,即内存来说。也就是说,在一个处理器上加入读屏障不能保证别的处理器上实际执行的就是这种顺序,也就是观察顺序执行顺序无关。

  • 注意2: 读屏障不保证屏障之前的所有读操作在屏障指令结束前结束。也就是说,读屏障序列化了读操作的发生顺序,却没保证操作结果发生的序列化。

写屏障/读屏障举例

注意,之所以要把这两种屏障放在一起举例原因就是:写屏障必须与读屏障一起使用

例如:

     CPU 1           CPU 2
     =============== ===============
     a = 1;
     <write barrier>
     b = 2;          x = b;
                     y = a;

假如,CPU 2上观察到x值为2, 能否保证其观察到的y值为1?

不能!这就是前面的注意1强调的内容。原因可能是CPU 2上的缓存中存有a的旧值,而正如何谓内存屏障一节中情景二所说的,由于CPU 1上写操作消息传递的延迟,可能CPU 2还未接收到a值更改的消息。

正确的做法是,在CPU 2上插入读屏障。配对的读/写屏障才能保证正确的程序行为

    CPU 1           CPU 2
    =============== ===============
    a = 1;
    <write barrier>
    b = 2;          x = b;
                    <read barrier>
                    y = a;

通用屏障(general barriers)

  • 定义: 在通用屏障之前的所有写和读操作指令都会在通用屏障之后的所有写和读操作指令更早发生。

  • 注意1: 这种顺序性是相对这些动作的承接者,即内存来说。也就是说,在一个处理器上加入通用屏障不能保证别的处理器上看到的就是这种顺序,也就是观察顺序执行顺序无关。

  • 注意2: 通用屏障不保证屏障之前的所有写和读操作在屏障指令结束前结束。也就是说,通用屏障序列化了写和读操作的发生顺序,却没保证操作结果发生的序列化。

  • 注意3: 通用屏障是最严格的屏障,这也意味着它的低效率。它可以替换在写屏障或读屏障出现的地方

数据依赖屏障(data dependency barriers)

前文说过,DEC ALPHA在Linux所支持的处理器架构中拥有最松散的内存模型,所以DEC ALPHA架构的内存模型定义了Linux的通用内存模型。因此,在内核中,多引入了一种内存屏障,叫做数据依赖屏障,因为在DEC ALPHA上会出现以下这种问题。看例子:

     CPU 1           CPU 2
     =============== ===============
     { A == 1, B == 2, C = 3, P == &A, Q == &C }
     B = 4;
     <write barrier>
     P = &B
                     Q = P;
                     D = *Q;

在CPU 2上,这里有个明显的数据依赖, D要加载Q所指内存位置的值,而Q的地址又要从P中先加载。在除了DEC ALPHA的Linux支持的所有架构中,都严格保证了这种依赖性,因此不需要加这两条指令中加什么内存屏障。但是,DEC ALPHA的弱内存模型连这都无法保证!于是,Linux内核新增了这种叫数据依赖屏障的内存屏障。

     CPU 1           CPU 2
     =============== ===============
     { A == 1, B == 2, C = 3, P == &A, Q == &C }
     B = 4;
     <write barrier>
     P = &B
                     Q = P;
                     <data dependency barrier>
                     D = *Q;

加上这个屏障后,就能保证所有的架构都能处理这种问题。详细见下一篇文章讨论。

下一篇文章将讨论Linux中的内存屏障接口和一些实现上相关问题。

分享到 --

本文内容遵从CC版权协议,转载请注明出自larmbr.com