Non-Profit, International

Spirit unsterblich.

C++ 和双重检查锁定模式(DCLP)的风险

字数统计:7837 blog

本文是 Scott Meyers 和 Andrei Alexandrescu 在 2004 年发表的 论文 的一篇翻译,由于原译者的 网站 已经无法访问,在此整理留作备份,有改动。

虽然文章是在 2004 年写的,C++11 标准发布后文章中的一些问题也不在存在,但是文章的思想仍然有用。


多线程其实只是一件事与其他事在前,在后,或者同时发生。

1 介绍

当你在网上搜索设计模式的相关资料时,你一定会找到最常被提及的一个模式:单例模式 1 (Singleton)。然而,当你尝试在项目中使用单例模式时,一定会遇到一个很重要的限制:若使用传统的实现方法(我们会在下文解释如何实现),单例模式是非线程安全的。

程序员们为了解决这一问题付出了很多努力,其中最流行的一种解决方法是使用一个新的设计模式:双重检查锁定模式 2 (DCLP,double checked locking pattern)。设计 DCLP 的目的在于在共享资源(如单例)初始化时添加有效的线程安全检查功能。但 DCLP 也存在一个问题:它是不可靠的。此外,在本质上不改变传统设计模式实现的基础上,几乎找不到一种简便方法能够使 DCLP 在 C/C++ 程序中变得可靠。更有趣的是,DCLP 无论在单处理器还是多处理器架构中,都可能由不同的原因导致失效。

本文将为大家解释以下几个问题:

  1. 为什么单例模式是非线程安全的?
  2. DCLP 是如何处理这个问题的?
  3. 为什么 DCLP 在单处理器和多处理器架构下都可能失效?
  4. 为什么我们很难为这个问题找到简便的解决办法?

在这个过程中,我们将澄清以下四个概念之间的关系:语句在源代码中的顺序、序列点 3 (sequence points)、 编译器和硬件优化,以及语句的实际执行顺序。最后,我们会总结一些关于如何给单例模式(或其他相似设计)添加线程安全机制的建议,使你的代码变得既可靠又高效。

2 单例模式与多线程

单例模式传统的实现方法是,当对象第一次使用时将其实例化,并用一个指针指向该对象,实现代码如下:


// from the header file 以下代码来自头文件
class Singleton
{
public:
    static Singleton *instance();
    ...
private:
    static Singleton *pInstance;
};

// from the implementation file 以下代码来自实现文件
Singleton *Singleton::pInstance = 0;

Singleton *Singleton::instance()
{
    if (pInstance == 0)
    {
        pInstance = new Singleton;
    }
    return pInstance;
}

在单线程环境下,虽然中断会引起某些问题,但大体上这段代码可以运行得很好。如果代码运行到 Singleton::instance() 内部时发生中断,而中断处理程序调用的也是 Singleton::instance(),可以想象你将会遇到什么样的麻烦。因此,如果撇开中断不考虑,那么这个实现在单线程环境下可以运行得很好。

很不幸,这个实现在多线程环境下不可靠。假设线程 A 进入 instance(),执行第 14 行代码,此时线程被挂起(suspended)。在A被挂起时,它刚判断出 pInstance 是空值,也就是说 Singleton 的对象还未被创建。

现在线程 B 开始运行,进入 instance() 函数,并执行第 14 行代码。线程 B 也判断出 pInstance 为空,因此它继续执行第 15 行,创建出一个 Singleton 对象,并将 pInstance 指向该对象,然后把 pInstance 返回给 instance() 的调用者。

之后的某一时刻,线程 A 恢复执行,它接着做的第一件事就是执行第 15 行:创建出另一个 Singleton 对象,并让 pInstance 指向新对象。这显然违反了“单例”的本意,因为现在我们有了两个 Singleton 对象。

从技术上说,第 11 行才是 pInstance 初始化的地方,但实际上,我们到第 15 行才将 pInstance 指向我们所希望它指向的内容,因此本文在提及 pInstance 初始化的地方,都指的是第 15 行。

