华章程序员书库
点击查看第二章
并发模式与应用实践
Concurrent Patterns and Best Practices

[印度]　阿图尔·S.科德（Atul S. Khot）　著
徐　坚　译

第1章

并发简介
什么是并发和并行？我们为什么要研究它们？本章将介绍并发编程领域的诸多方面。首先简要介绍并行编程，并分析我们为什么需要它，然后快速讨论基本概念。
“巨大的数据规模”和“容错”作为两股主力推动并发程序设计技术不断向前。在我们阅读本章时，里面的一些示例将涉及一些集群计算模式，例如MapReduce。对当今的开发人员来说，应用程序扩展性是非常重要的概念，我们将讨论并发如何帮助对应用程序进行扩展。水平扩展（https://*.com/questions/11707879/difference-between-scaling-horizontally-and-vertically-for-databases ）是当今大规模并行软件系统背后的关键技术。
并发使得并发实体之间必须实现通信。我们将研究两个主要的并发模型：消息传递模型和共享内存模型。我们将使用“UNIX shell管道”描述消息传递模型，然后，我们将描述共享内存模型，并讨论显式同步为何带来如此多的问题。
设计模式是上下文中出现的设计问题的解决方案。通过掌握模式目录，有助于我们针对特定问题提出一个更好的设计方案，本书将介绍常见的并发设计模式。
本章最后将介绍一些实现并发的替代方法，即actor范式和软件事务性内存。
本章将介绍以下主题：

• 并发
• 消息传递模型
• 共享内存和共享状态模型
• 模式和范式

如需完整的代码文件，可以访问https://github.com/PacktPublishing/Concurrent-Patterns-and-Best-Practices。

1.1　并发轻而易举

我们从一个简单的定义开始本章的学习。比如，当事情同时发生时，我们说事情正在并发。然而，就本书而言，只要可执行程序的某些部分同时运行，我们就是在进行并发编程。我们使用术语“并行编程”作为并发编程的同义词。
这个世界充满了并发现象。举个现实生活中的例子，假设有一定数量的汽车行驶于多车道高速公路，然而，在同一车道上，汽车需要跟随前面的车辆，在这种情况下，车道就是一种共享资源。
当遇到收费站时，情况会发生变化，每辆车会在其车道停留一两分钟去支付通行费和拿收据。当收费员对一辆车收费时，后面的车辆需要排队等待。但是，收费站有不止一个收费窗口，多个窗口的收费员会同时向不同的汽车收费。如果有三个收费员，每人服务一个窗口，那么三辆车可以在同一时间点支付费用，也就是说，它们可以并行接受服务，如图1-1所示。
请注意，在同一队伍排队的汽车是按顺序缴费的。在任何给定时刻，收费员只能为一辆车提供服务，因此队列中的其他车需要等待，直到轮到他们。
当我们看到一个收费站只有一个收费窗口的时候会感到奇怪，因为这不能提供并行的收费服务，严格的按顺序缴费会使大家不堪忍受。
当车流量过大（比如假期）时，即使有很多收费窗口，每个窗口也都会成为瓶颈，用于处理工作负载的资源会变得更少。

1.1.1　推动并发

让我们回到软件世界，比如你想边听音乐边写文章，这不是一个基本需求吗？是的，你的电子邮箱程序也应该并行工作，以便你可以及时收到重要的电子邮件。如果这些程序都不能并行运行，很难想象人们怎么工作。
随着时间的推移，软件占用的内存变得越来越大，需要更多更快的CPU。例如，现在的数据库事务每秒都在增加，数据处理需求超出了任何一台机器的能力，因此，人们采用了分治策略（divide and conquer strategy）：许多机器在不同的数据分区上同时工作。
另一个问题是芯片制造商正在触及芯片速度的极限，改进芯片以使CPU更快的办法具有固有的局限性。有关此问题的清晰解释，请参见http://www.gotw.ca/publications/concurrency-ddj.htm。
今天的大数据系统每秒处理数万亿条消息，并且全部使用商业硬件（我们在日常开发中用的普通硬件），没有什么特别的，它们就像超级计算机一样强大。
云的兴起使得配置能力掌握在每个人手中。你不需要花太多时间来测试新的想法，只需租用云上的一个处理基础架构，即可测试并实现你的想法。图1-2显示两种扩展的方法。

*基础设施的设计主要有两种扩展方法：水平扩展与垂直扩展。水平扩展本质上意味着使用分布式并发模式，它具有成本效益，是大数据领域的一个突出理念。例如，NoSQL数据库（比如Cassandra）、分析处理系统（比如Apache Spark）和消息代理（比如Apache Kafka）都使用水平扩展，这意味着分布式和并发处理。
另一方面，在单台计算机中安装更多内存或提高处理能力是垂直扩展的一个很好的例子。在网站https://www.g2techgroup.com/horizontal-vs-vertical-scaling-which-is-right-for-your-app/ 中可以看到两种扩展方法的比较。
我们将研究水平扩展系统的两个常见并发主题：MapReduce和容错。

