12.2  并发程序设计基础

Concurrent Programming Fundamentals

我们将用术语并发性指一类程序的特性，在这类程序里，两个或更多的执行上下文同时处于活动状态。按照这一定义，协作程序就不是并发的，因为在每个时刻只有一个协程是活动的。我们将用术语并行指并发程序里的一种特性，在其中的多个上下文里正在同时实际处于执行中。这样，真正的并行性需要有并行硬件。从语义观点看，在真正的并行与一个强占式并发系统里（这种系统会在不可预期的时刻在不同执行环境之间进行切换）的“准并行”之间并没有区别，这两种情况需要同样的程序设计技术。

我们把并发程序里的执行上下文称为线程。特定程序里的一组线程在操作系统提供的一个或多个进程上实现。操作系统的设计者通常区分了重量级进程（它有自己的地址空间）和轻量级进程（它们可能共享同一地址空间）。轻量级进程在20世纪80年代末到90年代初被加入Unix的各种版本里，以迎合共享内存多处理器系统的快速发展。如果没有轻量级进程，并发程序里的各个线程就必须在多个重量级线程上运行，语言实现就必须保证线程之间共享的数据都能映射到所有进程的地址空间里。

我们有时用术语作业指具有良好定义的、必须由某个线程执行的工作单元。在一种常见的程序设计惯用形式里，一集线程共享着一个公共的“作业袋”，也就是一组需要完成的作业。每个线程反复地从袋中取出一个作业，执行它，而后去再拿一个。一个作业的工作有时会导致把其他新作业加入袋中。

不幸的是，有关并发性程序设计的词汇表在不同的语言和作者那里并不统一。有些语言把线程称为进程，Ada把它们称为作业。有些操作系统把轻量级进程称为线程。Mach OS（OSF Unix和MacOS X都是由它派生出来的）把一些轻量级进程共享的地址空间称为作业。也有少数几个系统希望通过构造新词的方式避免这种混乱，提出的有“活动体”（actor）和“纤维”（filament）等。我们将设法一致地使用前面两个段落里给出的定义，当遇到特定语言或系统所用的术语与这些不同时再给以说明。

12.2.1  通信和同步

Communication and Synchronization

在任何并发程序设计模型里，需要处理的两个最关键的问题就是通信和同步。通信指线程可用于去获得其他线程产生的信息的各种机制。命令式程序里的通信机制通常都基于共享存储器或消息传递。在共享存储器的程序设计模型里，某些

或全部程序设计变量可以由多个线程访问。如果一对线程之间需要通信，只要一个线程把值写入某个变量，另一线程去读它。在消息传递程序设计模型里，不同线程没有公共的状态。当一对线程之间需要通信时，其中的一个必须执行一次明确的send操作，把数据传送给另一个线程。

同步指程序员可以用于控制不同线程之间操作发生的相对顺序的各种机制。消息传递模型里的同步通常是隐式的，消息的发送必须在接收之前。如果某个线程企图接收一个尚未发送的消息，那么它就必须等到发送方赶上来。在共享存储器程序设计模型里，同步通常不是隐式的，除非我们做了某些特殊的事情，否则“接收方”就可能在某个变量被“发送方”修改之前读到其中的“老”值。在共享存储器或基于消息的程序里，同步都可以采用自旋（也称为忙等待）方式或阻塞方式实现。在忙等待同步中，线程在一个循环中执行，它不断地重新求值某个条件，直至这个条件变为真（例如，直到某个消息队列不空，或者某个共享变量有了一个特定的值），假定这是在另外的某个处理器上运行的某个线程的动作产生的效果。请注意：在单一处理器上忙等待，对于线程同步根本没有意义。当我们独占着改变条件所必需的资源（这里指的就是处理器）时，根本不可能指望那个条件会改变。（在单一处理器上运行的线程有时可能忙等待着I/O的完成。但这时情况有所不同，因为I/O设备是与处理器并行工作的。）

在阻塞式同步（也称为基于调度的同步）中，等待线程自愿把自己占有的处理器交给另外的某个线程。在这样做之前，它在与同步条件关联的某个数据结构里留下相应的标记。如果另一线程在未来某个时刻使这个条件变为真，就会看到这个标记并采取某种动作，使被阻塞进程可以再次进入运行。我们将在12.2.4节简单地重新考虑同步问题，在12.3节更彻底地研究它。

