真实世界的并发 -

2008年10月24日
第6卷，第5期

真实世界的并发

您可能实际上不需要编写多线程代码。但是如果您这样做，一些关键原则将帮助您掌握这门“黑魔法”。

Bryan Cantrill 和 Jeff Bonwick，Sun Microsystems

如果最近的微处理器发展让今天的软件从业人员对软件的未来感到些许忧虑，那也是可以理解的。虽然摩尔定律仍然成立（即晶体管密度大约每18个月翻一番），但由于难以克服的物理限制和实际的工程考量，这种不断增长的密度不再用于提高时钟频率。相反，它被用来在单个CPU芯片上放置多个CPU核心。从软件的角度来看，这并不是一场革命性的转变，而是一场渐进式的演变：多核CPU不是新范式的诞生，而是旧范式（多处理）向更广泛部署的演进。然而，从最近许多关于这个主题的文章和论文来看，人们可能会认为这种并发性的蓬勃发展是世界末日，“免费午餐已经结束了。”¹

作为长期处于并发系统第一线的从业者，我们希望为这场常常陷入歇斯底里的讨论注入一些冷静的现实（如果不是一些来之不易的智慧）。具体来说，我们希望回答一个基本问题：并发性的普及对您开发的软件意味着什么？或许令人遗憾的是，这个问题的答案既不简单也不通用——您的软件与并发性的关系取决于它在物理上执行的位置、它在抽象堆栈中的位置以及围绕它的商业模式。

鉴于许多软件项目现在都在抽象堆栈的不同层和架构的不同层中拥有组件，您可能会发现，即使对于您编写的软件，您也没有一个答案，而是有几个答案：您可能能够让您的一些代码永远在顺序的幸福中执行，而另一些代码可能需要高度并行和显式多线程。更复杂的是，我们将论证，您的许多代码不会完全属于任何一个类别：它本质上是顺序的，但需要在某种程度上意识到并发性。

尽管我们断言，与某些人可能担心的相比，需要并行的代码更少——少得多——但编写并行代码仍然有点像黑魔法，这是事实。因此，我们也给出了开发高度并行系统的具体实现技术。因此，本文有些二分法：我们试图论证大多数代码可以在没有显式并行性的情况下实现并发性，同时阐明那些必须编写显式并行代码的人的技术。本文一半是对禁欲优点的严厉讲座，一半是爱经。

一些历史背景

在我们讨论当今应用程序的并发性之前，探讨并发执行的历史将有所帮助。甚至在20世纪60年代——计算机时代的早晨还湿漉漉的时候——人们越来越清楚地认识到，执行单个指令流的单个中央处理器将导致系统性能受到不必要的限制。虽然计算机设计师尝试了不同的想法来规避这种限制，但正是1961年推出的Burroughs B5000提出了最终被证明是前进方向的想法：不相交的CPU并发地执行不同的指令流，但共享一个公共内存。在这方面（和许多方面一样），B5000至少超前了十年。直到20世纪80年代，多处理的需求才被更广泛的研究人员所认识，他们在十年间探索了缓存一致性协议（例如，Xerox Dragon和DEC Firefly），原型化了并行操作系统（例如，在AT&T 3B20A上运行的多处理器Unix），并开发了并行数据库（例如，威斯康星大学的Gamma）。

在20世纪90年代，20世纪80年代研究人员播下的种子结出了实际系统的果实，许多计算机公司（例如，Sun、SGI、Sequent、Pyramid）在对称多处理上押下了重注。这些对并发硬件的押注必然需要在并发软件上进行相应的押注——如果操作系统不能并行执行，那么系统中的许多其他部分也不能——这些公司独立地意识到，他们的操作系统需要围绕并发执行的概念进行重写。这些重写发生在20世纪90年代早期，由此产生的系统在十年间得到了完善；今天，在开源操作系统（如OpenSolaris、FreeBSD和Linux）中可以看到许多由此产生的技术。

正如几家计算机公司围绕多处理进行了重大押注一样，几家数据库供应商围绕高度并行的关系数据库进行了押注；包括Oracle、Teradata、Tandem、Sybase和Informix在内的新兴公司需要利用并发性来获得相对于当时主导事务处理的大型机的性能优势。² 与操作系统一样，这项工作构思于20世纪80年代末和90年代初，并在十年间逐步改进。