1.1.1.1　MapReduce模式

MapReduce模式是需要并发处理的常见例子。图1-3显示一个单词频率计数器，如果有数万亿字的文本流，我们需要查看文本中每个单词出现的次数。该算法非常简单：我们将每个单词的计数保留在哈希表中，单词为键，计数器为值。哈希表允许我们快速查找下一个单词，并递增相关值（计数器）。

在给定输入文本大小的情况下，单个节点的内存无法容纳整个哈希表。通过使用Map-Reduce模式，可以为并发提供一种解决方案，如图1-3所示。
解决方案是分治策略：维护一个分布式哈希表，并运行适用于集群的相同算法。
主节点读取并分析文本，然后将其推送到一组“从属处理节点”（简称为“从节点”，与“主节点”对应）。这个想法是以一种由一个从节点处理一个单词的方式去分发文本。例如，给定三个从节点，如图1-3所示，我们将按范围划分：将以字符{a..j}开头的节点推送到节点1，将以{k..r}开头的节点推送到节点2，再将其余以{s..z}开头的节点推送到节点3。这就是映射的部分（将工作分散）。
一旦流处理完之后，每个从节点将其频率结果发送回主节点，主节点打印结果。
从节点全部都在同时进行相同的处理。请注意，如果我们添加更多的从节点（就是说，如果我们水平扩展它），算法将运行得更快。

1.1.1.2　容错

另一种常见的方法是建立故意的冗余来提供容错，例如，大数据处理系统（如Cass-andra、Kafka和ZooKeeper）不能承受彻底崩溃。图1-4显示如何通过并发复制输入流来防止从节点发生故障。这种模式通常用于Apache Kafka、Apache Cassandra和许多其他系统。

图1-4的右侧显示数据流被复制给冗余的机器。
在任何一个节点出现故障（硬件故障）的情况下，其他冗余节点都将取而代之，从而确保整个系统永远不会宕机。

1.1.2　分时

在现实生活中，我们也同时执行着许多任务。我们专心处理一项任务时，如果另一项任务也需要处理，我们将会切换到它，优先处理它，然后再回到上一项任务。让我们看一个真实例子：办公室接待员如何处理他们的任务。
当你来到一个办公室时，通常会有接待员接待你并询问你有什么事。这时办公室的电话响了，接待员像平常一样接听电话，并在与对方通话一段时间后，告诉你等一下。在你等待一段时间后，接待员会继续与你对话。该过程如图1-5所示。
接待员让各方分享她的时间，她采用的这种方式工作使得每个人都可以分享她的一部分时间。

现在，记住上面说的收费站和接待员，然后用CPU内核替换收费员，用任务替换汽车，你就可以获得当今并发硬件的基本模型。如果我们将收费员的数量从3个增加到6个，我们就能将并行（同时）服务的汽车数量增加到6个。那么将会产生一个令人愉悦的结果：排队的汽车会散开，每辆车都会更快得到服务。当我们执行并发程序时也是如此，因此，工作效率总体上会大幅度提升。
就像接待员同时做多件事一样（比如访客之间时间共享），CPU将其时间共享给进程（正在运行的程序），这就是在单个CPU上支持并发的方式。

1.1.3　两种并发编程模型

并发意味着多个任务并行地实现同一个目标。类似群体中的沟通一样，我们需要与并发执行任务的实体进行通信和协调。
例如，假设我们通过一个UI来呈现前面提到的词频计数器。用户上传大文件后单击“开始”按钮，开启了一个长时间运行的MapReduce作业。我们需要把这项工作分散到各个从节点上，同时，为了分配工作量，我们需要一种与它们通信的方式。图1-6显示此系统中所需的各种通信流。

如果用户改变主意并中止作业，我们需要把“停止消息”告诉每个并发实体，因为继续下去是没有用的。
并发通信有两个著名的模型：消息传递模型和共享内存模型。图1-6是消息传递模型。
我们首先以著名的“UNIX shell管道”为例来讨论消息传递模型。紧接着，我们将深入研究共享内存的方法及其相关问题。

1.2　消息传递模型

在深入研究消息传递模型之前，我们将介绍一些基本术语。
当可执行程序运行时，它是一个进程。shell查找可执行文件，使用系统调用与操作系统进行通信，从而创建子进程。操作系统还会分配内存和资源，例如文件描述符。因此，（例如）当你运行find命令（该可执行文件位于/usr/bin/find）时，它将成为父进程shell的子进程，如图1-7所示。
如果你没有pstree命令，可以尝试使用ptree命令替代。ps --forest命令也可以显示进程树。
下面是一个UNIX shell命令在目录树中递归地搜索包含某个单词的HTML文件：