硬件和软件通信

正如12.1.3节里提出的，在共享存储器和消息传递之间的差异不仅与语言和库有关，也与计算机硬件有关。注意到下面的情况也很重要：由语言或库提供的通信和同步模型完全不必与基础硬件的功能一致。很容易在共享存储器的硬件上实现消息传递。如果花一些功夫，也能在消息传递硬件上实现共享存储器。基于后面这种方式的系统有时被称为软件分布式共享存储器（S-DSM）系统。

12.2.2  语言和库

Languages and Libraries

把并发性提供给程序员的方式可以是通过明确提供了并发性功能的语言，或者通过编译器支持的传统顺序语言扩充，也可以通过在语言本身之外的库。后两种方式更常见得多，当前的大部分并行程序都是用针对向量机的加标注Fortran语言，或者用带有库调用的C/C++语言写出。随着Java和C# 的影响激增，这种情况正在改变，至少是在“低端”。但是，显式并行语言要在高性能并行应用方面取代Fortran、C和C++，估计还需要一段时间。

大多数SMP供应商都提供了基于共享存储器和线程的并行程序设计库。在Unix的世界里，这种库基本上都是按POSIX的pthread标准 [Ope96] 实现的（微软为Windows提供了类似的功能）。对基于消息传递的计算，现存的库可以分为主要的两类：一类主要是为了一个程序内部的进程间通信，另一类主要是为了跨过程序边界的通信。属于后一类的包通常实现某一种标准互联网协议 [PD03，第6章]，因此它们非常像文件I/O（7.9节）。

最流行的在并行程序内部做消息传递的包有两个，分别是PVM [Sun90，GBD⁺94] 和MPI [BDH⁺95，SOHL⁺98]。这两个包在许多方面都提供了类似的功能。在创建和管理异构的分布式网络中的进程方面，PVM的功能更丰富一些。在这种网络里，许多不同类型的计算机可以在执行中加入或离开有关的计算。MPI为如何实现通信（如何将它映射到特定的高性能多机系统的原语）提供了更多控制，还提供了一集更丰富的通信原语，特别是所谓的集合通信，即在一组线程中的一对多、多对一和多对多消息模式。存在着针对C、C++和Fortran的PVM和MPI实现。

至于基于客户端的服务器请求的通信，远程过程调用（RPC）为消息传递提供了一种很有吸引力的接口。RPC客户并不是直接与服务器交谈，而是调用一个本地的桩过程，该过程把得到的参数包装成一个消息送给服务器并等待回复，而后以结果参数的方式返回给客户端。有的供应商提供了一些工具，可用于从服务器接口的形式化描述自动生成桩过程。在Unix的世界里，Sun的RPC [Sri95] 是一种实质标准。RPC的一些推广正在基于互联网的计算中开展着激烈的竞争，其中的大多数是基于二进制组件（第518页）。在面向对象系统里，RPC有时被称为远程方法调用（RMI）。

与基于库程序包的方式相比，显式的并发性程序设计语言的优势在于可以得到编译器的支持。它们可以采用不同于过程调用的语法形式，可以把通信和线程管理与另外一些概念更紧密地集成到一起，例如类型检查、作用域和异常处理等。与此同时，由于大多数程序都是顺序的，因此并发性语言很难得到广泛的接受，特别是当其中的并发特征可能使顺序性程序变得难以理解时。正如12.1节所说的，Algol 68就包含了并发特征，虽然它们从来也没有被广泛使用过。并发性还出现在一些更新的“主流”语言里，包括Ada、Modula-3、Java和C#。更早一点的有Occam程序设计语言，它在商业上仍然很重要，一直有一个很活跃的用户群。它提供一种基于Hoare的通信顺序进程（CSP）的描述形式。Occam开始时被选作基于INMOS transputer处理器构造的系统的语言，这种系统当时在欧洲广泛使用，但现在已经没有了。Andrew的SR作为一种教学语言而流行。

