第 1 章 第一步:并发设计原理

第 1 章 第一步:并发设计原理

计算机系统的用户总是希望自己的系统具有更好的性能。他们想要获得质量更高的视频、更好的视频游戏和更快的网络速度。几年前,提高处理器的速度可以为用户提供更好的性能。但是如今,处理器的速度并没有加快。取而代之的是,处理器增加了更多核心,这样操作系统就可以同时执行多个任务。这就是所谓的并发处理。并发编程涵盖了在一台计算机上同时运行多个任务或进程所需的所有工具和技术,以及任务或进程之间为消除数据丢失或不一致而进行的通信和同步。本章将探讨如下主题。

  • 基本的并发概念。
  • 并发应用程序中可能出现的问题。
  • 设计并发算法的方法论。
  • Java并发API。
  • 并发设计模式。
  • 设计并发算法的提示和技巧。

1.1 基本的并发概念

首先介绍一下并发的基本概念。要理解本书其余的内容,必须先理解这些概念。

1.1.1 并发与并行

并发和并行是非常相似的概念,不同的作者会给这两个概念下不同的定义。关于并发,最被人们认可的定义是,在单个处理器上采用单核执行多个任务即为并发。在这种情况下,操作系统的任务调度程序会很快从一个任务切换到另一个任务,因此看起来所有任务都是同时运行的。对于并行来说也有同样的定义:同一时间在不同的计算机、处理器或处理器核心上同时运行多个任务,就是所谓的“并行”。

另一个关于并发的定义是,在系统上同时运行多个任务(不同的任务)就是并发。而另一个关于并行的定义是:同时在某个数据集的不同部分之上运行同一任务的不同实例就是并行。

关于并行的最后一个定义是,系统中同时运行了多个任务。关于并发的最后一个定义是,一种解释程序员将任务和它们对共享资源的访问同步的不同技术和机制的方法。

正如你看到的,这两个概念非常相似,而且这种相似性随着多核处理器的发展也在不断增强。

1.1.2 同步

在并发中,我们可以将同步定义为一种协调两个或更多任务以获得预期结果的机制。同步方式有两种。

  • 控制同步:例如,当一个任务的开始依赖于另一个任务的结束时,第二个任务不能在第一个任务完成之前开始。
  • 数据访问同步:当两个或更多任务访问共享变量时,在任意时间里,只有一个任务可以访问该变量。

与同步密切相关的一个概念是临界段。临界段是一段代码,由于它可以访问共享资源,因此在任何给定时间内,只能够被一个任务执行。互斥是用来保证这一要求的机制,而且可以采用不同的方式来实现。

请记住,同步可以帮助你在完成并发任务的同时避免一些错误(本章稍后将详述),但是它也为你的算法引入了一些开销。你必须非常仔细地计算任务的数量,这些任务可以独立执行,而无须并行算法中的互通信。这就涉及并发算法的粒度。如果算法有着粗粒度(低互通信的大型任务),同步方面的开销就会较低。然而,也许你不会用到系统所有的核心。如果算法有着细粒度(高互通信的小型任务),同步方面的开销就会很高,而且该算法的吞吐量可能不会很好。

并发系统中有不同的同步机制。从理论角度来看,最流行的机制如下。

  • 信号量(semaphore):一种用于控制对一个或多个单位资源进行访问的机制。它有一个用于存放可用资源数量的变量,并且可以采用两种原子操作来管理该变量的值。互斥(mutex,mutual exclusion的简写形式)是一种特殊类型的信号量,它只能取两个值(即资源空闲资源忙),而且只有将互斥设置为的那个进程才可以释放它。互斥可以通过保护临界段来帮助你避免出现竞争条件。
  • 监视器:一种在共享资源之上实现互斥的机制。它有一个互斥、一个条件变量、两种操作(等待条件和通报条件)。一旦你通报了该条件,在等待它的任务中只有一个会继续执行。

在本章中,你将要学习的与同步相关的最后一个概念是线程安全。如果共享数据的所有用户都受到同步机制的保护,那么代码(或方法、对象)就是线程安全的。数据的非阻塞的CAS(compare-and-swap,比较和交换)原语是不可变的,这样就可以在并发应用程序中使用该代码而不会出任何问题。

1.1.3 不可变对象

不可变对象是一种非常特殊的对象。在其初始化后,不能修改其可视状态(其属性值)。如果想修改一个不可变对象,那么你就必须创建一个新的对象。

不可变对象的主要优点在于它是线程安全的。你可以在并发应用程序中使用它而不会出现任何问题。

不可变对象的一个例子就是Java 中的String类。当你给一个String对象赋新值时,会创建一个新的String对象。

1.1.4 原子操作和原子变量

与应用程序的其他任务相比,原子操作是一种发生在瞬间的操作。在并发应用程序中,可以通过一个临界段来实现原子操作,以便对整个操作采用同步机制。

原子变量是一种通过原子操作来设置和获取其值的变量。可以使用某种同步机制来实现一个原子变量,或者也可以使用CAS以无锁方式来实现一个原子变量,而这种方式并不需要任何同步机制。

1.1.5 共享内存与消息传递

任务可以通过两种不同的方法来相互通信。第一种方法是共享内存,通常用于在同一台计算机上运行多任务的情况。任务在读取和写入值的时候使用相同的内存区域。为了避免出现问题,对该共享内存的访问必须在一个由同步机制保护的临界段内完成。

另一种同步机制是消息传递,通常用于在不同计算机上运行多任务的情形。当一个任务需要与另一个任务通信时,它会发送一个遵循预定义协议的消息。如果发送方保持阻塞并等待响应,那么该通信就是同步的;如果发送方在发送消息后继续执行自己的流程,那么该通信就是异步的。

