本书的主要部分集中讨论顺序程序，也就是那种只有一个活动的执行上下文的程序。如我们在第6章所见，顺序性是命令式程序设计的基本特性，它通常也隐含在说明性程序设计里，出现这一情况，部分地是由于函数式和逻辑式程序一般都包含着一些命令式的特征，部分地是由于人们需要开发说明性程序的命令式实现和概念模型（如应用序归约、带回溯的反向链等），虽然这些语言的语义原本可能并不需要这种模型。

与此相对应的，说一个程序是并发的，就意味着它包含了多于一个活动的执行上下文，即多于一个“控制线程”。并发性的出现至少有三方面的重要原因。

1.     为了反映一些问题的逻辑结构。许多程序，特别是各种服务器和图形应用，必须同时维护一批在很大程度上相互独立的“作业”的轨迹。构造这种程序的最简单最合逻辑的方式，就是用一个独立的控制线程表示一个作业。我们已经在讨论协程时（8.6节）接触到这种“多线程”结构，在12.1.2节还要在回到这个问题。

2.     为了应对相互独立的多台物理设备。有些软件从本质上说必须是并发的。操作系统可能在任何时候被某台设备中断，它需要用一个上下文表示在中断之前正在做的事情，用另一个上下文表示中断本身。与此类似，进行实时控制的系统（例如在一个工厂里，甚至在一部汽车里）很可能包含了许多处理器，每个连接到一台独立的机器或设备。每个处理器有自己的控制线程，它们必须与在其他处理器上运行的线程交互，以实现整个系统的整体行为。从某种意义上看，互联网上的消息路由软件是一个非常大的并发程序，运行在遍布世界的数以千计的服务器上。

3.     通过同时在多部处理器上运行以提高性能。即使并发不是由程序结构或其运行所在的硬件强制要求的东西，我们也常常能通过让多个处理器同时做一个问题的相关工作而提高系统的性能。利用大量的处理器并行运行可能得到很大的速度提升。

12.1节包含对并发程序设计的历史的一个简短回顾，其中强调指出了并行软件和应用的主要优势，举了一些多线程程序的例子（甚至是在单处理器上），概述了现代多处理器系统的体系结构特征。12.2节里概述了在应用中表述并行性的多种不同方式，介绍了通信和同步的共享内存方式和消息传递方式，并注意到它们既可以通过显式并发程序设计语言实现，也可以通过使用库程序包的方式在常规的顺序语言里实现。我们还基于协作程序的概念，解释了语言或库怎样构造线程并调度它们。在剩下两节（12.3节和12.4节）里，我们要考察共享内存和消息传递的细节。有关共享内存一节里的大部分时间在讨论同步问题。

12.1  基础和动力

Background and Motivation

并发性并不是什么新想法，有关并发程序设计的大部分理论基础工作是在20世纪60年代提出的，Algol 68已经包含了并发性程序设计特征。然而，对并发性的广泛兴趣却是相对较新的现象，其根源部分在于低价的多处理器系统的可用性，部分在于图形、多媒体和基于互联网的应用的蓬勃发展，用并发的控制线程描述这些应用显得特别自然。

在典型的计算机系统里，并发性问题出现在许多不同层次上。在数字逻辑层，几乎所有事情都是并行发生的，信号在数以千计的连线上同时传播。在这层之上，现代处理器里的流水线和超标量特征的设计就是为了利用经过良好调度的程序里的指令级并行性。在这一章里，我们将集中关注中尺度和大尺度上的并发性，这些并发性由程序员可以看到的结构的语义表示，在具有多部处理器的机器中有可能利用它们。在12.1.3节和12.3.6节，我们还会提到在专用的向量处理器可以利用的一种中间层次的并行性。

12.1.1  简单历史

A Little History

最早的计算机是单用户的机器，采用独占模式：人们登记一段时间，在这段时间他们将排他地占用整个计算机硬件。不幸的是，虽然这种单用户机器在今天有很好的经济性，在20世纪40年代后期却是过于昂贵了，那时最便宜的计算机的价值也达几百万美元。为了使计算机在一个用户检查输出或修改程序错误时可