将经典的单例实现成支持线程安全性是很容易的事,只需要在判断 pInstance 之前加锁即可:


Singleton *Singleton::instance()
{
    Lock lock; // acquire lock (params omitted for simplicity) 加锁(为了简便起见,代码中忽略了加锁所需要的参数)
    if (pInstance == 0)
    {
        pInstance = new Singleton;
    }
    return pInstance;
} // release lock (via Lock destructor) // 解锁(通过Lock的析构函数实现)

这个解决办法的缺点在于可能会导致昂贵的程序执行代价:每次访问该函数都需要进行一次加锁操作。但实际中,我们只有 pInstance 初始化时需要加锁。也就是说加锁操作只有 instance() 第一次被调用时才是必要的。如果在程序运行过程中, instance() 被调用了 n 次,那么只有第一次调用锁起了作用。既然另外的 n - 1 次锁操作都是没必要的,那么我们为什么还要付出 n 次锁操作的代价呢?DCLP 就是设计来解决这个问题的。

3 双重检查锁定模式

DCLP 的关键之处在于我们观察到的这一现象:调用者在调用 instance() 时,pInstance 在大部分时候都是非空的,因此没必要再次初始化。所以,DCLP 在加锁之前先做了一次 pInstance 是否为空的检查。只有判断结果为真(即 pInstance 还未初始化),加锁操作才会进行,然后再次检查 pInstance 是否为空(这就是该模式被命名为双重检查的原因)。第二次检查是必不可少的,因为,正如我们之前的分析,在第一次检验 pInstance 和加锁之间,可能有另一个线程对 pInstance 进行初始化。

以下是 DCLP 经典的实现代码:


Singleton *Singleton::instance()
{
    if (pInstance == 0)
    { // 1st test 第一次检查
        Lock lock;
        if (pInstance == 0)
        { // 2nd test 第二次检查
            pInstance = new Singleton;
        }
    }
    return pInstance;
}

定义 DCLP 的文章中讨论了一些实现中的问题(例如,对单例指针加上 volatile 限定 4 的重要性,以及多处理器系统上独立缓存的影响,这两点我们将在下文讨论;但关于某些读写操作需要确保原子性这一点本文不予讨论),但他们都没有考虑到一个更基本的问题:DCLP 的执行过程中必须确保机器指令是按一个可接受的顺序执行的。本文将着重讨论这个基本问题。

4 DCLP与指令执行顺序

我们再来思考一下初始化 pInstance 的这行代码:


pInstance = new Singleton;

这条语句实际做了三件事情:

  1. 为 Singleton 对象分配一片内存
  2. 构造一个 Singleton 对象,存入已分配的内存区
  3. 将 pInstance 指向这片内存区

这里至关重要的一点是:我们发现编译器并不会被强制按照以上顺序执行!实际上,编译器有时会交换步骤 2 和步骤 3 的执行顺序。编译器为什么要这么做?这个问题我们留待下文解决。当前,让我们先专注于如果编译这么做了,会发生些什么。

请看下面这段代码。我们将 pInstance 初始化的那行代码分解成我们上文提及的三个步骤来完成,把步骤 1(内存分配)和步骤 3(指针赋值)写成一条语句,接着写步骤 2(构造 Singleton 对象)。正常人当然不会这么写代码,可是编译器却有可能将我们上文写出的 DCLP 源码生成出以下形式的等价代码:


Singleton *Singleton::instance()
{
    if (pInstance == 0)
    {
        Lock lock;
        if (pInstance == 0)
        {
            pInstance =                      // Step 3 步骤3
            operator new(sizeof(Singleton)); // Step 1 步骤1
            new (pInstance) Singleton;       // Step 2 步骤2
        }
    }
    return pInstance;
}