我们在这里看到了一个shell管道。find命令搜索以当前目录为根的目录树，查找扩展名为.html的所有文件，并将文件名输出到标准输出设备。shell为find命令创建一个进程，并为xargs命令创建另一个进程。活动（即正在运行）的程序称为进程。shell还会通过管道将find命令的输出作为xargs命令的输入。
在这里，find进程是生产者，它生成的文件列表会被xargs命令消费。xargs收集一组文件名并对它们调用egrep。最后，输出显示在控制台中。请务必注意，两个进程并发运行，如图1-8所示。

这两个进程相互协作，因此我们实现了递归搜索目录树的目标。一个进程生成文件名，另一个进程搜索这些文件。当这两个进程并行运行时，一旦有合格的文件名，就会立即开始获取结果，这意味着系统响应迅速。
测验：如果这两个进程依次运行会发生什么？系统会如何将find命令的结果传递给xargs命令？
就像在现实生活中一样，协作需要通信。管道是使find进程能够与xargs进程通信的机制，管道既充当协调者，又充当通信机制。

1.2.1　协调和通信

我们需要确保当find进程没有什么可报告时（这意味着它已找到所有符合条件的文件名）egrep也应该停止！
同样，无论管道中的任何进程由于何种原因退出，整个管道也应该停止工作。
例如，这是一个计算1000的阶乘的管道：

管道有三个过滤器：seq、paste和bc。seq命令只打印1到1000之间的数字并将它们放到控制台中，shell的工作是保证把输出送入paste过滤器使用的管道。
现在，paste过滤器只多做了一点点工作就能使用*分隔符连接所有行，并将结果行输出到标准输出，如图1-9的屏幕截图所示。

paste命令写入控制台，shell再次安排输出进入管道。这一次，消费者是bc，bc命令或过滤器能够进行任意精度算术运算，简单来说，它可以执行非常大的计算。
当seq命令正常退出时，会触发管道上的EOF（文件结尾）。这会告诉paste，输入流没有其他内容可读，因此它执行连接，并将输出写入控制台（实际上是管道），然后依次退出。
这种退出导致了bc进程的EOF，因此它计算乘积，将结果打印到标准输出，这实际上是一个控制台，最后退出。这是一个顺序的关闭，不需要做更多工作，系统会自动退出并放弃其他并发进程的计算资源（如果有），这种制造者称为“毒丸”。有关更多详细信息，请参阅https://dzone.com/articles/producers-and-consumers-part-3 。
此时，管道处理完成，我们再次返回shell提示符，如图1-10所示。
参与管道的所有过滤器都不知道父shell已经做了这种协调。框架由较小的部分组成，而这些较小部分本身并不知道他们之间是如何组合在一起的，这种能力是一种很好的设计模式，称为管道和过滤器。我们将看到如何像这样组合成一个中心主题，从而产生强大的并发程序。

当seq进程产生的数字太快时会发生什么？消费者（在这种情况下是paste）会不堪重负么？答案是不会，管道中还内置了一个隐式流控制，这是另一个中心主题，称为背压（back-pressure），其中较快的生产者（或消费者）会*等待，以便较慢的过滤器赶上。
让我们接下来看一下这种“流控制”机制。

1.2.2　流控制

前面提到的管道背后的奇妙想法是：find生产者和xargs消费者彼此不了解。也就是说，你可以使用管道组成任意过滤器，这是著名的管道和过滤器设计模式。shell命令行提供了一个框架，使你可以将任意过滤器组合成一个管道。
它给了我们带来了什么？你可以用意想不到的创造性方式重用相同的过滤器来完成你的工作。每个过滤器只需要遵循一个简单的协议，即接受“文件描述符0”的输入，将输出写入“文件描述符1”，并将错误写入“文件描述符2”。
有关描述符和相关概念的更多信息，可以参阅“UNIX shell编程指南”。我个人最喜欢的是《UNIX Power Tools》第三版，作者是Jerry Peek等。
流控制意味着我们正试图调节某种流。当你告诉别人说话慢点，以便你可以听懂他们要说什么时，你就在试图控制话语的流动。
流控制对于确保生产者（如快速扬声器）不会压倒消费者（例如侦听器）是至关重要的。在之前的示例中，find进程可以更快地生成文件名，egrep进程可能需要更多时间来处理每个文件。find生产者可以按照自己的进度工作，而不用关心缓慢的消费者。
如果管道由于xargs消费较慢而变满，find的输出调用将被阻塞，也就是说，进程正在等待，因此无法运行。这会导致find暂停，直到消费者最终有时间消费一些文件名且管道有一些空闲空间。反之亦然，此时，一个快速消费者阻塞一个空管道。阻塞是一种进程级机制，而find（或任何其他筛选器）并不知道它是否处于阻塞状态。
进程开始运行的那一刻，它将执行find过滤器的计算功能，找出一些文件名，并将它们输出到控制台。图1-11是一个简化的状态图，显示了进程的生命周期。