以不闲置，计算机中心很快就转到了另一种操作模式，其中的用户以离线方式（例如在打孔机上）创建自己的作业（程序源代码和输入），而后由操作员把作业输入计算机执行。操作员可以常规性地维护一批排好队的作业，以穿孔卡片或磁带形式等着计算机输入。每个程序的最后一个操作都是把控制转回一个驻留的监控器程序（操作系统的一种初步形式），该程序立即把下一个程序读入内存，以便在当前作业或下一个作业里执行它，不需要操作员的干预。

不幸的是，在这种简单形式的批处理方式中，处理器仍然可能经常处于闲置状态，特别是在商务应用领域，这方面的应用常常需要从卡片或磁带读入大量数据记录，而处理每个记录只需要相对很少的计算。为执行一次I/O操作（把结果写到打印机或磁带，或者把新程序或输入数据读到内存），简单批处理系统里的处理器都要给I/O设备送一个命令，而后以忙等待方式等到有关工作完成，在其间不断检查相应设备在完成操作时会去修改的一个变量。假定穿孔卡读入设备每秒能读入4张卡片，在一张卡片的输入期间，一部40-kHz的电子管计算机就白白空耗了10 000条指令。如果在读入下一张卡片之前所需的计算不到10 000条指令，那么计算机的多一半时间就是闲置的！为了利用忙等待中闲置的这些周期，研究者们开发了使I/O与计算重叠进行的技术。特别是开发了中断驱动的I/O，它消除了对忙等待的需要；还有多道程序设计技术，它使多个应用程序可以同时驻留在内存里。这两项新发明都需要硬件支持。前者要求实现中断，后者要求实现内存保护，使一个程序的错误不会破坏另一个程序所占据的内存。

多道程序设计和中断驱动的I/O

在采用多道程序设计的批处理系统里，操作系统维持着许多程序的轨迹，知道哪些程序正在等待I/O结束，哪些程序是当前可运行的。如果要读入或写出一个记录，当前正在运行的程序就把控制传给操作系统（OS），OS向有关设备送命令，要求它开始执行所需的操作，然后立即把控制传给另一个程序（假定它可运行）。有关设备在完成其操作时会产生一个中断，这又导致处理器转回到操作系统。此时操作系统注意到原来那个程序又变成可运行的了，它就会从所有可运行的程序里选出一个并转移到那个程序去。这样，只有当已经装入内存的所有程序都在等待I/O时，处理器才会闲置。

中断驱动的I/O把并发性引进了操作系统。因为中断可能在任何时刻发生，包括控制已经位于操作系统里的时候，因此中断处理器和OS功能的主要部分也是并发的控制线程。如果中断发生时OS正在修改某个数据结构（例如正在修改可运行程序的队列），而中断处理器也可能使用它，那么中断处理器就可能看到数

据结构正处于某个不一致的状态（见图12.1）。这是竞态问题的一个实例：对应OS主体的线程和对应于设备的线程在到达代码里某些点的问题上出现了“竞争”，在这些点上它们要接触某些公共对象，而整个系统的行为将依赖于究竟哪个线程走在前面。为了保证系统的正确行为，我们就必须对这些线程的动作进行同步，也就是说，通过一些显式的步骤去控制它们中的动作发生的顺序。我们将在12.3节进一步讨论同步问题。应该注意，并非所有竞态条件都是坏东西，有时程序的任意结果都是可以接受的。同步的目标就是消除“坏的”竞态条件，也就是说，消除那些如果出现就会导致程序产生不正确结果的东西。

分时和分布

随着物理内存规模的增大及虚拟内存技术的发展，现在已经可能构造出一些系统，使其中几乎可以允许任意数量的可同时运行的程序。现在的用户不是离线地提交作业，而是坐在终端前面与计算机直接交互。然而，为了提供对击键动作的交互式响应，操作系统就需要实现强占功能。批处理系统只是在一个程序由于I/O而阻塞时才会转到另一个程序，而在强占式的分时系统里，可以是每秒常规地做几次切换工作。这种上下文切换可以防止计算量很大的程序一次占据计算机许多秒钟甚至许多分钟，以致系统无法去访问用户的键盘信息。

分时系统在20世纪70年代早期比较常见，这种系统通过扩充允许数据共享的机制，以及其他可用于正在运行的程序之间通信的机制，把并发性引进了用户应用层。此后不久出现的计算机网络，以分布式系统的方式引进了真正的并行性，其中的程序在物理上相互分离的机器中运行，通过消息的方式相互通信。

