线程的无痛体验 -

2005年12月16日
第3卷，第9期

线程的无痛体验

多线程编程不必如此令人焦虑。

ANDREAS GUSTAFSSON，ARANEUS 信息系统

当今的大部分软件都涉及多个并发任务。Web 浏览器支持多个并发 HTTP 连接，图形用户界面处理多个窗口和输入设备，Web 和 DNS 服务器处理来自大量客户端的并发连接或事务。

需要处理的并发任务数量不断增加，同时软件也变得越来越复杂。如何构建并发软件，使其既能满足不断增长的可扩展性需求，又能保持简单、结构化和安全，从而让普通的程序员能够构建日益复杂的系统，这是一个主要的工程挑战。

不同的并发编程方法在性能、可扩展性和编程复杂性方面提供了不同的权衡。本文考察并对比了其中的一些方法。本文基于作者在 Unix 环境中使用 C 和 C++ 编写网络服务器和 GUI 应用程序的经验，但其根本问题是普遍存在的，同样适用于其他类型的并发应用程序、编程语言和环境。

到底什么是多线程？

人们经常问：“这个程序是多线程的吗？” 这乍一看似乎是一个可以用简单的“是”或“否”来回答的直接问题，但实际上往往并非如此。“多线程”这个词对不同的人来说意味着不同的事情，而且人们常常甚至无法就一个特定的程序是否应该被认为是多线程的达成一致。

通常，问题“它是多线程的吗？” 反映了特定的关注点，例如：

它是否一次处理多个用户、连接、查询、事务或其他操作？
当它执行长时间运行的计算时，其用户界面是否保持响应？
它是否可以利用多个处理器？
它是否有随机的、非确定性的、难以找到的错误？

对于大多数实际程序而言，这些问题并非都具有相同的答案。有时它们甚至不是正确的问题；如果你有一台双处理器机器，你更愿意使用哪种程序？是使用两个处理器的程序，还是只使用其中一个处理器但运行速度更快的程序，因为它基于一种无法并行化但速度非常非常快的算法？

当在本文的其余部分中使用“多线程”这个词时，它将不具有上述任何问题的含义。相反，让我们简单地将多线程定义为具有多个控制流，无论这些流在哪里执行，或者在任何给定时刻有多少个流正在取得进展。

事件驱动方法

编写需要处理多个独立输入源的程序的一种流行方法是事件驱动模型。在事件驱动程序中，中央事件循环监视所有外部数据源（例如，网络连接、输入设备和定时器），并在每个数据到达时调用回调函数来处理数据。GUI 工具包的用户对这种模型很熟悉，并且它是许多网络服务器（例如 BIND DNS 服务器系列）的基础。

事件驱动程序具有高度的可移植性，因为它们不需要其环境提供任何特殊的多线程支持，并且在实践中，它们通常非常成功地创建了并发的错觉，以至于用户认为它们是多线程的，即使它们实际上只有一个控制线程。

事件驱动编程的缺点是它混乱、乏味、结构化差且重复。在事件驱动程序中，事件循环处于控制之中，而不是程序员。当事件驱动程序想要执行 I/O 操作（例如从网络连接读取一些数据）时，它不能简单地停止并等待数据。相反，它需要设置一个 I/O 请求，然后返回到事件循环。当数据可用时，事件循环将调用一个 I/O 完成回调函数来处理它。这迫使程序员通过将一个完美程序分解为一系列简短的回调函数来毁掉它。¹

自然地表示为函数调用和循环层次结构的算法必须进行修改，方法是在算法需要等待网络输入或其他外部事件的每个点将其拆分为单独的回调。在这些点上，算法的完整状态必须被费力地存储在一个数据结构中，同时执行返回到事件循环，等待下一个回调的调用。

在程序被迫返回到事件循环的点上，它将无法使用局部变量、while 或 for 循环、条件语句、子例程或递归——基本上是任何结构化编程的基本工具。相反，程序的控制流变得以返回到事件循环以等待回调的操作为中心，这本质上是一种（延迟的）GOTO 形式。在控制流方面，即使是用所谓的“高级”语言编写的事件驱动程序也往往类似于汇编语言程序。

线程来救援