这个调度状态是什么？如上所述，正在运行的进程可能会被阻塞，等待一些I/O发生，因此它无法使用CPU，所以，它将被暂时搁置一段时间，而其他等待轮到自己的进程则会被给予一次运行的机会。与前面提到的接待员的场景类似，接待员可以让我们坐下来等一会儿，然后继续服务队列中的下一位客人。
另一个想法是，该进程已经运行了分配给它的时间片，因此其他进程应该得到运行机会。在这种情况下，即使进程可以运行并使用CPU，它也会被回退到它的预定状态，等到其他进程使用完各自的时间片，该进程又可以再次运行。这就是抢占式多任务，它使所有进程都有公平的机会。进程需要运行，以便可以做有用的工作。抢占式调度是一种帮助每个进程获得一部分CPU时间片的思想。
然而，还有另一种观点可能会对这一计划产生不利影响，那就是优先级较高的进程优先于优先级较低的进程。
一个真实的例子应该有助于理解这一点。在道路上行驶时，当看到打开警报器的救护车或警车时，我们需要为它们让路。类似地，执行业务逻辑的进程可能需要拥有比数据备份进程更高的优先级。

1.2.3　分治策略

GNU并行程序（https://www.gnu.org/software/parallel/ ）是一个在一个或多个节点上并行执行命令的工具。图1-12显示了一个简单的运行，我们在其中生成10个文本文件并将它们（使用gzip命令）并行压缩。所有可用的内核都用于运行gzip，从而减少了总的处理时间。

其工作的核心原则是分治策略，我们再次看到相同的原理：一个可并行化的作业被分成多个部分，每个部分都被并行处理（从而能重叠处理并减少时间）。该并行程序还允许在不同节点（计算机）上分配运行时间长的作业，从而允许利用空闲（可能未使用）的内核来快速处理作业。

1.2.4　进程状态的概念

上一节中描述的通信可以看作是消息传递，find进程将文件名作为消息传递给egrep进程，或者seq进程将消息（数字）传递给paste进程。一般来说，这种情况下生产者正在向消费者发送消息以供其消费，如图1-13所示。

如图1-13所示，按照设计，每个进程都有自己的状态，并且这个状态对其他进程是隐藏的。进程通过显式消息传递通道进行通信，就像管道引导水流一样。
这种状态的概念对于理解各种即将出现的并发模式来说非常重要。我们可以将状态看作某个处理阶段的数据。例如，paste进程可以使用程序计数器来生成数字，它也可以将数字写入标准输出（文件描述符1；默认情况下是控制台）。同时，paste进程正在处理它的输入，并将数据写入它的标准输出。这两个进程都不关心彼此的状态，事实上，它们甚至对其他进程一无所知。
现实世界充满了封装状态，图1-14显示了一个示例。

如图1-14所示，让邮政部门员工知道顾客的状态（“需要买牛奶”）是违背常识的。对他来说，知道这个没什么用，还可能造成混乱。
同样，员工将继续处理他的日常任务，并有自己的日常状态。作为消费者，我们为什么需要知道他如何管理他的工作内容呢（派送大堆信件）？世界是并发的，世界上的各种实体也隐藏了彼此不必要的细节以避免混淆，如果我们不隐藏内部细节（即状态），就会造成混乱。
当然，可以问一下是否存在全局共享内存，如果有，那么我们可以将它用作消息通道，生产者可以使用所选的共享数据结构将数据放入其中，供随后被消费，也就是说，将内存用作通信渠道。

1.3　共享内存和共享状态模型

要是我们编写一个多线程程序来实现相同的结果又会怎样呢？执行线程是由操作系统调度和管理的一系列编程指令。一个进程可以包含多个线程，换句话来说，进程是一个用于并发执行线程的容器，如图1-15所示。

如图1-15所示，多个线程共享进程内存，但两个并发运行的进程不共享内存或任何其他资源，例如文件描述符。换句话说，不同的并发进程各有自己的地址空间，而同一进程中的多个线程则共享该进程的地址空间。每个线程也有自己的堆栈，该堆栈用于在进程调用之后返回，并且还在堆栈上创建了作用域在本地的变量。这些元素之间的关系如图1-16所示。

如图1-16所示，两个线程都通过进程的全局内存进行通信。有一个FIFO（先进先出）队列，生产者线程t1在其中输入文件名，而消费者线程t2则在条件允许时从中获取队列条目。
这个数据结构有什么作用？它的工作原理与前述管道类似，生产者可以根据需要或快或慢地生产产品，同样，消费者线程根据自身需要从队列中取出产品。两者都按照自己的节奏工作，互不关心，互不了解。
以这种方式交换信息看起来更简单，但是，它带来了许多问题，比如，对共享数据结构的访问需要正确同步，令人吃惊的是，这很难实现。接下来的几节将讨论各种突出的问题，我们还将看到各种回避共享状态模型而转向消息传递的范式。