一般情况下,将 DCLP 源码转化成这种代码是不正确的,因为在步骤 2 调用 Singleton 的构造函数时,有可能抛出异常(exception)。如果异常抛出,很重要的一点在于 pInstance 的值还没发生改变。这就是为什么一般来说编译器不会把步骤 2 和步骤 3 的位置对调。然而,在某些条件下,生成的这种代码是合法的。最简单的一种情况是编译器可以保证 Singleton 构造函数不会抛出异常(例如通过内联化后的流分析(post-inlining flow analysis),当然这不是唯一情况。有些抛出异常的构造函数会自行调整指令顺序,因此才会出现这个问题。

根据上述转化后的等价代码,我们来考虑以下场景:

  1. 线程 A 进入 instance(),检查出 pInstance 为空,请求加锁,而后执行由步骤1和步骤3组成的语句。之后线程A被挂起。此时,pInstance 已为非空指针,但pInstance 指向的内存里的 Singleton 对象还未被构造出来。
  2. 线程 B 进入 instance(), 检查出 pInstance 非空,直接将 pInstance 返回(return)给调用者。之后,调用者使用该返回指针去访问 Singleton 对象——啊哦,显然这个 Singleton 对象实际上还未被构造出来呢!

只有步骤 1 和步骤 2 在步骤 3 之前执行,DCLP 才有效,但在 C/C++ 中我们没有办法表达这种限制。这就像一把尖刀插进 DCLP 的心脏:我们必须为相关指令顺序定义一些限制,但我们所使用的语言却无法表达这种限制。

是的,C/C++ 标准确实为语句的求值顺序定义了相应的限制,即序列点(sequence points)。例如,C++ 标准中 1.9 章的第 7 段有句激动人心的描述:

“序列点是指程序运行到某个特别的时间点,在此之前的所有求值的副作用 3 (side effect)应已结束,且后续求值的副作用应还未发生。”

此外,标准中还声明了序列点在每条语句之后发生。看来只要你小心谨慎地将你的语句排好序,一切就都有条不紊了。

噢,奥德修斯 5 (Odysseus), 千万别被她动人的歌声所迷惑,前方还要许多艰难困苦等着你和你的弟兄们呢!

C/C++ 标准根据抽象机器的可见行为(observable behavior)定义了正确的程序行为。但抽象机器里并非所有行为都可见。例如下文中这个简单的函数:


void Foo()
{
    int x = 0, y = 0;       // Statement 1 语句1
    x = 5;                  // Statement 2 语句2
    y = 10;                 // Statement 3 语句3
    printf("%d, %d", x, y); // Statement 4 语句4
}

这个函数看起来挺傻,但它可能是 Foo 调用其它内联函数展开后的结果。

C/C++ 的标准都保证了 Foo() 的输出是 5, 10,因此我们也知道是这样的结果。但我们只是根据标准给出的保证,得出我们的结论。我们其实根本不知道语句 1-3 是否真的会被执行。

事实上,一个好的优化器会丢弃这三条语句。如果语句 1-3 被执行了,那么我们可以肯定语句 1 的执行先于语句 2-4(假设 printf 不是个内联函数,并且结果没有被进一步优化);我们也可以肯定语句 4 的执行晚于语句 1-3,但我们并不知道语句 2 和语句 3 的执行顺序。编译器可能让语句 2 先执行,也可能让语句 3 先执行,如果硬件支持,它甚至有可能让两条语句并行执行。这种可能性很大,因为现代处理器支持大字长以及多执行单元,两个或更多的运算器也很常见。这些机器都允许编译器生成可并行执行的代码,使得处理器在一个时钟周期内能够处理两条甚至更多指令。

优化编译器会仔细地分析并重新排序你的代码,使得程序执行时,在可见行为的限制下,同一时间能做尽可能多的事情。在串行代码中发现并利用这种并行性是重新排列代码并引入乱序执行最重要的原因,但并不是唯一原因,以下几个原因也可能使编译器(和链接器)将指令重新排序:

  1. 避免寄存器数据溢出
  2. 保持指令流水线连续
  3. 公共子表达式消除
  4. 降低生成的可执行文件的大小

C/C++ 的编译器和链接器执行这些优化操作时,只会受到 C/C++ 标准文档中定义的抽象机器上可见行为的原则这唯一的限制。很重要的一点是:这些抽象机器默认是单线程的。C/C++ 作为一种语言,二者都不存在线程这一概念,因此编译器在优化过程中无需考虑是否会破坏多线程程序。如果它们这么做了,请别惊讶。

既然如此,程序员怎样才能用 C/C++ 写出能正常工作的多线程程序呢?通过使用操作系统特定的库来解决。例如 Posix 线程库 6 (pthreads),这些线程库为各种同步原语的执行语义提供了严格的规范。由于编译器生成代码时需要依赖这些线程库,因此编译器不得不按线程库所约束的执行顺序生成代码。这也是为什么多线程库有一部分需要用直接用汇编语言实现,或者调用由汇编实现的系统调用(或者使用一些不可移植的语言)。换句话说,你必须跳出标准 C/C++ 语言在你的多线程程序中实现这种执行顺序的约束。DCLP 试图只使用一种语言来达到目的,所以 DCLP 不可靠。

由于编译器可以非常“聪明”的消除所有在单线程下安全但是在多线程中需要的代码,并且也会伴随指令的重新排序,甚至 CPU 的乱序执行技术也可以让看似顺序执行的指令不按照原本的顺序执行,所以这里有一个基本的问题,你没有能力改变:你希望利用约束条件让指令按顺序执行,但你所使用的语言不提供任何实现方法。

5 volatile 关键字的成名之路

注:此处内容已经过时,因为现代 C/C++ 已经对多线程进行了一些修复,不再建议使用 volatile 4 解决多线程问题,并且 volatile 也并不可靠。

6 多处理器上的 DCLP

假设你的机器有多个处理器,每个都有各自的高速缓存(容量小但是比内存更高效),所有处理器共享内存空间。这种架构需要设计者精确定义一个处理器该如何向共享内存执行写操作,又该何时执行这样的操作,并使其对其他处理器可见。我们很容易想象这样的场景:当某一个处理器在自己的高速缓存中更新的某个共享变量的值,但它并没有将该值更新至共享主存中,更不用说将该值更新到其他处理器的缓存中了。这种缓存间共享变量值不一致的情况被称为缓存一致性问题(cache coherency problem)。

假设处理器 A 改变了共享变量 x 的值,之后又改变了共享变量 y 的值,那么这些新值必须更新至内存中,这样其他处理器才能看到这些改变。然而,由于按地址顺序递增刷新缓存更高效,所以如果 y 的地址小于 x 的地址,那么 y 很有可能先于 x 更新至内存中。这样就导致其他处理器认为 y 值的改变是先于 x 值的。

对 DCLP 而言,这种可能性将是一个严重的问题。正确的 Singleton 初始化要求先初始化 Singleton 对象,再初始化 pInstance。如果在处理器 A 上运行的线程是按正确顺序执行,但处理器 B 上的线程却将两个步骤调换顺序,那么处理器 B 上的线程又会导致 pInstance 被赋值为未完成初始化的 Singleton 对象。

解决缓存一致性问题的一般方法是使用内存屏障(memory barriers), 例如使用栅栏 7 (fences):即在共享内存的多处理器系统中,用以限制对某些可能会对共享内存进行读写的指令进行重新排序,能被编译器、链接器,或者其他优化实体识别的指令。对 DCLP 而言,我们需要使用内存关卡以保证 pInstance 的赋值在 Singleton 初始化完成之后。下面这段伪代码与参考文献 [^8] 中的一个例子非常相似,我们只在需要加入内存关卡之处加入相应的注释,因为实际的代码是平台相关的(通常使用汇编)。


Singleton *Singleton::instance()
{
    Singleton *tmp = pInstance;
    ...
    // insert memory barrier 加入内存屏障
    if (tmp == 0)
    {
        Lock lock;
        tmp = pInstance;
        if (tmp == 0)
        {
            tmp = new Singleton;
            ...
            // insert memory barrier 加入内存屏障
            pInstance = tmp;
        }
    }
    return tmp;
}

Arch Robison 指出这种解决办法杀伤力过大了:从技术上说,我们并不需要完整的双向屏障。第一道屏障可以防止另一个线程先执行 Singleton 构造函数之后的代码,第二道屏障可以防止 pInstance 初始化的代码先于 Singleton 对象的初始化。有一组称作“请求”和“释放”操作可以比单纯用硬件支持内存关卡具有更高的效率。

但无论如何,只要你的机器支持内存屏障,这是 DCLP 一种可靠的实现方法。所有可以重新排列共享内存的写入操作指令顺序的处理器都支持各种不同的内存屏障。有趣的是,在单处理器系统中,同样的方法也适用。因为内存关卡本质上是“硬序列点”,即从硬件层面防止可能引发麻烦的指令重排序。

7 结论以及 DCLP 的替代方法

从以上讨论中我们可以得出许多经验。首先,请记住一点:基于分时的单处理机并行机制与真正跨多处理器的并行是完全不同的。这就是为什么在单处理器架构下针对某个编译器的线程安全的解决办法,在多处理器架构下就不可用了。即使你使用相同的编译器,也可能导致这个问题(这是个一般性结论,不仅仅存在于 DCLP 中)。

第二,尽管从本质上讲 DCLP 并不局限于单例模式,但以 DCLP 的方式使用单例模式往往会导致编译器去优化跟线程安全有关的语句。因此,你必须避免用 DCLP 实现 Singleton 模式。由于 DCLP 每次调用 instance() 时都需要加一个同步锁,如果你(或者你的客户)很在意加锁引起的性能问题,你可以建议你的客户将 instance() 返回的指针缓存起来,以达到最小化调用 instance() 的目的。例如,你可以建议他不要这么写代码:


Singleton::instance() -> transmogrify();
Singleton::instance() -> metamorphose();
Singleton::instance() -> transmute();
clients do things this way :

而应该将上述代码改写成:


Singleton * const instance =
Singleton::instance(); // cache instance pointer 用变量存instance()指针
instance -> transmogrify();
instance -> metamorphose();
instance -> transmute();

要实现这个想法有个有趣的办法,就是鼓励用户尽量在每个需要使用 Singleton 对象的线程开始时,只调用一次 instance(),之后该线程就可直接使用缓存在局部变量中的指针。使用该方法的代码,对每个线程都只需要承担一次 instance() 调用的代价即可。

在采用“缓存调用结果”这一建议之前,我们最好先验证一下这样是否真的能够显著地提高性能。加入一个线程库提供的锁,以确保 Singleton 初始化时的线程安全性,然后计时,看看这样的代价是否真正值得我们担心。

第三,请不要使用延迟初始化(lazily-initialized)的方式,除非你必须这么做。单例模式的经典实现方法就是基于这种方式:除非有需求,否则不进行初始化。替代方法是采用提前初始化(eager initialization)方式,即在程序运行之初就对所需资源进行初始化。因为多线程程序在运行之初通常只有一个线程,我们可以将某些对象的初始化语句写在程序只存在一个线程之时,这样就不用担心多线程所引起的初始化问题了。在很多情况下,将 Singleton 对象的初始化放在程序运行之初的单线程模式下(例如,在进入 main 函数之前初始化),是最简便最高效且线程安全的 Singleton 实现方法。

采用提前初始化的另一种方法是用单状态模式(Monostate 模式)代替单例模式。不过,Monostate 模式属于另一个话题,特别是关于构成它的状态的非局部静态对象初始化顺序的控制,是一个完全不同的问题。Effective C++ 一书中对 Monostate 的这个问题给出了介绍,很讽刺的是,关于这一问题,书中给出的方案是使用 Singleton 变量来避免(这个变量并不能保证线程安全)。

另一种可能的方法是每个线程使用一个局部 Singleton 来替代全局 Singleton,在线程内部存储 Singleton 数据。延迟初始化可以在这种方法下使用而无需考虑线程问题,但这同时也带来了新的问题:一个多线程程序中竟然有多个“单例”。

最后,DCLP 以及它在 C/C++ 语言中的问题证实了这么一个结论:想使用一种没有线程概念的语言来实现具有线程安全性的代码(或者其他形式的并发式代码)有着固有的困难。编程中对多线程的考虑很普遍,因为它们是代码生成中的核心问题。正如 Peter Buhr 的观点,指望脱离语言,只靠库函数来实现多线程简直就是痴心妄想。如果你这么做了,要么

  1. 库最终会在编译器生成代码时加入各种约束(pthreads 库正是如此)
  2. 编译器以及其它代码生成工具的优化功能将被禁用,即使针对单线程代码也不得不如此

多线程、无线程概念的编程语言、优化后的代码,这三者你只能挑选两个。例如,Java 和 .NET CLI 解决矛盾的办法是将线程概念加入其语言结构中

8 致谢

本文发表前曾邀请 Doug Lea, Kevlin Henney, Doug Schmidt, Chuck Allison, Petru Marginean, Hendrik Schober, David Brownell, Arch Robison, Bruce Leasure, and James Kanze 审阅及校稿。他们的点评建议为本文的发表做了很大的贡献,并使我们对 DCLP、多线程、指令重排序、编译器优化这些概念又有了进一步的理解。出版后,我们还加入了 Fedor Pikus, Al Stevens, Herb Sutter, and John Hicken 几人的点评建议。

9 关于作者

Scott Meyers 曾出版了三本《Effective C++》的书,并出任 Addison-Wesley 所著的《有效的软件开发系统丛书(Effective Software Developement Series)》的顾问编辑。目前他专注于研究提高软件质量的基本原则。他的主页是:Scott Meyers

Andrei Alexandrescu 是《Modern C++ Design》一书的作者,他还写过大量文章,其中大部分都是作为专栏作家为 CUJ 所写。目前他正在华盛顿大学攻读博士学位,专攻编程语言方向。他的主页是:Modern C++ Design(已不可访问)。



注:
  1. 单例模式是指某一个类只有一个独一无二的实例化对象。 

  2. DCLP 即在锁定之前检查一次,在锁定后检查一次,这两次检查是完全相同的。 

  3. 指程序运行到某个特别的时间点,在这个时间点之前的所有副作用(side effect,指这个语句进行的实际操作)已经结束,并且后续的副作用还没发生。  2

  4. volatile 限定(volatile-qualifying):volatile 是 C/C++ 中的关键字,与 const 类似,都是对变量进行附加修饰,旨在告之编译器,该对象的值可能在编译器未监测到的情况下被改变,编译器不能武断的对引用这些对象的代码作优化处理。  2

  5. 奥德修斯:《奥德赛》是古希腊最重要的两部史诗之一(两部史诗统称为《荷马史诗》,另一部是《伊利亚特》),奥德修斯是该作品中主人公的名字。作品讲述了主人公奥德修斯 10 年海上历险的故事。途中,他们经过一个妖鸟岛,岛上的女巫能用自己的歌声诱惑所有过路船只的船员,使他们的船触礁沉没。智勇双全的奥德修斯抵御了女巫的歌声诱惑,带领他的船员们顺利渡过难关。本文的作者借用《奥德赛》里的这个故事告诉大家不要被 C/C++ 的标准所迷惑 :D。 

  6. C/C++11 分别加入了 threads.h 线程库和 std::thread 模板,用于作为强平台关联的 pthreads 的替代,不过 GCC 对于 thread.h 的支持很消极,MSVC 在支持 thread.h 后又取消了支持。 

  7. 内存屏障是基于 CPU 特定平台的一系列技术,用于保障不同核心的高速缓存中的数据能够及时的同步获得安全正确的访问。 


若无特殊声明,本文以 CC BY-SA 3.0 许可协议 提供。