2011年12月28日
第9卷，第12期

关于共享变量或内存模型，你其实一窍不通

数据竞争是罪恶的。

Hans-J. Boehm，惠普实验室；Sarita V. Adve，伊利诺伊大学厄巴纳-香槟分校

在 Google 上搜索“线程是罪恶的”会产生 18,000 个结果，但线程——无论是否罪恶——都无处不在。现代 Windows PC 上运行的几乎所有进程都使用它们。软件线程通常是程序员让多核机器协同工作以更快地解决问题的方式。而且，它们通常也是让用户界面在应用程序执行后台计算时保持响应的原因。

线程是同时运行但共享变量的多个程序。通常，每个线程都可以访问应用程序的所有内存。共享变量是线程的核心优势，还是其罪恶的根源，取决于你的视角。它们允许线程轻松快速地通信，但也使线程有可能互相妨碍。

尽管共享变量是大多数程序的核心，但即使是专家也常常对使用它们的规则感到困惑。考虑以下简单示例。

递增计数器

要实现一个函数incr来递增一个计数器x，你的第一次尝试可能是

void incr() { x++; }

许多人会立即反对，认为当多个线程调用此函数时，不能保证产生正确的结果。语句x++等价于x=x+1，这相当于三个步骤：（1）获取 x 的值；（2）加一；（3）将结果写回 x。在不太可能的情况下，如果两个线程巧合地以锁步方式执行这些操作，它们都将读取相同的值，都对其加一，然后都写入相同的值，从而仅将 x 递增一而不是二。调用incr()的行为不是原子的；用户可以观察到它是由不同的步骤组成的。（原子性对不同的社区意味着不同的事物；我们的用法被数据库人员称为隔离。）

我们可以通过使用互斥锁来解决这个问题，互斥锁一次只能由一个线程锁定

void incr() { mtx.lock(); x++; mtx.unlock(); }

在 Java 中，这可能看起来像

void incr() { synchronized(mtx) { x++; } }

或者可能只是

synchronized void incr() { x++; }

这些方法都可以正确工作，但是互斥锁调用可能很慢，因此结果的运行速度可能比预期的慢。

如果我们只关心获得近似计数呢？如果我们只是不使用互斥锁，并接受一些不准确性呢？会发生什么不好的事情？

首先，我们观察到，在没有互斥锁的情况下，两个线程中递增此类计数器的某些实际代码通常会遗漏大约一半的计数，这可能是处理器缓存之间通信导致的不幸时序的结果。情况可能会更糟。一个线程可能只调用incr()一次，在开始时从 x 加载值零，长时间挂起，然后在程序终止之前写回一。这将导致最终计数为一，无论其他线程做什么。

这些情况不太令人惊讶，也更容易解释。最终计数也可能过高。考虑计数大于机器字的情况。为了避免处理二进制数，假设我们有一台十进制机器，其中每个字保存三位数字，计数器 x 可以保存六位数字。编译器将 x++ 转换为类似

tmp_hi = x_hi; tmp_lo = x_lo; (tmp_hi, tmp_lo)++; x_hi = tmp_hi; x_lo = tmp_lo;

其中tmp_lo和tmp_hi是机器寄存器，中间的递增操作实际上会涉及多个机器指令。现在假设 x 是 999（即，x_hi = 0，和x_lo = 999），以及两个线程，一个蓝色和一个红色线程，每个线程按如下方式递增 x（请记住，每个线程都有其自己的机器寄存器副本tmp_hi和tmp_lo):

tmp_hi = x_hi; tmp_lo = x_lo; (tmp_hi, tmp_lo)++; //tmp_hi = 1, tmp_lo = 0 x_hi = tmp_hi; //x_hi = 1, x_lo = 999, x = 1999 x++; //红色运行所有步骤 //x_hi = 2, x_lo = 0, x = 2000 x_lo = tmp_lo; //x_hi = 2, x_lo = 0

首先蓝色线程几乎运行完成；然后红色线程一次性运行完成；最后蓝色线程运行其最后一步。结果是我们将 999 递增两次得到 2000。这很难向不精确理解代码如何编译的程序员解释。

根本问题在于，多个线程同时访问 x，而没有适当的锁定或其他同步来确保一个线程在另一个线程之后发生。这种情况称为数据竞争——这真的是罪恶的！稍后我们将回到如何在没有锁的情况下避免数据竞争。

另一个竞争示例