这些趋势的结果是，到20世纪90年代末，并发系统已经取代了它们的单处理器前辈，成为高性能计算机：当1993年首次绘制TOP500超级计算机榜单时，世界上性能最高的单处理器仅排名第34位，而前500名中超过80%是各种类型的多处理器。到1997年，单处理器完全从榜单上消失了。在超级计算世界之外，许多面向事务的应用程序随着CPU的扩展而扩展，允许用户实现无需重新审视架构即可扩展系统的梦想。

20世纪90年代并发系统的兴起与另一个趋势同时发生：虽然CPU时钟频率持续提高，但主内存的速度却没有跟上。为了应对相对较慢的内存，微处理器架构师采用了更深（也更复杂）的流水线、缓存和预测单元。即便如此，时钟频率本身也很快变得有些虚假：虽然CPU可能能够以广告宣传的速率执行，但只有一小部分代码能够真正实现（更不用说超过）每个指令一个周期的速率——大多数代码都深陷于每个指令花费三、四、五（甚至更多）个周期。

许多人看到了这两个趋势——并发性的兴起和提高时钟频率的徒劳——并得出了逻辑结论：与其在“更快”的CPU上花费晶体管预算，而这些CPU实际上并没有在性能方面产生太多收益（并且在功耗、散热和面积方面具有可怕的成本），为什么不利用并发软件的兴起，使用晶体管来实现每个芯片多个（更简单）的核心呢？

并发软件的成功促成了芯片多处理的起源，这是一个非常重要的历史观点，值得再次强调。有一种看法认为，微处理器架构师——出于恶意、懦弱或绝望——将并发性强加于软件。³ 实际上，情况恰恰相反：正是并发软件的成熟促使架构师考虑芯片上的并发性。（读者可以参考最早的芯片多处理器之一——DEC的Piranha——以详细讨论这种动机。⁴）如果软件没有准备好，这些微处理器今天就不会在商业上可行。如果有什么不同的话，一些人声称已经结束的“免费午餐”实际上终于要上桌了。人们只需要饥饿并知道如何吃！

并发是为了性能

从这段历史探索中得出的最重要结论是，并发性一直以来都被用于一个目的：提高系统的性能。这似乎太明显了，以至于无需明确说明——如果不是为了提高性能，我们为什么还要并发？——然而，尽管它如此明显，但并发性的raison d’être却越来越被遗忘，就好像并发硬件的普及已经唤醒了一种焦虑，即所有软件都必须使用所有可用的物理资源。正如没有程序员感到有道德义务消除超标量微处理器上的流水线停顿一样，软件工程师也不应仅仅因为硬件支持并发性就感到有责任使用并发性。相反，应该考虑和使用并发性的原因只有一个：因为它需要产生一个性能可接受的系统。

并发执行可以通过三种基本方式提高性能：它可以减少延迟（即，使一个工作单元执行得更快）；它可以隐藏延迟（即，允许系统在长时间延迟操作期间继续工作）；或者它可以提高吞吐量（即，使系统能够执行更多的工作）。

使用并发性来减少延迟是高度特定于问题的，因为它需要手头任务的并行算法。对于某些类型的问题——尤其是科学计算中发现的那些问题——这很简单：可以先验地划分工作，并将多个计算元素设置为任务。然而，许多这些问题通常如此可并行化，以至于它们不需要共享内存的紧密耦合——并且它们通常能够在小型机器的网格上更经济地执行，而不是在少量高度并发的机器上执行。此外，使用并发性来减少延迟要求一个工作单元在其执行中足够长，以摊销协调多个计算元素的巨大成本：人们可以设想使用并发性来并行化排序4000万个元素——但仅仅排序40个元素不太可能花费足够的计算时间来支付并行性的开销。简而言之，使用并发性来减少延迟的程度更多地取决于问题，而不是努力解决问题的人——并且许多重要的问题根本不适合这样做。

对于无法并行化的长时间运行的操作，并发执行可以改为在操作挂起时执行有用的工作；在这种模型中，操作的延迟不会减少，但会被系统的进展所隐藏。当操作本身可能阻塞程序外部的实体时——例如，磁盘I/O操作或DNS查找——使用并发性来隐藏延迟尤其具有吸引力。尽管这可能很诱人，但在仅仅为了提高响应速度而考虑使用并发性时，必须非常小心：拥有一个并行程序可能会成为一个巨大的复杂性负担。此外，并发执行并不是隐藏系统引起的延迟的唯一方法：人们通常可以通过在顺序程序中使用非阻塞操作（例如，异步I/O）和事件循环（例如，Unix中发现的poll()/select()调用）来实现相同的效果。因此，希望隐藏延迟的程序员应将并发执行视为一种选择，而不是理所当然的结论。