多线程为事件驱动模型提供了一种替代方案。通过为每个网络连接、输入设备、用户或其他适当的实体创建一个单独的控制线程，程序员可以从该实体的角度以自然的方式表达控制流。在事件驱动模型中涉及返回到事件循环的 I/O 操作现在表现为简单的函数调用，这些函数会阻塞——即，导致当前正在执行的线程停止，直到操作完成。当线程停止时，其他线程可能会取得进展。由于无需返回到事件循环，因此可以在嵌套循环或递归函数的中间执行 I/O，并且局部变量在每个 I/O 操作中都得到保留。

尽管多线程通常被认为是提高性能的一种技术，但在这里我们使用线程是为了提高程序结构的另一个目标，使代码更小、更易读且更具表现力。使用线程来表达结构并不限于涉及 I/O 的情况；即使在程序内部，线程也可以用于表达生产者-消费者对、状态机和其他自然映射到多个控制线程的结构。

对线程的恐惧

如果事件驱动编程如此笨拙，那么为什么仍然有如此多的软件以事件驱动风格编写？原因之一是线程因容易出错且难以使用而声名狼藉。在题为“为什么线程是个坏主意（对于大多数用途）”的演讲中，John Ousterhout 指出，线程对于大多数程序员来说太难使用了，因为处理同步、锁定、竞争条件和死锁非常困难，他认为应该使用事件驱动模型来代替。²

同步问题极其难以正确解决。双重检查锁定模式³就是一个很好的例子，它是一种在多线程程序中高效初始化全局对象的技术。这种技术已被广泛使用和教授，但由于与优化编译器或多处理器计算机的内存子系统重新排序内存访问相关的细微问题，它并不可靠。⁴ 如果连专家都无法正确进行同步，我们又怎能期望普通程序员做到呢？

恐惧抢占，而不是线程

尽管程序员有充分的理由恐惧异步，但将其转化为对多线程的恐惧是错误的。人们通常认为，多线程程序需要担心同步、锁定和死锁，而事件驱动程序则不需要，但实际上，有些事件驱动程序也必须担心这些问题，而有些多线程程序则不需要。

大多数事件驱动系统能够避免 Ousterhout 警告的危险，原因不是它们的事件驱动性质。相反，是因为它们做出了一项不成文的保证，即一次只运行一个事件处理程序，并且它在运行时不会被中断。如果事件驱动系统不做出这些保证，则事件处理程序访问的任何共享数据都需要像典型的多线程系统一样受到锁的保护。例如，在一个可以同时执行多个事件处理程序以使用多个处理器的事件驱动系统中，情况就是如此。

相反，大多数多线程系统需要担心并发数据访问的原因不是它们有多个控制线程，而是这些线程可以同时执行，或者被强制抢占以调度另一个线程的执行。如果多线程系统保证一次只运行一个线程，并且正在运行的线程不会被抢占，那么就不会有机会让一个线程扰乱另一个线程的不变性，因此也就不需要锁定。

换句话说，程序的控制流是结构化为事件还是线程的问题与这些线程和事件是否被抢占式调度的问题是正交的；⁵ 这在表 1 中进行了说明。Ousterhout 警告的危险不是线程的危险，而是抢占的危险。

协作式线程

大多数多线程系统强调使用线程来提高性能，并将抢占式调度视为一项功能，因为它允许它们使用多个处理器，并保证没有单个线程可以不公平地垄断处理器并阻止其他线程无限期地运行。

然而，也有一类多线程环境，它们强调使用线程来表达结构，并将抢占式调度视为错误。它们不保证每个线程最终都会将控制权让给其他线程，而是保证相反的情况：没有线程必须意外地让出控制权。这种风格的多线程有许多不同的名称：非抢占式、同步或协作式线程，或基于协程的编程。在协作式多线程系统中，线程仅在某些明确定义的点（例如阻塞 I/O 操作或显式 yield 调用）自愿让出控制权。

使用抢占式线程，线程之间共享的任何数据结构都可能随时被另一个线程访问。这使得对这种数据结构的任何访问都可能发生竞争条件，并迫使程序员在大量地方引入锁定。另一方面，当非抢占得到保证时，共享数据结构只能在当前线程自愿阻塞的少数明确定义的点被其他线程访问。在大多数情况下，这完全消除了对锁定的需求，以及传统上与多线程相关的绝大多数危险。