大多数分布式系统都反映了我们有关并发性的第二条理由，它们需要并发，以便应对多台物理设备；也有少数系统反映了前面的第三条理由，其中的分布式就是为了利用多处理器所提供的加速性能。并行加速在一类多处理器系统中非常常见，这种系统的设计中包含了具有极高带宽的内部网络。虽然多处理器系统在60年代前后就已经发明出来，但在80年代之前一直是很罕见的东西。世纪之交，这种系统开始出现在用户级的桌面机器里。更复杂的单处理器系统遇到了冷却等方面的挑战，看来在今后的几年里，大部分桌面系统都将使用包含多个简单处理器的单一芯片。

12.1.2  多线程程序的不同情况

The Case for Multithreaded Programs

我们有关并发性的第一条理由是它反映某些特定应用的逻辑结构，这种说法在前面章节里也出现过多次。在7.9.1节里我们注意到，交互式I/O常常必须中断当前程序的执行。以视频游戏为例，在连续更新屏幕图像的同时，我们还必须处理击键和鼠标或游戏棒动作。在构造这种程序时，最方便的方式就是把输入处理表示为一些并发控制线程，使它们与一个或多个更新屏幕的线程共存。我们在8.6节考虑了屏幕保护程序，其中利用协程使文件系统的“完整性”检查与屏幕上运动图形的更新交替进行。在那里我们还考虑了离散事件模拟，其中用协程表示某个真实世界里的主动性物体。

离散事件模拟的语义要求事件在特定的时间点自动发生，协程提供了一种自然的实现方式，但也只能一次执行一个事件。而我们的其他例子——实际上是大多数“自然并发”的程序——所需要的都不是这种协程语义。通过为每个并发作业设定一个线程（而不是协程），我们将高兴地看到，如果存在多个可用处理器，这些作业就可以并行前进了。与此同时，我们也把确定哪个线程在哪个时刻可以运行的责任由程序员转移到语言的实现。

近年来，由于基于万维网的应用的发展，对多线程程序的需求已经变得特别明显了。在如Firefox或Internet Explorer浏览器里（见图12.2），通常都存在着多个同时活动的不同线程，为完成其工作，每个线程通常都要与远程的服务器（可能非常慢）通信许多次。当用户点击一个链接时，浏览器就会为这个特定的文件

请求创建一个线程。除了那些极小的页面外，这种线程都会收到长长的一系列消息“包”，线程必须随着消息包的到来去格式化它们，以便展示到屏幕上。这种格式化工作就像排版，线程必须访问各种字型，拼装起单词的序列，并把单词序列分割成行。对页面里的许多特殊标志，格式化线程还可能派生出其他线程，例如每个图像用一个线程，一个线程做背景（如果有背景），每个表格用一个线程做格式化，可能需要多个线程处理各种框架。这样派生出的每个线程都可能与服务器通信，以获得完成自己的特定工作所需的信息（例如图像的内容）。与此同时，用户还可能访问菜单里的项目，要求创建新的浏览器窗口，编辑书签，修改首选项目，如此等等，所有这些都是与页面的绘制同时进行的。

多线程的使用可以保证相对较快的操作（例如正文的显示）不需要等待较慢的操作（例如显示很大的图像）。无论何时某个线程被阻塞（由于等待消息或I/O），实现就会自动切换到另一个线程。在强占式的线程包里，实现还可以在其他时刻进行线程之间的切换，以保证没有线程可以霸占处理器。如果有读者还记得早期的更顺序性的浏览器的情况，就会看到采用多线程方式的浏览器在接受性能和反应速度方面与它们明显不同。

另一方式：指派循环

如果没有语言或库对线程的支持，浏览器就必须采用一种更顺序性的结构，或者是把对所有可能引起延迟的事件的处理都集中到一个指派循环（参看图12.3），用一个与指派循环关联的数据结构保存浏览器里所有尚未完成的作业的轨迹。每个作业的状态都可能很复杂。对于高层次的页面绘制作业，其状态必须表明已经接收到哪些数据包，哪些还没有收到。它还需要标识页面的各种子作业（图像、表格、框架等），以便在用户点击“停止”按钮时，可以找到所有这些东西并回收它们的状态。