当问题抵制并行化或没有明显的延迟需要隐藏时，并发执行可以提高性能的第三种方式是提高系统的吞吐量。与其使用并行逻辑来使单个操作更快，不如使用顺序逻辑的多个并发执行来容纳更多同时进行的工作。重要的是，使用并发性来提高吞吐量的系统不必完全（甚至主要）由多线程代码组成。相反，系统中不共享状态的那些组件可以完全保持顺序，系统并发执行这些组件的多个实例。然后，系统中的共享可以卸载到显式围绕共享状态上的并行执行设计的组件，理想情况下，这些组件可以减少到那些已知在并发环境中运行良好的元素：数据库和/或操作系统。

为了使这一点具体化，在典型的MVC（模型-视图-控制器）应用程序中，视图（通常在JavaScript、PHP或Flash等环境中实现）和控制器（通常在J2EE或Ruby on Rails等环境中实现）可以完全由顺序逻辑组成，并且仍然可以实现高水平的并发性，前提是模型（通常以数据库的形式实现）允许并行性。鉴于大多数人不会编写自己的数据库（并且实际上没有人编写自己的操作系统），因此可以构建（并且确实，许多人已经构建了）高度并发、高度可扩展的MVC系统，而无需显式创建单个线程或获取单个锁；它是通过架构而不是通过实现来实现并发性。

阐明黑魔法

如果您是开发操作系统或数据库或某些其他必须显式并行化的代码的人员，该怎么办？如果您认为自己是少数需要编写此类代码的人之一，那么您大概不需要被警告编写多线程代码很难。事实上，这个领域因其难度而闻名，以至于有些人（错误地）得出结论，认为编写多线程代码根本不可能：“没有人知道如何组织和维护依赖锁的大型系统，”最近一篇（且典型的）论断写道。⁵ 编写可扩展且正确的多线程代码的部分困难在于经验丰富的从业人员的书面智慧的稀缺性：口头传统代替正式写作使该领域笼罩在神秘之中。因此，为了使这个领域对我们的同行从业人员来说不那么神秘（如果不是也为了证明我们中的一些人实际上确实知道如何组织和维护大型基于锁的系统），我们展示了我们编写多线程代码的集体技巧。

区分冷路径和热路径。 如果要向那些必须开发并行系统的人员提供一条建议，那就是了解您希望能够并行执行的代码路径（热路径）与可以顺序执行而不影响性能的代码路径（冷路径）。根据我们的经验，我们编写的许多软件在并发执行方面都是冰冷的：它仅在初始化、管理路径、卸载等情况下执行。不仅使这些冷路径以高度并行的方式执行是浪费时间，而且也是危险的：这些路径通常是最难并行化且最容易出错的路径之一。

在冷路径中，尽可能保持粗粒度的锁定。不要犹豫，使用一个锁来覆盖子系统中广泛的罕见活动。相反，在热路径中——那些必须并发执行以提供最高吞吐量的路径——您必须更加小心：锁定策略必须简单且细粒度，并且您必须小心避免可能成为瓶颈的活动。如果您不知道给定的代码体是否将成为系统中的热路径怎么办？在没有数据的情况下，请站在假设您的代码位于冷路径的一侧，并采用相应的粗粒度锁定策略——但要准备好被数据证明是错误的。

直觉经常是错误的——要以数据为中心。 根据我们的经验，许多可扩展性问题可以归因于开发工程师最初认为（或希望）是冷路径的热路径。当从零开始创建新软件时，您需要一些直觉来推理热路径和冷路径——但是一旦您的软件功能正常，即使是原型形式，直觉的时间也结束了：您的直觉必须服从数据。在并发系统上收集数据本身就是一个难题。它首先要求您拥有一台执行中足够并发的机器，以便能够突出显示可扩展性问题。一旦您拥有了物理资源，它就要求您在系统上施加类似于您期望在系统部署到生产环境时看到的负载。一旦机器加载完毕，您必须拥有基础设施，以便能够动态地检测系统以找到任何可扩展性问题的根源。

这些问题中的第一个问题在历史上一直很严重：曾经有一段时间，多处理器非常稀有，以至于许多软件开发商店根本无法访问多处理器。幸运的是，随着多核CPU的兴起，这不再是一个问题：不再有任何借口找不到至少一台双处理器（双核）机器，并且只需稍作努力，大多数人将能够（截至撰写本文时）在八处理器（双插槽，四核）机器上运行他们的代码。

