并发与并行

分布式系统的一个重要特征就是计算能力是可以并发或者并行的。

在分布式系统中，往往会将一个大任务进行分解，而后下发给不同的节点去计算，从而节省整个任务的计算时间。

并发与并行的区别

计算机用户很容易认为他们的系统在一段时间内可以做多件事。比如，用户一边用浏览器下载视频文件，一边可以继续在浏览器上浏览网页。可以做这样的事情的软件被称为并发软件（ConcurrentSoftware）。

计算机能实现多个程序的同时执行，主要基于以下因素。

·资源利用率。某些情况下，程序必须等待其他外部的某个操作完成，才能往下继续执行，而在等待的过程中，该程序无法执行其他任何工作。因此，如果在等待的同时可以运行另外一个程序，无疑将提高资源的利用率。

·公平性。不同的用户和程序对于计算机上的资源有着同等的使用权。一种高效的运行方式是粗粒度的时间分片（Time Slicing）使这些用户和程序能共享计算机资源，而不是一个程序从头运行到尾，然后再启动下一个程序。

·便利性。通常来说，在计算多个任务时，应该编写多个程序，每个程序执行一个任务并在必要时相互通信，这比只编写一个程序来计算所有任务更加容易实现。

那么并发与并行到底是如何区别的呢？

The Practice of Programming一书的作者Rob Pike对并发与并行做了如下描述。

并发是同一时间应对（Dealing With）多件事情的能力；并行是同一时间动手做（Doing）多件事情的能力。并发（Concurrency）属于问题域（Problem Domain），并行（Parallelism）属于解决域（SolutionDomain）。并行和并发的区别在于有无状态，并行计算适合无状态应用，而并发解决的是有状态的高性能；有状态要着力解决并发计算，无状态要着力并行计算，云计算要能做到这两种计算自动伸缩扩展。

上述的描述貌似有点抽象。举一个生活中的例子，某些人工作很忙，那么会请钟点工来打扫卫生。一个钟点工在一小时可以帮你扫地、擦桌子、洗菜、做饭。客户并不关心哪件活儿先干哪件活儿后做，客户所关心的是，付费的这一小时，需要看到所有活儿都完成。在客户看来，这一小时内，所有的活儿都是一个钟点工干的，这就是并发。

再举一例子，客户的亲戚要来看望客户，还有不到一小时亲戚就要登门了。那么平时要花一小时才能做完的家务，如何才能提前做完呢？

答案是加人。多请几个钟点工来一起做事，比如某个钟点工专门扫地，某人专门抹桌子，某人专门负责洗菜、做饭。这样3人同时开工，就能缩短整体的时间，这就是并行。

从计算机的角度来说，单个CPU是需要被某个任务独占的，就如同钟点工，在扫地的同时不能做擦桌子的动作。如果她想去擦桌子，就需要将手头的扫地任务先停下来。当然，由于多个任务是不断切换的，因此，在外界看来，就有了“同时”执行多个任务的错觉。

现代的计算机大多是多核的，因此，多个CPU同时执行任务，就实现了任务的并行。

线程与并发

早期的分时系统中，每个进程以串行方式执行指令，并通过一组I/O指令来与外部设备通信。每条被执行的指令都有相应的“下一条指令”，程序中的控制流就是按照指令集的规则来确定的。

串行编程模型的优势是直观性和简单性，因为它模仿了人类的工作方式：每次只做一件事，做完再做其他事情。例如，早上起床，先穿衣，然后下楼，吃早饭。在编程语言中，这些现实世界的动作可以进一步被抽象为一组粒度更细的动作。例如，喝茶的动作可以被细化为：打开橱柜，挑选茶叶，将茶叶倒入杯中，查看茶壶的水是否够，不够要加水，将茶壶放在火炉上，点燃火炉，然后等水煮沸，等等。在等水煮沸这个过程中包含了一定程序的异步性。例如，在烧水过程中，你可以一直等，也可以做其他事情，比如开始烤面包，或者看报纸（这就是另一个异步任务），同时留意水是否煮沸了。但凡做事高效的人，总能在串行性和异步性之间找到合理的平衡，程序也是如此。

线程允许在同一个进程中同时存在多个线程控制流。线程会共享进程范围内的资源，例如内存句柄和文件句柄，但每个线程都有各自的程序计数器、栈以及局部变量。线程还提供了一种直观的分解模式来充分利用操作系统中的硬件并行性，而在同一个程序中的多个线程也可以被同时调度到多个CPU上运行。