1.2 并发应用程序中可能出现的问题

编写并发应用程序并不是一件容易的工作。如果不能正确使用同步机制,应用程序中的任务就会出现各种问题。本节将介绍一些此类问题。

1.2.1 数据竞争

如果有两个或者多个任务在临界段之外对一个共享变量进行写入操作,也就是说没有使用任何同步机制,那么应用程序可能存在数据竞争(也叫作竞争条件)。

在这些情况下,应用程序的最终结果可能取决于任务的执行顺序。请看下面的例子。

package com.packt.java.concurrency;

public class Account {

  private float balance;

  public void modify (float difference) {

    float value=this.balance;
    this.balance=value+difference;
  }

}

假设有两个不同的任务执行了同一个Account对象中的modify()方法。由于任务中语句的执行顺序不同,最终结果也会有所不同。假设初始余额为1000,而且两个任务都调用了modify()方法并采用1000作为参数。最终的结果应该是3000,但是如果两个任务都在同一时间执行了第一条语句,然后又在同一时间执行了第二条语句,那么最终的结果将是2000。正如你看到的,modify()方法不是原子的,而Account类也不是线程安全的。

1.2.2 死锁

当两个(或多个)任务正在等待必须由另一线程释放的某个共享资源,而该线程又正在等待必须由前述任务之一释放的另一共享资源时,并发应用程序就出现了死锁。当系统中同时出现如下四种条件时,就会导致这种情形。我们将其称为Coffman条件

  • 互斥:死锁中涉及的资源必须是不可共享的。一次只有一个任务可以使用该资源。
  • 占有并等待条件:一个任务在占有某一互斥的资源时又请求另一互斥的资源。当它在等待时,不会释放任何资源。
  • 不可剥夺:资源只能被那些持有它们的任务释放。
  • 循环等待:任务1正等待任务2所占有的资源,而任务2又正在等待任务3所占有的资源,以此类推,最终任务n又在等待由任务1所占有的资源,这样就出现了循环等待。

有一些机制可以用来避免死锁。

  • 忽略它们:这是最常用的机制。你可以假设自己的系统绝不会出现死锁,而如果发生死锁,结果就是你可以停止应用程序并且重新执行它。
  • 检测:系统中有一项专门分析系统状态的任务,可以检测是否发生了死锁。如果它检测到了死锁,可以采取一些措施来修复该问题,例如,结束某个任务或者强制释放某一资源。
  • 预防:如果你想防止系统出现死锁,就必须预防Coffman条件中的一条或多条出现。
  • 规避:如果你可以在某一任务执行之前得到该任务所使用资源的相关信息,那么死锁是可以规避的。当一个任务要开始执行时,你可以对系统中空闲的资源和任务所需的资源进行分析,这样就可以判断任务是否能够开始执行。

1.2.3 活锁

如果系统中有两个任务,它们总是因对方的行为而改变自己的状态,那么就出现了活锁。最终结果是它们陷入了状态变更的循环而无法继续向下执行。

例如,有两个任务:任务1和任务2,它们都需要用到两个资源:资源1和资源2。假设任务1对资源1加了一个锁,而任务2对资源2加了一个锁。当它们无法访问所需的资源时,就会释放自己的资源并且重新开始循环。这种情况可以无限地持续下去,所以这两个任务都不会结束自己的执行过程。

1.2.4 资源不足

当某个任务在系统中无法获取维持其继续执行所需的资源时,就会出现资源不足。当有多个任务在等待某一资源且该资源被释放时,系统需要选择下一个可以使用该资源的任务。如果你的系统中没有设计良好的算法,那么系统中有些线程很可能要为获取该资源而等待很长时间。

要解决这一问题就要确保公平原则。所有等待某一资源的任务必须在某一给定时间之内占有该资源。可选方案之一就是实现一个算法,在选择下一个将占有某一资源的任务时,对任务已等待该资源的时间因素加以考虑。然而,实现锁的公平需要增加额外的开销,这可能会降低程序的吞吐量。

1.2.5 优先权反转

当一个低优先权的任务持有了一个高优先级任务所需的资源时,就会发生优先权反转。这样的话,低优先权的任务就会在高优先权的任务之前执行。

1.3 设计并发算法的方法论

本节,我们将提出一个五步骤的方法论来获得某一串行算法的并发版本。该方法论基于Intel公司在其“Threading Methodology: Principles and Practices”文档中给出的方法论。

1.3.1 起点:算法的一个串行版本

我们实现并发算法的起点是该算法的一个串行版本。当然,也可以从头开始设计一个并发算法。不过我认为,算法的串行版本有两个方面的好处。

  • 我们可以使用串行算法来测试并发算法是否生成了正确的结果。当接收同样的输入时,这两个版本的算法必须生成同样的输出结果,这样我们就可以检测并发版本中的一些问题,例如数据竞争或者类似的条件。
  • 我们可以度量这两个算法的吞吐量,以此来观察使用并发处理是否能够改善响应时间或者提升算法一次性所能处理的数据量。

1.3.2 第1步:分析

在这一步中,我们将分析算法的串行版本来寻找它的代码中有哪些部分可以以并行方式执行。我们应该特别关注那些执行过程花费时间最多或者执行代码较多的部分,因为实现这些部分的并发版本将能获得较大的性能改进。

对这一过程而言,比较好的候选方案就是循环排查,让其中的一个步骤独立于其他步骤,或者让其中某些部分的代码独立于其他部分的代码(例如一个用于初始化某个应用程序的算法,它打开与数据库的连接,加载配置文件,初始化一些对象。所有这些前期任务都是相互独立的)。