然而，即使物理情况有所改善，这些问题中的第二个问题——知道如何在系统上施加负载——也变得更糟：生产部署变得越来越复杂，负载难以且昂贵地在开发中模拟。您必须尽可能地将负载生成和模拟视为首要问题；您越早解决开发中的这个问题，您就越早能够获得可能对您的软件产生巨大影响的关键数据。尽管测试负载应尽可能模仿其生产环境中的等效负载，但及时性比绝对准确性更重要：缺少完美的负载模拟不应阻止您完全模拟负载，因为将多线程系统置于错误的负载类型下也比不施加任何负载要好得多。

一旦系统被加载——无论是在开发中还是在生产中——如果无法理解其可扩展性的障碍，那么对软件开发来说是毫无用处的。理解生产系统上的可扩展性抑制因素需要能够安全地动态检测其同步原语。在开发Solaris时，我们对此的需求在历史上非常迫切，以至于导致我们中的一位（Bonwick）在1997年开发了一种技术（lockstat）来做到这一点。这个工具立即变得至关重要——我们很快开始怀疑没有它我们是如何解决可扩展性问题的——并且它导致我们中的另一位（Cantrill）将动态检测进一步推广到DTrace，这是一个用于几乎任意动态检测生产系统的系统，该系统于2004年在Solaris中首次发布，此后已移植到包括FreeBSD和Mac OS在内的许多其他系统。⁶ （lockstat中的检测方法已重新实现为DTrace提供程序，并且该工具本身已重新实现为DTrace使用者。）

今天，动态检测继续为我们提供所需的数据，不仅可以找到系统中抑制可扩展性的部分，还可以收集足够的数据来了解哪些技术最适合减少这种争用。原型化新的锁定策略是昂贵的，而且人们的直觉经常是错误的；在分解锁或重新架构子系统以使其更并行之前，我们始终努力掌握数据，表明子系统缺乏并行性是系统可扩展性的明显抑制因素！

知道何时——以及何时不——分解锁。 全局锁自然会成为可扩展性抑制因素，当收集到的数据表明存在单个热锁时，人们很自然地会想要将锁分解为每个CPU的锁、锁的哈希表、每个结构的锁等。这最终可能是正确的行动方案，但在盲目地沿着这条（复杂的）路径前进之前，请仔细检查在锁下完成的工作：分解锁不是减少争用的唯一方法，并且可以通过减少锁的持有时间来更容易地（并且通常是）减少争用。这可以通过算法改进来完成（许多可扩展性改进是通过将锁下的执行时间从二次时间减少到线性时间来实现的！），或者通过找到不必要地受锁保护的活动来完成。以下是后一种情况的经典示例：如果数据显示您正在花费时间（例如）从共享数据结构中释放元素，您可以将需要释放的数据出队并收集，同时持有锁，并将数据的实际释放推迟到释放锁之后。由于数据已在持有锁的情况下从共享数据结构中删除，因此不存在数据竞争（其他线程将数据的删除视为原子的），并且锁持有时间已减少，而实现复杂性仅略有增加。

警惕读写锁。 如果在尝试分解锁时存在新手错误，那就是：看到数据结构经常被读取，而很少被写入，人们可能会想用读写锁替换保护结构的互斥锁，以允许并发读取器。这似乎是合理的，但除非锁的持有时间很长，否则此解决方案的可扩展性不会比单个锁更好（实际上，可能会更差）。为什么？因为与读写锁关联的状态本身必须原子地更新，并且在没有更复杂（且空间效率较低）的同步原语的情况下，读写锁将使用一个字内存来存储读取器的数量。由于读取器的数量必须原子地更新，因此作为读取器获取锁需要与获取互斥锁相同的总线事务——读取以拥有——并且该行上的争用可能会造成同样大的损害。

在许多情况下，较长的持有时间（例如，在锁下作为读取器执行I/O）仍然足以弥补任何内存争用，但应确保收集数据以确保它对可扩展性产生预期的效果。即使在读写锁适用的情况下，也应注意围绕阻塞语义的额外警告。例如，如果锁实现阻止新的读取器在写入器被阻塞时（避免写入器饥饿的常见范例），则不能以读取器身份递归地获取锁：如果写入器在作为读取器的初始获取和作为读取器的递归获取之间被阻塞，则当递归获取被阻塞时将导致死锁。所有这些并不是说不应使用读写锁——只是不应将其浪漫化。

