当你打开本书，也许你正试图将你的应用改造成并行模式运行，也许你只是单纯地对并行程序感兴趣。无论出于何种原因，你正对并行计算充满好奇、疑问和求知欲。如果是这样，那就对了，带着你的好奇和疑问，让我们一起遨游并行程序的世界，深入了解它们究竟是如何工作的吧！
不过首先，我想要公布一条令人沮丧的消息。就在大伙儿都认为并行计算必然成为未来的大趋势时，2014年底，Avoiding ping pong论坛上，伟大的Linus Torvalds提出了一个截然不同的观点，他说：“忘掉那该死的并行吧！”（原文：Give it up. The whole "parallel computing is the future" is a bunch of crock.）
1.1 何去何从的并行计算
到底我们该如何选择呢？本节的目的就是拨云见日。
1.1.1 忘掉那该死的并行
Linus Torvalds是一个传奇式的人物（图1.1），是他给出了Linux的原型，并一直致力于推广和发展Linux系统。他在1991年首先在网络上发布了Linux源码，从此一发而不可收。Linux迅速崛起壮大，成为目前使用最广泛的操作系统之一。
图1-1 传奇的Linus Torvalds
自2002年起，Linus就决定使用BitKeeper作为Linux内核开发的版本控制工具，以此来维护Linux的内核源码。BitKeeper是一套分布式版本控制软件，它是一套商用系统，由BitMover公司开发。2005年，BitKeeper宣称发现Linux内核开发人员使用逆向工程来试图解析BitKeeper内部协议。因此，决定向Linus收回BitKeeper授权。尽管Linux核心团队与BitMover公司进行了协商，但是无法解决他们之间的分歧。因此，Linus决定自行研发版本控制工具来代替BitKeeper。于是，Git诞生了。
如果大家正在使用Git，我相信你们一定会被Git的魅力所折服，如果还没有了解过Git，那么我强烈建议你去关注一下这款优秀的产品。
而正是这位传奇人物，给目前红红火火的并行计算泼了一大盆冷水。那么，并行计算究竟应该何去何从呢？
在Linus的发言中这么说道：
Where the hell do you envision that those magical parallel algorithms would be used?
The only place where parallelism matters is in graphics or on the server side, where we already largely have it. Pushing it anywhere else is just pointless.
需要有多么奇葩的想象力才能想象出并行计算的用武之地？
并行计算只有在图像处理和服务端编程2个领域可以使用，并且它在这2个领域确实有着大量广泛的使用。但是在其他任何地方，并行计算毫无建树！
So the whole argument that people should parallelize their code is fundamentally flawed. It rests on incorrect assumptions. It's a fad that has been going on too long.
因此，人们在争论是否应该将他们的代码并行化是一个本质上的错误。这完全就基于一个错误的假设。“并行”是一个早该结束的时髦用语。
看了这段较为完整的表述，大家应该对Linus的观点有所感触，我对此也表示赞同。与串行程序不同，并行程序的设计和实现异常复杂，不仅仅体现在程序的功能分离上，多线程间的协调性、乱序性都会成为程序正确执行的障碍。只要你稍不留神，就会失之毫厘，谬以千里！混乱的程序难以阅读、难以理解，更难以调试。所谓并行，也就是把简单问题复杂化的典型。因此，只有“疯子”才会叫嚣并行就是未来（the crazies talking about scaling to hundreds of cores are just that - crazy）。
但是，Linus也提出了两个特例，那就是图像处理和服务端程序是可以、也需要使用并行技术的。仔细想想，为什么图像处理和服务端程序是特例呢？
和用户终端程序不同，图像处理往往拥有极大的计算量。一张1024×768像素的图片，包含多达78万6千多个像素。即使将所有的像素遍历一遍，也得花不少时间。更何况，图像处理涉及大量的矩阵计算。矩阵的规模和数量都会非常大。面对如此密集的计算，很有可能超过单核CPU的计算能力，所以自然需要引入多核计算了。
而服务端程序与一般的用户终端程序相比，一方面，服务端程序需要承受很重的用户访问压力。根据淘宝的数据，它在“双十一”一天，支付宝核心数据库集群处理了41亿个事务，执行285亿次SQL，生成15TB日志，访问1931亿次内存数据块，13亿个物理读。如此密集的访问，恐怕任何一台单机都难以胜任，因此，并行程序也就自然成了唯一的出路。另一方面，服务端程序往往会比用户终端程序拥有更复杂的业务模型。面对复杂业务模型，并行程序会比串行程序更容易适应业务需求，更容易模拟我们的现实世界。毕竟，我们的世界本质上是并行的。比如，当你开开心心去上学的时候，妈妈可能在家里忙着家务，爸爸在外打工赚钱，一家人其乐融融。如果有一天，你需要使用你的计算机来模拟这个场景，你会怎么做呢？如果你就在一个线程里，既做了你自己，又做了妈妈，又做了爸爸，显然这不是一种好的解决方案。但如果你使用三个线程，分别模拟这三个人，一切看起来又是那么自然，而且容易被人理解。
再举一个专业点的例子，比如基础平台Java虚拟机，虚拟机除了要执行main函数主线程外，还需要做JIT编译，需要做垃圾回收。无论是main函数、JIT编译还是垃圾回收，在虚拟机内部都实现为单独的一个线程。是什么使得虚拟机的研发人员这么做呢？显然，这是因为建模的需要。因为这里的每一个任务都是相对独立的。我们不应该将没有关联的业务代码拼凑在一起，分离为不同的线程更容易理解和维护。因此，使用并行也不完全出自性能的考虑，而有时候，我们会很自然地那么做。
1.1.2 可怕的现实：摩尔定律的失效
摩尔定律是由英特尔创始人之一戈登·摩尔提出来的。其内容为：集成电路上可容纳的电晶体（晶体管）数目，约每隔24个月便会增加一倍；经常被引用的“18个月”，是由英特尔首席执行官大卫·豪斯所说：预计18个月会将芯片的性能提高一倍（即更多的晶体管使其更快）。
说得直白点，就是每18个月到24个月，我们的计算机性能就能翻一番。
反过来说，就是每过18个月到24个月，你在未来用一半的价钱就能买到和现在性能相同的计算设备了。这听起来是一件多么激动人心的事情呀！
但是，摩尔定律并不是一种自然法则或者物理定律，它只是基于人为观测数据后，对未来的预测。按照这种速度，我们的计算能力将会按照指数速度增长，用不了多久，我们的计算能力就能超越“上帝”了！畅想未来，基于强劲的超级计算机，我们甚至可以模拟整个宇宙。
摩尔定律的有效性已经超过半个世纪了，然而，在2004年，Intel宣布将4GHz芯片的发布时间推迟到2005年，在2004年秋季，Intel宣布彻底取消4GHz计划（图1.2）。
图1.2 Intel CEO Barret单膝下跪对取消4GHz感到抱歉
是什么迫使世界顶级的科技巨头放弃4GHz的研发呢？显然，就目前的硅电路而言，很有可能已经走到了头。我们的制造工艺已经到了纳米了。1纳米是10-9米，也就是10亿分之一米。这已经是一个相当小的数字了。就目前的科技水平而言，如果无法在物质分子层面以下进行工作，那么也许4GHz的芯片就已经接近了理论极限。因为即使一个水分子，它的直径也有0.4纳米。再往下发展就显得有些困难。当然，如果我们使用完全不同的计算理论或者芯片生产工艺，也许会有本质的突破，但目前还没有看到这种技术被大规模使用的可能。
因此，摩尔定律在CPU的计算性能上可能已经失效。虽然，现在Intel已经研制出了4GHz芯片，但可以看到，在近10年的发展中，CPU主频的提升已经明显遇到了一些暂时不可逾越的瓶颈。
1.1.3 柳暗花明：不断地前进
虽然CPU的性能已经几近止步，长达半个世纪的摩尔定律轰然倒地。但是这依然没有阻挡科学家和工程师们带领我们不断向前的脚步。
从2005年开始，我们已经不再追求单核的计算速度，而着迷于研究如何将多个独立的计算单元整合到单独的CPU中，也就是我们所说的多核CPU。短短十几年的发展，家用型CPU，比如Intel i7就可以拥有4核心，甚至8核心。而专业服务器则通常可以配有几个独立的CPU，每一个CPU都拥有多达8个甚至更多的内核。从整体上看，专业服务器的内核总数甚至可以达到几百个。
非常令人激动，摩尔定律在另外一个侧面又生效了。根据这个定律，我们可以预测，每过18到24个月，CPU的核心数就会翻一番。用不了多久，拥有几十甚至上百CPU内核的芯片就能进入千家万户。
顶级计算机科学家唐纳德·尔文·克努斯（Donald Ervin Knuth），如此评价这种情况：在我看来，这种现象（并发）或多或少是由于硬件设计者已经无计可施了导致的，他们将摩尔定律失效的责任推脱给软件开发者。
唐纳德（图1.3）是著名计算机巨著《计算机程序设计艺术》的作者。《美国科学家》杂志曾将该书与爱因斯坦的《相对论》，狄拉克的《量子力学》和理查·费曼的《量子电动力学》等书并列为20世纪最重要的12本物理科学类专论书之一。
图1.3 唐纳德院士
1.1.4 光明或是黑暗
根据唐纳德的观点，摩尔定律本应该由硬件开发人员维持。但是，很不幸，硬件工程师似乎已经无计可施了。为了继续保持性能的高速发展，硬件工程师就破天荒地想出了将多个CPU内核塞进一个CPU里的奇妙想法。由此，并行计算就被非常自然地推广开来，而随之而来的问题也层出不穷，程序员的黑暗时期也随之到来。简化的硬件设计方案必然带来软件设计的复杂性。换句话说，软件工程师正在为硬件工程师无法完成的工作负责，因此，也就有了唐纳德的“他们将摩尔定律失效的责任推脱给了软件开发者”的说法。
所以，如何让多个CPU有效并且正确地工作也就成为了一门技术，甚至是很大的学问。比如，多线程间如何保证线程安全，如何正确理解线程间的无序性、可见性，如何尽可能提高并行程序的设计，又如何将串行程序改造为并行程序。而对并行计算的研究，也就是希望在这片黑暗中带来光明。
1.2 你必须知道的几个概念
现在，并行计算显然已经成为一门正式的学问。也许很多人（包括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次后，你应该可以顺利解决这个问题。因为这个时候，大家都会本能的对视，进行交流，保证这种情况不再发生。
但如果这种情况发生在两个线程间可能就不会那么幸运了。如果线程的智力不够，且都秉承着“谦让”的原则，主动将资源释放给他人使用，那么就会出现资源不断在两个线程中跳动，而没有一个线程可以同时拿到所有资源而正常执行。这种情况就是活锁。
1.3 并发级别
由于临界区的存在，多线程之间的并发必须受到控制。根据控制并发的策略，我们可以把并发的级别进行分类，大致上可以分为阻塞、无饥饿、无障碍、无锁、无等待几种。
1.3.1 阻塞（Blocking）
一个线程是阻塞的，那么在其他线程释放资源之前，当前线程无法继续执行。当我们使用synchronized关键字，或者重入锁时（我们将在第2、3章介绍这两种技术），我们得到的就是阻塞的线程。
无论是synchronized或者重入锁，都会试图在执行后续代码前，得到临界区的锁，如果得不到，线程就会被挂起等待，直到占有了所需资源为止。
1.3.2 无饥饿（Starvation-Free）
如果线程之间是有优先级的，那么线程调度的时候总是会倾向于满足高优先级的线程。也就说是，对于同一个资源的分配，是不公平的！如图1.7所示，显示了非公平与公平两种情况（五角星表示高优先级线程）。对于非公平的锁来说，系统允许高优先级的线程插队。这样有可能导致低优先级线程产生饥饿。但如果锁是公平的，满足先来后到，那么饥饿就不会产生，不管新来的线程优先级多高，要想获得资源，就必须乖乖排队。那么所有的线程都有机会执行。
图1.7 公平与非公平锁
1.3.3 无障碍（Obstruction-Free）
无障碍是一种最弱的非阻塞调度。两个线程如果是无障碍的执行，那么他们不会因为临界区的问题导致一方被挂起。换言之，大家都可以大摇大摆地进入临界区了。那么如果大家一起修改共享数据，把数据改坏了可怎么办呢？对于无障碍的线程来说，一旦检测到这种情况，它就会立即对自己所做的修改进行回滚，确保数据安全。但如果没有数据竞争发生，那么线程就可以顺利完成自己的工作，走出临界区。
如果说阻塞的控制方式是悲观策略。也就是说，系统认为两个线程之间很有可能发生不幸的冲突，因此，以保护共享数据为第一优先级。相对来说，非阻塞的调度就是一种乐观的策略。它认为多个线程之间很有可能不会发生冲突，或者说这种概率不大。因此大家都应该无障碍的执行，但是一旦检测到冲突，就应该进行回滚。
从这个策略中也可以看到，无障碍的多线程程序并不一定能顺畅的运行。因为当临界区中存在严重的冲突时，所有的线程可能都会不断地回滚自己的操作，而没有一个线程可以走出临界区。这种情况会影响系统的正常执行。所以，我们可能会非常希望在这一堆线程中，至少可以有一个线程能够在有限的时间内完成自己的操作，而退出临界区。至少这样可以保证系统不会在临界区中进行无限的等待。
一种可行的无障碍实现可以依赖一个“一致性标记”来实现。线程在操作之前，先读取并保存这个标记，在操作完成后，再次读取，检查这个标记是否被更改过，如果两者是一致的，则说明资源访问没有冲突。如果不一致，则说明资源可能在操作过程中与其他写线程冲突，需要重试操作。而任何对资源有修改操作的线程，在修改数据前，都需要更新这个一致性标记，表示数据不再安全。
1.3.4 无锁（Lock-Free）
无锁的并行都是无障碍的。在无锁的情况下，所有的线程都能尝试对临界区进行访问，但不同的是，无锁的并发保证必然有一个线程能够在有限步内完成操作离开临界区。
在无锁的调用中，一个典型的特点是可能会包含一个无穷循环。在这个循环中，线程会不断尝试修改共享变量。如果没有冲突，修改成功，那么程序退出，否则继续尝试修改。但无论如何，无锁的并行总能保证有一个线程是可以胜出的，不至于全军覆没。至于临界区中竞争失败的线程，它们则必须不断重试，直到自己获胜。如果运气很不好，总是尝试不成功，则会出现类似饥饿的现象，线程会停止不前。
下面就是一段无锁的示意代码，如果修改不成功，那么循环永远不会停止。
while (!atomicVar.compareAndSet(localVar, localVar+1)) { localVar = atomicVar.get(); }
有关无锁，我们将安排在“锁的优化与注意事项”一章中详细介绍。
1.3.5 无等待（Wait-Free）
无锁只要求有一个线程可以在有限步内完成操作，而无等待则在无锁的基础上更进一步进行扩展。它要求所有的线程都必须在有限步内完成，这样就不会引起饥饿问题。如果限制这个步骤上限，还可以进一步分解为有界无等待和线程数无关的无等待几种，它们之间的区别只是对循环次数的限制不同。
一种典型的无等待结构就是RCU（Read-Copy-Update）。它的基本思想是，对数据的读可以不加控制。因此，所有的读线程都是无等待的，它们既不会被锁定等待也不会引起任何冲突。但在写数据的时候，先取得原始数据的副本，接着只修改副本数据（这就是为什么读可以不加控制），修改完成后，在合适的时机回写数据。
1.4 有关并行的两个重要定律
有关为什么要使用并行程序的问题在之前已经进行了简单的探讨。总的来说，最重要的应该是出于两个目的。第一，为了获得更好的性能；第二，由于业务模型的需要，确实需要多个执行实体。在这里，我将更加关注于第一种情况，也就是有关性能的问题。将串行程序改造为并发，一般来说可以提供程序的整体性能，但是究竟能提高多少，甚至说究竟是否真的可以提高，还是一个需要研究的问题。目前，主要有两个定律对这个问题进行解答，一个是Amdahl定律，另外一个是Gustafson定律。
1.4.1 Amdahl定律
Amdahl定律是计算机科学中非常重要的定律。它定义了串行系统并行化后的加速比的计算公式和理论上限。
加速比定义：加速比 = 优化前系统耗时 / 优化后系统耗时
即，所谓加速比，就是优化前的耗时与优化后耗时的比值。加速比越高，表明优化效果越明显。图1.8显示了Amdahl公式的推导过程，其中n表示处理器个数，T表示时间，T1表示优化前耗时（也就是只有1个处理器时的耗时），Tn表示使用n个处理器优化后的耗时。F是程序中只能串行执行的比例。
图1.8 Amdahl公式的推导
根据这个公式，如果CPU处理器数量趋于无穷，那么加速比与系统的串行化率成反比，如果系统中必须有50%的代码串行执行，那么系统的最大加速比为2。
假设有一程序分为以下步骤执行，每个执行步骤花费100个时间单位。其中，只有步骤2和步骤5可以进行并行，步骤1、3、4必须串行，如图1.9所示。在全串行的情况下，系统合计耗时500个时间单位。
图1.9 串行工作流程
若将步骤2和步骤5并行化，假设在双核处理上，则有如图1.10所示的处理流程。在这种情况下，步骤2和步骤5的耗时将为50个时间单位。故系统整体耗时为400个时间单位。根据加速比的定义有：
加速比=优化前系统耗时/优化后系统耗时= 500 / 400 = 1.25
图1.10 双核处理上的并行化
或者根据前文中给出的加速比公式。由于5个步骤中，3个步骤必须串行，因此其串行化比重为3/5=0.6，即F=0.6，且双核处理器的处理器个数N为2。代入公式得：
加速比=1/(0.6+(1-0.6)/2)=1.25
在极端情况下，假设并行处理器个数为无穷大，则有如图1.11所示的处理过程。步骤2和步骤5的处理时间趋于0。即使这样，系统整体耗时依然大于300个时间单位。即加速比的极限为500/300=1.67。
图1.11 极端情况下的并行化
使用加速比计算公式，N趋于无穷大，有加速比=1/F，且F=0.6，故有加速比=1.67。
由此可见，为了提高系统的速度，仅增加CPU处理器的数量并不一定能起到有效的作用。需要从根本上修改程序的串行行为，提高系统内可并行化的模块比重，在此基础上，合理增加并行处理器数量，才能以最小的投入，得到最大的加速比。
注意：根据Amdahl定律，使用多核CPU对系统进行优化，优化的效果取决于CPU的数量以及系统中的串行化程序的比重。CPU数量越多，串行化比重越低，则优化效果越好。仅提高CPU数量而不降低程序的串行化比重，也无法提高系统性能。
1.4.2 Gustafson定律
Gustafson定律也试图说明处理器个数、串行比例和加速比之间的关系，如图1.12所示，但是Gustafson定律和Amdahl定律的角度不同。同样，加速比都定义为优化前的系统耗时除以优化后的系统耗时。
图1.12 Gustafson定律的推导
可以看到，由于切入角度的不同，Gustafson定律的公式和Amdahl定律的公式截然不同。从Gustafson定律中，我们可以更容易地发现，如果串行化比例很小，并行化比例很大，那么加速比就是处理器的个数。只要你不断地累加处理器，就能获得更快的速度。
1.4.3 Amdahl定律和Gustafson定律是否相互矛盾
由于Amdahl定律和Gustafson定律的结论不同，这是不是说明这两个理论之间有一个是错误的呢？其实不然，两者的差异其实是因为这两个定律对同一个客观事实从不同角度去审视后的结果，它们的偏重点有所不同。
举一个生活的例子，一辆汽车行驶在相聚60公里的城市。你花了一个小时，行驶了30公里。无论接下来开多快，你都不可能达到90公里/小时的时速。图1.13很好地说明了原因。
图1.13 Amdahl定律的偏重点
求解图1.13中的方程，你会发现如果你想达到90公里的时速，那么你从AB中点到达B点的时间会是一个负数，这显然不是一个合理的结论。实际上，如果前半程30km你使用了一小时，那么即使你从中点到B点使用光速，也只能把整体的平均时速维持在60km/hour。
也就是说Amdahl强调：当串行比例一定时，加速比是有上限的，不管你堆叠多少个CPU参与计算，都不能突破这个上限！
而Gustafson定律的出发点与之不同，对Gustafson定律来说，不管你从A点出发的速度有多慢，只要给你足够的时间和距离，只要你后期的速度比期望值快那么一点点，你总是可以把平均速度调整到非常接近那个期望值的。比如，你想要达到均速90km/hour，即使在前30km你的时速只有30km/hour，你只要在很后面的速度达到91km/hour，给你足够的时间和距离，你总有一天可以把均速提高到90km/hour。
因此，Gustafson定律关心的是：如果可被并行化的代码所占比重足够多，那么加速比就能随着CPU的数量线性增长。
所以，这两个定律并不矛盾。从极端角度来说，如果系统中没有可被串行化的代码（即F=1），那么对于这两个定律，其加速比都是1。反之，如果系统中可串行化代码比重达到100%，那么这两个定律得到加速比都是n（处理器个数）。
1.5 回到Java：JMM
前面我已经介绍了有关并行程序的一些关键概念和定律。这些概念可以说是与语言无关的。无论你使用Java或者C，或者其他任何一门语言编写并发程序，都有可能会涉及这些问题。但本书依然是一本面向Java程序员的书籍。因此，在本章最后，我们还是希望可以探讨一下有关Java的内存模型（JMM）。
由于并发程序要比串行程序复杂很多，其中一个重要原因是并发程序下数据访问的一致性和安全性将会受到严重挑战。如何保证一个线程可以看到正确的数据呢？这个问题看起来很白痴。对于串行程序来说，根本就是小菜一碟，如果你读取一个变量，这个变量的值是1，那么你读到的一定是1，就这么简单的问题在并行程序中居然变得复杂起来。事实上，如果不加控制地任由线程胡乱并行，即使原本是1的数值，你也有可能读到2。因此，我们需要在深入了解并行机制的前提下，再定义一种规则，保证多个线程间可以有效地、正确地协同工作。而JMM也就是为此而生的。
JMM的关键技术点都是围绕着多线程的原子性、可见性和有序性来建立的。因此，我们首先必须了解这些概念。
1.5.1 原子性（Atomicity）
原子性是指一个操作是不可中断的。即使是在多个线程一起执行的时候，一个操作一旦开始，就不会被其他线程干扰。
比如，对于一个静态全局变量int i，两个线程同时对它赋值，线程A给他赋值1，线程B给它赋值为-1。那么不管这2个线程以何种方式、何种步调工作，i的值要么是1，要么是-1。线程A和线程B之间是没有干扰的。这就是原子性的一个特点，不可被中断。
但如果我们不使用int型而使用long型的话，可能就没有那么幸运了。对于32位系统来说，long型数据的读写不是原子性的（因为long有64位）。也就是说，如果两个线程同时对long进行写入的话（或者读取），对线程之间的结果是有干扰的。
大家可以仔细观察一下下面的代码：
public class MultiThreadLong { public static long t=0; public static class ChangeT implements Runnable{ private long to; public ChangeT(long to){ this.to=to; } @Override public void run() { while(true){ MultiThreadLong.t=to; Thread.yield(); } } } public static class ReadT implements Runnable{ @Override public void run() { while(true){ long tmp=MultiThreadLong.t; if(tmp!=111L && tmp!=-999L && tmp!=333L && tmp!=-444L) System.out.println(tmp); Thread.yield(); } } } public static void main(String[] args) { new Thread(new ChangeT(111L)).start(); new Thread(new ChangeT(-999L)).start(); new Thread(new ChangeT(333L)).start(); new Thread(new ChangeT(-444L)).start(); new Thread(new ReadT()).start(); } }
上述代码有4个线程对long型数据t进行赋值，分别对t赋值为111、-999、333、444。然后，有一个读取线程，读取这个t的值。一般来说，t的值总是这4个数值中的一个。这当然也是我们的期望了。但很不幸，在32位的Java虚拟机中，未必总是这样。
如果读取线程ReadT总是读到合理的数据，那么这个程序应该没有任何输出。但是，实际上，这个程序一旦运行，就会大量输出以下信息：（再次强调，使用32位虚拟机）
…… -4294966963 4294966852 -4294966963 ……
这里截取了部分输出。我们可以看到，读取线程居然读到了两个似乎根本不可能存在的数值。这不是幻觉，在这里，你看到的确实是事实，其中的原因也就是因为32位系统中long型数据的读和写都不是原子性的，多线程之间相互干扰了！
如果我给出这几个数值的2进制表示，大家就会有更清晰的认识了：
+111=0000000000000000000000000000000000000000000000000000000001101111 -999=1111111111111111111111111111111111111111111111111111110000011001 +333=0000000000000000000000000000000000000000000000000000000101001101 -444=1111111111111111111111111111111111111111111111111111111001000100 +4294966852=0000000000000000000000000000000011111111111111111111111001000100 -4294967185=1111111111111111111111111111111100000000000000000000000001101111
上面显示了这几个相关数字的补码形式，也就是在计算机内的真实存储内容。不难发现，这个奇怪的4294966852，其实是111或者333的前32位，与-444的后32位夹杂后的数字。而-4294967185只是-999或者-444的前32位与111夹杂后的数字。换句话说，由于并行的关系，数字被写乱了，或者读的时候，读串位了。
通过这个例子，我想大家都原子性应该有了基本的认识。
1.5.2 可见性（Visibility）
可见性是指当一个线程修改了某一个共享变量的值，其他线程是否能够立即知道这个修改。显然，对于串行程序来说，可见性问题是不存在的。因为你在任何一个操作步骤中修改了某个变量，那么在后续的步骤中，读取这个变量的值，一定是修改后的新值。