在科学计算的社团里，有关向量化编译器的研究已经发展出一些针对多机系统和多处理器系统的并行化编译器，它们能设法去利用程序员写的标注。从事这方面研究的一些小组在20世纪90年代聚集到一起，开发了高性能Fortran（HPF）[KLS⁺94]，这是Fortran 90的一种数据并行方言。（在数据并行程序里，并行性的主要来源是把公共操作用到一个很大的数据集的所有成员。作业并行程序中并行性主要来源于并发地执行不同的操作。数据并行语言就是为写数据并行程序而设计的语言。）

12.2.3  创建线程的语法

Thread Creation Syntax

我们可以设想一种并发程序设计系统，其中有着固定的一组由语言实现创建的线程。通常认为这种静态形式的并发性太受限制了。大多数并发性系统都允许程序员在运行中创建新的线程。在不同语言和库之间，创建线程的语法和语义细节变化非常大。存在至少6种创建方式：（1）co-bigen，（2）并行循环，（3）在加工时启动，（4）fork（可能伴有join），（5）隐含接收，（6）早回复。前两种方式把线程分离出来作为一种特殊的控制流结构，其他则采用类似于（或者就是等同于）子程序的语法去声明线程。

SR程序设计语言里提供了所有的这6种方式。Algol 68和Occam使用co-begin。Occam还采用了并行循环，HPF也用了并行循环。Ada用了在加工时启动和fork。Modula-3、Java和C# 用的是fork/join。隐式接收是RPC系统的通行机制。Simula的detach操作可以看成早回复的一种形式。

co-begin

在Algol 68里，begin...end块的行为依赖于其中的表达式是用分号还是逗号分隔。前一种情况得到的是普通的顺序语义，后一情况得到的就是非确定性的

或并发的语义，依赖于在begin的前面有没有一个par关键字。块：

表明对a或b的赋值可以按任何顺序发生。块：

说明它们可以并行发生。当然，对于赋值这样的简单操作，并行执行并没有什么意思。par begin结构通常用于更有趣的操作：

这里p和s的执行与嵌套块的顺序执行（其中调用了q和r）可以并行：

另外几种并发性语言里也提供了par begin的变形。Occam用缩格作为嵌套控制结构的限界，在那里可以写：

一般而言，我们把包含一系列可并发执行的语句的结构都称为co-begin。

并行循环

有几种并行语言（包括SR、Occam，以及Fortran的一些方言）提供了一种循环，其中的迭代是并发执行的。在SR里可以写：

在Occam里写：

SR程序员有责任保证并发执行的安全性，也就是说，保证代码的正确性不依赖于竞态条件的任何实际情况。在上面例子里，一般而言，在p的不同实例里对全局变量的访问需要同步，以保证它们不相互冲突。Occam的语言规则禁止有冲突的访问，编译器会检查并保证由一个线程写的变量不会被另一个并发活动的线程读或写。对上面的例子，Occam编译器将强制性要求p的三个参数都必须是传递值的（不是传递结果的）。在Occam里并发的活动线程只能通过传送消息的方式相互通信。

Fortran的几个并行方言都提供了并行循环，但采用的语义各不相同。HPF的forall循环后来被纳入1995年的Fortran 90修订版。与Occam和SR的并行循环类似，它也说明其中的迭代可以并行。为了消除竞态条件，它还强调了对循环的组成语句的自动内部同步，要求其中的每个语句都必须是赋值语句或嵌套的forall循环。特别是在所有迭代中，任何给定赋值语句里对变量的所有读操作，都必须在任一迭代里对左部的写操作之前完成。而任何对左部的写操作又必须在

栈帧和嵌套的线程

在Algol 68和Occam的实现里，由co-begin创建的线程必须共享地访问一个公共的栈帧。为避免实现的复杂性，SR提供了一种co-begin的变形（用co...oc界定），其中的一系列语句都必须是过程调用，每一个都将在它自己的栈帧里开始执行。事实上，SR里的每个线程都在一个新的独立子程序上创建，而且没有子程序嵌套。这就使SR不需要8.6.1节介绍的仙人掌栈。

随后赋值语句的任何读操作之前完成。在下面的例子里，循环的第一个语句要读B的n – 1个元素和C的n – 1个元素，而后更新A的n – 1个元素。随后的第二个赋值语句将读A的全部n个元素而后更新其中的n – 1个：

