Datenlord |内存顺序问题(一)

内存顺序,通俗地讲,是关于代码编译成机器指令后的执行顺序问题。内存顺序和编译器、硬件架构密切相关。那为什么会产生内存顺序问题呢?有两方面原因: 一方面,编译器为了优化程序性能,不会完全按照开发者写的代码的顺序来生成机器指令; 另一方面,在程序运行时,为了提高性能,CPU也不完全按照程序的指令顺序执行,比如体系结构里经典的Tomasulo算法。
对于大部分开发者而言,在写单线程程序,或者基于锁(Mutex)和信号量(Semaphore)之类编程框架提供的同步元语写多线程程序的时候,并不需要关心内存顺序的问题。 这是因为编译器和硬件架构保证了,虽然指令执行顺序可能跟开发者写的代码语句的顺序不一致,但是执行后的结果是一样的,即语义一致。 换句话讲,编译器和硬件架构提供了一层抽象用以屏蔽内存顺序问题,保证代码和编译出来的程序执行语义一致。 这样一方面提高程序性能,另一方面让开发者不用关心底层细节。编译器和硬件架构提供的这一层抽象叫作内存模型(Memory Model)。
这种为了便于理解和使用而提出一层抽象以屏蔽底层复杂细节的做法,在各个学科中比比皆是。 类比经典力学和相对论,在远低于光速的运动中,适用经典力学,在接近或达到光速的运动中,适用相对论而不适用经典力学; 经典力学和相对论之间,有一层抽象,速度远低于光速,抽象成立,速度接近或达到光速,抽象被打破。 类似的,编译器和硬件架构提供了内存模型这一层抽象用以屏蔽内存顺序问题。 对于大部分开发者而言,写单线程程序,或基于编程框架提供的同步元语写多线程程序的时候,内存模型抽象成立,无需考虑内存顺序问题; 当开发者写多线程程序,对于多线程并发访问(或读或写)共享数据,使用原子操作,而不是基于锁互斥访问数据,即无锁化编程的时候, 这时内存模型的抽象被打破,开发者必须考虑内存顺序问题。
内存顺序问题涉及编译器和硬件架构的很多细节,我尝试用对于大部分开发者来说浅显易懂的语言来描述内存顺序问题, 尽可能避免编译器和硬件架构的实现细节,以便于大家理解。 下面依次介绍内存模型、内存顺序、原子操作,最后以C++11为例讲解开发者如何规约内存顺序。
内存模型
内存模型是编程语言对程序运行时内存访问模式的抽象,即内存被多个程序(进程和线程)共享,程序对内存的访问是无法预知的。 通俗地讲,内存模型指的是CPU并发随机访问内存,或从内存加载数据(Load)或把数据写入到内存(Store)。 Load和Store是机器指令(或汇编语言)的术语,其实就是读(Read)操作和写(Write)操作。 这里,内存模型屏蔽了很多硬件的细节,比如CPU的寄存器、缓存等等(因为寄存器和缓存属于程序执行上下文,CPU访问寄存器和缓存不存在并发)。 内存模型比较好理解,每个开发者或多或少都接触到内存模型。 有了内存模型这一层抽象,那么内存顺序问题可以等价于读操作和写操作的执行顺序问题,因为内存模型里CPU对内存的访问只有读和写两种操作。
开发者在写代码时,代码语句的先后顺序往往约定了对内存访问的先后顺序的,即使访问的不是同一个内存地址。但是这个约定是基于内存模型这层抽象成立的前提。 前面提到,内存模型在单线程编程和基于编程框架提供的同步元语实现多线程编程的情况下,对内存顺序问题进行屏蔽,怎么理解呢?
下面通过例子说明单线程程序的内存顺序问题:

int x, y = 0; x = y + 1; y = 2;

这段代码定义了两个整数,x和y,并对y初始化赋值为0,然后给x赋值的时候用到y的值,之后再给y赋值。 看上去,对y的写操作必须在对x的写操作之后,但是改写上述代码片段如下:
int x, y = 0; int tmp; tmp = y; y = 2; x = tmp + 1;

增加了变量tmp之后,首先把y的值付给tmp,然后就可以先对y赋新值,再给x赋值。对x和y来说,上面两段程序的执行结果是等价的。 变量tmp在这里可以理解为是CPU的寄存器,有了寄存器的帮助,代码里的读操作和写操作先后顺序可能被改变。 通俗地讲,编译器对代码语句的顺序调整也是类似的原理 (仅供对编译器不熟的读者理解编译器如何对代码语句顺序的调整,实际编译器对代码的优化很复杂,细节暂不展开)。
上述例子说明了,单线程情况下,内存模型的抽象成立,开发者无需考虑内存顺序问题。 再考虑多线程的情况,把对x的写操作和对y的写操作放在不同的线程里:
int x, y = 0; void thread_func1() { x = y + 1; }void thread_func2() { y = 2; }