1.3.1　线程交错—同步的需要

调度线程运行的方式受限于操作系统。诸如系统负载以及机器上每次运行的进程数量等因素使线程调度变得不可预测。让我们来举一个通俗易懂的例子，这就是电影院的座位。
比方说，一部正在上映的电影吸引了大批观众，此时我们需要遵循一个协议，即通过预订座位来确定电影票，图1-17显示基于票务预订系统的规则。

要是错误地将一张电影票同时预订给两个人会怎么样？这将造成混乱，因为两者都会理所当然地试图占据这个座位。
我们有一个框架可以确保这种情况在现实中不会发生，电影院座位由大家一起共享，电影票需要提前预订，这样，上述情况就不会发生了。
同样，线程需要锁定资源（即共享的可变数据结构），问题在于显式锁定，如果正确同步的责任在于应用程序，那么某个人在某天可能会忘记正确地执行同步，然后一切都会失控。
为了说明正确同步的必要性，图1-18显示两个线程共享的整数变量。

如图1-18所示，如果交错恰好是正确的，那么一切可能正常。否则，我们要处理一个丢失更新（lost update）。
相反，就像充当锁的电影票一样，每个Java对象都有一个锁，线程会获取它，并执行状态转换，然后解锁。整个序列会是一个临界区，如果临界区需要改变一组对象，则需要分别锁定每个对象。
通常，我们建议使得临界区尽可能小，我们将在下一节讨论原因。

1.3.2　竞争条件和海森堡bug

丢失更新是竞争条件的一个例子。竞争条件意味着程序的正确性（它的预期工作方式）取决于被调度线程的相对时机，所以有时候它运作正常，有时却不行。
这是一种非常难以调试的情况，我们需要重现一个问题来研究它，还可能在调试器中运行它。但是，困难在于竞争条件难以再现，交错指令的顺序取决于受到环境强烈影响的事件的相对时机。引起延迟的原因可能是其他正在运行的程序、网络流量、OS（操作系统）调度决策和处理器时钟速度发生变化等。包含竞争条件的程序可能在不同时间表现出不同的行为。
图1-19解释了海森堡bug和竞争条件。

这些是海森堡bug ,基本上都是非确定性的，并且很难再现。如果我们通过附带调试器来尝试调试海森堡bug，这个bug可能会消失。
根本没有办法调试和修复这些bug，但有一些支持工具，例如tha工具（https://docs.oracle.com/cd/E37069_01/html/E54439/tha-1.html ）和helgrind（http://valgrind.org/docs/manual/drd-manual.html ），但这些工具是特定于语言或平台的，并不一定证明没有竞争。
显然，我们需要通过设计来避免竞争条件，因此需要研究并发模式。

1.3.3　正确的内存可见性和happens-before原则

还有另一个问题可能导致错误的同步：不正确的内存可见性。关键字synchronized可以防止多个线程都去执行临界区，该关键字同时还可以确保线程的本地内存与共享内存正确同步，如图1-20所示。

什么是本地内存？请注意，在多核CPU上，由于性能原因，每个CPU都有一个缓存，这个缓存需要与主共享内存同步，同时还需要确保缓存一致性，以便在CPU上运行的每个线程都具有共享数据的正确视图。
如图1-20所示，当线程退出同步块时，它会发出“写入屏障（write barrier）”，从而将其缓存中的更改同步到共享内存。另一方面，当线程进入同步块时，它会发出“读取屏障（read barrier）”，所以会以共享内存的最新变化来更新它的本地缓存。
请注意，这同样不容易。实际上，非常有经验的程序员在提出双重检查锁定模式时也会犯错。根据前面的内存同步规则，发现这种看似出色的优化也存在缺陷。
有关此次优化尝试的更多信息请查看https://www.javaworld.com/article/ 2074979/java-concurrency/double-checked-locking--clever--but-broken.html 。
然而，Java的volatile关键字可确保正确的内存可见性，你不需要只是为了确保正确的可见性而执行同步。这个关键字还可以保证排序，这是一种happens-before关系。happens-before关系确保一条语句的所有“写内存”操作对另一条语句是可见的，如下面的代码所示：

由于正在设置的volatile，所有变量值都将被设置为具有happens-before关系。这意味着在设置变量k之后，所有之前的更改都保证已经发生了！因此，保证设置了i和j变量的值，如下面的代码片段所示：

但是，volatile关键字不保证原子性。有关更多信息，请访问http://tutorials.jenkov.com/ java- concurrency/volatile.html 。

1.3.4　共享、阻塞和公平