请特别注意，第一个赋值语句里对A(i) 的所有更新都必须发生在第二个赋值语句的所有读操作之前。进一步说，第二个赋值语句里对A(i + 1) 的更新在“下面”迭代中读A(i) 时都不会看到，因为这些迭代是并行发生的，右部所有读变量的操作发生在对其左部的更新之前。

对于这种在数组的元素上“迭代”的循环，forall的这一语义特别适合在向量机上执行。经过一些努力，也可以把它调整到更常规的处理器上。HPF提供了一组很丰富的数据分布和对齐指示字，使程序员可以把数组元素散布到与大量处理器关联的存储器里。在一个forall循环里，特定赋值语句的计算通常由“拥有”左部元素的处理器实际执行。在许多情况下，HPF或Fortran 95编译器都能证明一个forall循环的特定（部分的）成分语句之间没有依赖关系，因此可以允许它们执行而不需要实际地去做同步。

加工时启动

Ada和SR（以及许多其他语言）允许用类似无参子程序的语法形式声明线程代码。在加工这种声明时创建一个执行这段代码的线程。在Ada里（线程称为task）可以写：

作业T有自己的begin...end块，一旦控制进入过程P，这个块就开始执行。如果P是递归的，那么就可能同时存在多个T的实例，它们都并发执行，也与执行P的那个作业（的当前实例）并发执行。主程序的行为就像是初始的默认作业。

如果控制达到过程P的最后，它会在返回之前等待T的相应实例（也就是在这个P的实例开始执行时创建的那个实例）完成。这一规则保证了P的局部变量（按照静态作用域规则，它们在T中是可见的）绝不会在T做完对它们的所有事情之前被释放。

在SR里，加工时启动的线程称为process。

fork/join

co-begin、并行循环和加工时启动导致的并发控制流模式（线程在其中执行）都是正常嵌套的（见图12.6(a)）。并行循环里的每个线程用不同的数据执行同样的代码；在co-begin和加工时启动中，不同线程的代码可以不同。换一种说法，并行循环通常是数据并行，而co-begin和加工时启动则是作业并行。

fork操作的功能更一般，它通过显式的可执行的操作创建线程。与之匹配的join操作使线程可以等待以前fork的某个线程的完成。由于fork和join并不与嵌套结构关联，因此它们可能导致任意的并发控制流模式（见图12.6(b)）。

Ada除提了供加工时启动的作业外，也允许程序员定义作业类型：

此后程序员就可以声明类型为access T的（指向T的指针）变量，并通过动态分配的方式创建新作业：

这里的new操作就是fork，它创建一个新线程并启动其执行。在Ada里没有显式的join操作，父作业和子作业当然可以根据需要显式同步（例如，在子作业马上要完成其执行时）。在任何声明了作业类型的作用域里，控制将一直在作用域的结束处自动等待，直至这个类型的所有动态创建的作业终止。这种约定可以避免出现对局部变量的悬空引用（Ada的栈帧具有受限的生存期）。

Modula-3提供了fork和join操作。fork操作的返回类型为thread的引用，join操作以这种引用作为实际参数：

Modula-3的线程从一个特殊的子程序开始执行。语言设计者也可以选择把这个子程序作为Fork的参数，但是采用那种方式将迫使所有Fork子程序都接受同样一集固定的参数，以适应语言的强类型的需要。为了避免这种限制，Modula-3把Fork的参数定义为一种“线程闭包”对象，如9.4.5节所述。在这个对象里包含着对线程的初始化子程序的一个引用，还有启动所需的所有实际参数。Fork操作调用这个特殊子程序，只传过去一个参数，也就是对有关线程闭包对象的引用。在标准线程库里定义了一个线程闭包类，其中只包含这种子程序引用。程序员可以定义它的派生类，增加线程子程序可以访问的域。Ada没提供与此类似的给作业传递启动参数的机制。在Modula-3里可以通过线程闭包的域传递的信息，在Ada里只能通过消息或共享变量的方式传给启动后的线程。

SR可以通过给一个proc送消息的方式创建线程。proc类似于带有一个另外的前向声明的过程，被称为op。SR最有特色的性质之一就是其中顺序与并发结构、消息传递与子程序调用的优美集成。一个SR子程序实际上就是一对proc/op的语法包装，它具有受限的call风格的fork，其中父线程一直等到子

