第1章 引言

计算机产业正在经历着一场重大的结构重组和巨变，在没有其他变革之前，这个过程无疑将会继续进行。主要的芯片制造商，至少是现在，都纷纷放弃尝试研制速度更快的处理器。虽然摩尔定律仍旧适用：每年集成在同样大小空间中的晶体管数越来越多，然而，由于散热问题难于解决，它们的时钟速度无法继续得到提高。取而代之的做法是，制造商开始转向“多核”系统结构的研制，由多个处理器（多核）共享硬件高速缓存直接进行通信。通过将多个处理器同时分配给单一任务以获得更高的并行性，从而提高计算的效率。

多处理器系统结构的普及对计算机软件的发展带来了深刻的影响。直至今日以前，技术的进步意味着时钟速度的提升，时钟本身的加速导致了软件执行效率的提高。今天，这种搭便车的现象已不复存在，技术的进步不再指时钟速度的提升而是指并行度的提升，并行问题已经成为现代计算机科学的主要挑战。

本书着重讲述共享存储器通信方式下的多处理器编程(www.cppentry.com)技术。通常称这样的系统为共享存储器的多处理器，现在称之为多核。在各种规模的多处理器系统中都存在着不同的编程(www.cppentry.com)挑战—对于小规模的系统来说，需要协调单个芯片内的多个处理器对同一个共享存储单元的访问；对于大规模系统来说，需要协调一台超级计算机中各个处理器之间的数据路由。其次，现代计算机系统所固有的异步特征也给多处理器编程(www.cppentry.com)带来了挑战：在没有任何警示的情形下，系统的活动可以被各种不同的事件中止或延迟，例如中断、抢占、cache缺失和系统故障等。这种延迟现象本身是无法预测的，时延的长短也是不确定的：cache缺失可以造成不到十条指令执行时间的时延，页故障可能造成几百万条指令执行时间的时延，而操作系统抢占则会导致多达上亿条指令执行时间的时延。

本书从原理和实践这两个互补的方面阐述多处理器的程序设计。原理部分着重于可计算性理论：理解异步并发环境中的可计算问题。借助于一个理想化的计算模型，对异步并发环境中什么是可解的这一问题进行了深入研究。在这个模型中，多个并发线程对一组共享对象进行操作，这些并发线程的对象操作序列被称为并发程序或并发算法。该模型实质上也正是JavaTM、C#及C++(www.cppentry.com)线程库中所采用的计算模型。

令人不可思议的是，的确存在一些易于说明的共享对象，我们无法采用任何并发算法来实现。因此，在编写多处理器程序之前弄清楚什么问题不能用计算机解决是十分重要的。大多数困扰多处理器程序员的问题都源自于计算模型自身的限制，所以，对并发共享存储器模型中可计算性理论的理解是学习多处理器编程(www.cppentry.com)必不可少的一个环节。书中与原理相关的章节向读者展现了各种各样的可计算问题，以帮助读者尽快地了解异步可计算性理论，同时也讲述了如何通过硬件和软件机制来解决这些问题。

理解可计算性的关键在于描述和证明特定程序的实际执行行为，更准确地说，即程序正确性问题。由于其自身的特点，多处理器程序的正确性比顺序程序的正确性更为复杂，因此，需要一系列不同的辅助论证工具来证明并发程序的正确性，甚至有可能只是为了“非形式化地证明”程序正确性（实际上程序员往往这么做）。顺序程序的正确性主要关心程序的各种安全特性。安全性说明了“不好的事件”绝不会发生。例如，即使在断电时，交通指示灯也决不给任何方向显示绿灯。同样，并发程序的正确性也需要考虑安全性，但要考虑如何确保多个并发线程在各种可能的交互情形下的安全性，这使问题的解决变得难上加难。另外，还要考虑一个同样重要的因素，并发程序的正确性包括了各种各样的活性特性，而这种特性是顺序程序执行中所不会出现的。所谓活性，是指一个特定的“好的事件”一定会发生。例如，红色指示灯最终一定会变为绿灯。本书原理部分的最终目标就是要引入一系列分析推理并发程序的衡量标准和方法，为接下来研究现实对象和程序的正确性奠定基础。