毫无疑问，多线程编程使得程序任务并发成为可能。而并发控制主要是为了解决多个线程之间资源争夺等问题。并发一般发生在数据聚合的地方，只要有聚合，就有争夺发生，传统解决争夺的方式是采取线程锁机制，这是强行对CPU管理线程进行人为干预，线程唤醒成本高，新的无锁并发策略来源于异步编程、非阻塞I/O等编程模型。

并发带来的风险

多线程并发会带来以下问题。

·安全性问题。在没有充足同步的情况下，多个线程中的操作执行顺序是不可预测的，甚至会产生奇怪的结果。线程间的通信主要是通过共享访问字段及其字段所引用的对象来实现的。这种形式的通信是非常有效的，但可能导致两种错误：线程干扰（Thread Interference）和内存一致性错误（Memory Consistency Errors）。

·活跃度问题。一个并行应用程序的及时执行能力被称为它的活跃度（Liveness）。安全性的含义是“永远不发生糟糕的事情”，而活跃度则关注另外一个目标，即“某件正确的事情最终会发生”。当某个操作无法继续执行下去，就会发生活跃度问题。在串行程序中，活跃度问题形式之一就是无意中造成的无限循环（死循环）。而在多线程程序中，常见的活跃度问题主要有死锁、饥饿以及活锁。

·性能问题。在设计良好的并发应用程序中，线程能提升程序的性能，但无论如何，线程总是带来某种程度的运行时开销。而这种开销主要是在线程调度器临时关闭活跃线程并转而运行另外一个线程的上下文切换操作（Context Switch）上，因为执行上下文切换，需要保存和恢复执行上下文，丢失局部性，并且CPU时间将更多地花在线程调度而不是在线程运行上。当线程共享数据时，必须使用同步机制，而这些机制往往会抑制某些编译器优化，使内存缓存区中的数据无效，以及增加贡献内存总线的同步流量。所以这些因素都会带来额外的性能开销。

死锁

死锁（Deadlock）是指两个或两个以上的线程永远被阻塞，一直等待对方的资源。下面是一个用JAVA编写的死锁的例子。

Alphonse和Gaston是朋友，都很有礼貌。礼貌的一个严格的规则是，当你给一个朋友鞠躬时，你必须保持鞠躬，直到你的朋友回给你鞠躬。不幸的是，这条规则有个缺陷，那就是如果两个朋友同一时间向对方鞠躬，那就永远不会完了。这个示例应用程序中，死锁模型如下。

package com.waylau.java.demo.concurrency;
public class Deadlock {
public static void main(String[] args) {
final Friend alphonse = new Friend("Alphonse");
final Friend gaston = new Friend("Gaston");
new Thread(new Runnable() {
public void run() {
alphonse.bow(gaston);
}
}).start();
new Thread(new Runnable() {
public void run() {
gaston.bow(alphonse);
}
}).start();
}
static class Friend {
private final String name;
public Friend(String name) {
this.name = name;
}
public String getName() {
return this.name;
}
public synchronized void bow(Friend bower) {
System.out.format("%s: %s" + " has bowed to me!%n",
this.name, bower.getName());
bower.bowBack(this);
}
public synchronized void bowBack(Friend bower) {
System.out.format("%s: %s" + " has bowed back to me!%n",
this.name, bower.getName());
}
}
}

当它们尝试调用bowBack时两个线程将被阻塞。无论是哪个线程，都永远不会结束，因为每个线程都在等待对方鞠躬。这就是死锁了。

本节示例，可以在java-concurrency项目下找到。

饥饿

饥饿（Starvation）描述了一个线程由于访问足够的共享资源而不能执行程序的现象。这种情况一般出现在共享资源被某些“贪婪”线程占用，而导致资源长时间不被其他线程可用。例如，假设一个对象提供一个同步的方法，往往需要很长时间返回。如果一个线程频繁调用该方法，其他线程若也需要频繁地同步访问同一个对象则通常会被阻塞。

活锁