线程结束之后才继续向下执行。与Ada一样，SR也没有显式的join操作，当然，父线程与子线程总可以根据需要显式同步。

在Java里也可以得到线程，方法是构造预定义的Thread类的派生类的对象：

从表面上看，这里new的使用很像Ada里动态作业的创建。但Java中通过new创建的线程并不是一创建就执行。如果要启动它，父线程（或者其他线程）就必须调用其成员函数（方法）start，这也是在Thread里定义的：

start使线程变成可运行的，安排去执行它的名为run的函数，而后返回调用者。程序员必须为Thread的每个派生类定义适当的run方法，这种run方法的本义就是只由start调用，程序员不应该显式地调用它，也不应该重新定义start。在这里也有一个join方法：

Java 5（带有其java.util.concurrent并行库）并不鼓励程序员去显式地创建线程。相反，可以把建立的作业（也就是支持Callable或Runnable接口的对象）送给一个Executor对象，它可能转而把作业寄放到线程管理池中。通过把作业与线程的概念分离开，Java使Executor类能够去优化真并行和调度方式的水平，以适应基础平台的特点。

在这里，newFixedThreadPool（这是一大批标准的Executor工厂之一）的实际参数表明这个pool应管理4个线程。对pool.execute调用中指定的每个作业都将由这些线程之一运行。C# 的线程和线程池功能与Java的类似。

隐式接收

上面几节所描述的机制都允许程序在运行中创建新线程，在每种情况里，这些新线程都与现存线程在同一个地址空间里运行。在RPC系统里，为了响应来自某个另外的地址空间的请求，常常需要自动创建新线程。此时服务器不是让某个已有线程去执行receive操作，而是把通信通道（它可能称为链接、套接字或连接）约束（bind）到一个局部线程体或子程序上。当请求到来时就生成一个新的线程去处理它。

从效果看，这种bind操作赋予用户在服务器的地址空间里执行fork操作创建线程的能力。要在SR里实现bind的效果，就需要声明一个能力变量，用一个过程引用（一个存在对应的proc的op）去初始化它，而后把它放在消息里送给位于另一地址空间的线程。此后接受线程就可以在send或call操作里使用这个能力，就像是在使用一个局部op的名字一样。在这样做时，作为结果的消息的效果就像是在原地址空间里执行了一个fork操作。在为用于常规的顺序语言而设计的RPC桩系统里，处理外来调用的线程的创建和管理常常不是完全自动化的，我们将在第12.4.4节考虑其他的可能方式。

早回复

在SR里fork和隐式接收的相似性，反映了子程序特性中一种重要的对偶性质。我们通常总是在一个线程的基础上考虑顺序子程序的问题，这种线程保存起当时的上下文（其程序计数器和寄存器）去执行子程序，而后返回继续去做以前正在做的事情（见图12.7(a)）。但如果我们有两个线程，其中一个扮演调用者的角色，另一个作为被调用者，效果也是一样的（见图12.7(b)）。条件是调用者在继续向下执行前一直等到被调用者的回复。调用本身也就是一对fork/join，或者是在通信通道上为被调用者的隐式接收而设置好send和receive。

考虑子程序调用的这两种方式，实际上提出两种不同的实现，其中任何一种都可以用于实现另一种。一般而言，为了节约时间，编译器都希望尽可能避免创建另一个独立线程。正如前面有关fork/join一节里提到的，SR采用了子程序调用的双线程模型。当然，由于是在同一个地址空间里，在可能情况下，SR都会用常规子程序调用的方式实现它们。Hermes语言 [SBG⁺91] 的情况与此类似，其中也是用线程和消息的方式模拟子程序，对最常见的情况也能采用常规子程序调

用的方式实现。如果我们以调用者和被调用者分别采用独立线程的方式考虑子程序，那么就没有任何特别理由要求被调用者一定首先结束执行，而后才能允许调用者继续：它必须做的事情就是完成结果参数所依赖的那部分工作。早回复是一种机制，它使被调用者可以在没有终止之前就把结果返回调用者。在早回复之后，调用者和被调用者将并发地执行（见图12.7(c)）。

违背直觉的实现