实际上，协作式多线程与事件驱动编程一样，可以安全地避免竞争条件。任何协作式多线程程序都可以转换为等效的事件驱动程序，方法是将每个阻塞操作转换为返回到事件循环（以添加大量簿记为代价，以便可以正确恢复操作），反之亦然。

线程开销

程序员避开线程的另一个原因是线程通常在时间和内存方面都带有很大的开销。创建和销毁线程可能很慢，并且在抢占式线程的情况下，每次访问共享数据都会产生锁定开销。由于为每个线程分配了固定大小的堆栈，因此会浪费大量内存（或至少是虚拟地址空间）。

对于需要比单个处理器提供的性能更高的应用程序，并且表现出足够粗粒度的并行性，以便可以将开销分摊到大量计算中，这些牺牲可能是值得的；但是，对于想要使用线程仅仅是因为他的问题的解决方案自然地表示为数千个小的、频繁通信的线程的程序员来说，开销可能太大了。

状态线程

一种试图将多线程的结构优势与事件驱动编程的可扩展性和安全性相结合的多线程环境是状态线程。⁶ 这是一个开源、可移植、轻量级的用户空间线程库，专门设计用于替换 Internet 应用程序中的事件循环。“状态线程”这个名称指的是使用线程作为一种跟踪程序状态的方式，在事件驱动程序中，程序状态必须手动管理。

与许多其他类 Unix 系统的线程库不同，状态线程不是 Posix 线程 (pthreads) 标准的实现。相反，它提供了自己的编程接口，包括诸如 st_thread_create()、st_thread_join()、st_read()、st_write() 等函数。它省略了 pthreads 标准中价值可疑或导致大量开销的功能（特别是每个线程的信号掩码），并添加了旨在简化网络编程的功能，例如在执行网络 I/O 调用时指定超时时间的能力。

更重要的是，状态线程与 pthreads 的不同之处在于它保证了非抢占。由于这种保证，大多数状态线程应用程序根本不需要进行任何锁定。程序员只需确保在调用阻塞函数（例如 st_read()）时，任何共享数据都处于一致状态即可；这与事件驱动系统的程序员在返回到事件循环时必须确保共享数据一致没有什么不同。

与标准 pthreads 实现相比，状态线程非常简单轻巧。库本身由不到 4,000 行 C 代码组成，并且线程创建、线程销毁和线程上下文切换操作在普通的 PC 硬件上每次都只需不到一微秒。这与在事件驱动系统中调度事件处理程序所涉及的开销相当。基于状态线程的应用程序通常优于等效的基于 pthreads 的应用程序（这得益于更快的上下文切换和没有锁定开销），以及事件驱动的应用程序（这得益于更小更简单）。

那些讨厌的固定大小的堆栈

尽管像状态线程这样的轻量级线程库在执行时间开销方面可以与事件驱动编程相媲美，但在内存方面，事件仍然具有优势。在过去的几十年中，大多数固定大小的编程结构都让位于更动态的结构：固定大小的数组已被动态分配甚至可变大小的数组所取代，固定大小的文件已被动态扩展的文件所取代，等等。堆栈是一个明显的例外：多线程系统仍然为每个线程分配一个固定大小的堆栈。这使得线程程序员面临着令人不安的权衡，即堆栈太小会冒堆栈溢出的风险，或者堆栈大于需要会浪费内存和地址空间。

当线程数量很少且内存充足时，这通常不是问题；您可以负担得起将堆栈设置得足够大——例如，每个堆栈 1MB。当尝试将多线程系统扩展到数千个线程或在内存受限的嵌入式系统上运行时，这会成为一个问题。

pthreads 实现中的典型默认堆栈大小为 1MB。状态线程库中的默认堆栈大小为 64KB，这有助于扩展到更多线程，但要求状态线程程序员谨慎行事以避免堆栈溢出，例如消除大型堆栈分配的数组并避免深度递归。在某些系统上，标准 C 库也会通过在堆栈上分配大型缓冲区来引起问题——例如，在 printf() 中格式化输出时。尽管如此，一些基于状态线程的应用程序可以仅使用每个线程 4KB 的堆栈；这些应用程序实际上可以扩展到数十万个线程。