考虑每个CPU的锁定。 每个CPU的锁定（即，基于当前CPU标识符获取锁）可能是分散争用的便捷技术，因为每个CPU的锁不太可能被争用（一个CPU一次只能运行一个线程）。如果持有时间短且操作模式具有不同的连贯性要求，则可以让线程在常见（非连贯）情况下获取每个CPU的锁，然后强制不常见情况获取所有每个CPU的锁以构建连贯状态。考虑这个具体的（即使是微不足道的）示例：如果要实现一个全局计数器，该计数器经常更新但很少读取，则可以实现一个受其自身锁保护的每个CPU的计数器。对计数器的更新将仅更新每个CPU的副本，而在需要读取计数器的不常见情况下，可以获取所有每个CPU的锁并对其对应的值求和。

关于此技术的两点说明：首先，只有当数据表明有必要时才应使用它，因为它显然为实现引入了大量的复杂性；其次，确保在冷路径中获取所有锁时采用单一顺序：如果一种情况从最低到最高获取每个CPU的锁，而另一种情况从最高到最低获取它们，则（自然地）会导致死锁。

知道何时广播——以及何时发出信号。 实际上，所有条件变量实现都允许通过信号（在这种情况下，唤醒一个在变量上休眠的线程）或通过广播（在这种情况下，唤醒所有在变量上休眠的线程）来唤醒在变量上等待的线程。这些构造具有细微不同的语义：由于广播将唤醒所有等待线程，因此通常应将其用于指示状态更改而不是资源可用性。如果在条件信号更合适的情况下使用条件广播，结果将是惊群效应：所有等待线程都将醒来，争夺保护条件变量的锁，并且（假设第一个获取锁的线程也消耗了可用资源）当他们发现资源已被消耗时，将再次休眠。这种不必要的调度和锁定活动可能会对性能产生严重影响，尤其是在基于Java的系统中，其中notifyAll()（即，广播）似乎已牢固地确立了自己的首选范例；已知将这些调用更改为notify()（即，信号）会导致性能的显着提高。⁷

学会事后调试。 在一些并发性的卡桑德拉眼中，死锁似乎是一种特殊的妖魔鬼怪，已成为基于锁的多线程编程中所有困难的化身。这种恐惧有点奇怪，因为死锁实际上是软件中最简单的病态之一：因为（根据定义）卷入死锁的线程停止向前推进，它们为实现者提供了有效地冻结系统并保持所有状态完好无损的服务。要调试死锁，只需要线程列表、其相应的堆栈回溯以及一些系统知识。此信息包含在对软件开发至关重要的状态快照中，以至于它的名称本身就反映了它在计算之初的起源：它是核心转储。

从核心转储进行调试——事后调试——是那些实现并行系统的人员必须掌握的一项基本技能：高度并行系统中的问题不一定是可重现的，而单个核心转储通常是调试它们的唯一机会。大多数调试器都支持事后调试，并且许多调试器允许用户定义的扩展。⁸ 我们鼓励从业人员了解他们的调试器对事后调试（尤其是并行程序的事后调试）的支持，并开发特定于调试其系统的扩展。

将您的系统设计为可组合的。 在基于锁的系统的批评者提出的更令人恼火的说法中，有一种观点认为它们在某种程度上是不可组合的：“锁和条件变量不支持模块化编程，”一篇典型的厚颜无耻的论断写道，“通过将较小的程序粘合在一起来构建大型程序[:] 锁使这不可能。”⁹ 当然，这种说法是不正确的。为了证明这一点，人们只需要指出基于锁的系统（如数据库和操作系统）组合成更大的系统，这些系统仍然完全不知道较低级别的锁定。

有两种方法可以使基于锁的系统完全可组合，每种方法都有其自身的用途。首先（也是最明显的），可以将锁定完全置于子系统内部。例如，在并发操作系统中，控制永远不会在持有内核锁的情况下返回到用户级别；用于实现系统本身的锁完全位于构成系统接口的系统调用接口之后。更一般地说，当软件组件之间存在清晰的接口时，此模型就可以工作：只要控制流永远不会在持有锁的情况下返回给调用方，子系统将保持可组合性。

其次（也许违反直觉），可以通过完全不使用锁来实现并发性和可组合性。在这种情况下，必须没有全局子系统状态——子系统状态必须捕获在每个实例的状态中，并且必须由子系统的使用者来确保他们不并行访问他们的实例。通过将锁定留给子系统的客户端，子系统本身可以由不同的子系统在不同的上下文中并发使用。这方面的一个具体例子是Solaris内核中广泛使用的AVL树实现。与任何平衡二叉树一样，该实现的复杂性足以值得组件化，但通过不拥有任何全局状态，该实现可以由不相交的子系统并发使用——唯一的约束是必须序列化对单个AVL树实例的操作。