1.3.3 第2步:设计

一旦你知道了要对哪些部分的代码并行处理,就要决定如何对其进行并行化处理了。

代码的变化将影响应用程序的两个主要部分。

  • 代码的结构。
  • 数据结构的组织。

你可以采用两种方式来完成这一任务。

  • 任务分解:当你将代码划分成两个或多个可以立刻执行的独立任务时,就是在进行任务分解。其中有些任务可能必须按照某种给定的顺序来执行,或者必须在同一点上等待。你必须使用同步机制来实现这样的行为。
  • 数据分解:当使用同一任务的多个实例分别对数据集的一个子集进行处理时,就是在进行数据分解。该数据集是一个共享资源,因此,如果这些任务需要修改数据,那你必须实现一个临界段来保护对数据的访问。

另一个必须牢记的要点是解决方案的粒度。实现一个算法的并发版本,其目标在于实现性能的改善,因此你应该使用所有可用的处理器或核。另一方面,当你采用某种同步机制时,就引入了一些额外的必须执行的指令。如果你将算法分割成很多小任务(细粒度),实现同步机制所需额外引入的代码就会导致性能下降。如果你将算法分割成比核数还少的任务(粗粒度),那么就没有充分利用全部资源。同样,你还要考虑每个线程都必须要做的工作,尤其是当你实现细粒度解决方案时。如果某个任务的执行时间比其他任务长,那么该任务将决定整个应用程序的执行时间。你需要在这两点之间找到平衡。

1.3.4 第3步:实现

下一步就是使用某种编程语言来实现并发算法了,而且如果必要,还要用到线程库。在本书的例子中,我们将使用Java语言来实现所有算法。

1.3.5 第4步:测试

在完成实现过程之后,你应该对该并行算法进行测试。如果你有了算法的串行版本,可以对比这两个版本算法的结果,从而验证并行版本是否正确。

测试和调试一个并行程序的具体实现是非常困难的任务,因为应用程序中不同任务的执行顺序是无法保证的。在第12章中,你将学到一些提示、技巧和工具,从而可以高效地完成这些任务。

1.3.6 第5步:调整

最后一步是对比并行算法和串行算法的吞吐量。如果结果并未达到预期,那么你必须重新审查该算法,查找造成并行算法性能较差的原因。

你也可以测试该算法的不同参数(例如任务的粒度或数量),从而找到最佳配置。

还有其他一些指标可用来评估通过使算法并行处理可能获得的性能改进。下面给出的是最常见的三个指标。

  • 加速比(speedup):这是一个用于评价并行版算法和串行版算法之间相对性能改进情况的指标。

    {\rm Speedup}=\frac{T_{{\rm sequential}}}{T_{{\rm concurrent}}}

    其中,Tsequential是算法串行版的执行时间,而Tconcurrent是算法并行版的执行时间。

  • Amdahl定律:该定律用于计算对算法并行化处理之后可获得的最大期望改进。

    其中,P 是可以进行并行化处理的代码的百分比,而N 是你准备用于执行该算法的计算机的核数。

    例如,如果你可以对75%的代码进行并行化处理并且有四个核,那么最大加速比可按照如下公式进行计算。

  • Gustafson-Barsis定律1:Amdahl定律具有一定缺陷。它假设当你增加核的数量时输入数据集是相同的,但是一般来说,当拥有更多的核时,你就想处理更多的数据。Gustafson定律认为,当你有更多可用的核时,可同时解决的问题规模就越大,其公式如下

    {\rm Speedup}=P-\alpha\times(P-1)

    其中,N 为核数,而P 为可并行处理代码所占的百分比。

    如果我们使用之前的同一示例,那么Gustafson定律计算出的可伸缩加速比如下。

    {\rm Speedup}=4-0.25\times(3)=3.25

1也称作Gustafson定律。——译者注

1.3.7 结论

在本节中,你知晓了在对某一串行算法进行并行化处理时必须考虑的问题。

首先,并非每一个算法都可以进行并行化处理。例如,如果你要执行一个循环,其每次迭代的结果取决于前一次迭代的结果,那么你就不能对该循环进行并行化处理。基于同样的原因,递归算法是无法进行并行化处理的另一个例子。

你要牢记的另一重要事项是:对性能良好的串行版算法实现并行处理,实际上是个糟糕的出发点。如果在你开始对某个算法进行并行化处理时,发现并不容易找到代码的独立部分,那么你就要找一找该算法的其他版本,并且验证一下该版本的算法是否能够很方便地进行并行化处理。

最后,当你实现一个并发应用程序时(从头开始或者基于一个串行算法),必须要考虑下面几点。

  • 效率:并行版算法花费的时间必须比串行版算法少。对算法进行并行处理的首要目标就是实现运行时间比串行版算法少,或者说它能够在相同时间内处理更多的数据。
  • 简单:当你实现一个算法(无论是否为并行算法)时,必须尽可能确保其简单。它应该更加容易实现、测试、调试和维护,这样就会少出错。
  • 可移植性:你的并行算法应该只需要很少的更改就能够在不同的平台上执行。因为在本书中使用Java语言,所以做到这一点非常简单。有了Java,你就可以在每一种操作系统中执行程序而无须任何更改(除非因为程序实现而必须更改)。
  • 伸缩性:如果你增加了核的数目,算法会发生什么情况?正如前面提到的,你应该使用所有可用的核,这样一来你的算法就能利用所有可用的资源。

1.4 Java并发API

Java编程语言含有非常丰富的并发API。它含有管理基本并发元素所需的类,例如ThreadLockSemaphore等类,以及用于实现非常高层同步机制的类,例如执行器框架或新增加的并行Stream API。