我们才刚刚开始看到数据竞争引起的问题。这是一个在实际代码中经常尝试的示例。一个线程初始化一块数据（比如，x）并在完成后设置一个标志（称为done）。任何稍后读取 x 的线程都首先等待done标志，如图 1 所示。可能会出现什么问题？

这段代码可能在“笨拙”的编译器上可靠地工作，但任何“聪明”的优化编译器都可能破坏它。当编译器看到循环时，它可能会观察到done在循环中未被修改（即，它是“循环不变的”）。因此，它可以假设done在循环中不会更改。

当然，这个假设对于我们的示例实际上并不正确，但编译器仍然可以做出这个假设，原因有两个：（1）编译器传统上被设计为编译顺序代码，而不是多线程代码；（2）因为，正如我们将看到的，即使是现代多线程语言也继续允许这样做，这是有充分理由的。

因此，循环很可能被转换为

tmp = done; while (!tmp) {}

甚至可能

tmp = done; if (!tmp) while (true) {}

在任何一种情况下，如果done在红色线程启动时尚未设置，则红色线程保证进入无限循环。

假设我们有一个“笨拙”的编译器，它不执行这种转换，并且完全按照编写的方式编译代码。根据硬件的不同，这段代码仍然可能失败。

这次的问题是硬件可能会优化蓝色线程。几乎所有处理器架构都允许将对内存的存储保存在仅对该处理器核心可见的缓冲区中，然后再将它们写入对其他处理器核心可见的内存。² 某些处理器，例如你智能手机中可能使用的 ARM 芯片，允许存储以不同的顺序对其他处理器核心可见。在这种处理器上，蓝色线程对done的写入可能在红色线程（在另一个核心上运行）之前对蓝色线程的写入可见。因此，红色线程可能会看到done设置为true，并且循环可能会在它检索到 x 的正确值之前终止。因此，当红色线程访问 x 时，它可能仍然得到未初始化的值。

与在循环外读取done一次的原始问题不同，这个问题将不经常发生，并且很可能在测试期间被忽略。

这里再次核心问题是，尽管done标志旨在防止同时访问 x，但它本身可以被两个线程同时访问。而数据竞争是罪恶的！

位和字节

到目前为止，我们只讨论了两个线程同时访问完全相同的变量或对象字段的数据竞争。但这并非一直是唯一关注的问题。根据一些较旧的标准，当你声明两个小字段b1和b2彼此相邻时，例如，那么更新 b1 可以使用以下步骤实现

1. 将包含b1和b2的机器字加载到机器寄存器中。

2. 更新机器寄存器中的b1部分。

3. 将寄存器存储回从中加载的位置。

不幸的是，如果另一个线程在最后一步之前更新 b2，那么该更新将被最后一步覆盖并有效地丢失。如果两个字段最初都为零，并且一个线程执行b1 = 1，而另一个线程执行b2 = 1, b2仍然可能为零，当它们都完成时。尽管原始程序行为良好且没有数据竞争，但编译器添加了一个对b2的隐式更新，从而创建了数据竞争。

长期以来，Java 已经明确禁止了这种数据竞争插入。最近发布的 C++11 和 C11 标准都禁止了它。我们不知道任何存在此类问题的 Java 实现，现代 C 和 C++ 编译器通常也不会精确地表现出这个问题。不幸的是，许多编译器在某些晦涩、不太可能和不可预测的条件下确实会引入数据竞争。随着 C++11 和 C11 得到广泛支持，这个问题将消失。

对于 C 和 C++，位字段的故事稍微复杂一些。稍后我们将对此进行更多讨论。

真正的规则是...

关于线程最简单的观点，也是我们开始时的观点，是多线程程序是通过交错每个线程的步骤来执行的。逻辑上，计算机执行来自一个线程的步骤，然后选择另一个线程，或可能是同一个线程，执行其下一步，依此类推。这是一个顺序一致性执行。

正如已经展示的那样，实际的机器和编译器有时会导致非顺序一致性执行：例如，当对变量和done标志的赋值以无序的方式对其他线程可见时。然而，顺序一致性对于理解真实共享变量的行为至关重要，原因有二

• 基本上所有现代语言（Java、C++11、C11）实际上都承诺对于没有数据竞争的程序具有顺序一致性。这种保证通常会被一些低级语言特性所违反——特别是 Java 的lazySet()和 C++11 和 C11 的显式memory_order... 规范，这些规范很容易避免（OpenMP 的 atomic 指令可能除外），我们在这里主要忽略这些规范。大多数程序员也会希望忽略这些特性。