为了保证很好的交互响应，我们还必须保证continue_task的任何子动作都不需要很长的执行时间。事情很清楚，如果在某个时刻需要等一个消息，那么就必须停止当前的动作。希望从文件读入时也必须停止当前动作，因为磁盘操作非常慢。最后，如果任何作业所需要的计算时间长于十分之一秒（这是人可观察的典型阈值），那么就必须把这个作业划分成一些片段，在片段之间保存状态并回到指派循环的开始。这些考虑也意味着在循环最上面的条件里必须覆盖了所有同步事件，进一步说，对循环条件的求值也必须与所有由于计算时间长而划分出来的作业的继续执行交错进行。（在实践中，我们可能需要比简单交错更复杂的机制，以保证任何输入驱动的或计算密集的作业都不会长期占用某些共享资源。）

除了分割子作业和保存状态的复杂性之外，指派循环的主要问题就是它隐藏了程序本身的算法结构。如果不是那些可能引起延迟的操作需要不时返回指派循环的顶部，每个作业（接收一个图像、绘制一个图像、穿过嵌套的菜单等）原本都可以用标准控制流结构很好地描述。从效果上看，这种指派循环把程序的内部翻了出来，把对作业的管理变成程序里显式的东西，作业内部的控制流反而变成

隐含的了。这样做带来的复杂性，与我们在6.5.3节试图用迭代器对象枚举递归集合时遇到的情况类似。与真迭代器一样，线程包也能把程序转回正确的形式，使作业（线程）的管理变成隐式的，而作业内部的控制流变成显式的。

个人计算机

随着个人计算机的发展，操作系统历史中的大部分情况又重复了一遍。早期的PC执行忙等待I/O并且一次运行一个应用。随着微软Windows系统和MacOS的Multifinder版本的开发，PC供应商为系统增加了同时在内存里维持着多个程序的能力，以及在它们与I/O之间来回切换的能力。当然，由于PC是单用户机器，对强占性的需求没有在多用户系统里那么迫切。在很长时间里，人们都认为让当前运行程序长期霸占处理器是可以接受的事情，因为不管怎么说，这个程序也是（那一个）用户希望运行的。然而，随着PC变得越来越复杂，用户开始要求线程的并发性执行，就像在浏览器里的情况，还希望有“后台”线程去更新窗口、检查电子邮件、照顾慢速的打印机，等等。从某种意义上看，只要每个程序都能“志愿”在计算中的一些良好定义的“干净点”交出处理器控制，就可以满足后台计算的需要。这类“合作式多道程序设计”可以在Windows 3.1和MacOS版本7中看到。不幸的是，如果有些程序不能按所需的频繁程度交出控制，合作式多道程序设计系统就无法保证一致的响应，这种情况使用户越来越感到愤怒。Windows 95把强占加入32位应用，Windows NT和MacOS X把强占加入所有程序，并在独立的地址空间里运行它们，使一个程序的错误不会破坏另一个程序，也不会导致整个系统垮台。

12.1.3  多处理器体系结构

Multiprocessor Architecture

单机箱（非分布式）的并行计算机可以分为比较广泛的两类，一类计算机中的处理器以共享方式访问公共的存储器，另一类中的处理器只能通过消息相互通信。术语多处理器系统通常用于指共享存储器的机器，偶然也被用于指基于消息传递的机器。一个多处理器系统通常放在一个机柜里，其中的多个处理器不但共享内存，还共享磁盘、电源和操作系统的同一份拷贝。近年还出现了计算机集群的快速增长，在这种系统里，一批物理上能完全独立操作的单处理器或小型多处理器被安装在共用的一组机架中，通过高速系统级网络连接起来，作为一个整体进行管理。大规模的在线服务系统，例如Google、Amazon或eBay，通常都是由成百甚至成千台处理器构成的集群。有时也能听到人们用术语多机系统指采用消息传递的单机架的机器。在20世纪八九十年代，多机系统在科学计算与数据库应用领域很流行，然而在最近一些年，这类系统已在很大程度上被集群和大型的多处理器取代了。

小型的共享存储器的多机系统通常是对称的，这里的对称是指所有内存与所有处理器之间的距离相同。大型的共享内存多处理器通常采用分布式存储器体系结构，其中每组存储器在物理上紧邻一台特定处理器或不大的一组处理器。任何处理器都可以访问其他处理器的存储器，但访问局部存储器的速度更快一些。小型机器常被称为SMP，表示“对称多处理器（symmetric multiprocessor）”结构。大型系统有时称为NUMA机器，表示“非统一的存储器访问（nonuniform memory access）”。