一个线程常常处于响应另一个线程的动作，如果其他线程也常常响应该线程的动作，那么就可能出现活锁（Livelock）。与死锁的线程一样，程序无法进一步执行。然而，线程是不会阻塞的，它们只是会忙于应对彼此的恢复工作。现实中的例子是，两人面对面试图通过一条走廊：Alphonse移动到他的左侧给Gaston让路，而Gaston移动到他的右侧想让Alphonse过去，两个人同时让路，但其实两人都挡住了对方，他们仍然彼此阻塞。

下节将介绍几种解决并发风险的常用方法。

解决并发风险

同步（Synchronization）和原子访问（Atomic Access），是解决并发风险的两种重要方式。

同步

同步是避免线程干扰和内存一致性错误的常用手段。下面就用Java来演示这几种问题，以及如何用同步解决这类问题。

1.线程干扰

下面描述当多个线程访问共享数据时错误是如何出现的。考虑下面的一个简单的类Counter。

public class Counter {
private int c = 0;
public void increment() {
c++;
}
public void decrement() {
c--;
}
public int value() {
return c;
}
}

其中的increment方法用来对c加1；decrement方法用来对c减1。然而，多个线程中都存在对某个Counter对象的引用，那么线程间的干扰就可能导致出现我们不想要的结果。

线程间的干扰出现在多个线程对同一个数据进行多个操作的时候，也就是出现了“交错（Interleave）”。这就意味着操作是由多个步骤构成的，而此时，在这多个步骤的执行上出现了叠加。Counter类对象的操作貌似不可能出现这种“交错”，因为其中的两个关于c的操作都很简单，只有一条语句。然而，即使是一条语句也会被虚拟机翻译成多个步骤，在这里，我们不深究虚拟机具体将上面的操作翻译成了什么样的步骤。只需要知道即使简单的像c++这样的表达式也会被翻译成3个步骤。

（1）获取c的当前值。

（2）对其当前值加1。

（3）将增加后的值存储到c中。

表达式c--也会被按照同样的方式进行翻译，只不过第二步变成了减1，而不是加1。

假定线程A中调用increment方法，线程B中调用decrement方法，而调用时间基本相同。如果c的初始值为0，那么这两个操作的“交错”顺序可能如下。

（1）线程A：获取c的值。

（2）线程B：获取c的值。

（3）线程A：对获取到的值加1，其结果是1。

（4）线程B：对获取到的值减1，其结果是-1。

（5）线程A：将结果存储到c中，此时c的值是1。

（6）线程B：将结果存储到c中，此时c的值是-1。

这样线程A计算的值就丢失了，也就是被线程B的值覆盖了。上面的这种“交错”只是其中的一种可能性。在不同的系统环境中，有可能是线程B的结果丢失了，或者是根本就不会出现错误。由于这种“交错”是不可预测的，线程间相互干扰造成的Bug是很难定位和修改的。

2.内存一致性错误

下面介绍通过共享内存出现的不一致的错误。

内存一致性错误发生在不同线程对同一数据产生不同的“看法”。导致内存一致性错误的原因很复杂，超出了本书的描述范围。庆幸的是，程序员并不需要知道出现这些原因的细节，我们需要的是一种可以避免这种错误的方法。

避免出现内存一致性错误的关键在于理解hAppens-before关系。这种关系是一种简单的方法，能够确保一条语句中对内存的写操作对于其他特定的语句都是可见的。为了理解这点，我们可以考虑如下的示例。假设定义了一个简单的int类型的字段并对其进行初始化。

int counter = 0;

该字段由两个线程共享：A和B。假定线程A对counter进行了自增操作。

counter ++;

然后，线程B输出counter的值。

System.out.println(counter);

如果以上两条语句是在同一个线程中执行的，那么输出的结果自然是1。但是如果这两条语句是在两个不同的线程中，那么输出的结果有可能是0。这是因为没有保证线程A对counter的修改操作对线程B来说是可见的，除非程序员在这两条语句间建立了一定的happens-before关系。

我们可以采取多种方式建立这种happens-before关系。使用同步就是其中之一。到目前为止，我们已经看到了两种建立这种happens-before的方式。

·当一条语句中调用了Thread.start方法，那么每一条和该语句已经建立了happens-before关系的语句都和新线程中的每一条语句有这种happens-before关系。引入并创建这个新线程的代码产生的结果对该新线程来说都是可见的。