• 到目前为止，我们对于什么构成数据竞争有点不精确。由于这现在已成为我们编程规则的关键部分，我们可以使其更加精确，如下所示：如果两个内存操作访问相同的内存位置，并且至少一个访问是写操作，则它们冲突。对于我们的目的，内存位置是一个可以单独更新的内存单元。通常，每个标量（非结构化）变量或字段都占用其自己的内存位置；每个都可以独立更新。然而，连续的 C 或 C++ 位字段通常共享一个位置；更新一个可能会干扰其他字段。

如果两个冲突的数据操作来自不同的线程并且可以“同时”执行，则它们形成数据竞争。但这在什么时候可能发生？显然，这取决于共享变量的行为方式，而我们正试图定义这种行为方式。

我们通过仅考虑顺序一致性执行来打破这种循环性，在数据竞争的定义中：如果顺序一致性执行中的两个冲突操作同时执行，如果一个操作在该执行的交错中紧随另一个操作之后执行。现在我们可以说，如果其顺序一致性执行中没有数据竞争，则程序是无数据竞争的。

这里我们已经根据数据操作明确定义了数据竞争，以排除同步操作，例如锁定和解锁互斥锁。如果对同一互斥锁的两个操作在交错中彼此相邻出现，则不会引入数据竞争。实际上，如果不允许并发访问互斥锁，它们就无法有效地控制同时数据访问。

因此，基本的编程模型是

• 编写代码，使数据竞争不可能发生，假设实现遵循顺序一致性规则。

• 然后，实现保证此类代码的顺序一致性（假设避免了先前提到的低级特性）。

这与承诺所有程序的完全顺序一致性非常不同；我们之前的示例不能保证按预期工作，因为它们都存在数据竞争。尽管如此，在编写程序时，无需显式考虑编译器或硬件内存重排序；只要我们遵守规则并避免数据竞争，我们仍然可以完全根据顺序一致性进行推理。

这有一些常常令程序员惊讶的后果。考虑图 2 中的程序，其中 x 和 y 最初为 false。当推理这是否具有数据竞争时，我们观察到没有顺序一致性执行（即，没有线程步骤的交错）执行任何赋值。因此，没有成对的冲突操作，因此当然没有数据竞争。

在更高的级别上工作

到目前为止，我们的编程模型仍然让我们在内存访问或指令级别考虑交错线程执行。数据竞争是根据对内存位置的访问定义的，顺序一致性是根据交错不可分割的步骤（实际上是机器指令）定义的。这是一个全新的复杂情况。编写顺序代码的程序员不需要了解机器指令的粒度以及内存是以字节还是一次一个字访问。

幸运的是，一旦我们坚持无数据竞争的程序，这个问题就消失了。我们的模型的一个非常有用的副作用是，线程的无同步区域看起来是不可分割的或原子的。因此，尽管我们的模型是根据内存位置和单个步骤定义的，但实际上没有办法在不引入数据竞争的情况下判断这些步骤和内存位置是什么。

更一般地，无数据竞争的程序的行为始终好像它们仅在同步操作（例如互斥锁锁定/解锁操作）处交错。如果不是这种情况，则来自不同线程的无同步代码段将如图 3 和图 4 所示交错。

在第一种情况（图 3）中，没有此类交错代码段包含冲突操作，并且每个段有效地在其自己的单独的内存位置集上运行。指令交错完全等同于这样一种情况，即这些代码段如图所示一个接一个地执行，唯一的可见交错在同步操作处（未显示）。

在第二种情况（图 4）中，两个代码段包含对同一内存位置的冲突操作。在这种情况下，存在一种替代的交错，其中冲突操作彼此相邻出现，并且有效地显示了数据竞争，如图所示。因此，这对于无数据竞争的程序来说不会发生。

这意味着，对于无数据竞争的程序，任何不包含同步操作的代码段的行为都好像它是原子地（即，一次性地）执行的，而不受其他线程的影响，并且没有其他线程能够看到在该代码段中间发生的任何变量值。因此，坚持无数据竞争的程序有一些令人愉快的结果

• 我们不再关心内存是以字节还是一次一个字更新。正确编写的代码无法分辨，就像顺序代码一样。

• 不使用内部同步的库调用表现得好像它们在单个步骤中执行。中间状态不能被另一个线程看到。因此，此类库可以继续仅指定调用的总体效果，而不是变量可能采用哪些中间值。当然，这就是我们一直以来所做的事情，但只有在无数据竞争的情况下才真正有意义。