从20世纪60年代后期开始，在高端超级计算机市场上，所谓的向量处理器一直占据主导地位。这种机器提供了一些特殊指令，能把同样操作应用于一个数组里的每一个元素。向量指令很容易流水线化，它们在许多科学计算程序里非常有用，特别是对于那些程序员可以明确标明某些循环的迭代能并发执行的程序（12.2.3节 [例12.9] 和12.3.6节将讨论这种循环）。当然，传统上的向量机是专用的、多芯片设计的。今天通用微处理器的不可动摇的优势已经严重地侵蚀了它们的市场份额。与此同时，向量机的思想也在微处理器的世界里发挥着作用，例如对于奔腾处理器指令集的MMX扩充就是一个例子。

从语言或库的实现者的角度看，基于消息的多机系统与共享存储的多处理器系统之间的最重要差异，就在于前者里面的通信需要位于连接两端的处理器的主动参与，一个传送，另一个接收。在共享存储的机器里，处理器可以直接读写远程的存储器，无需远程处理器的协助。在大多数情况下，远程读写采用的是与局部读写完全一样的接口（也就是说，也用装载和保存指令）。

互联网络

无论采用什么样的通信模型，并行计算机都需要采用某种类型的互联网络，把它的处理器和存储器连到一起。大多数小型的对称机器用一条总线实现互连；少数几种采用纵横开关网，使每部处理器与每块存储器都有直连，形成了一个完全二部图。大型机器可以分为两类，分别采用间接的或者直接的网络。其中间接网络就像是一张围在圆柱体外面的渔网（见图12.4），网上的结是消息路由开关。在直接网络里没有内部开关，所有连接都从一个结点直接到另一个结点。间接网络和直接网络都有许多拓扑变形。间接网络的设计通常要求从一个结点到任意其他结点的距离是O(logP)，这里的P是结点总数。直接网络中结点间的最大距离

可能达到O()。实践中有一种称为虫洞路由的技术，可以使与远距离结点的通信几乎与邻接结点一样快。

存储器一致性

在任何基于新型微处理器构造起来的机器里，系统的性能都高度依赖于快速（低等待时间）的存储器访问。为使延迟达到最小，几乎所有机器都要依靠缓存。在消息传递机器里，每个处理器有自己的存储器。然而，共享存储机器里的缓存却可能引起严重的问题：除非我们做一些特殊的事情，否则当某处理器缓存起一个特定存储器位置时，它将无法看到其他处理器对该位置的修改。这个问题（如何保持被缓存的存储器位置的统一）称为一致性问题（参看图12.5）。在基于总线的对称机器上，这个问题相对比较容易解决，这里的通信介质的广播特性使缓存控制器可以窃听（窥视）其他处理器的存储器通信情况。当另外的某个处理器向一个位置写，而这一位置包含在局部缓存里的情况下，控制器或者是直接从总线把值抓过来，或者（更常见）把受影响的缓存行设置为非法，迫使处理器在下次需要这个行的时候回到存储器（或其他处理器的缓存）。基于总线的缓存一致性算法现在已经成了标准，成为多数商品微处理器的内部组成部分。对于大型机器，由于缺乏广播式的总线，缓存一致性变成一个更困难的问题。虽然也有可用的商品实现，但这个问题仍然是一个活跃的研究课题。

在2005年，有数以十计的厂商提供小型的基于总线的SMP，基于采用x86、

PowerPC、Sparc、AMD64（Opteron）或IA-64（Itanium）处理器。也有几家公司最近发布了，或者正在开发单芯片的多处理器。大型的缓存一致性的共享存储多处理器机器也可以从几家厂商购买，包括Sun、HP、IBM和SGI。与此相对应，Cray X1有一个共享的一致性的地址空间，其中的远程位置绝不缓存。这个领域一直处于动荡不定中，最近几年已经有若干大型并行机器和厂商从市场上消失了，也有几种新机器正计划在不久的将来面世。

1．  请说明并发的理由，为什么人们要写并发程序？为什么最近一些年人们对并发的兴趣不断增长？

2．  请叙述计算机操作从独占模式到批处理，再到多道程序和分时的发展历程。

3．  什么是中断驱动的I/O？它与并发有什么关系？

4．  什么是竞态条件？

5．  什么是上下文切换？什么是强占？

6．  什么是指派循环？其优点和缺点有哪些？

7．  请解释多处理器系统与集群之间的不同。

8．  请解释多处理器缓存中的一致性问题。