本节将涵盖形成并发API的基本类。

1.4.1 基本并发类

并发API的基本类如下。

  • Thread:该类描述了执行并发Java应用程序的所有线程。
  • Runnable接口:这是Java中创建并发应用程序的另一种方式。
  • ThreadLocal:该类用于存放从属于某一线程的变量。
  • ThreadFactory接口:这是实现Factory设计模式的基类,你可以用它来创建定制线程。

1.4.2 同步机制

Java并发API包括多种同步机制,可以支持你:

  • 定义用于访问某一共享资源的临界段;
  • 在某一共同点上同步不同的任务。

下面是最重要的同步机制。

  • synchronized关键字synchronized关键字允许你在某个代码块或者某个完整的方法中定义一个临界段。
  • Lock接口Lock提供了比synchronized关键字更为灵活的同步操作。Lock接口有多种不同类型:ReentrantLock用于实现一个可与某种条件相关联的锁;ReentrantReadWriteLock将读写操作分离开来;StampedLock是Java 8中增加的一种新特性,它包括三种控制读/写访问的模式。
  • Semaphore:该类通过实现经典的信号量机制来实现同步。Java支持二进制信号量和一般信号量。
  • CountDownLatch:该类允许一个任务等待多项操作的结束。
  • CyclicBarrier:该类允许多线程在某一共同点上进行同步。
  • Phaser:该类允许你控制那些分割成多个阶段的任务的执行。在所有任务都完成当前阶段之前,任何任务都不能进入下一阶段。

1.4.3 执行器

执行器框架是在实现并发任务时将线程的创建和管理分割开来的一种机制。你不必担心线程的创建和管理,只需要关心任务的创建并且将其发送给执行器。该框架中涉及的主要类如下。

  • Executor接口和ExecutorService接口:它们包含了所有执行器共有的execute()方法。
  • ThreadPoolExecutor:该类允许你获取一个含有线程池的执行器,而且可以定义并行任务的最大数目。
  • ScheduledThreadPoolExecutor:这是一种特殊的执行器,可以使你在某段延迟之后执行任务或者周期性执行任务。
  • Executors:该类使执行器的创建更为容易。
  • Callable接口:这是Runnable接口的替代接口——可返回值的一个单独的任务。
  • Future接口:该接口包含了一些能获取Callable接口返回值并且控制其状态的方法。

1.4.4 Fork/Join框架

Fork/Join框架定义了一种特殊的执行器,尤其针对采用分治方法进行求解的问题。针对解决这类问题的并发任务,它还提供了一种优化其执行的机制。Fork/Join是为细粒度并行处理量身定制的,因为它的开销非常小,这也是将新任务加入队列中并且按照队列排序执行任务的需要。该框架涉及的主要类和接口如下。

  • ForkJoinPool:该类实现了要用于运行任务的执行器。
  • ForkJoinTask:这是一个可以在ForkJoinPool类中执行的任务。
  • ForkJoinWorkerThread:这是一个准备在ForkJoinPool类中执行任务的线程。

1.4.5 并行流

lambda表达式可能是Java 8中最重要的两个新特性。流已经被增加为Collection接口和其他一些数据源的方法,它允许处理某一数据结构的所有元素、生成新的结构、筛选数据和使用MapReduce方法来实现算法。

并行流是一种特殊的流,它以一种并行方式实现其操作。使用并行流时涉及的最重要的元素如下。

  • Stream接口:该接口定义了所有可以在一个流上实施的操作。
  • Optional:这是一个容器对象,可能(也可能不)包含一个非空值。
  • Collectors:该类实现了约简(reduction)操作,而该操作可作为流操作序列的一部分使用。
  • lambda表达式:流被认为是可以处理lambda表达式的。大多数流方法都会接收一个lambda表达式作为参数,这让你可以实现更为紧凑的操作。

1.4.6 并发数据结构

Java API中的常见数据结构(例如ArrayListHashtable等)并不能在并发应用程序中使用,除非采用某种外部同步机制。但是如果你采用了某种同步机制,应用程序就会增加大量的额外计算时间。而如果你不采用同步机制,那么应用程序中很可能出现竞争条件。如果你在多个线程中修改数据,那么就会出现竞争条件,你可能会面对各种异常(例如ConcurrentModificationExceptionArrayIndexOutOfBoundsException),出现隐性数据丢失,或者应用程序会陷入死循环。

Java并发API中含有大量可以在并发应用中使用而没有风险的数据结构。我们将它们分为以下两大类别。

  • 阻塞型数据结构:这些数据结构含有一些能够阻塞调用任务的方法,例如,当数据结构为空而你又要从中获取值时。
  • 非阻塞型数据结构:如果操作可以立即进行,它并不会阻塞调用任务。否则,它将返回null值或者抛出异常。

下面是其中的一些数据结构。

  • ConcurrentLinkedDeque:这是一个非阻塞型的列表。
  • ConcurrentLinkedQueue:这是一个非阻塞型的队列。
  • LinkedBlockingDeque:这是一个阻塞型的列表。
  • LinkedBlockingQueue:这是一个阻塞型的队列。
  • PriorityBlockingQueue:这是一个基于优先级对元素进行排序的阻塞型队列。
  • ConcurrentSkipListMap:这是一个非阻塞型的NavigableMap
  • ConcurrentHashMap:这是一个非阻塞型的哈希表。
  • AtomicBooleanAtomicIntegerAtomicLongAtomicReference:这些是基本Java数据类型的原子实现。

1.5 并发设计模式