可以看出,x会有多种结果,取决于程序运行时两个线程的执行顺序,这就跟之前单线程的执行结果不一致了。 因为这里没有采用编程框架提供的同步元语来实现线程间同步,内存模型的抽象被打破,编译器和硬件架构无法保证语义一致。 此时,开发者要么采用编程框架提供的同步元语实现线程间同步以满足内存模型的抽象,要么显式规约指令执行顺序以保证结果正确。 改写上面的例子,可以采用编程框架提供的同步元语,规约程序运行时线程的执行顺序,这里使用信号量来实现线程间同步:
sem_t semaphore; // 初始化信号量,初始值为0,最大值为1 sem_init(&semaphore, 0, 1); int x, y = 0; void thread_func1() { x = y + 1; sem_post(&semaphore); }void thread_func2() { sem_wait(&semaphore); y = 2; }

可以看出,使用信号量规约了两个线程在程序运行时的执行顺序,线程函数thread_func2要等待线程函数thread_func1对x完成赋值后才能对y赋值。 上述例子中,采用信号量之后,内存模型的抽象成立,多线程情况下的执行结果和单线程情况下一样,即语义一致。
内存顺序
从上面对内存模型的介绍可以看出,内存顺序,通俗地讲,就是规约编译器和硬件架构对读写操作的执行顺序。 当内存模型抽象成立时,内存模型对内存顺序做出规约,从而对开发者屏蔽内存顺序问题;当内存模型不成立时,开发者就需要显式规约内存顺序。
前述讲内存模型用到的例子展示了对两个写操作的内存顺序问题。推而广之,内存顺序包含四种情况:
四种情况 读操作在后 写操作在后
读操作在先 读读 读写
写操作在先 写读 写写
即,读操作与读操作、读操作与写操作、写操作与读操作、写操作与写操作,四种情况下的指令执行顺序问题(不论是否读写同一个内存地址)。 开发者可以要求编译器和硬件架构在上述四种情况下分别做出规约,即:
  • 读读,读操作之后的读操作,之间的顺序不能改变;
  • 读写,读操作之后的写操作,之间的顺序不能改变;
  • 写读,写操作之后的读操作,之间的顺序不能改变;
  • 写写,写操作之后的写操作,之间的顺序不能改变。
也可以换一种表达:
  • 读读,读操作之前的读操作,之间的顺序不能改变;
  • 读写,写操作之前的读操作,之间的顺序不能改变;
  • 写读,读操作之前的写操作,之间的顺序不能改变;
  • 写写,写操作之前的写操作,之间的顺序不能改变。
换一种表达是为了方便后面理解C++原子操作的内存顺序。
原子操作
原子操作要么执行成功,要么尚未开始执行,不存在中间状态。 原子操作是要靠底层硬件架构来实现,只有硬件架构的某些指令才能保证原子操作,比如Compare and Swap(CAS)指令。 编程语言基于硬件架构的原子操作指令封装了一些原子类型以及原子操作(函数调用),以方便开发者使用。 如前所述,当内存模型抽象成立的时候,开发者无需考虑内存顺序问题; 当开发者使用原子操作的时候,内存模型的抽象被打破,此时开发者必须显式规约原子操作的内存顺序。
另外,当CPU读写地址对齐的内存数据的时候,有可能是原子操作。 比如32位CPU,访问一个32位整数,如果这个整数的地址是4的倍数,即内存地址对齐,那么访问操作就是原子的, 即CPU执行一条指令(在一个指令周期内)读取或写入这个整数; 但是如果这个整数的地址不是4的倍数,那CPU还是要两次访问(执行两条指令)才能读取或写入这个整数,在这两次访问中间CPU有可能被其他程序抢占。 由于在编程的时候不能假设数据的内存地址一定是4的倍数,所以开发者要默认每一条代码语句都不是原子操作,除非明确使用原子操作。
C++的内存顺序
下面以C++语言为例,介绍开发者如何显式对原子操作的内存顺序做出规约,即要求编译器和硬件架构保证按照期望的顺序来执行原子操作指令。
C++11提供了Atomic泛型,用于封装原子类型和原子操作。C++还定义了atomic_int、atomic_long、atomic_bool等类型,方便开发者直接使用。 下面的代码片段给出了Atomic泛型的定义,以及三个Atomic泛型的方法(为了便于读者理解,方法的定义略有删节):
template struct atomic; ... T load (memory_order sync) const noexcept; void store (T val, memory_order sync) noexcept; bool compare_exchange_strong (T& expected, T val, memory_order sync) noexcept; ...

