Question

现在，并行计算显然已经成为一门正式的学问。也许很多人（包括Linus在内），都会觉得并行计算或者说并行算法是多么奇葩。但现在我们也不得不承认，在某些领域，这些算法还是有用武之地的。既然说服务端编程还是大量需要并行计算的，而Java也主要占领着服务端市场，那么对Java的并行计算的研究也就显得非常的必要。但首先，我想在这里先介绍几个重要的相关概念。

1.2.1　同步（Synchronous）和异步（Asynchronous）

同步和异步通常用来形容一次方法调用。同步方法调用一旦开始，调用者必须等到方法调用返回后，才能继续后续的行为。异步方法调用更像一个消息传递，一旦开始，方法调用就会立即返回，调用者就可以继续后续的操作。而异步方法通常会在另外一个线程中“真实”地执行。整个过程，不会阻碍调用者的工作。图1.4显示了同步方法调用和异步方法调用的区别。对于调用者来说，异步调用似乎是一瞬间就完成的。如果异步调用需要返回结果，那么当这个异步调用真实完成时，则会通知调用者。

图1.4　同步和异步方法调用

打个比方，比如我们去购物，如果你去商场实体店买一台空调，当你到了商场看中了一款空调，你就想售货员下单。售货员去仓库帮你调配物品。这天你热得实在不行了，就催着商家赶紧给你送货，于是你就等在商店里，候着他们，直到商家把你和空调一起送回家，一次愉快的购物就结束了。这就是同步调用。

不过，如果我们赶时髦，就坐在家里打开电脑，在网上订购了一台空调。当你完成网上支付的时候，对你来说购物过程已经结束了。虽然空调还没送到家，但是你的任务都已经完成了。商家接到了你的订单后，就会加紧安排送货，当然这一切已经跟你无关了。你已经支付完成，想干什么就能去干什么，出去溜几圈都不成问题，等送货上门的时候，接到商家的电话，回家一趟签收就完事了。这就是异步调用。

1.2.2　并发（Concurrency）和并行（Parallelism）

并发和并行是两个非常容易被混淆的概念。它们都可以表示两个或者多个任务一起执行，但是偏重点有些不同。并发偏重于多个任务交替执行，而多个任务之间有可能还是串行的。而并行是真正意义上的“同时执行”。图1.5很好地诠释了这点。

图1.5　并发和并行

严格意义上来说，并行的多个任务是真实的同时执行，而对于并发来说，这个过程只是交替的，一会儿运行任务A一会儿执行任务B，系统会不停地在两者间切换。但对于外部观察者来说，即使多个任务之间是串行并发的，也会造成多任务间是并行执行的错觉。

这两种情况在生活中都很常见。我曾经去黄山旅游过两次，黄山风景奇特，有着“五岳归来不看山，黄山归来不看岳”的美称。只要去过黄山的人都应该知道，导游时常挂在嘴边的“走路不看景，看景不走路”。因为黄山顶上经常下雨，地面湿滑，地形险峻。如果边走边看，跌倒擦伤那是常有的事。安全起见，就要求旅游在看景的时候，能够停下脚步，走路的时候能够专心看着地面，管好双脚。这就是“并发”。它和“边走边看”有着非常奇妙的关系，因为这两种情况，都可以被认为是“同时在看景和走路”。

那么在黄山上真正的“并行”应该是什么样子呢？聪明的同学应该可以想到，那就是坐缆车上山。缆车可以代替步行，你坐在缆车上才能专心欣赏沿途的风景，“走路”这些事情全部交给缆车去完成就好了。

实际上，如果系统内只有一个CPU，而使用多进程或者多线程任务，那么真实环境中这些任务不可能是真实并行的，毕竟一个CPU一次只能执行一条指令，这种情况下多进程或者多线程就是并发的，而不是并行的（操作系统会不停切换多个任务）。真实的并行也只可能出现在拥有多个CPU的系统中（比如多核CPU）。

由于并发的最终效果可能是和并行一样的，因此，如果没有特别的需要，我在本书中不会特别强调两者的区别。