• 关于多线程程序的推理仍然很困难，但如果没有数据竞争，它并不像人们经常声称的那么困难。特别是，我们不必关心交错线程指令的所有可能方式。最多，我们关心无同步区域的交错。

当然，所有这些属性都要求程序是无数据竞争的。如今，检测和避免数据竞争错误远非易事。稍后我们将讨论在使其更容易方面取得的最新进展。

特别是，为了确保无数据竞争，足以确保同时运行的无同步代码段不会同时写入或读取和写入相同的变量。因此，我们可以剪枝大量为此目的需要探索的指令级交错。

库可以（并且通常是）被设计为清晰地划分库和客户端代码之间避免数据竞争的责任。在客户端代码中，我们在逻辑对象的级别上推理数据竞争，而不是内存位置。当决定同时调用两个库例程是否安全时，我们只需要确保它们不都访问同一个对象，或者如果它们这样做，则没有一个访问修改对象。库有责任确保对逻辑上不同的对象的访问不会由于对某些内部隐藏内存位置的不受保护的访问而引入数据竞争。同样，库也有责任确保读取对象不会引入对对象的内部写入，从而可能创建数据竞争。

使用无数据竞争的方法，库实现的容器数据类型可以像内置整数或指针一样工作；程序员无需关心内部发生的事情。只要两个不同的线程不同时访问同一个容器，或者它们都是读取访问，实现就保持隐藏。

再次强调，虽然所有这些属性都简化了对并行代码的推理，但它们假设库编写者和客户端负责遵守规定的规范。

但是如果锁太慢怎么办？

避免数据竞争的最常见方法是使用互斥锁来确保访问同一代码段的代码段之间的互斥。在某些情况下，其他同步机制（例如 OpenMP 的屏障）更合适。然而，经验表明，在少数情况下，这些机制是不够的。互斥锁在信号或中断处理程序中效果不佳，并且通常涉及大量开销，即使它们在最近的处理器上开始变得更快。

不幸的是，许多环境（例如 Posix 线程）没有提供任何真正的替代方案——所以人们作弊。Pthreads 代码通常包含数据竞争，通常声称这些竞争是“良性的”。其中一些是彻头彻尾的错误，因为代码在当前编译的情况下，很可能会以小概率失败。其余的通常有被编译器“错误编译”的风险，这些编译器要么直接假设没有数据竞争⁴，因此被错误的假设误导，要么只是产生一些先前讨论过的令人惊讶的效果。

为了摆脱这种困境，大多数现代编程语言都提供了一种声明同步变量的方法。这些变量的行为类似于普通变量，但是由于对它们的访问被认为是同步操作，而不是数据操作，因此可以从多个线程安全地访问同步变量，而不会创建数据竞争。在 Java 中，volatile int 是一个可以从多个线程并发访问的整数。在 C++11 中，你可以改为编写 atomic<int>（volatile 在 C 或 C++ 中意味着微妙的不同）。

编译器对同步变量进行特殊处理，因此我们的基本编程模型得以保留。如果没有数据竞争，线程仍然表现得好像它们以交错的方式执行。然而，访问同步变量是一种同步操作；跨越此类访问的代码序列不再显得不可分割。

同步变量有时是用于非常简单的共享数据的正确工具，例如图 1 中的done标志。这里唯一的数据竞争是在done标志上，因此只需将其声明为同步变量即可解决问题。

但是，请记住，同步变量很难用于复杂的数据结构，因为没有简单的方法可以在一个原子操作中对数据结构进行多次更新。同步变量不能替代互斥锁。

在如图 1 所示的情况下，同步变量通常避免了大部分锁定开销。由于它们仍然太昂贵，因此 C++11 和 Java 都提供了一些显式的专家专用机制，允许你放宽基于交错的模型，如前所述。与使用数据竞争进行编程不同，可以使用这些机制编写正确的代码，但我们的经验是，很少有人真正做到这一点。我们希望未来的硬件将减少对它的需求——并且硬件已经在这方面做得越来越好。

真正的语言

大多数真正的语言都符合我们的基本模型。C++11 和 C11 完全提供了这个模型。数据竞争具有“未定义行为”；它们是错误，与越界数组访问的意义相同。这通常被称为数据竞争的自燃语义（尽管我们不知道任何机器因数据竞争而实际着火的案例）。