迈向百万线程应用程序

有些应用程序可以从非常大的数量（甚至数百万）的线程中获益——例如，试图模拟大量独立计算机行为的网络流量模拟器。对于如此大量的线程，固定大小堆栈造成的内存浪费成为一个问题。

解决这个问题的长期方案是完全摆脱固定大小的堆栈。使用 Python 语言的程序员已经可以在基于堆栈和无堆栈的 Python 实现⁷之间进行选择，其中无堆栈变体以执行串行代码的速度稍慢为代价提供了轻量级微线程。同样，Scheme 程序员可以在基于堆栈和无堆栈的 Scheme 实现之间进行选择。

C 和 C++ 程序员也应该可以在基于堆栈和无堆栈的实现之间进行选择。无堆栈 C 编译器将在堆而不是堆栈上为函数参数和局部变量分配空间。这不需要对 C 语言本身进行任何更改，尽管会存在性能损失，并且在与使用基于堆栈的调用序列的现有库互操作方面存在一些挑战。

整合在一起

不同形式的多线程适用于解决不同的问题。有些应用程序涉及繁重的数值计算，单个 CPU 的性能根本不够，而功能齐全的抢占式线程是唯一的选择。其他应用程序在计算方面较轻，而在与用户、网络以及线程之间的交互方面较重。协作方法更适合这些应用程序。协作式线程不会取代抢占式线程，但它们可以很好地替代无处不在的事件循环。当同一应用程序的不同部分对线程提出不同的要求时，最佳解决方案可能是混合方法，例如将轻量级协作式线程调度程序作为抢占式线程系统的一个线程运行。

尽管当今的大多数编程环境都提供对事件和抢占式多线程的支持，但对协作式线程的完全集成支持（更不用说对混合抢占式和非抢占式线程的支持）却很少见。状态线程等第三方库和 Stackless Python 等语言有助于暂时弥合这一差距。希望未来的系统将为抢占式和协作式线程提供集成且平等的支持。

参考文献

Fuchs, M. 1996. 逃离事件循环：多线程 GUI 的替代控制结构。载于人机交互工程，编辑：C. Unger 和 L. J. Bass。Chapman & Hall。
Ousterhout, J. 1996. 为什么线程是个坏主意（对于大多数用途）。在 Usenix 技术会议上的特邀演讲。
Schmidt, D. 和 Harrison, T. 1996. 双重检查锁定：一种用于高效初始化和访问线程安全对象的优化模式。第三届程序设计模式语言会议； http://www.cs.wustl.edu/~schmidt/PDF/DC-Locking.pdf。
Meyers, S. 和 Alexandrescu, A. 2004. C++ 和双重检查锁定的危险。《Dr. Dobbs Journal》（7-8 月）； http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf。
Adya, A.、Howell, J.、Theimer, M.、Bolosky, W. J. 和 Douceur, J. R. 无需手动堆栈管理的协作式任务管理，或者事件驱动编程并非线程编程的对立面； http://research.microsoft.com/sn/Farsite/USENIX2002.ps。
用于 Internet 应用程序的状态线程库； http://state-threads.sourceforge.net/。
Stackless Python； http://www.stackless.com/wiki/Stackless。

ANDREAS GUSTAFSSON ([email protected]) 自 1989 年以来一直从事事件驱动的图形用户界面和 Internet 应用程序的编写工作。在过去的 10 年中，他花费了大部分时间开发 DNS（域名系统）服务器，特别是作为 Internet Systems Consortium 的抢占式事件驱动 BIND 9 服务器的合著者，以及协作式线程 Nominum CNS（缓存名称服务器）的架构师。他目前为自己的公司 Araneus Information Systems 工作，担任顾问和硬件随机数生成器供应商。他拥有赫尔辛基理工大学的工学硕士学位。

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

更多相关文章

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 的更好抽象来解决。这些 Promise 允许程序员将异步函数调用连接在一起，等待每个函数返回成功或失败，然后再运行链中的下一个适当函数。

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