浅析C++多线程内存模型

标签: 并行编程 C++1x 多核 多线程内存模型 多线程编程 | 发表时间:2011-08-27 11:39 | 作者:Guancheng 2sin18
出处:http://www.parallellabs.com

注:本文发表于《程序员》2011年第6期并行编程专栏,略有删改。

在即将到来的C++1x标准中,一个重大的更新就是引入了C++多线程内存模型。本文的主要目的在于介绍C++多线程内存模型涉及到的一些原理和概念,以帮助大家理解C++多线程内存模型的作用和意义。

1. 顺序一致性模型(Sequential Consistency)

在介绍C++多线程模型之前,让我们先介绍一下最基本的顺序一致性模型。对多线程程序来说,最直观,最容易被理解的执行方式就是顺序一致性模型。顺序一致性的提出者Lamport给出的定义是:
“… 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.”
从这个定义中我们可以看出,顺序一致性主要约定了两件事情:
(1)从单个线程的角度来看,每个线程内部的指令都是按照程序规定的顺序(program order)来执行的;
(2)从整个多线程程序的角度来看,整个多线程程序的执行顺序是按照某种交错顺序来执行的,且是全局一致的;

下面我们通过一个例子来理解顺序一致性。假设我们有两个线程(线程1和线程2),它们分别运行在两个CPU核上,有两个初始值为0的全局共享变量x和y,两个线程分别执行下面两条指令:
初始条件: x = y = 0;

线程 1 线程 2
x = 1; y=1;
r1 = y; r2 = x;

因为多线程程序交错执行的顺序是不确定的,所以该程序可能有如下几种执行顺序:

顺序 1 顺序 2 顺序 3
x = 1;
r1 = y;
y = 1;
r2 = x;
结果:r1==0 and r2 == 1
y = 1;
r2 = x;
x = 1;
r1 = y;
结果: r1 == 1 and r2 == 0
x = 1;
y = 1;
r1 = y;
r2 = x;
结果: r1 == 1 and r2 == 1

顺序一致性模型的第一个约定要求每个线程内部的语句都是按照程序规定的顺序执行,例如,线程1里面的两条语句在该线程中一定是x=1先执行,r1=y后执行。顺序一致性的第二个约定要求多线程程序按照某种顺序执行,且所有线程看见的整体执行顺序必须一致,即该多线程程序可以按照顺序1、顺序2或者顺序3(以及其他可能的执行顺序)执行,且线程1和线程2所观察到的整个程序的执行顺序是一致的(例如,如果线程1“看见”整个程序的执行顺序是顺序 1,那么线程2“看见”的整个程序的执行顺序也必须是顺序1,而不能是顺序2或者顺序3)。依照顺序一致性模型,虽然这个程序还可能按其他的交错顺序执行,但是r1和r2的值却只可能出现上面三种结果,而不可能出现r1和r2同时为0的情况。

然而,尽管顺序一致性模型非常易于理解,但是它却对CPU和编译器的性能优化做出了很大的限制,所以常见的多核CPU和编译器大都没有实现顺序一致性模型。例如,编译器可能会为了隐藏一部分读操作的延迟而做如下优化,把线程1中对y的读操作(即r1=y)调换到x=1之前执行:

初始条件:x=y=0;

线程 1 线程 2
r1 = y; y=1;
x = 1; r2 = x;

在这种情况下,该程序如果按下面的顺序执行就可能就会出现r1和r2都为0这样的违反顺序一致性的结果:

顺序 4
r1 = y;
y = 1;
r2 = x;
x = 1;

那么为什么编译器会做这样的乱序优化呢?因为读一个在内存中而不是在cache中的共享变量需要较长的时钟周期,所以编译器就“自作聪明”的让读操作先执行,从而隐藏掉一些指令执行的延迟,从而提高程序的性能。实际上,这种优化是串行时代非常普遍的,因为它对单线程程序的语义是没有影响的。但是在进入多核时代后,编译器缺少语言级的内存模型的约束,导致其可能做出违法顺序一致性规定的多线程语义的错误优化。同样的,多核CPU中的写缓冲区(store buffer)也可能实施乱序优化:它会把要写入内存的值先在缓冲区中缓存起来,以便让该写操作之后的指令先执行,进而出现违反顺序一致性的执行顺序。