·当一个线程终止了并导致另外的线程中调用Thread.join的语句返回时，这个终止了的线程中执行了的所有语句都与随后的join语句中的所有语句建立了这种happens-before关系。也就是说，终止了的线程中的代码效果对调用join方法的线程来说是可见的。

3.同步方法

Java编程语言中提供了两种基本的同步用语：同步方法（Synchronized Method）和同步语句（Synchronized Statement）。同步语句相对而言更为复杂，本节重点讨论同步方法。我们只需要在声明方法的时候增加关键字synchronized。

public class SynchronizedCounter {
private int c = 0;
public synchronized void increment() {
c++;
}
public synchronized void decrement() {
c--;
}
public synchronized int value() {
return c;
}
}

如果count是SynchronizedCounter类的实例，设置其方法为同步方法会有两个效果。

·首先，不可能出现对同一对象的同步方法的两个调用的“交错”。

当一个线程在执行一个对象的同步方法的时候，其他所有调用该对象的同步方法的线程都会被“挂起”，直到第一个线程对该对象操作完毕。

·其次，当一个同步方法退出时，会自动与该对象的同步方法的后续调用建立happens-before关系。这就确保了对该对象的修改对于其他线程是可见的。同步方法是一种简单的、可以避免线程相互干扰和内存一致性错误的策略：如果一个对象对多个线程都是可见的，那么所有对该对象的变量的读写都应该是通过同步方法完成的（一个例外就是final字段，它在对象创建完成后是不能被修改的。因此，在对象创建完毕后，可以通过非同步的方法对其进行安全的读取）。这种策略是有效的，但是可能导致“活跃度问题”。这点我们会在后面进行描述。

4.内部锁和同步

同步是构建在被称为“内部锁（Intrinsic Lock）”或者是“监视锁（Monitor Lock）”的内部实体上的。在API中通常被称为“监视器（Monitor）”。内部锁在两个方面都扮演着重要的角色：保证对对象状态访问的排他性，建立对象可见性相关的happens-before关系。每一个对象都有一个与之相关联的内部锁。按照传统的做法，当一个线程需要对一个对象的字段进行排他性访问并保持访问的一致性时，它必须在访问前先获取该对象的内部锁，然后才能访问，最后释放该内部锁。在线程获取对象的内部锁到释放对象的内部锁的这段时间，我们说该线程拥有该对象的内部锁。只要有一个线程已经拥有了一个内部锁，其他线程就不能再拥有该锁了，其他线程在试图获取该锁的时候会被阻塞。当一个线程释放了一个内部锁，那么就会建立起该动作和后续获取该锁之间的happens-before关系。

5.同步方法中的锁

当一个线程调用一个同步方法的时候，它就自动地获得了该方法所属对象的内部锁，并在方法返回的时候释放该锁。即使由于出现了没有被捕获的异常而导致方法返回，该锁也会被释放。

我们可能会感到疑惑：当调用一个静态的同步方法的时候会怎样？

静态方法是和类相关的，而不是和对象相关的。在这种情况下，线程获取的是该类的类对象的内部锁。这样对于静态字段的方法来说，这是由和类的实例的锁相区别的另外的一个锁来进行操作的。

6.同步语句

另外一种创建同步代码的方式就是使用同步语句。和同步方法不同，使用同步语句必须指明要使用哪个对象的内部锁。

public void addName(String name) {
synchronized(this) {
lastName = name;
nameCount++;
}
nameList.add(name);
}

在上面的示例中，方法addName需要对lastName和nameCount的修改进行同步，还要避免同步调用其他对象的方法（在同步代码段中调用其他对象的方法可能导致出现“活跃度”中描述的问题）。如果没有使用同步语句，那么将不得不使用一个单独、未同步的方法来完成对nameList.add的调用。

在改善并发性时，巧妙地使用同步语句能起到很大的帮助作用。例如，我们假定类MsLunch有两个实例字段，c1和c2，这两个变量绝不会一起使用。所有对这两个变量的更新都需要进行同步。但是没有理由阻止对c1的更新和对c2的更新出现交错——这样做会创建不必要的阻塞，进而降低并发性。此时，我们没有使用同步方法或者使用和this相关的锁，而是创建了两个单独的对象来提供锁。

public class MsLunch {
private long c1 = 0;
private long c2 = 0;
private Object lock1 = new Object();
private Object lock2 = new Object();
public void inc1() {
synchronized(lock1) {
c1++;}
}
public void inc2() {
synchronized(lock2) {
c2++;
}
}
}