正如进程有生命周期一样，线程也有生命周期。图1-21显示了各种线程状态，包括可运行、运行中和定时等待状态下的三个线程t1、t2和t3。以下是每个状态的简要说明：

• 新建：刚刚创建Thread对象时，该线程还没有启动。
• 可运行：当在线程对象上调用start()函数时，其状态将更改为可运行。如图1-21所示，一个线程调度器将决定在什么时候调度这个线程运行。
• 运行中：最后，线程调度程序从可运行线程池中选择一个线程，并将其状态更改为运行中，这时线程开始执行，同时CPU开始执行该线程。
• 阻塞：线程正在等待监视器锁定。如前所述，对于共享资源(比如可变内存数据结构)，只有线程可以访问/读取/修改它。当线程被锁定时，其他线程将会被阻止。
• 等待：等待另一个线程执行操作，线程通常在执行I/O时阻塞。
• 定时等待：线程在有限的时间内等待一个事件。
• 终止：线程已被终止，无法返回到任何其他状态。

一旦等待的事件发生，线程就会回到可运行状态。
如图1-21所示，阻塞线程既昂贵又浪费。为什么会这样？请记住，线程本身就是一种资源。让一个被阻止的线程去处理其他有用的事情不是很好吗？
保持较小的临界区是一种公平对待所有线程的方法，没有线程会长时间持有锁（尽管这是可以改变的）。
我们能否避免阻塞线程，而将其用于其他用途？这就引出了异步执行与同步执行的主题。

1.3.5　异步与同步执行

阻塞操作可以说是很糟糕了，因为它们浪费资源。所谓阻塞，我们指的是需要很长时间才能完成的操作。同步执行允许任务按顺序执行，等待当前操作完成，然后再开始下一个操作。例如，拨打电话是同步的，我们拨打号码，等待对方说“你好”，然后继续通话。
而寄信是异步完成的。一个人不会寄出一封信并停止一切活动去等待对方的回复。我们寄出它，然后去做别的事情。在未来的某个时间，我们期待对方的一个回复（如果无法投递信件，则应返回出错信息）。
另一个例子是关于餐馆午餐券的。你支付午餐费并获得一张午餐券，这是一个“承诺”，表示你可以在不久的将来使用它吃午餐。如果柜台前有很长的队列，你可以在此期间做其他事情，过会再来就餐。
这是一个异步模型。
想象一下，如果没有午餐券会发生什么。你付费，然后等待轮到你就餐，当排在队伍前面的用户还没吃完时，你就被阻止了。
同样回到软件世界，文件和网络I/O都有阻塞。使用阻塞驱动器的数据库调用也是如此，如图1-22所示。

我们可以将工作流看作无阻塞任务和有阻塞任务的混合体，而不是阻塞和浪费空闲线程。然后，我们使用future处理阻塞任务：future是一种抽象，表示最终将完成并返回结果或错误。
这是范式中的一个变化，我们开始考虑以不同的方式设计任务，并使用更高级别的抽象来表示它们，例如future（我们之前讨论过），而不是直接处理线程。actor是对线程的另一种抽象，也就是另一种范式。
future提供组合性（composability），它们是单子（monad）。你可以创建future操作的管道来执行更高级别的计算，我们将在后面的章节中看到这一点。

1.3.6　Java的非阻塞I/O

Java NIO（New IO）是Java的非阻塞I/O API。这个NIO是标准Java I/O API的替代品。它提供了诸如通道、缓冲区和选择器这样的抽象。其想法是提供一种可以使用操作系统所提供的最有效的操作的实现，如图1-23所示。

通道只是一个双向I/O流。单个线程可以监视应用程序已打开的所有通道，到达任何通道的数据都是一个事件，并且监听线程会得到它已经到达的通知。
选择器使用事件通知：线程可以检查I/O是否完整，而不需要阻塞。单个线程可以处理多个并发连接。
这转化为两个主要好处：

• 你需要的线程更少。由于线程也会占用内存，因此内存管理的开销会减少。
• 当没有I/O时，线程可以做一些有用的事情，这为优化提供了可能，因为线程是一种有价值的资源。

Netty框架（https://netty.io/）是一个基于NIO的“客户端-服务器”框架。Play框架是基于Netty的高性能、反应式的Web框架。

1.4　模式和范式

脱离显式状态管理是编程中一个非常突出的主题。对于共享状态模型，我们总是需要更高级别的抽象，正如前面所解释的，显式锁定并不能解决问题。
我们将在本书中学习的各种并发模式都试图避免显式锁定。例如，不变性是一个主要主题，它为我们提供了可持久化的数据结构。可持久化的数据结构在写入时执行智能复制，从而完全避免突变，如图1-24所示。