在软件工程中,设计模式是针对某一类共同问题的解决方案。这种解决方案被多次使用,而且已经被证明是针对该类问题的最优解决方案。每当你需要解决这其中的某个问题,就可以使用它们来避免做重复工作。其中,单例模式(Singleton)和工厂模式(Factory)是几乎每个应用程序中都要用到的通用设计模式。

并发处理也有其自己的设计模式。本节,我们将介绍一些最常用的并发设计模式,以及它们的Java语言实现。

1.5.1 信号模式

这种设计模式介绍了如何实现某一任务向另一任务通告某一事件的情形。实现这种设计模式最简单的方式是采用信号量或者互斥,使用Java语言中的ReentrantLock类或Semaphore类即可,甚至可以采用Object类中的wait()方法和notify()方法。

请看下面的例子。

public void task1() {
  section1();
  commonObject.notify();
}

public void task2() {
  commonObject.wait();
  section2();
}

在上述情况下,section2()方法总是在section1()方法之后执行。

1.5.2 会合模式

这种设计模式是信号模式的推广。在这种情况下,第一个任务将等待第二个任务的某一事件,而第二个任务又在等待第一个任务的某一事件。其解决方案和信号模式非常相似,只不过在这种情况下,你必须使用两个对象而不是一个。

请看下面的例子。

public void task1() {
  section1_1();
  commonObject1.notify();
  commonObject2.wait();
  section1_2();
}
public void task2() {
  section2_1();
  commonObject2.notify();
  commonObject1.wait();
  section2_2();
}

在上述情况下,section2_2()方法总是会在section1_1()方法之后执行,而section1_2()方法总是会在section2_1()方法之后执行。仔细想想就会发现,如果你将对wait()方法的调用放在对notify()方法的调用之前,那么就会出现死锁。

1.5.3 互斥模式

互斥这种机制可以用来实现临界段,确保操作相互排斥。这就是说,一次只有一个任务可以执行由互斥机制保护的代码片段。在Java中,你可以使用synchronized关键字(这允许你保护一段代码或者一个完整的方法)、ReentrantLock类或者Semaphore类来实现一个临界段。

让我们看看下面的例子。