本书的第二部分阐述多处理器程序设计的具体实践，着重于并发程序性能的分析。多处理器并发算法的性能分析与顺序算法的性能分析在风格上完全不同。顺序程序设计是基于一组易于理解且完备定义的抽象来进行的。编写顺序程序时，不需要了解底层的详细细节，例如，在硬盘和内存之间如何交换页面，在层次结构的高速缓存中如何移进/移出那些较小的内存单位。这种复杂的存储器层次结构实质上对程序员是不可见的，它被隐藏在一种完全的编程(www.cppentry.com)抽象之中。

然而在多处理器环境下，这种编程(www.cppentry.com)抽象被打破了，至少从性能角度来讲应该这样做。为了获得足够好的性能，程序设计人员有时需要比底层存储器系统“做得更好”，他们编写的程序代码可能让那些不熟悉多处理器系统结构的人感到莫名其妙。或许某一天，并发系统结构会像今天的顺序系统结构一样支持完全的抽象，然而到那时，程序设计人员早已了解这种新的系统结构了。

本书的原理部分讲述了一组共享对象和编程(www.cppentry.com)工具，着眼于每种对象和工具自身的能力，并借助于它们引出一些高层次的问题：用自旋锁来说明争用，用链表阐述数据结构设计中锁的作用等。这些问题对程序的性能都有着重要的影响，希望读者能充分理解它们，并能将所理解的内容应用于日后具体的多处理器系统设计中。最后，通过讨论诸如事务内存这种目前最先进的技术，作为本书的结束。

下面简要说明本书的写作风格。尽管有很多合适的语言可供选择，但本书仍采用了Java程序设计语言。当然，有大量的理由可以解释为何要做出这种选择，然而这样的话题还是更适于在闲暇时讨论! 附录解释了Java所支持的一些概念在其他的常用语言或库中是如何表示的，同时也介绍了关于多处理器硬件的一些基础知识。纵观全书，我们尽量避免列出关于程序和算法性能的具体数据，而是从一般情形来考虑。这样做的理由是：多处理器系统之间差异很大，在一台机器上工作良好的并发程序并不代表在另一台机器上也有同样的表现，紧密结合一般情形能够保证本书所陈述的结论具有更加长久的有效性。

在每一章的末尾都提供了相关文献的引用，读者可以根据参考文献目录找到相应内容以便进一步阅读。此外，每章都提供了一些习题，读者可以据此检查自己对知识的理解程度。

1.1   共享对象和同步（1）

在开始新工作的第一天，老板要求在一台能够支持10个并发线程的并行机上编写出查找1～1010之间素数的程序（不要考虑为什么这样做）。机器是按照分钟租用的，程序运行时间越长，花费也就越大。如果想给老板留下一个不错的印象，应该怎样去做？

在最初的尝试中，可能会为每个线程分配一个大小相等的输入域。各个线程分别找出109个数字内的素数，如图1-1所示。这种方法可能会由于一个简单但很重要的原因而最终导致失败，那就是相同大小的输入范围并不意味着相同的工作量。素数的分布是不均匀的：在1～109之间有很多素数，但分布在9*109～1010的素数却非常少。更为糟糕的是，整个范围内不同素数的计算时间也是不相同的：判断一个较大的数是否为素数通常要比判断较小的数所花费的时间更长。简而言之，没有理由认为这种方式能够使得整个工作是由所有的线程平均承担完成的，甚至也不清楚哪个线程承担的工作最多。

在线程间划分工作的另一种可行方案就是为每个线程一次分配一个整数（图1-2）。当一个线程结束对该整数的判断后，再次请求分配另一个整数。为此，需要引入一个共享计数器对象。该对象将一个整型值封装起来，线程通过调用getAndIncrement()方法对该整型值进行自增操作，并返回未被增加前的先前值。