因为现有的多核CPU和编译器都没有遵守顺序一致模型,而且C/C++的现有标准中都没有把多线程考虑在内,所以给编写多线程程序带来了一些问题。例如,为了正确地用C++实现Double-Checked Locking,我们需要使用非常底层的内存栅栏(Memory Barrier)指令来显式地规定代码的内存顺序性(memory ordering)[5]。然而,这种方案依赖于具体的硬件,因此可移植性很差;而且它过于底层,不方便使用。

2. C++多线程内存模型

为了更容易的进行多线程编程,程序员希望程序能按照顺序一致性模型执行;但是顺序一致性对性能的损失太大了,CPU和编译器为了提高性能就必须要做优化。为了在易编程性和性能间取得一个平衡,一个新的模型出炉了:sequential consistency for data race free programs,它就是即将到来的C++1x标准中多线程内存模型的基础。对C++程序员来说,随着C++1x标准的到来,我们终于可以依赖高级语言内建的多线程内存模型来编写正确的、高性能的多线程程序。

C++内存模型可以被看作是C++程序和计算机系统(包括编译器,多核CPU等可能对程序进行乱序优化的软硬件)之间的契约,它规定了多个线程访问同一个内存地址时的语义,以及某个线程对内存地址的更新何时能被其它线程看见。这个模型约定:没有数据竞跑的程序是遵循顺序一致性的。该模型的核心思想就是由程序员用同步原语(例如锁或者C++1x中新引入的atomic类型的共享变量)来保证你程序是没有数据竞跑的,这样CPU和编译器就会保证程序是按程序员所想的那样执行的(即顺序一致性)。换句话说,程序员只需要恰当地使用具有同步语义的指令来标记那些真正需要同步的变量和操作,就相当于告诉CPU和编译器不要对这些标记好的同步操作和变量做违反顺序一致性的优化,而其它未被标记的地方可以做原有的优化。编译器和CPU的大部分优化手段都可以继续实施,只是在同步原语处需要对优化做出相应的限制;而且程序员只需要保证正确地使用同步原语即可,因为它们最终表现出来的执行效果与顺序一致性模型一致。由此,C++多线程内存模型帮助我们在易编程性和性能之间取得了一个平衡。

在C++1x标准之前,C++是在建立在单线程语义上的。为了进行多线程编程,C++程序员通过使用诸如Pthreads,Windows Thread等C++语言标准之外的线程库来完成代码设计。以Pthreads为例,它提供了类似pthread_mutex_lock这样的函数来保证对共享变量的互斥访问,以防止数据竞跑。人们不禁会问,Pthreads这样的线程库我用的好好的,干嘛需要C++引入的多线程,这不是多此一举么?其实,以线程库的形式进行多线程编程在绝大多数应用场景下都是没有问题的。然而,线程库的解决方案也有其先天缺陷。第一,如果没有在编程语言中定义内存模型的话,我们就不能清楚的定义到底什么样的编译器/CPU优化是合法的,而程序员也不能确定程序到底会怎么样被优化执行。例如,Pthreads标准中并未对什么是数据竞跑(Data Race)做出精确定义,因此C++编译器可能会进行一些错误优化从而导致数据竞跑[3]。第二,绝大多数情况下线程库能正确的完成任务,而在极少数对性能有更高要求的情况下(尤其是需要利用底层的硬件特性来实现高性能Lock Free算法时)需要更精确的内存模型以规定好程序的行为。简而言之,把内存模型集成到编程语言中去是比线程库更好的选择。

3. C++1x中引入的atomic类型

C++作为一种高性能的系统语言,其设计目标之一就在于提供足够底层的操作,以满足对高性能的需求。在这个前提之下,C++1x除了提供传统的锁、条件变量等同步机制之外,还引入了新的atomic类型。相对于传统的mutex锁来说,atomic类型更底层,具备更好的性能,因此能用于实现诸如Lock Free等高性能并行算法。有了atomic类型,C++程序员就不需要像原来一样使用汇编代码来实现高性能的多线程程序了。而且,把atomic类型集成到C++语言中之后,程序员就可以更容易地实现可移植的多线程程序,而不用再依赖那些平台相关的汇编语句或者线程库。