上面Atomic泛型的方法里有个输入参数sync的类型memory_order,用于规约Atomic泛型方法的内存顺序。memory_order在C++11里定义为枚举类型,共有六个值,是C++11定义的内存顺序类型,可供开发者使用:
typedef enum memory_order { memory_order_relaxed, memory_order_consume, memory_order_acquire, memory_order_release, memory_order_acq_rel, memory_order_seq_cst } memory_order;

限于篇幅,这里只介绍memory_order_acquire(简称Acquire)和memory_order_release(简称Release)这两种内存顺序,后续再介绍C++的其他内存顺序。 下表给出了Acquire和Release的语义:
先后次序 语义
Acquire 读操作在前 读读、读写
Release 写操作在后 读写、写写
即,Acquire要求,针对某个读操作,该读操作之后的读操作或写操作,这两种情况下的指令顺序不能改变; Release要求,针对某个写操作,该写操作之前的读操作或写操作,这两种情况下的执行顺序不能改变。、 可以看出,Acquire和Release涉及四种内存顺序中的三种情况,读读、读写和写写,不涉及写读这种情况。
采用原子操作和Acquire和Release语义改写之前介绍内存模型用到的例子:
#include #include #include std::atomic_int indicator (0); // 初始值为零int x, y = 0; void thread_func1() { x = y + 1; // 通知thread_func2 indicator.store(1, // 写操作 std::memory_order_release); }void thread_func2() { int ready = indicator.load( // 读操作 std::memory_order_acquire); // 等待thread_func1 if (read > 0) { y = 2; } }

上述代码定义了一个原子整数变量indicator, 线程函数thread_func1在对x赋值完成之后,用indicator通知线程函数thread_func2。 特别要注意两个原子操作indicator.store()和indicator.load()的内存顺序, 为什么indicator.store()用Release语义,而indicator.load()用Acquire语义呢?
先考虑indicator.store()的Release语义。 线程函数thread_func1先对x赋值,然后调用indicator.store()把indicator的值改为1, indicator.store()的执行顺序不允许改变,绝不能是先调用indicator.store()再给x赋值。 也就是说,对indicator的写操作indicator.store()之前的操作(对x赋值),必须保证在indicator.store()之前执行,符合Release的语义。
【Datenlord |内存顺序问题(一)】再看indicator.load()的Acquire语义。 线程函数thread_func2先是调用indicator.load()读取indicator的值,检查是否不等于零,如果不为零,则对y赋值, indicator.load()的执行顺序不允许改变,绝不能是先对y赋值,再读取indicator的值。 也就是说,对indicator的读操作indicator.load()之后的操作(对y赋值),必须保证在indicator.load()之后执行,符合Acquire的语义。
简单来说,对于原子写操作要求Release语义,对于原子读操作要求Acquire语义。 有些文章把Acquire和Release比作是对一个锁进行加锁和解锁操作,个人认为这样的比喻不是很准确。 因为,Release和Acquire这类内存顺序,跟锁和信号量的抽象层面不一样,内存顺序比锁和信号量更底层,可以用原子操作和内存顺序来实现锁和信号量。 原子操作indicator.store()和indicator.load()分别采用Release和Acquire语义,定义了两个线程间的同步通知关系(Synchronize with), 用indicator这个原子变量来指示x是否完成赋值。这种同步通知关系不是静态规约好的,而是在程序运行时动态检查, 即x是否完成赋值并不阻塞线程函数thread_func2的执行,只是x是否完成赋值会影响线程函数thread_func2的执行结果, 有可能x尚未完成赋值但线程函数thread_func2已经执行完毕(此时线程函数thread_func2没有对y赋新值)。 如果采用锁或信号量,则x尚未完成赋值会阻塞线程函数thread_func2的执行,这样可以保证线程函数thread_func2对y赋新值。 可见,采用原子操作和内存顺序规约的线程同步通知机制,弱于锁和信号量等编程框架提供的同步元语实现的同步机制。 因此Release不是解锁操作,Acquire也不是加锁操作,这跟锁的互斥机制不一样。
当然可以改写线程函数thread_func2,使其忙等待线程函数thread_func1对x完成赋值:
void thread_func2() { int ready; // 等待thread_func1 do { ready = indicator.load( // 读操作 std::memory_order_acquire); } while (ready == 0); y = 2; }

这样一来,相当于是基于原子操作和内存顺序实现了一个信号量,只是这个信号量让线程函数thread_func2忙等待而不是阻塞休眠。 这种做法在Linux内核里很常见,比如某个中断响应程序采用自旋锁(Spin Lock)忙等待某个资源,而不采用锁以避免阻塞休眠, 因为中断处理程序本身如果阻塞休眠或被其他程序抢占,会导致很复杂的程序上下文切换,也可能导致死锁。
限于篇幅,我后续再对C++的其他内存顺序和同步通知机制做详细介绍。
作者 | 王璞

    推荐阅读