如图1-24所示，原始链表有三个元素{1,2,3}，链表的头元素的值为1，线程T1开始计算链表中元素的个数。
在任何时间点，线程T2都可以将元素添加到原始链表中，并且这不会扰乱线程T1的世界，它仍然应该可以看到原始链表。换句话说，T1看到的链表版本得到了保存。链表中发生任何更改都会导致创建新版本的数据结构，因为所有的数据结构版本都在需要的时候存在（即可持久化），所以我们不需要任何锁定。
同样，线程T2删除前两个元素是通过将其头部设置为第三个元素来实现的；再次，这将不会扰乱T1和T2所见的状态。
这基本上就是写时拷贝技术（copy-on-write），不可变性是函数式编程语言的基石。
典型的并发模式是主动对象（active object）模式。例如，如何使用来自多个线程的遗留代码库？代码库是在不考虑并行性的情况下编写的，并且状态遍布四周，几乎不可能弄明白。
brute-force算法可能是将代码打包在一个大的God对象中。每个线程都可以锁定这个对象、使用它和放弃锁定。但是，这种设计会损害并发性，因为这意味着其他线程必须等待。相反，我们可以使用主动对象模式，如图1-25所示。

要使用这个主动对象，将有一个代理位于调用者线程和实际代码库之间，它把对API的每次调用转换为runnable，并将其放入阻塞队列（线程安全的FIFO队列）。
在God对象中只有一个线程运行时，它将逐个执行队列中的runnable，与典型的Java对象方法的被动调用方式形成对比，在这里，对象本身执行放在队列上的工作，因此才有术语“主动对象”。
本章的余下部分描述经过多年发展起来的许多模式和范式，这些模式和范式用于避免共享状态的显式锁定。

1.4.1　事件驱动的架构

事件驱动编程是一种编程风格，在这种风格中，代码对事件(如按键或鼠标单击)进行响应，简而言之，程序流由事件驱动。
GUI编程是事件驱动编程的一个例子。例如，X Windows（驱动大多数Linux GUI）处理一系列XEvent。每一次按键以及鼠标按钮的按下、释放和鼠标的移动都会产生一系列事件。如果你使用的是Linux，则会有一个名为xev的命令，通过终端运行它会产生一个窗口，在窗口上移动鼠标或按某些键时，可以看到生成的事件。
图1-26是在Linux笔记本电脑上用xev程序捕获的事件。

你可以插入一个回调函数，让它在接收到此类事件时被触发。例如，编辑器程序可以使用keypress事件来更新其状态（导致其文档被编辑），传统的事件驱动编程可能会创建复杂的回调函数流，从而很难发现代码中的控制流。
事件驱动架构（EDA）有助于解耦系统的模块。组件使用封装在消息中的事件进行通信，发出事件的组件对事件消费者一无所知，这使得EDA的耦合极度松散。该体系结构本质上是异步的，事件消息的生产者不知道谁是消费者。此过程如图1-27所示。

有了一个线程和“事件循环”，还有快速执行的回调，这样，我们就有了一个很好的体系架构。这一切与并发有什么关系？这样就可以在一个线程池中运行多个事件循环。线程池是一个基本概念，我们将在后面的章节中讨论它。
正如我们所看到的，事件循环管理事件。事件被传递到一个已安装的处理程序，并在其中进行处理。处理程序对事件的反应有两种结果：成功或失败。失败作为另一个事件再次传递给事件循环，由异常处理程序相应地决定要做出何种反应。

1.4.2　响应式编程

响应式编程（reactive programming）是一种相关的编程范式。电子表格程序是响应式应用程序的一个很好的例子，如果我们设置一个公式并更改任何列值，则电子表格程序会做出反应，并计算新的结果列。
消息驱动体系结构（message-driven architecture）是响应式应用程序的基础，消息驱动的应用程序可以是由事件驱动的或基于actor的，或者是两者的组合。
图1-28是可观察组合的示意图。

可组合事件流（event stream）使事件处理更容易理解。响应性扩展（Rx）是一个提供可组合可观察对象的框架。这个框架的核心是具有函数风格的观察者模式（observer pattern），该框架允许我们组合多个可观察对象，观察者以异步方式获得结果事件流。有关更多信息请参阅http://reactivex.io/intro.html。
组合函数如图1-29所示。

这个Scala代码显示了5种独立方法，每种方法都被转换为一个函数，然后被收集到一个变量list中。reduceRight调用遍历此列表，并将所有函数组合成更大的函数f。
f("hello")调用显示组合成功！

1.4.3　actor范式

所有这些并发编程都很棘手。什么是正确的同步和可见性呢？要是我们可以回到更简单的顺序编程模型，并让平台为我们处理并发性，又会怎样呢？
请看图1-30。

actor是线程的抽象，我们只使用消息传递模型来编写代码，与actor对话的唯一方法是向其发送消息。
回顾一下我们的UNIX shell模型，它采用了并发性，但我们不直接处理它。通过使用actor，我们就可以像为“顺序消息处理器”编程一样编写代码。