在至今为止的12章里，我们已经看到过一些情况，其中语言特征的实现可能与程序员的直觉相悖。早回复是一个最新的例子，其他例子包括表达式的求值顺序（6.1.4节），子程序的在线展开（8.2.4节），尾递归（6.6.1节），活动记录的非栈分配（为了无限的生存期，3.5.2节），记录域的乱序或者非连续布局（7.3.2节），在一个中心引用表里的变量查找（3.4.2节），在变量的引用模型下的非可变对象（6.1.2节），在泛型的实现中让不同类型参数的实例之间共享代码（3.6.3节和8.4节）。编译器可能生成与其输入的组织方式截然不同的代码，特别是在按较高的代码改进级别工作时。除非受到语言定义的约束，实现完全可以选择任何翻译方式，只要能证明它与输入等价。

如果我们按照调用者和被调用者采用同一线程的方式思考子程序调用问题，那么就应该把早回复看作是一种创建新线程的方法了。当执行子程序的线程做早回复操作时，它就把自己分裂为一对线程，其中一个返回，另一个继续执行子程序（见图12.7(d)）。

在SR里，任何子程序都可以执行早回复操作：

对于单一地址空间里的调用，SR编译器一直等到reply再创建新线程，这样，如果子程序返回前没执行reply，就可以对调用者和被调用者使用一个实现线程了。在遇到reply时，子程序的栈帧属于调用线程。为使它成为一个新创建的线程的初始帧，SR实现可以采用一种内存管理模式，其中的栈帧都通过动态分配并用指针连接。实现也可以采用另一种方式，把当前帧复制到在reply时新分配的栈的最下面。早回复类似于Simula协程的detach操作，它也出现在Lynx里 [Sco91]。

引入早回复的主要动力来自一些应用，其中新建线程的父线程需要保证新线程在自己（父线程）继续执行前已经完全初始化。以万维网浏览器为例，其中负责格式化页面的线程可能为每个内嵌图像创建一个子线程，这种子线程将与适当的服务器联络并开始传送数据。服务器最先送来的是有关图像大小的指示字。页面格式化线程（负责描绘图像的线程的父线程）需要知道这一大小，以便正确安置页面中的文字和其他图像。早回复机制使父线程能创建起这种子线程，而后等它送回图像大小信息。到了这一点，两个进程就可以并行地继续下去了。（我们在图12.2里忽略了这个问题。）

Java和C# 把进程创建与start方法调用分开，也能起到类似作用。在我们的浏览器例子里，页面格式化线程在创建了一个描绘图像的线程之后，可以在调用子线程的start方法之前先调用它的get_size方法。get_size方法可以创建与服务器的初始连接，并把大小信息返回父线程。由于get_size是子线程的函数成员，它初始化的任何数据都保存在这个线程对象的数据成员里，包括图像大小和与服务器的连接，线程的run方法可以直接使用它们。

12.2.4  线程的实现

Implementation of Threads

正如第12.2节的开始提到的，一个并发程序里的所有线程通常是在操作系统提供的一个或几个进程上实现的。作为一个极端，我们可以对每个线程使用一个操作系统的进程，另一极端是让程序里的所有线程以多路方式实现在唯一

的一个进程上。在具有单一地址空间，而且进程的代价并不很高的个人计算机里，一个进程实现一个线程的极端方式通常可以接受。在单处理器上只有单一语言的情况下，让所有的线程对应一个进程的方式也可以接受。最常见的情况是，语言实现采用某种中间方式，让可能数量很大的线程运行在不太多的一批进程上（参看图12.8）。

对每个线程用一个独立进程，最主要的问题是许多操作系统的进程（即使是“轻量级”进程）也实在太昂贵，因为它们实现在系统的内核里，对它们的任何操作都需要做一次系统调用。由于这种进程是最通用的，它们提供的许多特征在大部分语言里都不需要，但却必须为之付出代价。（这方面的例子包括独立的地址空间、优先级、簿记信息、信号和I/O接口，所有这些都超出了本书的范围。）作为另一个极端，把所有线程都放在一个进程上也存在两个问题：首先，这种方式从一开始就排除了在多处理器上并行执行；其次，如果当前运行的线程由于系统调用而进入阻塞（例如等待I/O），那么该程序的任何其他线程也不能运行了，因为这个唯一的进程已经被OS挂起了。