在互斥锁足以胜任的情况下，不要使用信号量。 信号量是由Dijkstra最初描述的通用同步原语，可用于实现广泛的行为。可能很想使用信号量代替互斥锁来保护临界区，但是这两种构造之间存在一个重要的区别：与信号量不同，互斥锁具有所有权的概念——锁要么被拥有，要么不被拥有，如果被拥有，则它有一个已知的所有者。相比之下，信号量（及其同类条件变量）没有所有权的概念：当在信号量上休眠时，人们无法知道自己正在阻塞哪个线程。

当用于保护临界区时，缺乏所有权会带来几个问题。首先，无法将阻塞线程的调度优先级传播到临界区中的线程。这种传播调度优先级的能力——优先级继承——在实时系统中至关重要，并且在没有其他协议的情况下，基于信号量的系统始终容易受到优先级反转的影响。缺乏所有权的第二个问题是，它剥夺了系统对自身进行断言的能力。例如，当跟踪所有权时，实现线程阻塞的机制可以检测到病态，例如死锁和递归锁获取，从而在检测到时导致致命故障（以及所有重要的核心转储）。最后，缺乏所有权使调试变得更加繁琐。多线程系统中的常见病态是在某些错误的返回路径中未释放锁。当跟踪所有权时，人们至少拥有过去（错误的）所有者的确凿证据——因此，可以找到锁未正确释放的代码路径的线索。在没有所有权的情况下，人们会感到茫然，并且只能通过盯着代码/天花板/太空进行调试。

所有这些并不是说不应该使用信号量（实际上，某些问题非常适合信号量的语义），而是说当互斥锁就足够时，不应该使用信号量。

考虑使用内存回收来实现每链哈希表锁。 哈希表是性能关键型系统软件中常见的数据结构，有时必须并行访问。在这种情况下，向每个哈希链添加一个锁，在读者或写者遍历链时持有该每链锁，这似乎很简单。然而，问题在于调整表大小：动态调整哈希表大小对于其高效运行至关重要，而调整大小意味着更改包含表的内存。也就是说，在调整大小时，哈希表的指针必须更改——但我们不希望哈希查找需要获取全局锁来确定当前的哈希表！

这个问题有几种解决方案，但一个（相对）直接的解决方案是回收与旧哈希表关联的内存，而不是释放它。在调整大小时，会获取所有每链锁（使用明确定义的顺序以防止死锁），然后分配一个新表，并将旧哈希表的内容重新哈希到新表中。在此操作之后，旧表不会被释放，而是放入旧哈希表的队列中。然后，哈希查找需要稍作修改才能正确操作：在获取每链锁之后，查找必须检查哈希表指针，并将其与用于确定哈希链的哈希表指针进行比较。如果哈希表已更改（即，如果发生了哈希大小调整），则必须释放锁并重复查找（这将在新表中获取正确的链锁）。

在实现这一点时存在一些微妙的问题——哈希表指针必须声明为 volatile，并且哈希表的大小必须包含在表本身中——但考虑到其他替代方案，实现复杂性是适度的，并且（假设哈希表在调整大小时加倍）内存成本仅为两倍。有关生产代码中此示例，读者可以参考 Solaris 中的文件描述符锁定，可以通过在互联网上搜索“flist_grow”找到其源代码。

注意伪共享。 在缓存多处理器系统中，有多种不同的协议用于保持内存一致性。通常，这些协议规定只有一个缓存可以在脏状态下拥有给定的内存行。如果不同的缓存希望写入脏行，则新缓存必须首先从拥有缓存中读取并拥有该脏行。用于一致性的行大小（一致性粒度）对并行软件具有重要的影响：因为只有一个缓存可以在给定时间拥有一个行，所以人们希望避免这样一种情况，即两个（或更多）小的、不相交的数据结构都包含在单个行中并且由不相交的缓存并行访问。这种情况——称为伪共享——可能会导致原本可扩展的软件的可伸缩性降低。这种情况在实践中最常发生在尝试使用锁数组来分散争用时：锁结构的大小通常不超过一个或两个指针的大小，并且通常远小于一致性粒度（通常约为 64 字节）。因此，获取不同锁的不相交 CPU 可能会争用同一个缓存行。