对常见的数据类型,C++1x都提供了与之相对应的atomic类型。以bool类型举例,与之相对应的atomic_bool类型具备两个新属性:原子性与顺序性。顾名思义,原子性的意思是说atomic_bool的操作都是不可分割的,原子的;而顺序性则指定了对该变量的操作何时对其他线程可见。在C++1x中,为了满足对性能的追求,atomic类型提供了三种顺序属性:sequential consistency ordering(即顺序一致性),acquire release ordering以及relaxed ordering。因为sequential consistency是最易理解的模型,所以默认情况下所有atomic类型的操作都会使sequential consistency顺序。当然,顺序一致性的性能相对来说比较差,所以程序员还可以使用对顺序性要求稍弱一些的acquire release ordering与最弱的relaxed ordering。

在下面这个例子中,atomic_bool类型的变量data_ready就被用来实现两个线程间的同步操作。需要注意的是,对data_ready的写操作仍然可以通过直接使用赋值操作符(即“=”)来进行,但是对其的读操作就必须调用load()函数来进行。在默认的情况下,所有atomic类型变量的顺序性都是顺序一致性(即sequential consistency)。在这个例子中,因为data_ready的顺序性被规定为顺序一致性,所以线程1中对data_ready的写操作会与线程2中对data_ready的读操作构建起synchronize-with的同步关系,即#2->#3。又因为writer_thread()中的代码顺序规定了#1在#2之前发生,即#1->#2;而且reader_thread中的代码顺序规定了#3->#4,所以就有了#1->#2->#3->#4这样的顺序关系,从而可以保证在#4中读取data的值时,#1已经执行完毕,即#4一定能读到#1写入的值(10)。

#include <atomic>
#include <vector>
#include <iostream>

std::vector<int> data;
std::atomic_bool data_ready(false);

// 线程1
void writer_thread()
{
data.push_back(10); // #1:对data的写操作
data_ready = true; // #2:对data_ready的写操作
}

// 线程2
void reader_thread()
{
while(!data_ready.load()) // #3:对data_ready的读操作
{
std::this_thread::sleep(std::milliseconds(10));
}
std::cout << ”data is ” << data[0] << ”\n”; // #4:对data的读操作
}

相信很多朋友会纳闷,这样的执行顺序不是显然的么?其实不然。如果我们把data_ready的顺序性制定为relaxed ordering的话,编译器和CPU就可以自由地做违反顺序一致性的乱序优化,从而导致#1不一定在#2之前被执行,最终导致#4中读到的data的值不为10。

简单的来说,在atomic类型提供的三种顺序属性中,acquire release ordering对顺序性的约束程度介于sequential consistency(顺序一致性)和relaxed ordering之间,因为它不要求全局一致性,但是具有synchronized with的关系。Relaxed ordering最弱,因为它对顺序性不做任何要求。由此可见,除非非常必要,我们一般不建议使用relaxed ordering,因为这不能保证任何顺序性。关于这三种属性更详细的信息大家可以参考[1]。

通过上面的例子我们可以看到,C++1x中的多线程内存模型为了通过atomic类型提供足够的灵活性和性能,最大限度地将底层细节(三种不同的顺序属性)暴露给了程序员。这样的设计原则一方面给程序员提供了实现高性能多线程算法的可能,但却也大大增加了使用上的难度。我个人的建议是,如果常规的mutex锁、条件变量、future信号能满足您的设计需求,那么您完全不需要使用atomic变量。如果您决定使用atomic变量,请尽量使用默认的顺序一致性属性。

4. 总结

本文对C++1x标准中新引入的多线程内存模型进行了简要介绍。C++1x多线程内存模型的引入使得广大C++程序员可以享受语言原生支持的多线程机制,并为实现高性能多线程算法提供了足够丰富的工具(例如atomic类型)。但是,多线程内存模型本身的复杂性,以及一些底层机制(例如不同的顺序性属性)的引入也给使用C++进行多线程编程带来了不小的复杂度。如何高效、可靠的利用好这些新引入的多线程机制将会成为一个新的挑战。

参考资料

[1] C++ Concurrency in Action
[2] C++1x standard draft
[3] Threads cannot be implemented as a library
[4] Memory Models: A Case for Rethinking Parallel Languages and Hardware
[5] The “Double-Checked Locking is Broken” Declaration

冠诚, IBM中国研究院, 研究员
任何与多核、并行、多线程有关的话题都可以找我聊聊:-) 我的邮箱是chenguancheng AT gmail.com

相关日志