在常见的并发性的两层组织结构中（把用户层线程放在内核进程的上面），系统的两个层次上可能出现类似的代码：语言运行系统在一个或几个进程上实现线程，很像操作系统在一个或几个物理处理器上实现进程。为了尽可能减少同步延

迟，多处理器操作系统可能设法把属于同一应用的不同进程安排到不同的处理器上同时运行（这一技术也称为协同调度或成组调度）。它也可以采用另一种方式，让一个应用排他性地使用所有处理器的某个子集合（这种技术称为空间共享或处理器划分）。这些内核层的问题也超出了本书的范围，下面我们将集中关注用户层线程。

典型的用户层线程是在协程（8.6节）的基础上构造起来的。请回忆一下，协程是一种顺序性的控制流机制，按照设计，它是在一个操作系统进程上实现的。程序员可以通过调用transfer操作挂起当前协程并唤醒另一个特定协程。transfer的参数通常是被唤醒协程的上下文块指针。

为了把协程改为线程，我们可以通过三个步骤：第一步，通过实现一个调度器，把transfer的参数隐藏起来，在当前线程交出处理器时，由调度器去选择下一个进入运行的线程；第二步，我们要实现一种强占机制，以便能按某种常规的方式自动挂起当前线程，以便给其他线程提供运行的机会；第三步，我们需要多个OS进程能共享描述线程集合的数据结构，这样才能使线程可以运行在任何进程上，而这些进程可能运行在不同的处理器上。

单处理器调度

图12.9展示了一个调度器使用的数据结构。在任何特定时刻，一个线程或者是被阻塞的（例如为了同步），或者是可运行的。某个可运行线程可能正实际地在某个处理器上运行，也可能正在等待自己的运行机会。那些可运行但当时并没有运行的线程的上下文块驻留在一个称为就绪表的队列里。那些由于调度器同步而阻塞的线程的上下文块，驻留在与它们所等待的条件相关联的数据结构里（通常也是队列）。如果需要把处理器交给其他线程，正在运行的线程就应该去调用调度器：

如果一个线程希望在未来的某个时刻再次运行，那么它在调进调度器之前，就必须把自己的上下文块放入某个适当的数据结构。如果它是由于某种公平性的原因而阻塞（例如为了让其他线程有运行的机会），那么它就应该把自己的上下文块放入就绪队列：

当线程为了同步而阻塞自己时，应该把自己加入与等待条件相关联的队列里：

当正在运行的线程执行了一个操作，使得某个条件变成真的时候，它就会从相关的队列里去掉一个或多个线程，并将它们加入就绪队列。

当一个线程可能运行很长一段时间，同时还有其他可运行线程时，就出现了公平性问题。即使是在单处理器上，为了给并行的活动一个幻觉，我们也需要保证每个线程都能经常得到处理器“片段”。在合作式的多线程中，任何长期运行的线程都必须显式地不时交出处理器（例如在各循环的顶部），以使其他线程能够运行。正如第12.1.2节所说的，这种方式将允许没有正确写好的线程独占处理器。即使线程都写得很好，因为不同线程的yield（交出处理器的操作）之间的时间间隔可能不同，这种方式也会产生实际的非公平性。

强占

理想的情况是，我们希望能公平地按某种相对较小的粒度（例如每秒许多次）来安排处理器，不需要各线程显式调用yield。在许多系统里，我们可以在语言实现中利用时钟信号完成强占式多线程。为完成线程间的切换，我们要求操作系统（它能访问硬件时钟）在未来某个特定时刻给当前运行进程发一个信号。OS处理这种信号的方式是把当前进程的上下文（寄存器和pc）保存到当前栈顶，并把控制传给语言运行系统里事先指定的一个特殊的处理器例程。一旦这个处理器被调用，它就会去修改当前运行线程的状态，使该进程看起来就像是刚刚调用了标准的yield例程。而后这个处理器“返回”到这个yield例程，由它把控制传递给另外的某个线程，就像刚才运行的那个线程自愿放弃了对进程的控制似的。