动态检测伪共享非常困难：它不仅需要总线分析仪，还需要一种从总线的物理地址转换为对软件有意义的虚拟地址的方法，然后再从那里转换为导致伪共享的实际结构。（这个过程非常艰巨且容易出错，以至于我们已经尝试使用静态机制来检测伪共享，并取得了一些成功。¹⁰）幸运的是，伪共享很少是系统中单一最大的可伸缩性抑制因素，并且预计在多核系统上这个问题会更少（在多核系统中，缓存更可能在 CPU 之间共享）。尽管如此，这仍然是实践者应该注意的问题，尤其是在创建旨在并行访问的数组时。（在这种情况下，数组元素应该填充到一致性粒度的倍数。）

考虑使用非阻塞同步例程来监视争用。 许多同步原语都有不同的入口点，用于指定原语不可用时的不同行为：默认入口点通常会阻塞，而替代入口点会返回错误代码而不是阻塞。第二种变体有许多用途，但一个特别有趣的用途是监视自身的争用：当尝试获取同步原语失败时，子系统可以知道存在争用。如果子系统有一种动态减少其争用的方法，这将特别有用。例如，Solaris 内核内存分配器具有每 CPU 缓存的内存缓冲区。当 CPU 耗尽其每 CPU 缓存时，它必须从全局池中获取一系列新的缓冲区。在这种情况下，代码不是简单地获取锁，而是尝试获取锁，当此操作失败时递增一个计数器（然后通过阻塞入口点获取锁）。如果计数器达到预定义的阈值，则每 CPU 缓存的大小会增加，从而动态减少争用。

重新获取锁时，考虑使用代计数来检测状态更改。 当锁排序变得复杂时，有时需要释放一个锁，获取另一个锁，然后再重新获取第一个锁。这可能很棘手，因为第一个锁保护的状态可能在锁被释放期间发生了更改——并且重新验证此状态可能既耗时又低效，甚至是不可能的。在这些情况下，请考虑将代计数与数据结构关联；当对数据结构进行更改时，代计数会递增。释放和重新获取锁的逻辑必须在释放锁之前缓存代，然后在重新获取时检查代：如果计数相同，则数据结构与释放锁时相同，逻辑可以继续；如果计数不同，则状态已更改，逻辑可以做出相应的反应（例如，重新尝试更大的操作）。

仅在绝对必要时才使用无等待和无锁结构。 在我们的职业生涯中，我们每个人都在生产代码中实现了无等待和无锁数据结构，但我们仅在出于正确性原因而无法获取锁的情况下才这样做。示例包括锁定系统本身的实现¹¹、跨越中断级别的子系统以及动态检测工具¹²。这些受约束的上下文是例外，而不是规则；在正常上下文中，应避免使用无等待和无锁数据结构，因为它们的故障模式非常糟糕（活锁比死锁更难调试），它们对复杂性和维护负担的影响很大，并且它们在性能方面的益处通常为零。

准备好迎接胜利的喜悦——以及失败的痛苦。 使系统可扩展可能是一项令人沮丧的追求：在消除所有可伸缩性障碍之前，系统将无法扩展，但通常不可能知道当前的可伸缩性障碍是否是最后一个障碍。消除最后一个障碍是非常令人欣慰的：随着这种改变，吞吐量最终像从敞开的水闸中一样涌入系统。相反，努力解决复杂的锁分解，结果却发现虽然它是可伸缩性的障碍，但它只是隐藏了另一个障碍，并且消除它对性能的提升很小——甚至根本没有提升，这可能会令人沮丧。尽管这可能令人沮丧，但您必须返回系统以收集数据：系统无法扩展是因为对障碍的理解有误，还是因为遇到了新的障碍？如果是后者，您可以安慰自己，知道您的工作对于实现可伸缩性是必要的——尽管不是充分的——并且有一天吞吐量涌入系统的荣耀仍在等待着您。

并发自助餐

人们普遍认为，编写多线程代码很困难：尽管我们试图阐明多年来吸取的一些教训，但这仍然可以用一个词来形容，那就是困难。有些人对这种困难感到困惑，认为多核计算的到来对软件来说是一场灾难。这种恐惧是没有根据的，因为它忽略了一个事实，即实际上只有少数软件工程师需要编写多线程代码：对于大多数人来说，可以通过站在那些已经在实现中高度并行的子系统的肩膀上来实现并发。那些正在实现数据库或操作系统或虚拟机的人员将继续需要仔细研究编写多线程代码的细节，但对于其他人来说，挑战不是如何实现这些组件，而是如何最好地使用它们来交付可扩展的系统。虽然午餐可能不是完全免费的，但实际上是自助餐式的——而且自助餐已经开放！

参考文献