采用这种方式时需要特别小心，我们必须确保相关字段的访问交错是完全安全的。

7.重入同步

回忆前面提到的：线程不能获取已经被别的线程获取的锁。但是线程可以获取自身已经拥有的锁。允许一个线程能重复获得同一个锁就称为重入同步（Reentrant Synchronization）。它是这样的一种情况：在同步代码中直接或者间接地调用了还有同步代码的方法，两个同步代码段中使用的是同一个锁。如果没有重入同步，在编写同步代码时需要额外小心，以避免线程将自己阻塞。

原子访问

下面介绍另外一种可以避免被其他线程干扰的做法的总体思路——原子访问。

在编程中，原子性动作就是指一次性有效完成的动作。原子性动作是不能在中间停止的：要么一次性完全执行完毕，要么就不执行。在动作没有执行完毕之前，是不会产生可见结果的。

通过前面的示例，我们已经发现了诸如c++这样的自增表达式并不属于原子性动作。即使是非常简单的表达式也包含了复杂的动作，这些动作可以被解释成许多别的动作。然而，的确存在一些原子性动作。

·对几乎所有的原生数据类型变量（除了long和double）的读写以及引用变量的读写都是原子的。

·对所有声明为volatile的变量的读写都是原子的，包括long和double类型。

原子性动作是不会出现交错的，因此，使用这些原子性动作时不用考虑线程间的干扰。然而，这并不意味着可以移除对原子性动作的同步，因为内存一致性错误还是有可能出现的。使用volatile变量可以降低内存一致性错误的风险，因为任何对volatile变量的写操作都和后续对该变量的读操作建立了happens-before关系。这就意味着对volatile类型变量的修改对于别的线程来说是可见的。更重要的是，这意味着当一个线程读取一个volatile类型的变量时，它看到的不仅仅是对该变量的最后一次修改，还看到了导致这种修改的代码带来的其他影响。

使用简单的原子变量访问比通过同步代码来访问变量更高效，但是需要程序员更多细心的考虑，以避免出现内存一致性错误。这种额外的付出是否值得完全取决于应用程序的大小和复杂度。

 提升系统并发能力

除了使用多线程外，还有以下方式可以提升系统的并发能力。

无锁化设计提升并发能力

加锁是为了避免在并发环境下，同时访问共享资源产生的风险问题。那么，在并发环境下，必须加锁吗？答案是否定的。并非所有的并发都需要加锁。适当降低锁的粒度，甚至是采用无锁化的设计，更能提升并发能力。

比如，JDK中的ConcurrentHashMap，巧妙采用了桶粒度的锁，避免了put和get中对整个map的锁定，尤其在get中，只对一个HashEntry做锁定操作，性能提升是显而易见的。

又比如，程序中可以合理考虑业务数据的隔离性，实现无锁化的并发。比如，程序中预计会有2个并发任务，那么每个任务可以对所需要处理的数据进行分组，任务1去处理尾数为0~4的业务数据，任务2处理尾数为5~9的业务数据。那么，这两个并发任务所要处理的数据，就是天然隔离的，也就无须加锁。

缓存提升并发能力

有时，为了提升整个网站的性能，我们会将经常需要访问的数据缓存起来，这样，在下次查询的时候，能快速地找到这些数据。缓存系统往往有着比传统的数据存储设备（如关系型数据库）更快的访问速度。

缓存的使用与系统的时效性有着非常大的关系。当我们的系统时效性要求不高时，选择使用缓存是极好的。当系统要求的时效性比较高时，则并不适合用缓存。在第14章中，我们还将详细探讨缓存的应用。

更细颗粒度的并发单元

在前面章节中，我们也讨论了线程是操作系统内核级别最小的并发单元。虽然与进程相比，创建线程的开销要小很多，但当在高并发场景下，创建大量的线程仍然会耗费系统大量的资源。为此，某些编程语言提供了更细颗粒度的并发单元，比如纤程，类似于Golang的goroutine、Erlang风格的actor。与线程相比，纤程可以轻松实现百万级的并发量，而且占用更加少的硬件资源。

Java虽然没有定义纤程，但仍有一些第三方库可供选择，比如Quasar。读者有兴趣的话，可以参阅Quasar在线手册。