但是，我们需要了解底层线程模型。例如，我们应该始终使用tell而不是ask模式，如图1-31所示。在tell模式中，我们向actor发送消息，然后忘记它，也就是说，不会为等待答案而造成阻塞。本质上，这是异步方式。

actor是轻量级实体（线程是重量级），从经济角度来讲，actor的创造和销毁类似于Java对象的创建和销毁，正如在设计UNIX管道时不用考虑成本（主要关注完成工作），actor给了我们同样的*。
这些actor还允许添加监督和重启功能，从而使我们能够编写既健壮又灵活的系统。
actor作为一种设计是相当古老的，该范式曾在电信领域使用Erlang语言进行过尝试和测试。
我们将在即将到来的章节中详细介绍actor模型和Akka库。

1.4.4　消息代理

消息代理（message broker）是一种架构模式，该模式用于通过“消息驱动范式”来集成应用程序。例如，你可以创建一个Python应用程序，并将其与另一个用C或Java编写的应用程序集成。对于企业来说，集成是至关重要的，因为不同的应用程序可以相互合作。
这里显然暗含并发处理。由于生产者和消费者完全解耦（它们甚至不知道其他方是否存在），生产者和消费者应用程序甚至可以运行在不同的机器上，从而能够重叠处理，并提高整体吞吐量，如图1-32所示。

当你开始考虑并发系统时，解耦实际上是一个核心概念。由松散耦合的组件系统构成的设计系统为我们带来了许多好处。例如，我们可以重用组件，以减少开发和维护成本。它还为实现更大的并发铺平了道路。
当生产者生成消息的速度太快时会发生什么？代理将缓冲消息。这实质上意味着会有一种固有的流控制机制，一个行动缓慢的消费者可以按自己的节奏消费，同样，生产者可以用更快的速度生产消息，由于双方都看不见对方，因此整个系统可以顺畅运作。

1.4.5　软件事务性内存

数据库事务的思想也基于并发的读取和写入。事务表示一个原子操作，这意味着操作中的所有步骤要么全部完成，要么全部不完成。如果所有操作都完成，则事务成功，否则，事务将中止。软件事务性内存（STM）是一个类似的并发控制机制，它也是一种不同的范式，是基于锁来实现同步的替代方案。
就像数据库事务一样，线程做出修改，然后尝试提交更改。当然，如果其他事务获胜，则回滚并重试。如果出现错误，则事务中止，然后再次重试。
这种方案称为乐观锁定，在这里，我们不关心其他可能的并发事务，我们只是做出改变，希望提交成功。如果它失败了，我们会继续努力，直到它最终成功。
这有什么好处？好处是得到了更高的并发性，因为没有显式锁定，并且所有线程都在继续前进，只有在发生冲突时才会重试。
STM简化了我们对多线程程序的理解，反过来，这使得程序更容易维护，每个事务都可以表示为单线程计算，如图1-33所示，我们根本不用担心锁定。

可组合性是一个很大的主题：基于锁的程序不能组合。你不能进行了两个原子操作，并从中再创建一个原子操作，你需要专门为它们编写临界区。另一方面，STM可以将这两个操作包装在事务块中，如图1-33所示。

1.4.6　并行集合

假设我正在向你描述一些令人兴奋的新算法，我首先会讲该算法是如何利用哈希表的，通常认为这样的数据结构全部驻留在内存中、被锁定（如果需要的话），并由一个线程处理。
例如，有一个数字列表，假设我们要对所有这些数字求和，这个操作可以通过使用线程在多个内核上并行执行。
现在，我们需要远离显式锁。并发处理列表的抽象是非常好的想法。它会拆分列表，对每个子列表运行函数，并在最后整理结果，如图1-34所示，这是典型的MapReduce范式。

图1-34显示一个已并行化的Scala集合，以便在内部使用并发。
如果数据结构太大 ，以至于不能完全容纳在一台机器的内存中又该怎么办？我们可以将集合分散到一组机器上。
Apache Spark框架为我们做到了这一点。Spark的弹性分布式数据集（RDD）是一个分区集合，它将数据结构分散到集群机器上，因此可以处理大量集合，通常用于执行分析处理。

1.5　本章小结

亲爱的读者，这是一次并行世界的旋风之旅，对于许多你可能已经知道的事情，它更像是一种记忆式的回顾。
我们发现，并发性在现实世界以及软件世界中非常普遍。我们学习了消息传递和共享内存模型，并看到很多影响这两个模型的常见主题。
如果共享内存模型使用显式锁定，则会出现许多问题。我们讨论了竞争条件、死锁、临界区和海森堡bug。
我们还讨论了异步性、actor范式和软件事务性内存。现在我们掌握了所有这些背景知识，在下一章中，我们将介绍一些核心并发模式。