相关 [多线程 内存 模型] 推荐:

浅析C++多线程内存模型

- 2sin18 - 并行实验室 | Parallel Labs
注:本文发表于《程序员》2011年第6期并行编程专栏,略有删改. 在即将到来的C++1x标准中,一个重大的更新就是引入了C++多线程内存模型. 本文的主要目的在于介绍C++多线程内存模型涉及到的一些原理和概念,以帮助大家理解C++多线程内存模型的作用和意义. 顺序一致性模型(Sequential Consistency).

Java 多线程内存模型

- - ITeye博客
Java 多线程内存模型.       Java虚拟机规范中试图定义一种Java内存模型(Java Memory Model,JMM)来屏蔽掉各种硬件和操作系统的内存访问差异,以实现让Java程序在各种平台下都能达到一致的并发效果. 在此之前,主流程序怨言(如C/C++等)直接使用物理硬件(或者说操作系统的内存模型),因此,会由于不同的平台上内存模型差异,导致程序在一套平台上并发完成正常,而在另一套平台上并发访问却经常出错,因此经常需要针对不同的平台来编写程序.

Java多线程之内存可见性

- - CSDN博客推荐文章
一、JAVA内存模型简介. JAVA Merory  Model描述了JAVA程序中各种变量(线程共享变量)的访问规则,以及在JVM中将变量存储到内存和从内存中读取变量这样的底层细节. 所有的变量都保存在主内存中,但是每个线程都有自己的独立工作内存,保存该线程使用到的变量的一个副本. 1.线程对共享变量的操作只能在独立的工作内存中进行,不能在主内存中直接读写;.

深入Java内存模型

- - ImportNew
你可以在网上找到一大堆资料让你了解JMM是什么东西,但大多在你看完后仍然会有很多疑问. happen-before是怎么工作的呢. 用volatile会导致缓存的丢弃吗. 为什么我们从一开始就需要内存模型. 通过这篇文章,读者可以学习到足以回答以上所有问题的知识. 它包含两大部分:第一部分是硬件层次的大体架构,第二部分是深入OpenJdk源代码和实现.

Java 内存模型 JMM

- - 码蜂笔记
JMM,Java Memory Model,Java 内存模型. 什么是内存模型,要他何用. 假定一个线程为变量var赋值: var = 3;,内存模型要回答的问题是:在什么条件下,读取变量var的线程可以看到 3这个值. 如果缺少了同步,线程可能无法看到其他线程操作的结果. 导致这种情况的原因可以有:编译器生成指令的次序可以不同于源代码的“显然”版本,编译器还会把变量存储在寄存器而不是内存中;处理器可以乱序或并行执行指令;缓存会改变写入提交到主存得到变量的次序;存储在处理器本地缓存中的变量对其他处理器不可见 等等.

Java运行时的内存模型

- - CSDN博客编程语言推荐文章
每个线程单独的数据区(线程间不共享). 每个线程都有一片单独的内存区域,这里面包含:程序计数器(program counter register),JVM栈和本地方法栈(Native Method Stack). 当一个新的线程被创建的时候,这片内存就已经被分配出来了. 程序计数器:为了线程切换后能恢复到正确的执行位置,每条线程都需要有一个独立的程序计数器,各线程之间的计数器互不影响,独立存储.

Java内存模型修订了!

- - 互联网 - ITeye博客
传统的Java内存模型涵盖了很多Java语言的语义保证. 在这篇文章中,我们将重点介绍其中的几个语义,以更深入地了解他们. 对于本文中描述的语义,我们还将尝试体会对现有Java内存模型更新的动机. 本文中与JMM未来更新相关的讨论,将被称为JMM9. 现有的Java内存模型,如JSR133(以下称为JMM-JSR133)中所定义的,为共享内存指定了一致性模型,并且有助于为开发者提供与JMM-JSR133表述一致的定义.

非一致性内存访问模型与内存分配器

- est - snnn的blog
CPU主频涨不上去了,一直停留在2-3G. 前端总线的时钟频率也涨不上去了,我现在用的这个小黑,Intel Core2 P8600,前端总线的时钟频率只有266MHz. 于是,虽然内存越来越便宜了,但是没有那么大的高速带宽来连接CPU和内存啊. CPU组成node,每个node各自管理几十G内存,然后node和node之间通过Point-to-Point的方式建立高速直连.