1.2.3　临界区

临界区用来表示一种公共资源或者说是共享数据，可以被多个线程使用。但是每一次，只能有一个线程使用它，一旦临界区资源被占用，其他线程要想使用这个资源，就必须等待。

比如，在一个办公室里有一台打印机。打印机一次只能执行一个任务。如果小王和小明同时需要打印文件，很显然，如果小王先下发了打印任务，打印机就开始打印小王的文件。小明的任务就只能等待小王打印结束后才能打印。这里的打印机就是一个临界区的例子。

在并行程序中，临界区资源是保护的对象，如果意外出现打印机同时执行两个打印任务，那么最可能的结果就是打印出来的文件就会是损坏的文件。它既不是小王想要的，也不是小明想要的。

1.2.4　阻塞（Blocking）和非阻塞（Non-Blocking）

阻塞和非阻塞通常用来形容多线程间的相互影响。比如一个线程占用了临界区资源，那么其他所有需要这个资源的线程就必须在这个临界区中进行等待。等待会导致线程挂起，这种情况就是阻塞。此时，如果占用资源的线程一直不愿意释放资源，那么其他所有阻塞在这个临界区上的线程都不能工作。

非阻塞的意思与之相反，它强调没有一个线程可以妨碍其他线程执行。所有的线程都会尝试不断前向执行。有关这个概念，将在本章“并发级别”一节中做更详细的描述。

1.2.5　死锁（Deadlock）、饥饿（Starvation）和活锁（Livelock）

死锁、饥饿和活锁都属于多线程的活跃性问题。如果发现上述几种情况，那么相关线程可能就不再活跃，也就说它可能很难再继续往下执行了。

死锁应该是最糟糕的一种情况了（当然，其他几种情况也好不到哪里去），图1.6显示了一个死锁的发生。

图1.6　死锁的发生

A、B、C、D四辆小车在这种情况下都无法继续行驶了。它们彼此之间相互占用了其他车辆的车道，如果大家都不愿意释放自己的车道，那么这个状态将永远维持下去，谁都不可能通过。死锁是一个很严重的，并且应该避免和时时小心的问题，我们将安排在“锁的优化与注意事项”一章中进行更详细的讨论。

饥饿是指某一个或者多个线程因为种种原因无法获得所需要的资源，导致一直无法执行。比如它的线程优先级可能太低，而高优先级的线程不断抢占它需要的资源，导致低优先级线程无法工作。在自然界中，母鸟喂食雏鸟时，很容易出现这种情况。由于雏鸟很多，食物可能有限，雏鸟之间的食物竞争可能非常厉害，小雏鸟因为经常抢不到食物，有可能会被饿死。线程的饥饿也非常类似这种情况。另外一种可能是，某一个线程一直占着关键资源不放，导致其他需要这个资源的线程无法正常执行，这种情况也是饥饿的一种。与死锁相比，饥饿还是有可能在未来一段时间内解决的（比如高优先级的线程已经完成任务，不再疯狂的执行）。

活锁是一种非常有趣的情况。不知道大家是不是有遇到过这么一种场景，当你要坐电梯下楼，电梯到了，门开了，这时你正准备出去。但很不巧的是，门外一个人挡着你的去路，他想进来。于是，你很绅士地靠左走，避让对方。同时，对方也是非常绅士地，但他靠右走希望避让你。结果，你们俩就又撞上了。于是乎，你们都意识到了问题，希望尽快避让对方，你立即向右边走，同时，他立即向左边走。结果，又撞上了！不过介于人类的智能，我相信这个动作重复2、3次后，你应该可以顺利解决这个问题。因为这个时候，大家都会本能的对视，进行交流，保证这种情况不再发生。

但如果这种情况发生在两个线程间可能就不会那么幸运了。如果线程的智力不够，且都秉承着“谦让”的原则，主动将资源释放给他人使用，那么就会出现资源不断在两个线程中跳动，而没有一个线程可以同时拿到所有资源而正常执行。这种情况就是活锁。