不幸的是，这种信号可能在任何时刻到达，这一事实将引起对调度器的自愿调用和由于强占而触发的自动调用之间的竞态。为了阐释这个问题，现在假定在有一个信号到达时，当前运行进程刚刚在yield里把当前运行线程放入就绪队列，正要去调用reschedule。当信号处理器通过“返回”进入yield时，进程就会第二次把当前线程放入就绪队列。如果将来某个时刻这个线程由于同步而阻塞了，位于就绪表里它的第二个入口就会导致它又立即投入运行，而此时它实际上应该等待。更糟糕的问题是，如果信号出现在enqueue中间，就绪队列甚至可能不再是结构良好的队列。为了消除这种竞态以避免就绪表被破坏，线程包通常都禁止在调度器调用期间发送信号。

要使这种约定能起作用，调用reschedule的每处代码都必须在调用之前先禁止信号，而且必须在调用之后重新允许它们。由于reschedule里包含了对transfer的调用，因此就可能需要在一个线程里禁止信号，而后在另一个线程里允许。

现在事情已经很清楚了，sleep_on例程也必须假定信号是由调用者禁止和允许的。要看是什么原因，我们假定线程先检查了一个条件并发现它为假，而后就调用sleep_on把自己挂入与该条件相关的队列。再假定在时钟信号正好出现上述的条件检查之后，而且又在调用sleep_on之前，最后，我们再假定信号之后被允许运行的线程把条件变为真。由于第一个线程没机会把自己放入有关条件的队列，第二个线程也就不可能找到它并使它重新变为可运行的。当第一个线程重新运行时，它将立即挂起自己，而且可能永远也不会再醒过来。为了关闭这一时间窗口，保证内部并发事件不会影响程序的正确性，调用者必须保证在检查条件之前禁止信号：

在单处理器系统中禁止这种信号，就能保证有关的检查和睡眠动作出现在一个原子操作中，也就是说，从其他线程的观点看，它们总是“一下子”就做完的。

多处理器调度

有几种并发语言（例如Distributed Processes [Bri78] 和Lynx [Sco91]）是显式非并行的，也就是说，语言的语义保证在任何时刻都只有一个线程在特定的地址空间里运行，线程之间的切换只出现在代码中某些定义良好的点。当然，大多数并发语言都允许线程并行地运行。如我们在12.2节指出的，从程序员的观点看，真正的并行（在多处理器上）与基于时钟中断而在不同线程之间切换的“准并行”系统并没有什么差别。在这两种情况中，应用系统里的线程都需要显式同步，以便应对各种竞态条件。

我们可以扩充前面的强占式并行包，使之能运行在OS提供的多个进程上，方法就是做出一种安排，使这些进程能共享就绪表和相关数据结构（条件队列，等等。注意，这时每个进程有自己独立的current_thread变量）。如果这些进程运行在共享存储器的多处理器系统的多个处理器上，那么就有可能出现多个线程同时运行的情况。如果这些进程共享同一个处理器，那么只要有一个进程没在操作系统里阻塞，程序还是有可能向前进展的。任何可运行线程都被放在就绪表里，从而成为这个应用的任何进程都可以执行的候选线程。当某个进程调用reschedule时，前面例子里一直在用的基于队列的就绪表就把等待时间最长的线程送给它。采用更精细的调度器的就绪表可以优先选择交互式线程，或者时间攸关的线程，或者那些上次在当前处理器上运行的线程，因为其数据有可能还在缓存里。

正如强占会引进对调度器操作的自愿调用和自动调用之间的竞态一样，真的或准的并行性也会引起不同OS进程之间调用的竞态。为了消除竞态，就必须实现更多的同步，以保证在各进程里的调度器操作都是原子的。我们将在12.3.2节回到这一问题。

10.   请解释协程、线程、轻量级进程、重量级进程之间的差异。

11.   什么是准并行？

12.   请描述作业袋程序设计模型。

13.   什么是忙等待？什么是它的主要替代物？

14.   请列举出4种显式并发的程序设计语言。

15.   为什么消息传递程序不需要显式的同步机制？

16.   在基于语言的和基于库的并发实现之间有那些权衡因素？

17.   请说明数据并行和作业并行之间的差异。

18.   什么是组合通信？

19.   请描述在并发程序里创建新的控制线程时常用的6种不同语法结构。

20.   在什么意义上fork/join比co-begin的功能更强？

21.   Java里的线程池是什么？其用途是什么？

22.   两层线程实现是什么意思？

23.   什么是就绪表？

24.   请说明如何基于协程逐步实现调度、强占和（真）并行。