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类，因为它不是线程安全的。在这种情况下，你可以使用一个线程安全的类，例如ConcurrentLinkedDeque、CopyOnWriteArrayList或者LinkedBlockingDeque。如果你要用的类不是线程安全的，你必须首先查找一个线程安全的替代方案。采用并发API很可能比你所能实现的任何替代方案都更加优化。

1.6.5　绝不要假定执行顺序

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

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

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

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

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

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

另一个可选方案是使用ConcurrentHashMap这样的方式，像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对象，它们都试图以不同顺序来获取锁。

  1. public void operation1() {
  2.   lock1.lock();
  3.   lock2.lock();
  4.      .
  5. }
  6. public void operation2() {
  7.   lock2.lock();
  8.   lock1.lock();
  9. }

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

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

  1. public void operation2() {
  2.   lock1.lock();
  3.   lock2.lock();
  4. }

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操作结束，而其他任务则一直在等待临界段。

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