尽管自燃语义有时仍然存在争议，但它们绝不是什么新鲜事物。Ada 83 和 1995 Posix 线程规范不太精确，但基本上采取了相同的立场。

C++11 和 C11 分别提供同步变量作为 atomic<t> 和 _Atomic(t)。除了读取和写入这些变量之外，它们还支持一些简单的不可分割的复合操作；例如，使用“++”运算符递增同步（原子）变量是一个不可分割的操作。

托管语言的情况更为复杂，主要是因为它们添加了安全要求以支持不受信任的代码。Java 完全支持我们的编程模型，但它也尝试为具有数据竞争的程序提供一些保证，但收效甚微。尽管数据竞争并非正式错误，但现在很清楚，我们无法精确定义具有数据竞争的程序实际上意味着什么。⁸ 数据竞争仍然是罪恶的。

迈向没有邪恶的未来？

我们已经讨论了数据竞争的缺失如何导致通用语言支持的简单编程模型。似乎根本没有其他合理的替代方案。¹ 不幸的是，仍然存在一个棘手的问题：保证无数据竞争仍然很困难。大型程序几乎总是包含错误，并且这些错误通常是数据竞争。当今流行的语言没有为这些程序提供任何可用的语义，从而使调试变得困难。

展望未来，我们势在必行地开发自动化技术来检测或消除数据竞争。事实上，在几个方面最近取得了重大进展：数据竞争的动态精确检测；^5,6 硬件支持在数据竞争时引发异常；⁷ 和基于语言的注释，通过设计从程序中消除数据竞争。³ 这些技术保证所考虑的执行或程序没有数据竞争（允许使用简单模型），但它们仍然需要更多的研究才能在商业上可行。检测数据竞争的商业产品已经开始出现（例如，Intel Inspector），尽管它们不能保证无数据竞争，但它们朝着正确的方向迈出了重要一步。我们乐观地认为，在不久的将来，我们将以某种方式（我们必须！）征服邪恶（数据竞争）。

参考文献

有关更完整的背景参考文献集，请参阅参考文献 1。

1. Adve, S. V., Boehm, H.-J. 2010. 内存模型：重新思考并行语言和硬件的理由。《通讯》53(8): 90–101。

2. Adve, S. V., Gharachorloo, K. 1996. 共享内存一致性模型：教程。《IEEE 计算机》29(12): 66–76。

3. Bocchino et al, R. 2009. 用于确定性并行 Java 的类型和效果系统。载于面向对象编程、系统、语言和应用程序国际会议论文集。

4. Boehm, H.-J. 2011. 如何错误编译具有“良性”数据竞争的程序。载于HotPar（并行性热点主题）。

5. Elmas, T., Qadeer, S., Tasiran, S. 2007. Goldilocks：一种竞争和事务感知的 Java 运行时。载于2007 年编程语言设计与实现会议论文集：245–255。

6. Flanagan, C., Freund, S. 2009. FastTrack：高效且精确的动态竞争检测。载于编程语言设计与实现会议论文集。

7. Lucia, B., Ceze, L., Strauss, K., Qadeer, S., Boehm, H.-J. 2010. 冲突异常：通过精确的硬件异常提供简单的并发语言语义。载于计算机体系结构国际研讨会论文集。

8. Sevcik, J., Aspinall, D. 2008. 关于 Java 内存模型中程序转换的有效性。载于欧洲面向对象编程会议论文集：27–51。

喜欢它，讨厌它？请告诉我们

[email protected]

HANS-J. BOEHM 是惠普实验室的研究经理。他可能最出名的是常用垃圾回收库的主要作者。在该项目中使用线程的经验最终促使他发起努力，以在 C++11 中正确定义线程和共享变量。他是杰出科学家。他被授予 PLDI 2003 最具影响力论文奖和 SIGPLAN 2006 杰出服务奖。他拥有华盛顿大学的理学学士学位以及康奈尔大学的理学硕士和博士学位。

SARITA V. ADVE 是伊利诺伊大学厄巴纳-香槟分校计算机科学系的教授。她的研究兴趣在于计算机体系结构和系统、并行计算以及功耗和可靠性感知系统。在她所做的贡献中，她共同开发了 C++ 和 Java 编程语言的内存模型，这基于她早期关于无数据竞争模型的工作。Adve 是会士。她获得了威斯康星大学麦迪逊分校的计算机科学博士和硕士学位，以及印度理工学院的电气工程学士学位。

最初发表于 Queue 第 9 卷，第 12 期—
在数字图书馆中评论本文