Sutter, H., Larus, J. 2005. Software and the concurrency revolution. 3(7): 54-62.
DeWitt, D., Gray, J. 1992. Parallel database systems: the future of high-performance database systems. Communications of the 35(6): 85-98.
Oskin, M. 2008. The revolution inside the box. Communications of the 51(7): 70-78.
Barroso, L. A., Gharachorloo, K., McNamara, R., Nowatzyk, A., Qadeer, S., Sano, B., Smith, S., Stets, R., Verghese, B. 2000. Piranha: a scalable architecture based on single-chip multiprocessing. In Proceedings of the 27th Annual International Symposium on Computer Architecture: 282-293.
Shavit, N. 2008. Transactions are tomorrow’s loads and stores. Communications of the 51(8): 90.
Cantrill, B. 2006. Hidden in plain sight. 4(1): 26-36.
McKusick, K. A. 2006. A conversation with Jarod Jenson. 4(1): 16-24.
Cantrill, B. 2003. Postmortem object type identification. In Proceedings of the Fifth International Workshop on Automated Debugging.
Peyton Jones, S. 2007. Beautiful concurrency. In Beautiful Code, ed. A. Oram and G. Wilson. Cambridge, MA: O’Reilly.
参见参考文献 8。
Cantrill, B. 2007. A spoonful of sewage. In Beautiful Code, ed. A. Oram and G. Wilson. Cambridge, MA: O’Reilly.
参见参考文献 6。

BRYAN CANTRILL 是 Sun Microsystems 的杰出工程师，自 1996 年来到 Sun 与 Jeff Bonwick 一起从事 Solaris 性能工作以来，他一直致力于并发系统。Cantrill 与同事 Mike Shapiro 和 Adam Leventhal 一起开发了 DTrace，这是一种用于生产系统的动态检测工具，其灵感直接来自于他在理解并发系统行为方面的挫败感。

JEFF BONWICK 是 Sun Microsystems 的研究员，自 1990 年以来一直致力于并发系统。他最出名的是发明并领导了 Sun 的 ZFS（Zettabyte 文件系统）的开发，但在此之前，他以编写（或者更确切地说，是重写）Solaris 内核中许多最并行的子系统而闻名，包括同步原语、内核内存分配器和线程阻塞机制。

最初发表于 Queue vol. 6, no. 5—
在数字图书馆中评论本文

更多相关文章

Adam Morrison - 多核程序中的可扩展同步
为现代多核处理器设计软件提出了一个难题。传统的软件设计，其中线程操作共享数据，其可伸缩性有限，因为对共享数据更新的同步会串行化线程并限制并行性。替代的分布式软件设计，其中线程不共享可变数据，消除了同步并提供了更好的可伸缩性。但是，分布式设计使得实现共享数据结构自然提供的功能（例如动态负载平衡和强一致性保证）具有挑战性，并且根本不适合每个程序。然而，通常，共享可变数据结构的性能受到当今使用的同步方法的限制，无论是基于锁的还是无锁的。

Fabien Gaud, Baptiste Lepers, Justin Funston, Mohammad Dashti, Alexandra Fedorova, Vivien Quéma, Renaud Lachaize, Mark Roth - 现代 NUMA 系统上内存管理的挑战
现代服务器级系统通常构建为在单个系统中组合在一起的多个多核芯片。每个芯片都有一个本地 DRAM（动态随机存取存储器）模块；它们一起被称为一个节点。节点通过高速互连连接，并且系统是完全一致的。这意味着，对程序员透明地，内核可以向其节点的本地内存以及其他节点的内存发出请求。关键的区别在于远程请求将花费更长的时间，因为它们会受到更长的线路延迟的影响，并且可能必须跳过多个跳点才能遍历互连。

Spencer Rathbun - 使用 Promise 进行并行处理
在当今世界，有很多理由编写并发软件。提高性能和增加吞吐量的愿望导致了许多不同的异步技术。然而，所涉及的技术通常很复杂，并且是许多细微错误的根源，特别是如果它们需要共享可变状态。如果不需要共享状态，那么这些问题可以通过一种称为 Promise 的更好抽象来解决。这些抽象允许程序员将异步函数调用连接在一起，等待每个调用返回成功或失败，然后再运行链中的下一个适当的函数。

Davidlohr Bueso - 实用同步原语的可扩展性技术
在理想的世界中，应用程序有望在越来越大的系统上执行时自动扩展。然而，在实践中，不仅这种扩展不会发生，而且在那些更大的系统上看到性能实际上恶化是很常见的。