public void task() {
  preCriticalSection();
  try {
    lockObject.lock() // 临界段开始
    criticalSection();
  } catch (Exception e) {

  } finally {
    lockObject.unlock(); // 临界段结束
    postCriticalSection();
}

1.5.4 多元复用模式

多元复用设计模式是互斥机制的推广。在这种情形下,规定数目的任务可以同时执行临界段。这很有用,例如,当你拥有某一资源的多个副本时。在Java中实现这种设计模式最简单的方式是使用Semaphore类,并且使用可同时执行临界段的任务数来初始化该类。

请看如下示例。

public void task() {
  preCriticalSection();
  semaphoreObject.acquire();
  criticalSection();
  semaphoreObject.release();
  postCriticalSection();
}

1.5.5 栅栏模式

这种设计模式解释了如何在某一共同点上实现任务同步的情形。每个任务都必须等到所有任务都到达同步点后才能继续执行。Java并发API提供了CyclicBarrier类,它是这种设计模式的一个实现。

请看下面的例子。

public void task() {
  preSyncPoint();
  barrierObject.await();
  postSyncPoint();
}

1.5.6 双重检查锁定模式

当你获得某个锁之后要检查某项条件时,这种设计模式可以为解决该问题提供方案。如果该条件为假,你实际上也已经花费了获取到理想的锁所需的开销。对象的延迟初始化就是针对这种情形的例子。如果你有一个类实现了单例设计模式,那可能会有如下这样的代码。

public class Singleton{
  private static Singleton reference;
  private static final Lock lock=new ReentrantLock();

  public static Singleton getReference() {
    try {
      lock.lock();
      if (reference==null) {
        reference=new Object();
      }
    } catch (Exception e) {
        System.out.println(e);
    } finally {
        lock.unlock();
    }
    return reference;
  }
}

一种可能的解决方案就是在条件之中包含锁。

public class Singleton{
  private Object reference;
  private Lock lock=new ReentrantLock();
  public Object getReference() {
    if (reference==null) {
      lock.lock();
      if (reference == null) {
        reference=new Object();
      }
      lock.unlock();
    }
    return reference;
  }
}

该解决方案仍然存在问题。如果两个任务同时检查条件,你将要创建两个对象。解决这一问题的最佳方案就是不使用任何显式的同步机制。

public class Singleton {

  private static class LazySingleton {
    private static final Singleton INSTANCE = new Singleton();
  }

  public static Singleton getSingleton() {
    return LazySingleton.INSTANCE;
  }

}

1.5.7 读-写锁模式

当你使用锁来保护对某个共享变量的访问时,只有一个任务可以访问该变量,这和你将要对该变量实施的操作是相互独立的。有时,你的变量需要修改的次数很少,却需要读取很多次。这种情况下,锁的性能就会比较差了,因为所有读操作都可以并发进行而不会带来任何问题。为解决这样的问题,出现了读-写锁设计模式。这种模式定义了一种特殊的锁,它含有两个内部锁:一个用于读操作,而另一个用于写操作。该锁的行为特点如下所示。

  • 如果一个任务正在执行读操作而另一任务想要进行另一个读操作,那么另一任务可以进行该操作。
  • 如果一个任务正在执行读操作而另一任务想要进行写操作,那么另一任务将被阻塞,直到所有的读取方都完成操作为止。
  • 如果一个任务正在执行写操作而另一任务想要执行另一操作(读或者写),那么另一任务将被阻塞,直到写入方完成操作为止。

Java并发API中含有ReentrantReadWriteLock类,该类实现了这种设计模式。如果你想从头开始实现该设计模式,就必须非常注意读任务和写任务之间的优先级。如果有太多读任务存在,那么写任务等待的时间就会很长。

1.5.8 线程池模式

这种设计模式试图减少为执行每个任务而创建线程所引入的开销。该模式由一个线程集合和一个待执行的任务队列构成。线程集合通常具有固定大小。当一个线程完成了某个任务的执行时,它本身并不会结束执行,它要寻找队列中的另一个任务。如果存在另一个任务,那么它将执行该任务。如果不存在另一个任务,那么该线程将一直等待,直到有任务插入队列中为止,但是线程本身不会被终结。

Java并发API包含一些实现ExecutorService接口的类,该接口内部采用了一个线程池。

1.5.9 线程局部存储模式

这种设计模式定义了如何使用局部从属于任务的全局变量或静态变量。当在某个类中有一个静态属性时,那么该类的所有对象都会访问该属性的同一存在。如果使用了线程局部存储,则每个线程都会访问该变量的一个不同实例。

Java并发API包含了ThreadLocal类,该类实现了这种设计模式。

1.6 设计并发算法的提示和技巧

本节汇编了一些需要你牢记的提示和技巧,它们可以帮助你设计出良好的并发应用程序。

1.6.1 正确识别独立任务

你只能执行那些相互独立的并发任务。如果两个或多个任务之间存在某种顺序依赖,你可能没兴趣尝试以并发方式执行它们,同时引入某种同步机制来保证执行顺序。这些任务将以串行方式执行,而你还必须使用同步机制。另一种不同的场景是,你的任务具有一些先决条件,但是这些先决条件都是相互独立的。在这种情形下,你可以以并发方式执行这些先决条件,然后在完成先决条件后使用一个同步类来控制任务的执行。

另一个无法使用并发处理的场景是,你有一个循环,而所有步骤所使用的数据都是由它之前的步骤生成的,或者存在一些需要从一个步骤流转到下一步骤的状态信息。

1.6.2 在尽可能高的层面上实施并发处理

像Java并发API这样丰富的线程处理API,为你在应用程序中实现并发处理提供了不同的类。对于Java来说,你可以使用Thread类或Lock类来控制线程的创建和同步,不过Java也提供了高层次的并发处理对象,例如执行器或Fork/Join框架,它们都可以支持你执行并发任务。这种高层机制有下述好处。

  • 你不需要担心线程的创建和管理,只需要创建并且发送任务以使其执行。Java并发API会帮助你控制线程的创建和管理。
  • 它们都经过了优化,可以比直接使用线程提供更好的性能。例如,它们使用了一个线程池,可对线程进行重用,避免了为每个任务都创建线程。你可以从头开始实现这些机制,但是这会花费你大量的时间,而且这也是一项复杂的任务。
  • 它们含有一些高级特性,可以使API更加强大。例如,有了Java中的执行器,你可以执行以Future对象形式返回结果的任务。同样,你也可以从头开始实现这些机制,但是并不建议这样做。
  • 你的应用程序很容易从一个操作系统被迁移到另一个,而且它将具有更好的伸缩性。
  • 你的应用程序在今后的Java版本中可能会更加快速。Java开发人员一直都在改进内部构件,而且JVM优化也会更加适合于JDK API。

总之,出于性能和开发时间方面的原因,在实现并发算法之前,要分析一下线程API提供的高层机制。

1.6.3 考虑伸缩性

若是要实现一个并发算法,主要目标之一就是要利用计算机的全部资源,尤其是要充分利用处理器或者核的数目。但是这个数目可能会随时间推移而发生变化。硬件是不断改进的,而且其成本每年都在降低。

当你使用数据分解来设计并发算法时,不要预先假定应用程序要在多少个核或者处理器上执行。要动态获取系统的有关信息(例如,在Java中可以使用Runtime.getRuntime().availableProcessors()方法来获取信息),并且让你的算法使用这些信息来计算它要执行的任务数。这个过程会给算法执行时间带来额外开销,但是你的算法将有更好的伸缩性。

如果你使用任务分解来设计并发算法,情况就会更加复杂。你要根据算法中独立任务的数目来设计,而且强制执行较多的任务将会增加由同步机制引入的开销,而且应用程序的整体性能甚至会更糟糕。要详细分析算法来判断是否要采用动态的任务数。

1.6.4 使用线程安全API

如果你需要在并发应用程序中使用某个Java库,首先要阅读其文档以了解该库是否为线程安全的。如果它是线程安全的,那么你可以在自己的应用程序中使用它而不会出现任何问题。如果它不是线程安全的,那么你有如下两个选择。

  • 如果已经存在一个线程安全的替代方案,那么就应该使用该替代方案。
  • 如果不存在线程安全的替代方案,就应该添加必要的同步机制来避免所有可能出现问题的情形,尤其是数据竞争条件。

例如,如果你在并发应用程序中需要用到一个List,且需要在多个线程中对其更新,那么就不应该使用ArrayList类,因为它不是线程安全的。在这种情况下,你可以使用一个线程安全的类,例如ConcurrentLinkedDequeCopyOnWriteArrayList或者LinkedBlockingDeque。如果你要用的类不是线程安全的,你必须首先查找一个线程安全的替代方案。采用并发API很可能比你所能实现的任何替代方案都更加优化。

1.6.5 绝不要假定执行顺序

如果你不采用任何同步机制,那么在并发应用程序中任务的执行顺序是不确定的。任务执行的顺序以及每个任务执行的时间,是由操作系统的调度器所决定的。在多次执行时,调度器并不关心执行顺序是否相同。下一次执行时顺序可能就不同了。

假定某一执行顺序的结果通常会导致数据竞争问题。算法的最终结果取决于任务执行的顺序。有时,结果可能是正确的,但在其他时候可能是错误的。检测导致数据竞争条件的原因非常困难,因此你必须小心谨慎,不要忘记所有必须进行同步的元素。

1.6.6 在静态和共享场合尽可能使用局部线程变量

线程局部变量是一种特殊的变量。每个任务针对该变量都有一个独立的值,这样你就不需要任何同步机制来保护对该变量的访问。

这听起来有些奇怪。对于该类的各个属性,每个对象都有自己的一个副本,那么为什么我们还需要线程局部变量呢?试想这样的场景:你创建了一个Runnable任务,而且你也想执行该任务的多个实例。你可以为要执行的每个线程都创建一个Runnable对象,但另一个可选方案是创建一个Runnable对象并且使用该对象创建所有线程。在后一种情况中,所有线程都将访问该类各属性的同一副本,除非你使用ThreadLocal类。ThreadLocal类确保了每个线程都将访问自己针对该变量的实例,而不需要使用Lock类、Semaphore类或者类似的类。

另一种场景是,你所使用的Thread局部变量带有静态属性。此时,类的所有实例都会共享其静态属性,除非你使用ThreadLocal类来声明它们。在使用ThreadLocal类声明的情况下,每个线程都访问其自己的副本。

另一个可选方案是使用ConcurrentHashMap<Thread, MyType>这样的方式,像var.get(Thread.currentThread())var.put(Thread.currentThread(), newValue)这样使用它。通常,由于可能出现竞争,这种方式要比采用ThreadLocal的方式明显慢一些(采用ThreadLocal根本就没有竞争)。不过这种方式也有其优点:你可以完全清空哈希表,这样对每个线程来说其中的值都会消失。因此,采用这种方式有时也是有用的。

1.6.7 寻找更易于并行处理的算法版本

我们将算法定义为解决某一问题的一系列步骤。解决同一问题可以有许多方式。有些方式速度更快,有些方式使用的资源更少,还有一些方式能够更好地适应输入数据的特定特征。例如,如果你想要对一组数排序,可以使用已实现的多种排序算法之一来解决问题。

在前一节中,我们推荐你使用串行版算法作为实现并发算法的起点。这种方式主要有两个优点。

  • 很容易测试并行算法结果的正确性。
  • 可以度量采用并发处理后获得的性能提升。

但是并非每个算法都可以并行化处理,至少并不那么容易。你可能认为最好的起点是解决待并行处理的问题的性能最佳的串行算法,但这是一种错误的假设。你应该寻找更容易并行化的算法,然后将该并发算法和其性能最佳的串行版本对比,看看哪个可以提供更高的吞吐量。

1.6.8 尽可能使用不可变对象

在并发应用程序中遇到的一个主要问题就是数据竞争条件。前文已经提到,如果两个或多个任务能修改在某个共享变量中存放的数据,却没有在临界段中实现对该变量的访问,就会发生数据竞争条件这样的情况。

例如,当你使用Java这样的面向对象的语言时,可以将应用程序作为一个对象集合来实现。每个对象都有一些属性,还有一些方法用来读取和更改这些属性的值。如果有些任务共享了某个对象,那么当你调用某个没有同步机制保护的方法来更改该对象某个属性的值时,就很可能会出现数据不一致问题。

有一些特殊的对象叫作不可变对象,其主要特征是初始化之后你不能对其任何属性进行修改。如果你想要修改某一属性的值,必须创建另一个对象。Java中的String类是不可变对象的最佳例子。当你使用某种看起来会改变String对象值的运算符(例如=+=)时,实际上创建了一个新的对象。

在并发应用程序中使用不可变对象有如下两个非常重要的好处。

  • 不需要任何同步机制来保护这些类的方法。如果两个任务要修改同一对象,它们将创建新的对象,因此绝不会出现两个任务同时修改同一对象的情况。
  • 不会有任何数据不一致问题,因为这是第一点的必然结果。

不可变对象存在一个缺点。如果你创建了太多的对象,可能会影响应用程序的吞吐量和内存使用。如果你有一个没有内部数据结构的简单对象,将其作为不可变对象通常是没有问题的。然而,构造由其他对象集合整合而成的复杂不可变对象通常会导致严重的性能问题。

1.6.9 通过对锁排序来避免死锁

在并发应用程序中避免死锁的最佳机制之一是强制要求任务总是以相同顺序获取资源。实现这种机制的一种简单方式是为每个资源都分配一个编号。当一个任务需要多个资源时,它需要按照顺序来请求。

例如,你有两个任务T1和T2,它们都需要两项资源R1和R2,你可以强制它们首先请求R1资源然后请求R2资源,这样就不会发生死锁。

另一方面,如果T1首先请求了R1资源然后请求R2资源,并且T2首先请求了R2资源然后请求R1资源,那么就会发生死锁。

这一技巧的一种错误使用如下所示。你有两个任务都需要获得两个Lock对象,它们都试图以不同顺序来获取锁。

public void operation1() {
  lock1.lock();
  lock2.lock();
     .
}
public void operation2() {
  lock2.lock();
  lock1.lock();
}

可能operation1()方法执行了它的第一条语句,而operation2()方法也执行了它的第一条语句,这样它们都将等待另一个锁,也就发生了死锁。

只要按照同样的顺序获取锁,就可以避免这一点。如果按照下述代码更改operation2()方法,就绝不会发生死锁。

public void operation2() {
  lock1.lock();
  lock2.lock();
}

1.6.10 使用原子变量代替同步

当你要在两个或者多个任务之间共享数据时,必须使用同步机制来保护对该数据的访问,并且避免任何数据不一致问题。

某些情况下,你可以使用volatile关键字而不使用同步机制。如果只有一个任务修改数据而其他任务都读取数据,那么你可以使用volatile关键字而无须任何同步机制,并且不会出现数据不一致问题。在其他场合,你需要使用锁、synchronized关键字或者其他同步方法。

在Java 5中,并发API中有一种新的变量,叫作原子变量。这些变量都是在单个变量上支持原子操作的类。它们含有一个名为compareAndSet(oldValue, newValue)的方法,该方法具有一种机制,可用于探测某个步骤中将新值赋给变量的操作是否完成。如果变量的值等于oldValue,那么该方法将变量的值更改为newValue并且返回true。否则,该方法返回false。以类似方式工作的方法还有很多,例如getAndIncrement()getAndDecrement()等。这些方法也都是原子的。

该解决方案是免锁的,也就是说不需要使用锁或者任何同步机制,因此它的性能比任何采用同步机制的解决方案要好。

在Java中可用的最重要的原子变量有如下几种:

  • AtomicInteger
  • AtomicLong
  • AtomicReference
  • AtomicBoolean
  • LongAdder
  • DoubleAdder

1.6.11 占有锁的时间尽可能短

和其他所有同步机制一样,锁允许你定义一个临界段,一次只有一个任务可以执行。当一个任务执行该临界段时,其他要执行临界段的任务都将被阻塞并且要等待该临界段被释放。这样,该应用程序其实是以串行方式来工作的。

你要特别注意临界段中的指令,因为如果不了解它的话会降低应用程序的性能。你必须将临界段定制得尽可能小,而且它必须仅包含处理与其他任务共享的数据的指令,这样应用程序花费在串行处理上的时间就会最少。

避免在临界段中执行你无法控制的代码。例如,你写了一个库,它接收一个用户自定义的Callable对象作为参数,但是该对象有时候需要由你启动,而你并不知道该Callable对象中到底有什么。也许它会阻塞输入/输出、获取某些锁、调用你库中的其他方法,或者只是需要处理很长一段时间。因此,如果可能的话,在你的库并不占有任何锁时,再尝试执行这些代码。如果对你的算法来说不可能做到这一点,就在该库的文档中说明这一情况,并且尽可能说明对用户提供的代码的限制(例如,这些代码不应该加任何锁)。一个很好的例子就是ConcurrentHashMap类的compute()方法的文档说明。

1.6.12 谨慎使用延迟初始化

延迟初始化就是将对象的创建延迟到该对象在应用程序中首次使用时的一种机制。它的主要优点是可以使内存使用最小化,因为你只需要创建实际需要的对象。但是在并发应用程序中它也可能引发问题。

如果你使用某个方法初始化某一对象,并且该方法同时被两个不同的任务调用,那么你可以初始化两个不同的对象。但是这可能会带来问题(例如对单例模式的类来说),因为你只想为这些类创建一个对象。

这一问题已经有了很好的解决方案,这就是延迟加载的单例模式(请查看维基百科中关于“initialization-on-demand holder idiom”的解释)。

1.6.13 避免在临界段中使用阻塞操作

阻塞操作是指阻塞任务对其进行调用,直到某一事件发生后再调用的操作。例如,当你从某一文件读取数据或者向控制台输出数据时,调用这些操作的任务必须等待,直到这些操作完成为止。

如果临界段中包含了这样的操作,应用程序的性能就会降低,因为需要执行该临界段的任务都无法执行临界段了。位于临界段中的操作等待某个I/O操作结束,而其他任务则一直在等待临界段。

除非必要,否则不要在临界段中加入阻塞操作。

1.7 小结

并发程序设计包含了在一台计算机上同时运行多个任务或者进程所必需的工具和技术,以及在它们之间确保不出现数据丢失和不一致所需的通信和同步。

本章一开始介绍了并发的基本概念。要完全理解本书中的例子,你必须知道并理解并发、并行和同步等术语。然而,并发处理也会产生一些问题,例如数据竞争条件、死锁、活锁等。你还必须知道并发应用程序可能存在的问题,这会帮助你识别和解决这些问题。

我们还介绍了Intel公司提出的一个五步骤的简单方法论,它用于将一个串行算法转换成并发算法。此外还展示了采用Java语言实现的一些并发设计模式,介绍了一些在实现并发应用程序时可以借鉴的技巧。

最后简单介绍了Java并发API的组件。这是一个非常丰富的API,既有低层机制,也有很高层的机制,让你很容易实现强大的并发应用程序。

下一章,你将学习如何使用Java并发应用程序的基本要素:Thread类和Runnable接口。

目录

  • 版权声明
  • 译者序
  • 前言
  • 第 1 章 第一步:并发设计原理
  • 第 2 章 使用基本元素:Thread和Runnable
  • 第 3 章 管理大量线程:执行器
  • 第 4 章 充分利用执行器
  • 第 5 章 从任务获取数据:Callable接口与Future接口
  • 第 6 章 运行分为多阶段的任务:Phaser类
  • 第 7 章 优化分治解决方案:Fork/Join框架
  • 第 8 章 使用并行流处理大规模数据集:MapReduce模型
  • 第 9 章 使用并行流处理大规模数据集:MapCollect模型
  • 第 10 章 异步流处理:反应流
  • 第 11 章 探究并发数据结构和同步工具
  • 第 12 章 测试与监视并发应用程序
  • 第 13 章 JVM中的并发处理:Clojure、带有GPars库的Groovy以及Scala