并发的艺术(The Art of Concurrency: A Thread Monkey's Guide to Writing Parallel Applications)

内容简介
如果你希望通过并发编程来充分发挥多核处理器的强大功能，那么本书将为你提供所需的理论知识和实际经验。《并发的艺术》是为数不多的几本介绍如何在多核处理器的共享内存模型中实现算法的书籍之一，它并非仅仅介绍一些理论模型或者分布式内存架构。本书详细分析了各种示例程序，这些内容非常有助于你将串行代码转换为并行代码，此外还介绍了如何避免一些常见的错误。
本书的作者是Intel公司的一位资深工程师，他从事并发编程已经有20多年的时间，本书将帮助你：
- 分析在共享内存模型与在分布式内存模型之间的编程差异。
- 学习如何设计多线程程序，包括对程序的测试和调优。
- 了解如何最有效地使用各种不同的线程化机制，包括Windows线程，POSIX线程，OpenMP以及Intel Threading Building Blocks。
- 掌握如何实现各种并发算法，包括排序，搜索，图以及其他一些使用的计算。
《并发的艺术》还介绍了如何在算法中实现高可伸缩性，使得算法能够充分发挥将来包含更多核处理器的强大功能。对于开发并行代码算法的程序员来说，本书是必不可少的

作者简介
Clay Breshears博士，目前是一位课程设计师，主要从事多核与多线程方面的编程和培训。

    多核处理器的出现，使得程序开发人员开始关注并发编程技术，然而要掌握并合理使用并发技术却并不容易。对于长期编写串行程序的开发人员来说，转向并发编程并不仅仅意味在代码中增加一些同步对象，或者调用某个第三方并行库的API ，而是要在程序架构设计、编程模型选择、代码测试以及调优等方面做出整体改变。与其他任何一种技术一样，程序员在学习并发编程时应该采取一种循序渐进的、由理论到实践的方法，而这也是本书为读者给出的学习方式。
    《并发的艺术》的前面部分给出了一个完备的并发程序开发框架，包括并发的基础理论知识、不同并发模型的选择与适用环境、编写并发程序的基本步骤，并发算法的正确性证明与性能评价，以及在编写并发程序时遵循的一些指导原则等。这些内容使读者能够对并发编程有基本的了解，在开始动手编写并发代码之前首先作出全面的思考，这样不仅可以提高编码的效率，而且可以减少代码中的错误以及后续的修改/维护工作。
    之后，书中对一些典型算法的并行化过程进行了详细分析，这些算法包括并行求和与前缀求和、映射归约、排序、搜索以及图算法等。在对算法并行化时采取的讲解方式是：首先给出算法的串行实现，然后对算法中的并发性进行分析并选择合理的技术来实现这些并发性，最后从效率、简单性、可移植性以及可伸缩性等4个方面对并发算法衡量。
    这些分析也是本书中最具价值的部分，读者在阅读这些内容时要反复思考和琢磨，做到融会贯通，举一反三。这些算法虽然简单，但我们都知道复杂算法通常是由多个简单算法组成的，因此只要掌握了这些简单并发算法的设计，更复杂的算法也就会迎刃而解。
    总体来说，本书是一本更侧重于实践的书，书中提到的许多技术都可以直接应用到日常工作中，并且书中的代码只需要稍加修改就可以直接使用。本书适合所有程序员阅读，只需具备一些基础的数据结构和算法知识，就不难理解本书的内容。

为什么要读这本书？
多核处理器在问世之初就展示出了强大的威力。由于发热量以及能耗的增加，处理器的时钟频率无法再像过去三十年那样每18个月翻一番。为了保证下一代处理器运算能力的持续增加，处理器生产商们开始在芯片内部设计多个处理器核。虽然多核处理器的运行速度有所降低，但与时钟频率翻番的单核处理器核相比，它们产生的热量更少，并且能耗也更低。
然而，如何来充分发挥多核的强大运算能力？我们可以每次运行多个程序，并且为每个程序专门分配一个处理器核来运行。这就实现了真正意义上的并行执行。然而，在这种情况下能够同时运行的程序数量也只能是等于处理器核的数量。如果这些程序并非是计算密集型的程序，那么可能会浪费计算周期。
另一种方式是，在编写程序时，将需要执行大量计算并且在计算之间彼此独立的代码放在另外的处理器核上执行。编写这种程序的过程就被称之为并发编程。与任何一种编程语言或者方法一样，在设计和实现并发程序中同样存在着许多技术，窍门，误区以及工具。我始终觉得这种编程还是一种“艺术”，留有足够大的自由发挥空间，而并非像一门“科学”那样有着严格的步骤可供遵循。因此，本书将介绍并发编程中的一些基础知识和少量的“内幕技术”。
在过去，并行编程只是少数程序员的专有技术，他们的研究领域通常与科学计算等方面相关。然而，从现在开始，并发编程正在逐步成为一种主流技术。并行编程最终将编程“编程”的同义词。现在，你要着手开始学习并行编程，或者至少要跟上并发编程的发展趋势。

本书的目标读者
本书适合于各种程序员阅读。
在我工作的计算机公司中，团队里只有我一个人拥有计算机科学学位。当我提到想通过一个确定型下推自动机（Deterministic Pushdown Automata）来解析LR(1)语法时，在办公室里也只有另一个人能明白我的意思。因此，计算机专业的学生只是本书目标读者的一部分。 在本书中，我尽可能地少使用计算机专业的特定知识。我假设本书的读者已经在数据结构，算法，以及算法复杂度等方面具备了一定的基础知识，这些知识通常会在计算机科学专业的本科课程中教授。对于我所介绍的其他内容，我都会尽力给出足够详细的解释来使读者了解其中的思想。如果你有着一年以上的编码经验，那么理解起来就不成问题。
我用C语言编写了所有的代码。这并不意味着不尊重其他语言，而是我发现C语言是支持线程并且得到最多认同的编程语言之一。其他语言，例如Java和C#等，同样支持线程，但如果我在书中用这些语言来编写代码，而你又没有使用过这些语言，那么就不会阅读本书。我认为，大多数能够编写并发程序的程序员至少都能够“读懂”C代码。理解在代码中使用的各种并发方法要比用某种特定语言来编写代码的能力更为重要。你同样可以在C#或者Java中实现这些思想。
我假设你至少已经读过了一本介绍多线程编程的书。在市面上已经有许多这类的书，因此我不会在本书中详细介绍多线程编程的各种机制（因为这些内容至少要占到1到2本书的篇幅）。在本书中我同样不会只使用一种编程模式，因为许多编程模式的功能在很大程度上都是重叠的。在本书的后半部分，我将给出如何在各种算法中使用线程化方法。在一些情况中，如果某种方法与其他方法在使用上存在较大的差异，那么在书中将指出这些差异。
对于在本书中使用的各种线程化编程方法，我都给出了简要的回顾，这样你能够重新回想起它们，或者了解那些还没有使用过的方法。但我的本意并非是说你需要知道所有编写多线程程序的方式。只要了解其中一种就足够了。不过，如果你换了一份工作或者发现你所掌握的多线程编程方法不能很好地解决你所遇到的问题，那么了解其他的多线程编程方就是有用的——这将帮助你很快地学习和使用某种新方法。

本书的内容
第1章，“想不想让程序运行得更快？想的话就举手！”，介绍了一些在并发编程中常见的问题以及相应的答案。本章介绍了“并行（Parallel）”与“并发（Concurrent）”这两个术语的区别，并给出了线程化方法中的四个步骤。在本章的结尾介绍了关于并发编程的一些背景知识，以及在分布式内存模型和共享内存模型之间的一些差异和相似性。
第2章，“是否采用并发？”，介绍了如何根据串行算法来设计并发算法。本章详细阐述了两种并发设计模型——任务分解与数据分解。本章还给出了一些无法并行化的串行代码示例。在一些可以并行化的示例中，我给出了相应的提示和技巧来将串行代码修改为更易于并行化的形式。
第3章，“算法正确性证明与性能衡量”，首先介绍了如何证明在并发算法中不包含一些常见的线程化错误，并且指出了你所可能遇到的问题（这样就可以修复这些问题）。在本章的第2部分介绍了如何判断并发代码相对于最初串行代码的性能提升程度。在本章的结尾处简单回顾了硬件从过去一直到当前多核处理器的发展历程，因为我觉得似乎只有在这个地方才合适介绍这些内容。
第4章，“多线程程序设计中的八条简单规则”，介绍的内容在本章标题中已经说得很清楚了。在本中的许多地方都将提到这些简单的规则。
第5章，“线程化库”，介绍了OpenMP，Intel Threading Building Block，POSIX线程以及Windows线程库等。在本章的结尾处还介绍了在一些特定领域使用的库。
第6章，“并行求和与前缀求和”，详细介绍了两种并发算法。本章同样还介绍了并发选择算法，并且在实现并发选择算法时分别使用了并行求和与前缀求和。
第7章，“映射归约”，介绍了映射归约算法框架；如何实现一个完全并发的归约运算；并且在本章的末尾介绍了如何通过映射归约算法框架来找出互为友好的数值。
第8章，“排序”，介绍了并发的冒泡排序，奇偶排序，希尔排序，快速排序，以及两种基数排序。
第9章，“搜索”，介绍了对已排序数据和未排序数据进行并发搜索的算法。
第10章，“图算法”，分析了深度优先搜索算法和宽度优先搜索算法。同时还讨论了如何并发地计算两节点之间最短路径以及最小生成树。
第11章，“线程化工具”，介绍了一些软件工具来帮助找出并发程序中线程化错误和性能瓶颈。当并发代码变得越来越复杂时，你将发现这些工具的强大之处，它们能够在几分钟之内诊断出问题，而不是数天或者数个星期。

本书的勘误，示例以及其他信息位于以下页面： http://www.oreilly.com/catalog/9780596521530 
关于本书的技术问题请发电子邮件到： bookquestions@oreilly.com

致谢
我想感谢以下对我的职业生涯有着重要影响并且支持我写这本书的人们。如果没有他们的帮助和支持，也就不会有这本书，而我的生活也不会像现在这么美妙。
感谢JOSEPH SARGENT和STANLEY CHASE出品的电影《Colossus:The Forbin Project》(1970)。这部电影对早期的我产生了非常大的影响，它使我对计算机编程产生了浓厚的兴趣，并且充满了好奇心要找出计算机能够实现的各种奇妙功能。
感谢ROGER WINK点燃了我对计算机的兴趣，我们之间有着30多年的友谊。他教会了我用COBOL语言编写冒泡排序，每次我们见面时，他总是能够带来一些新鲜有趣的东西。
感谢BILL MAGRO和TOM CORTESE，他们分别是我在Intel公司的第一位经理和Intel Parallel Application Center的第一位同事。在PAC的工作经历中，我有幸参与编写了各种不同的并行代码，与来自不同技术领域和商业领域的客户进行沟通，并且学到了许多新的方法和新的线程化库。这对我来说就是一种梦想中的工作。
感谢我在Intel公司的同事JERRY BAUGH, BOB CHESEBROUGH, JEFF GALLAGHER, RAVI MANOHAR, MIKE PEARCE, MICHAEL WRINN, and HUA (SELWYN )，感谢你们本书中技术内容的审阅和建议。他们每个人的技术知识都给了我很大的帮助；感谢他们对我的项目和目标的支持，有见地的建议，以及多年在Intel公司的友谊。
感谢编辑MIKE LOUKIDES，以及O’Reilly公司参与本书编撰的其他工作人员。如果没有他们的帮助和建议，我将完成不了本书。
感谢GERGANA SLAVOVA作为我的“目标读者”，他帮我一遍又一遍地审阅本书的内容。她帮助我用简洁的语言来阐述一些复杂的思想，并且当我在单个段落中放入过多的细节时增加一些示例，除此之外，她的幽默注释使得本书的修改过程不再乏味无趣。
感谢Henry Gabb在并行编程和多线程编程方面的知识，他说服我申请PAC的职位，并且在2000年重新回到Intel与他一起工作，感谢他对SEC Football和Chicago Cubs的热爱。我们彼此之间相互了解已经有大约15年了。我们在许多不同的项目上共事过，并且相互讨论技术问题。他不仅本书的技术审稿人，而且多年来帮我审阅了多篇文章，这些都帮助我将写作技术提高了一个层次。
最后，感谢我深爱的妻子Lorna，现在她的丈夫又回到了她身边。

前言............................................................................ 1
第1章并行让程序运行得更快....................................... 7
你可能会想到的一些问题...................................................................................8
采用线程化方法的4个步骤...............................................................................13
并行算法的背景知识.........................................................................................18
共享内存编程与分布式内存编程的比较...........................................................21
本书采用的并发编程方法.................................................................................24
第2章是否采用并发................................................... 27
并发算法的设计模型.........................................................................................28
哪些算法不能并行.............................................................................................47
第3章算法正确性证明与性能衡量.............................. 53
并行算法的验证................................................................................................54
示例：临界区问题.............................................................................................56
性能测试（程序的执行情况如何）.................................................................69
硬件并行性的发展历史.....................................................................................75
第4章多线程程序设计中的8条简单规则...................... 77
规则1：找出真正独立的运算............................................................................78
规则2：在尽可能高的层次上实现并发.............................................................78
规则3：尽早考虑通过增加处理器核的数量来获得可伸缩性...........................79
规则4：尽可能使用线程安全的库....................................................................80
规则5：使用正确的多线程模型........................................................................81
规则6：永远不要假设程序会按照某种特定的顺序执行...................................81
规则7：尽可能使用线程局部存储或者与特定数据相关的锁...........................82
规则8：要敢于对代码进行修改以获得更好的并发性......................................83
小结.............................83
第5章线程化库......................................................... 85
隐式线程化........................................................................................................86
显式线程化........................................................................................................92
其他主题...........................................................................................................96
特定领域的库....................................................................................................96
第6章并行求和与前缀求和........................................ 99
并行求和.........................................................................................................100
前缀求和.........................................................................................................106
选择.......................................... 115
最后的思考.................................................126
第7章映射归约....................................................... 127
并发映射运算..................................................................................................129
并发归约运算..................................................................................................131
映射归约的应用..............................................................................................139
映射归约作为一般性并发...............................................................................144
第8章排序.............................................................. 145
冒泡排序.........................................................................................................146
奇偶换位排序..................................................................................................153
希尔排序.........................................................................................................162
快速排序.........................................................................................................168
基数排序.........................................................................................................180
第9章搜索.............................................................. 197
未排序的数据序列...........................................................................................198
二分搜索.........................................................................................................206
第10 章图算法......................................................... 215
深度优先搜索..................................................................................................218
最短路径问题..................................................................................................233
最小生成树......................................................................................................238
第11 章线程化工具.................................................. 249
调试器.....................................................................250
性能工具.........................................................................252
其他主题...................................................................................254
再接再厉....................................................................................255
术语表.................................................................... 257
照片说明................................................................. 267

“在这个精美的小玻璃瓶里装着一种神奇的能量，它不仅能使你思考和行动的速度翻倍，而且还能让你在规定的时间里完成双份的工作。”
——节选自H.G.Wells 的短篇科幻小说《The New Accelerator 》(1901)

    我希望通过本书来揭开并发编程的神秘面纱，以及消除围绕着并发编程的种种担心和误解。我想把我在过去20 年中在并发（Concurrent）/并行（Parallel ）编程方面积累的一些经验和技巧向各位读者阐述清楚。
    我在讲解这些经验和技巧（我将它们统称为并发编程的艺术）时采用的方法是，首先给出算法的串行代码实现，然后通过对串行代码进行修改来获得算法的并行版本。我在每个示例中都会详细介绍完整的思考和分析过程，从而让读者能够更深入地理解和掌握如何编写并发代码。在实现这些算法时，我将采用线程作为共享内存环境（Shared-Memory Environment ）中的并发模型。在本书中，我将使用多种常见的线程化库（Threading Library ），并将指出在具体实现中采用不同线程化库时可能存在的一些差异。
    与任何一种编程技术一样，在开始编写并发程序或者多线程程序之前，你首先需要具备一定的基础知识。你可以通过阅读图书和编写实际的代码来掌握这些知识（如在实现互斥时可以采用哪些语法和方式，以及如何对数据进行共享等）。同样，还存在着一些逻辑思维方式可以帮助我们解决或者避免一些很简单的并发编程问题。如果我们能够将这些逻辑思维方式运用自如并从中获得某种直觉，或者能够以并行的方式来思考线程的执行，那么就基本上掌握了并发编程和多线程编程的核心技术。虽然你也可以从专家们的讲课过程中学习到一些知识，但只有当你自身具备一定的基础后，才能真正理解这些知识并将它们应用于其他情况。现在，既然你已经选择了《并发的艺术》这本书，那么我就相信你已经具备了这种基础。本书将帮助你进一步完善和提高在并发编程和多线程编程等方面的各项技术。

    当你阅读完前面的内容，或者当你在书架上看到这本书时，脑海里或许会冒出一些问题。让我们首先来看看其中一些问题。

哪些人可以称之为线程高手
    线程高手（Thread Monkey ）是指某个程序员不仅能够设计包含多线程、并发以及并行的软件，而且还能够编写出正确且高效的代码来实现这些设计。
    就像“机械高手（Grease Monkey ）”能够对汽车的构造熟稔于心一样，线程高手在运用并发编程时同样是得心应手。“线程高手”是一种值得骄傲的称谓，它与“代码高手（Code Monkey ）”不同，后者往往是一种带有贬义的称谓。

并行和并发：二者的差异是什么
    自从多核处理器面世以来，人们开始越来越多地提到“并行”和“并发”这两个术语。即使在这之前，这两个术语的定义在其他计算领域中同样存在着一些混淆。二者的差异是什么，或者说二者之间是否存在差异，因为这两个术语看上去似乎可以彼此替代。
    如果某个系统支持两个或者多个动作（Action ）同时存在，那么这个系统就是一个并发系统。如果某个系统支持两个或者多个动作同时执行，那么这个系统就是一个并行系统。并发系统与并行系统这两个定义之间的关键差异在于“存在”这个词。
    在并发程序中可以同时拥有两个或者多个线程。这意味着，如果程序在单核处理器上运行，那么这两个线程将交替地换入或者换出内存。这些线程是同时“存在”的—— 每个线程都处于执行过程中的某个状态。如果程序能够并行执行，那么就一定是运行在多核处理器上。此时，程序中的每个线程都将分配到一个独立的处理器核上，因此可以同时运行。
    我相信你已经能够得出结论——“并行”概念是“并发”概念的一个子集。也就是说，你可以编写一个拥有多个线程或者进程的并发程序，但如果没有多核处理器来执行这个程序，那么就不能以并行方式来运行代码。因此，凡是在求解单个问题时涉及多个执行流程的编程模式或者执行行为，都属于并发编程的范畴。
    在二十年前，并行编程与消息传递（Message-Passing ）编程或者分布式内存（Distributed-Memory ）编程几乎是同义词。在这种并行计算平台中通常包含多个计算节点，这些计算节点或者处于同一个集群（Cluster ）中，或者通过网络互联，每个节点都拥有一个或者多个处理器。在这种环境中编写程序时需要使用一种特殊的编程方法，即如何对计算工作进行分解以及如何共享数据。由于线程是共享内存编程模型的一部分，因此，如果在编写程序时用到了线程，那么就可以将其视作为并发编程，这种编程模型非常适合用于在单核系统中访问平台内的所有内存。
    在本书中，我将努力正确地区分和使用“并行”和“并发”这两个术语。这意味着，在设计并发算法时将假设代码既可以在单核系统上运行，也可以在多核系统上运行，而无需做重大修改。尽管采用了线程这种实现模型，我仍将对并发代码的并行执行进行讨论，因为我假设可以在多核处理器上执行这些线程。此外，我将用“并行化（Parallelization ）”这个术语来表示将串行程序转换为并发程序的过程（因为“并发化（Concurrentization ）”这个词念起来比较拗口）。

为什么要了解并发？并发能带来什么
    我只能告诉你，并发这个主题是无法回避的；随着多核处理器的日益普及，如果你还希望成为一名有雇用价值的程序员，那么除了学习和掌握并发编程技术之外，你将别无选择。当然，我的这种说法或许有些过分，使你感到不安。尽管现实情况在某种程度上确实如此，但我还是希望通过一种更为温和的方式来获得你的信任，并使你融入到并发编程的潮流中。
    无论你是在大型的软件公司中工作，还是在小型的软件作坊中写代码，或者编写开源软件，或者只是将编写代码作为一种业余爱好，你都会或多或少地接触到多核处理器。在过去，要想使程序的性能得到大幅提升，你只需要等待下一代处理器的出现，因为下一代处理器的时钟频率要高出上一代处理器不少。我的一位同事曾经这样设想：首先花9 个月的时间去玩架子鼓或者冲浪，然后当新的芯片发布时，在这些新芯片运行某些测试基准（Benchmark ），之后就可以宣称你成功地提高了程序的运行速度。在一篇颇具影响力（现在可以说无人不知、无人不晓）的文章“免费的午餐已经结束：并发将成为提升软件运行速度的重要手段”（于2005 年3月发表于《Dr. Dobb’s 》杂志）中，Herb Sutter 阐述了通过芯片速度的提升来加快软件运行速度的方法已经不再可行。程序员需要开始编写并发代码，以便充分发挥多核处理器的强大功能并且使程序性能得到提升。
    那么，通过在多核处理器上编写并发程序，你可以获得何种程度的性能提升？最理想的情况是，当在双核处理器上运行并发程序时，总的执行时间将减半，在4核处理器上运行时将降为1/4 ，在8核处理器上时降为1/8 ，依此类推。这听上去似乎比新一代处理器降低20%～30% 运行时间的情况要更好。然而，如果想要使代码充分发挥多核处理器的优势，那么需要付出一定的努力。此外，通常很少有代码能够达到理想情况下的性能提升程度。事实上，随着处理器核数量的增加，你或许会发现性能提升的程度实际上在逐渐降低。不过，如果你能编写出高质量的并发多线程程序，那么还是可以获得不错的性能提升（或者可以反过来解释为什么你不能获得性能提升）。更理想的情况是，如果你开发出的并发算法在8核，16 核或者更多核的处理器上运行时，能够获得与在双核或者4核上运行时一样大的性能提升程度，那么你就确实可以抽时间去玩架子鼓和冲浪了。本书的重点之一就是，指出在哪些情况下以及如何开发这种可伸缩的算法。

并发编程难不难
    确实，并发编程不像在公园散步那样轻松。然而，我也并不认为并发编程难到足以令人畏惧或者像你想象中的那么困难。如果采取一种循序渐进的方法，那么学习和使用并发编程其实不会比学习一种新的编程语言更难。
    在串行程序中，代码的执行路径是可预测的。只要通过某种有条不紊且有逻辑的方法，总是可以找出其中的逻辑错误和其他bug 。随着你在编程过程中积累越来越多的经验和技巧，你还将遇到其他一些问题（例如，内存泄露、缓冲区溢出、文件I/O 错误、浮点精
度以及舍入等问题），你同样将学会如何识别、找出以及纠正这些问题。有些软件工具可以帮助我们快速定位一些没有按照预期方式执行或者出现问题的代码。如果能够理解导致问题的原因，并且在分析过程中对这些软件工具加以合理运用，那么将极大地增加你在诊断和解决问题时的成功概率。
    在并发算法和多线程编程中，你需要考虑同时有多个执行流程的情况，以及如何对这些执行流程进行协调以完成指定的计算任务。此外，你还将面临一组全新的错误/性能问题，这些问题在串行编程中是不会出现的。这些新问题正是由于在线程并发执行过程中的不确定性和异步性而直接导致的。也正是因为这两种属性，多线程程序中包含的错误有时候会表现出来，有时候也不会。例如，如果多个线程按照某种特定的顺序来执行（或者交替执行），那么可能刚好会使得错误不会暴露出来，但如果在对执行环境进行某种调整时改变了线程的执行顺序，那么就会开始出现错误。即使没有对硬件做任何改变并且以相同的输入参数来运行同一个应用程序，也可能会产生不同的结果，而你根本找不到任何原因。
    要想找出问题，就考虑所有不同的执行方式，这就好比在双手之间有多种手指交叉方式。两只手就像两个运行中的线程，而手指就好比在线程中并行执行的指令。每只手上的四个指头与另一只手上的四个指头之间共有70 种不同的交叉方式。如果只有4%（3 种）的交叉方式会产生错误，那么你如何来找出错误的起因？尤其是像海森伯格测不准原理（Heisenberg Uncertainty Principle ）一样，有时候在通过标准调试技术来查找错误时，线程只会按照某一种交替顺序来执行，而这种顺序并不会产生错误。幸运的是，还有一些软件工具专门被设计用来找出多线程代码中的正确性和性能等方面的问题。
    如果掌握了正确的知识和方法，那么在编写代码时就能更好地避开常见的多线程问题。我将在本书中介绍这方面的知识，而如何在具体的实践中应用这些知识则要靠你自己了。

线程危不危险
    可以说是，也可以说不是。在多核处理器成为主流技术的这几年中，许多人都对线程模型提出了批评。这些人指出了在使用共享内存以进行线程间通信时存在着种种危险，以及在使用标准同步对象时将导致不可伸缩性。我不想欺骗你，这些批评确实有值得注意的地方。
    那么，既然在线程中充满了各种危险性，我为什么还要在本书中以线程作为并发的实现模型呢？每种编程语言都有其自身的风险，但如果你能知道可能存在哪些潜在的问题，那么就可以知道如何避开它们。即使你在代码中无意间引入了一个与线程相关的错误，但如果能知道到哪些地方去检查代码，那么都会比最好的调试器还要有帮助。例如，在FORTRAN 77 中，未声明的变量将被赋予一个默认类型，而这个类型将根据变量名的第一个字母来确定。如果你写错了变量的名字，那么编译器将把它作为一个新的变量。如果你知道有可能将字母“I”误写为数字“1”，或者把数字“0”误写为“O”，那么就能更快地找出程序中的拼写错误。
    你可能会问，当前有没有其他“更好的”并发实现方式可供使用或者正在开发，如果有的话，那么为什么还要花时间来学习本书中的线程知识？在我多年从事并行编程和并发编程的经历中，曾经使用过一些其他并行编程语言。现在，其中大多数语言都已经消失了。我相信与我合作的出版商并不希望我编写一本介绍这些语言的书，因为我不能保证书中的内容在6个月之内不会过时。我同样相信，在编写本书时，学术界正在研究各种更优的、更少错误的，以及更友好的方法来编写并发程序。在这些方法中，有许多都比线程要更好，并且有些方法还可能被采纳为主流的编程语言。在某些方法中甚至还可能产生全新的并发编程语言。
    不过，就现在以及可预见的将来而言，线程仍然会是一种主流的并发编程方法。其他能克服当前语言和方法中各种缺点的替代方法，将会在几年之后出现。目前，多核处理器已经出现了，因此你需要立即熟悉并发编程方法。如果你从现在就开始做准备，那么当任何新技术/方法出现时，就能够更好地掌握并发程序的各种基础构件（还有一种更好的选择，那就是等我在若干年后再版本书时使用新的并发方法来代替线程）。

并发编程入门
    并发编程的核心内容是指计算机能够以任何顺序来执行的独立计算（Independent Computation ）。例如，在代码中可独立执行的循环迭代和函数调用都属于独立计算。从串行代码中提取出并发工作可以分配到多个线程上（或者相互协作的进程上），并且可以在多核处理器中的任何一个核上运行（或者在单核处理器上运行，此时需要将不同的独立计算换入/换出处理器核，从而形成一种并行执行的假象）。然而，在一个程序中，并非各个计算部分都是独立的，因此你仍然需要处理各个并发工作之间的串行执行工作。
    要想将并发工作分配到多个线程上，你需要调用一些实现了线程化机制的库函数。这些额外的函数调用将增加并发执行的开销（overhead ），因为在最初的串行代码中并不包含这些函数调用。任何为了控制和协调线程而增加的额外代码，尤其是调用线程化库函数的代码，同样是一种开销。此外，你还需要增加一部分代码来判断计算是应该继续执行，还是应该获取更多的工作或者在满足指定的条件时触发其他线程，这也是我们需要考虑的开销。不仅如此，我们还需要增加一些代码专门用来确保将等量的工作分配到每个线
程上。这种线程之间的负载均衡可以使线程不会处于空闲状态并浪费系统资源，这同样被认为是一种开销。在并发代码中必须尽可能地将上述开销维持在最低水平。要想获得最大程度的性能提升并且使并发代码实现尽可能高的可伸缩性，那么分配到每个线程的工作就要足够得多，以便减少或者掩盖由于这些开销而带来的负面影响。
    由于有多个线程在共享内存中同时运行，因此有时候两个或者多个线程需要访问同一个内存位置。如果多个线程都希望更新这个内存位置上的值，那么就会出现存储冲突（Storage Conflict ）或者说数据竞争（Data Race ）。操作系统将依次调度每个线程以执行。由于调度算法依赖于系统当前状态的诸多方面，因此调度行为看上去是异步的。在不同的线程执行顺序下，有可能会出现数据竞争，也可能不会出现。如果你的并发代码只有在特定的内存更新顺序下才能正确执行（即其他线程只能在这种顺序下才能获得正确的值），那么程序本身就要负责确保代码按照这种顺序来执行。例如，在航空票务预定系统中，假设两个旅行代理机构同时看到了某个航班上的一个空位，并且他们都把各自客户的名字填到这个座位上然后出票。当两位不同的乘客都出现在机场时，谁将得到这个座位？为了避免出现这种冲突情况，同时又要确保上座率，必须通过某种方法来控制对共享资源的更新。
    有几种不同的方法可以用来对线程进程同步，以确保实现在访问共享内存时需要的互斥行为。虽然同步是一种可行的措施，但在使用同步对象时将带来一定的开销（这种开销与线程创建函数和其他协同函数带来的开销是相同性质的），并且只有在无法采用其他方式来解决问题时才应该使用同步对象。
    当然，我们的最终目的都是为了通过减少程序的执行时间来提升程序的性能，或者使程序能够在给定的时间里处理更多数据。你需要清楚地意识到在并发编程中存在的各种危险和陷阱，以及如何避免或者纠正它们，只有这样才能编写出执行正确并且性能令人满意的应用程序。

    在开发软件时，尤其是大型的商业应用程序时，通常会采用一种正规的流程来完成各个阶段的工作，从而按时并且高效地满足软件的各项预定指标。这种流程有时也被称之为软件生命周期（Software Lifecycle ），具体包含以下6个步骤。
规范（Specification）
    与软件用户进行谈话沟通以找出功能需求，包括输入规范和输出规范，然后根据用户的反馈，以书面形式描述在应用程序中需要包含的功能，整体结构以及实现代码。
设计（Design）
    制定出应用程序以及各个功能组件的详细开发计划。
实现（Implement）
    编写应用程序的代码。
测试（Test）
    确保应用程序的各个组件都能按照预期的方式正确工作，包括各个组件不仅能够在独立运行的情况下正确工作，而且当合并到应用程序的整体框架内时同样能工作，并且修复在这一过程中发现的任何问题。
调优（Tune）
    对代码进行改进以提高其在目标平台上的运行性能。
维护（Maintenance）
     修复应用程序中的错误并持续改进程序性能，并且增加在最初设计中没有包含的新功能。
    在“实现”、“测试”和“调优”等步骤之间并没有严格的分界线，因为程序员在编写代码的过程中将反复地对代码进行编写、测试、修复以及调优。这些步骤构成了一个循环，即使有单独的QA（Quality Assurance ，质量保证）工程师来进行测试也是如此。事实上，当某些功能无法实现，或者在最初制定的规范中没有考虑到功能之间的某种交互时，这个循环可能需要重新回到“设计”步骤。
    在将串行应用程序转换为并发程序时，同样存在一个类似的生命周期。例如，Intel 公司的工程师们在编写多线程和并行程序时发明的“线程化方法学（Threading Methodology ）”就是一种生命周期。在线程化方法学中包含了4个步骤，这比软件生命周期中的步骤要少。
分析（Analysis）
    这个步骤类似于软件生命周期中的“规范”步骤，该步骤的工作是识别出应用程序中包含了独立计算的功能（代码）。
设计与实现（Design and implementation）
    这个步骤的工作从字面上很容易知道。
测试正确性（Test for Correctness）
    找出代码中由于没有正确实现或者没有完全实现线程化机制而导致的各种错误。如果在修改代码时错误地改变了原有的串行逻辑，那么很可能又会引入新的逻辑错误。
性能调优（Tune for Performance）
    当正确地通过线程实现了并发之后，接下来的工作就是要努力减少程序的执行时间。
    在“线程化方法学”中没有包含“维护”步骤。我认为，每当编写完一个应用程序时（无论是串行的还是并发的），都必须把应用程序的维护作为日常业务中不可缺少的一部分。接下来，我们将依次对线程化方法学中的这4个步骤进行详细讨论。

第1步分析：找出并发性
    在应用程序的串行代码中已经包含了设计和编写等步骤，因此可以很清楚地知道这个应用程序所具备的功能。同样，你还知道在指定的输入参数下将产生怎样的输出。现在，你需要找出哪些代码可以通过线程模型来实现；也就是找出在应用程序中包含了独立计算的代码。
    如果你对这个应用程序非常熟悉，那么就能很快地找出这些代码。如果不太熟悉，那么可以通过对程序的执行性能进行分析以找出可能包含独立计算的热点（Hotspot ）位置。
    热点是指一段包含了大量操作的代码。在性能分析器中，可以将在计算中消耗的时间作为判断是否为热点的标准。在找出程序中执行时间消耗最多的位置后，就可以开始执行这些位置上的代码，并判断它们是否可以并发执行。
    然而，消耗最多执行时间并不一定就意味着代码可以被修改为并发执行。你必须通过对代码的算法进行分析来判断在这段代码中是否包含足够高的独立性以支持并发执行。尽管如此，通过搜索应用程序中执行时间消耗最多的代码部分，你还是可以达到事半功倍的效果（即对整体结果是最有益的）。如果我们花一个月的时间来编写、测试并且调优一段占串行执行时间75% 的代码，那么肯定比对一段仅占串行执行时间2% 的代码进行相同工作所获得的效果要好得多。

第2步设计与实现：采用线程来实现算法
    在找出了独立的计算后，就需要考虑如何将串行代码修改为并发代码。这个步骤也正是本书的核心内容。在这里我不会花太多时间来讨论这个主题，因为在后面的章节中将详细介绍各种具体方法。

第3步测试正确性：检测并修复在线程化时引入的错误
    在对应用程序的代码进行修改时，很可能会引入新的错误。因此，对于在串行程序中增加代码以创建和控制多个线程的情况来说，也不例外。我在前面已经提到过，多线程的程序在测试中可能会暴露出问题，也可能不会。即便你已经将这个程序正确地运行了数百次，但当在另一个新系统上运行该程序时，仍有可能出现错误，当然也可能仍不出错。有时候，虽然代码在正常运行时发现了一个错误，但在调试器（甚至是一个能够感知线程的调试器）下运行代码时，仍可能出现无法定位问题，这是因为调试器的单步执行特性可能会掩盖正在分析的错误。通过print 语句（这也是所有调试工具中最常使用的方法）来输出变量的值则可能修改线程交替执行的时间，因此同样可能隐藏错误。
    如果你知道一些常见线程化错误（如数据竞争和死锁等）的产生原因，并且在“设计与实现”步骤中通过缜密的措施来防止它们的发生，那么就可以彻底避免这些错误。然而，如果在编程语言中用到了指针和其他间接引用方式，那么这些问题几乎是无法预见的。事实上，你还可能遇到这样的情况：某个错误是否显现取决于所输入的数据。幸运的是，有一些工具有助于找出这些与线程相关的错误。我将在第11章中列出其中一些工具。
    即使在消除了所有由于修改代码而引入的错误后，代码仍有可能无法获得与串行版本一样的结果。如果结果只存在细微的偏差，那么或许是由于舍入造成的误差，因为在多线程的情况下，将各个线程计算结果合并起来的顺序与在串行代码中合并结果的顺序并不相同。
    如果结果偏差很大，那么极有可能是因为在使用线程时引入了某个逻辑错误。例如，在循环中将某次迭代操作执行了多次，而有些迭代操作则根本没有被执行。此时你可能无法通过任何线程分析工具来找出这种类型的错误，但可以通过某种调试工具来追踪这个问题。本书的另一个主题就是关于在编写线程代码时可能引入的一些常见逻辑错误，以及如何避免这些错误。通过严谨的设计，你可以将与线程相关的逻辑错误数量保持在最低的水平，这样在查找和纠正代码中的错误时就不会浪费太多时间。

第4步性能调优：消除性能瓶颈
    在确保已经消除了代码中所有与线程相关的错误后，最后一步就是确保代码能以最优的性能运行。在通过线程对串行程序进行改写之前，首先要确保串行程序的代码已经被调整为最优性能。如果在对代码进行线程化之后再对其串行执行进行调优，那么可能会改变代码的整体行为，并使得增加的线程化代码反而降低程序的性能。如果需要并行化的串行代码已经被调整为最优性能，那么你只需将重点放在对线程化的代码进行性能调优上。
    对线程化代码进行调优通常可以归结为识别出一些问题情况，包括：在同步对象上发生竞争，分配到每个线程上的计算量不均衡，在调用线程化API 时开销过多，或者并行完成的工作量不足以弥补对代码线程化时产生的开销。与线程化错误一样，同样有一些软件工具可以帮助诊断和找出这些性能问题。
    然而，你同样要清楚，用线程来改写代码可能正是造成性能瓶颈的主要原因。通过将串行计算分解为不同的部分并将它们分配到多个线程上，那些曾经被精心调优过的串行执行可能无法获得像以前一样的性能。此外，你还可能引入一些导致性能下降的错误，如伪共享（False Sharing ）、低效的内存访问模式或者总线过载（Bus Overload ）等。要想找出这种类型的错误，需要借助一些在查找这类串行性能错误时使用的技术。本书的另一个主题就是如何同时避免线程化问题和（由于使用了线程而引入的）串行性能问题。通过严谨的设计，你能够实现非常好的并行性能，因此在查找或者调优代码中的性能问题时就不会花费太多的时间。
测试与调优的循环周期
    当你对代码进行修改以纠正某个性能错误时，可能会在无意中引入一个与线程相关的错误。特别在修改对同步对象的使用时，尤其会出现这种情况。在完成了代码修改并实现了性能调优后，你应该重新回到“测试正确性”步骤，以确保在修复性能问题时没有引入新的逻辑错误。如果发现引入了任何新的正确性问题并再次通过修改代码来纠正它们，那么要确保再一次检查代码，以避免在修复正确性问题时又引入了新的性能问题。
    有时候，情况会变得更糟糕。如果你无法使程序实现预期的性能提升，那么可能需要重新回到“设计与实现”步骤，并且全部重新来过。显然，如果在应用程序中有多个位置采用了并发，那么在完成了之前的代码段之后，对于每段代码都可能需要从设计步骤开始。如果某些采用了线程的代码段能够提升程序的性能，除非对算法和全局数据结构的修改将影响这些代码段，那么可以将这些代码段保持不变。这是一个烦琐的循环周期，如果你过于纠缠于其中的细节思考，很快就会变得头晕脑涨。

从一开始就采用并发是否可行
    到目前为止（对于本书的剩余内容来说同样如此），我都假设首先是有一段能正确执行的串行代码，然后再将这段串行代码转换为并发代码。那么，能否不需要实现串行代码而直接设计并发代码？确实可以，但我不建议你这么做。最主要的原因是，在对一开始就采用并发的代码进行调试时，可能会同时存在两种类型的问题：在算法或者实现中的逻辑错误，以及在代码中与线程相关的问题。例如，你发现的错误是由于数据竞争导致的，还是由于在循环中没有递增足够多的次数而导致的？
    在将来，随着对这方面问题的深入研究，将会出现更丰富的理论、模型、方法以及一到两种并发编程语言，到那时候你就可以从一开始就编写并发代码。就目前而言，我建议你首先编写一个能正确工作的串行代码，然后分析如何将其转换为并发代码。尽管在设计软件时将潜在的并发性纳入考虑范围是一种很好的思维方式，但首先还是要编写和调试好串行版本的代码。

   如果你不熟悉并行算法或者并行编程，那么可以通过本节的内容来了解一些背景知识—— 本节简要介绍了多核处理器上并发编程的发展历程。

理论模型
    我获得的所有学位都是计算机科学专业。在我的学生时代，我学习并使用过多种不同的计算机模型。在计算机科学中，用于研究算法的基本处理器架构之一就是随机访问机（Random Access Machine，RAM）。这是一种基于冯·诺伊曼架构的简化模型。在这种模型中包含了所有基本组件：CPU 、输入设备、输出设备以及随机访问内存。在图1-1 中给出了RAM 模型中各个组件的示意图以及组件之间的数据流动情况。

图1-1：RAM 模型中的数据流，箭头表示方向

    你可以将缓存（Cache）层次结构增加到内存中，将一个随机访问磁盘作为支持输入和输出的单个设备，控制CPU 的复杂度和架构，或者还可以做其他一些修改来使得模型接近于实际情况。然而，无论你进行怎样的修改，这个模型的基本架构仍然保持不变，这在设计串行算法时是非常有用的。
     在设计并行算法时，有些研究人员使用了RAM 模型的一种变化形式，称之为并行随机访问机（Parallel Random Access Machine，PRAM）。简单来说，PRAM 就是多个CPU 连接到无限大的内存，并且这个内存在所有CPU 之间是共享的。我们假设在这些CPU 上执行的多个线程是以一种步调一致的方式（Lockstep Fashion）来执行（即所有线程都同时执行同一条指令，然后再同时执行下一条指令，依次类推），并且无论处理器的数量是多少，对于内存位置的访问时间都是相同的。我们通常不考虑在这些CPU 和内存之间的连接方式，除非某种特殊的配置方式有可能对算法的设计会造成影响。在图1-2 中给出了PRAM 的架构，其中使用了（不产生冲突的）共享总线来连接内存和处理器。

图1-2：PRAM 结构示意图，其中采用了共享总线来连接CPU和内存

    与RAM 一样，如果真实世界中某些处理器的特殊功能可能对算法的设计产生影响，那么我们可以对基本的PRAM 模型做各种变形以模拟这些功能。通常，对PRAM 上的算法设计会产生影响的常见功能之一就是共享内存。在这个模型中没有为程序员提供对同步对象的软件支持或硬件支持。因此，PRAM 模型将模拟在不同处理器上执行的线程在执行读操作和写操作时采用的内存访问方式。共有两种类型的读操作限制和两种类型的写操作限制：并发或者独占（Exclusive ）。在设计PRAM 算法时，你必须首先定义算法的PRAM 访问类型。在表1-1 中列出了四种类型的PRAM。

表1-1 ：不同内存访问模式下的PRAM 变化形式


    除了这些限制之前，PRAM 算法需要负责实施所选择模型的独占读和独占写等行为。在并发写模型中，模型进一步规定了当两个线程同时尝试将值写入到同一个内存位置时发生的行为。这种PRAM 有多种常见的变化形式，如使算法确保被写入的值是同一个值，从两个或者多个尝试写入的值中选择一个随机值，或者保存多个值的加和（或者其他某种运算的结果）。由于所有处理器都以一种步调一致的形式执行，因此对内存的写入操作是同时执行的，这使得更容易实施所指定的策略。
    你不仅必须指定PRAM 的内存访问行为以及在设计算法时与该模型保持一致，而且还要指定在算法中将要使用的处理器个数。由于这是一种理论模型，因此可以使用的处理器数量为无限多个。处理器的数量通常取决于输入参数的规模。例如，如果设计一个需要处理N个输入项的算法，那么可以指定在PRAM 中必须有N 2个处理器和线程，并且它们都可以访问共享内存。
    由于在PRAM 中可以使用无限多的处理器和内存，因此这显然是一种用于并行算法设计的理论模型。如果要在有限资源的平台上实现PRAM 算法，那么只需在模型中模拟在N 个逻辑处理器上进行计算的情况。在后面将介绍算法设计和实现的章节中，有些算法将以PRAM 算法作为基础起始点来进行设计，并我将告诉你如何将它转换为在多核处理器上正确执行。

分布式内存编程
    在20 世纪80 年代末期和90 年代早期，由于共享总线的连接问题，基于共享内存模型的并行计算机在处理器的使用数量上达到了一个上限，即最多不超过32 个处理器。于是，研究人员提出了分布式内存（Distributed-Memory ）模型以进一步提高处理器的数量并行算法需要对数据进行一定程度的共享。然而，由于在分布式内存中每个节点与其他节点都是独立的，没有直接的共享机制，开发人员需要通过各种函数库在各个节点之间传递消息。
    例如，在分布式内存编程中，假定处理器1（P1 ）需要获得来自处理器0（P0 ）的一组值。在P0 上运行的程序需要将这组值封装到一个缓冲区中，并且调用函数将缓冲区从P0 所在的节点上发送到网络上，然后将缓冲区的内容传入到P1 所在节点的内存中。在P1 所在的节点上，程序必须调用接收函数以接收传入到节点内存的数据，并将数据复制到内存中某个指定的缓冲区以由P1 访问。
    起先，每个提供分布式内存机的厂商都有其自己的库和一组函数，它们既支持简单的点到点通信，也支持诸如广播这样的聚合通信。随着时间的推移，人们开发出了一些可移植的库，例如，PVM（Parallel Virtual Machine ，并行虚拟机）以及MPI（Message-Passing Interface ，消息传递接口）。PVM 能够将一组互连的计算机改造为一个虚拟并行机，并且这个虚拟并行机的开销要小于专门并行平台的开销。MPI 是一个实现了消息传递功能的标准库，这些功能在并行机或者一组互连的计算机上都被支持。在Beowulf 项目中介绍了如何通过Linux 和MPI 将PC 集群创建为一个低成本的分布式内存并行平台。

并行算法简介
    在许多书中都介绍了并行算法。其中有许多算法都采用了将消息传递作为实现并行的方法。在一些早期文献介绍的并行算法中，将网络配置（例如，网状网络（Mesh ）或者超立方体网络（Hypercube ））也作为算法设计的一部分；在后来的文献中则并不关注在特定网络配置中开发算法，而是将执行平台抽象为一个处理器节点集合。在后面介绍算法设计和实现的章节中，有些算法将以分布式内存算法作为算法作为基础起始点来进行设计，并我将告诉你如何将它转换为在多核处理器上正确执行。

    有些读者可能已经具备分布式内存编程的背景知识，并且希望了解如何在多核处理器上进行线程编程。在这里，我整理了一些共享内存编程与分布式内存编程之间的比较与对照。如果你对分布式内存编程一无所知，那么通过这些比较将能了解这两种编程方法之间的一些差异。即使你以前只编写过串行程序，从下面的内容中仍然可以获得在共享内存上编写并发程序的一些基本知识，这些知识是你在编写单线程程序时不会遇到的。

共有功能
    下面这些功能是共享内存模型和分布式内存模型的共有功能。
冗余工作
    无论一个算法的并发程度如何，在程序中仍然存在一部分代码必须串行执行。当需要用到串行计算的结果时，你可以在其中一个进程中执行串行计算，然后将计算结果通过广播传递到其他需要该结果的进程。在发送信息时会增加一定的执行开销。另一种方式是，如果其他进程都能获得在串行计算中需要的各项数据，那么也可以让每个线程都执行相同的串行计算并生成结果，这样就无须发送任何消息。在共享内存模型中，默认情况下在计算中需要用到的数据对于每个进程来说都是可访问的。尽管在多个线程中执行冗余的工作将使得处理资源保持忙碌的状态，并且极大地减少同步操作的数量，但却需要消耗更多内存以保存同一个值的多个副本。
分解工作
    计算工作必须被分配到多个线程或者进程上。例如，将需要处理的数据集合分为多个数据块并分配到多个线程/进程上，每个线程/进程对分配到的数据块执行相同的计算；还有一种方式是将整体计算分解为多个计算步骤，并且为每个线程/进程分配一个执行不同
代码的计算步骤。
共享数据
    在某些情况下，应用程序需要共享数据。例如，某个计数器的值，或者一组浮点数，或者一组图顶点（Graph vetex ）。无论是何种情况，线程/进程都需要在计算过程中能够访问到这些数据。显然，共享数据的方法有多种；在共享内存模型中，程序只需要访问内存中指定的位置，而在分布式内存中，程序必须通过发送和接收消息来共享数据。
工作的静态/动态分配
    根据串行算法的特性，采用的并发实现方式以及线程/进程的数量，你可能会选择一次性分配完所有工作（通常是在计算开始时），或者随着代码的执行来逐渐分配工作。前一种方法被称之为静态分配，因为最初分配的工作量在分配完成之后就不会再发生变化。
后者也被称之为动态分配，因为只有在需要时才会分配工作。在动态分配情况中你会发现，如果将程序运行多次，那么同一个线程并不会每次都执行相同的工作量，而在静态分配中则每次都将为同一个线程分配相同的工作量（假定每次运行程序时生成的线程数量都是相同的）。
    通常，如果可以工作分解的数量等于线程/进程的数量，并且总的执行时间就大致等于每一部分工作的执行时间之和，那么静态分配就是最优的分配方法。采用静态分配方法的代码通常是最容易实现和维护的。当工作的数量远多于线程的数量，并且每部分工作的执行时间都不相同或者无法在计算开始时知道，那么就应该采用动态分配方式。虽然在动态分配方式中会存在一定的开销，但带来的好处是在执行过程中的负载更为均衡。

共享内存模型的特有功能
    接下来的内容是分布式内存模型与共享内存模型的区别之处。如果你熟悉基于分布式内存的并行编程，那么就可以看到其中的差异。对于不熟悉分布式内存并行编程的读者来说，理解其中的要点和思想同样是非常重要的。
局部变量与线程局部存储
    在共享内存中所有东西都是共享的，然而在某些情况下需要使用私有的或者局部的变量，并且这个变量只能由一个线程访问。在线程被创建之后，任何在代码执行路径中被声明的变量（例如，在函数调用中声明的变量）都将自动被作为执行变量声明语句的线程的局部变量。在分布式内存机的某个节点上执行的进程将拥有该节点上的所有局部内存。
    在Windows 线程和POSIX 线程中都定义了线程局部存储（Thread-Local Storage，TLS） API 。虽然在不同的线程化库中有着不同的实现方式，但这些API 的作用都是为线程分配私有内存，并且允许线程存储和提取一个只能由该线程访问的值。TLS 与局部变量的不同之处在于，TLS 中的值在不同的函数调用之间将保持不变。这种行为非常像静态变量的行为，只不过在TLS 中，每个线程都将获得一个单独的值。
内存效应
    由于处理器核上的内存对于所有在该核上执行的线程来说都是共享的，因此会出现由于共享而带来的性能问题。我在前面已经提到了写入冲突和数据竞争。处理器架构将决定着线程是否共享缓存还是各自访问独立的缓存。如果在两个处理器核之间共享缓存，那么线程可用的缓存数量将减半，而如果各自使用独立的缓存，那么在共享数据时将变得低效。对于一些需要经常访问的只读数据来说，共享缓存是非常高效的，因为只需要一个副本。
    伪共享是指，虽然线程并没有访问同一个变量，但它们各自访问的不同变量都被包含在同一条缓存线（Cache Line ）中。根据缓存一致性协议，当某个线程更新缓存线中的一个变量时，如果另一个线程希望访问该缓存线中的其他内容时，需要首先将该缓存线写回到内存中。当两个或者多个线程不断更新同一条缓存线时，那么这条缓存线将在内存与缓存之间反复地移动。
内存中的通信
    在基于分布式内存的程序中，共享数据是通过在进程之间发送和接收消息来实现的。而在共享内存模型中共享数据时，一个线程只需将值写入到某个内存位置，而其他线程从这个内存位置上读取这个值。当然，要确保数据被正确地读取，写入数据的线程必须在读取数据的线程访问该共享内存位置之前首先将值写入。因此，我们必须对写入线程和读取线程进行同步。发送/接收消息的模式其实是分布式进程之间一种隐式的同步形式。
互斥
    在某些情况下，当多个线程需要在内存中相互通信时，必须保护对共享内存位置的访问。实现这种保护的方法就是，每次只允许一个线程访问这些共享变量。这也被称之为互斥（Mutual Exclusion ）。有几种不同的同步机制可以用来实现互斥（具体采用何种机制通常取决于你所使用的线程化方法）。
    读取数据的操作和写入数据的操作都必须被保护。如果多个线程读取同一个数据，那么这种行为不会导致任何问题。当有多个线程写入同一个内存位置时，写入操作的执行顺序将决定着最终写入到这个内存位置的值，以及其他线程从这个内存位置读出的值（如航空订票系统中两个乘客得到同一个座位的情况）。当有一个线程读取某个内存位置而另一个线程写入这个内存位置时，如果没有正确地同步，那么可能读取到两个不同的值（旧值或者新值）。在这两个值中，很可能只有一个值是我们预期的值，因为在最初的串行代码中认为只会出现一个值。如果并发算法的正确执行需要依赖某个变量的特定值，而这个变量由多个线程更新，那么你必须确保在正确的时间写入正确的值；这就需要使用互斥以及其他同步机制。
生产者/消费者
    在分布式内存程序中，一种用来将数据或者任务分配到不同进程的方法就是老板/工人（boss/worker ）方法。“工人”进程向“老板”进程发送消息以请求新任务；在收到请求后，“老板”进程将回送消息/任务/数据给“工人”进程。你可以编写一种在多个线
程中分配任务的“老板/工人”机制，但需要非常多的同步。
    要采用共享内存模型，那么你需要对“老板/工人”方式做一些变化，使用一个共享队列来分配任务。这种模型被称之为“生产者/消费者”模型。生产者线程将创建任务并将它们存储到共享队列中。当消费者线程需要执行工作时，它们将从共享队列中提取任务。你必须通过某种形式的互斥来保护对共享队列的访问，从而确保任务被正确地插入到队列中，并且从队列中取出的任务也只能被分配给一个线程。
读/写锁
    由于多个线程在同时读取共享变量时不会产生问题，因此在多个读取线程上使用互斥就会不必要地产生性能瓶颈。不过，如果有任何线程试图更新共享变量，那么就必须使用互斥。但当共享变量的更新操作远少于读取操作时，可以使用读/写锁（Reader/Writer
Lock ）来作为同步对象。
    读/写锁允许多个读取线程进入访问共享变量的代码保护区。当有线程试图更新（写入）共享变量的值时，这个锁将确保之前的读线程首先全部执行完成，然后再允许写入线程执行更新操作。当读/写锁允许某个写入线程访问共享变量时，新的读取线程或者其他写入线程都将不能执行，直到当前的写入线程执行完成。

    在编写本书时，我正在阅读《Feynman Lectures on Computation 》（于1996 年出版）这本书。Feynman 在第3章中阐述了计算理论。他首先给出了一个有限状态机（自动机），然后再介绍了图灵机（Turing Machine ）。最初我感到有些惊讶，因为既没有任何内容是关于下推自动机（push-down automata ）或者上下文无关语言（context-free language ），也没有任何内容是关于非确定有限状态机（nondeterministic finite-state machine ）以及如何与语法进行关联或者从语言中识别字符串。我认为一种介绍所有主题的循序渐进的好方法就是我在学生时代学习这些知识的方式。
    我很快意识到，Feynman 只用了一堂课来介绍图灵机和可计算性的思想，因此显然他无法全面介绍我在8个星期时间的课程里学到的所有内容。后来我意识到，他授课的目标学生并非计算机科学专业的学生，而是物理和数学专业的学生。因此，他只需要向学生讲授一些关于背景知识的主题，以及可计算理论的概述。
    这正是我在本书中采取的方法。我不会介绍关于并发编程和并行编程的所有历史背景或者理论知识。我希望简要介绍一些这方面的内容以及一些实例，这样你（我知道你是一位聪明的程序员）就可以根据它们来修改代码和应用程序以在多核处理器上并行运行。在后面章节中介绍的各种算法都可以在一些算法入门课程中找到。即使你可能永远都不会用到本书中任何一种并发算法，但这些代码仍然很好地解释了一些并发方法的设计，而你可以将这些方法应用到你自己的程序中。因此，借用著名厨师Gordon Ramsay 的话，我希望给出对并发编程的“简单而又浅显”的介绍，从而使你能够对这一领域有所了解。

    在开始介绍本章内容之前，我将首先简要地介绍并发算法的两种设计方法。我可以提前告诉你，在后面的章节中将有大量的代码示例来证明这些方法的正确性。本书的主要内容是介绍各种并发算法的设计，而在本章中我收集了一些基本方法，在你遇到的大多数代码中都可以使用这些方法（如果没有示例代码可供参考，那么学习过程将变得枯燥无味）。
    此外，我希望你明白，无论你怎样努力，总会有一些计算无法改写为并发形式。为了减少在无用工作上浪费的时间，在“哪些算法不能并行”一节中将给出一些不适合被并行化的算法和计算。当对这些算法进行修改以实现并行执行时，我将给出一些相应的技巧和提示。

    如果你想将某段串行代码转换为并发代码，那么首先要找出代码中包含的可并发执行的独立计算。你在编写串行代码时采用的方式将影响着如何将这些独立计算重新组织为并发代码。一种组织方式是任务分解（Task Decomposition），在这种方式中计算被分解为
一组独立的任务，而多个线程可以用任意顺序来执行这些任务。另一种组织方式是数据分解（Data Decomposition），在这种方式中应用程序需要处理一个大型的数据集合，并且可以对数据集合中的每个元素进行独立计算。
    在接下来的两节内容中将进一步介绍这两种方式，并且对每种方式都将给出一个示例。这两种方式并非仅有的并行设计模型，但我发现它们却是最常被使用的。至于其他计算模式以及如何将它们转换为并发算法，请阅读Timothy G. Mattson 等人撰写的《Patterns
for Parallel Programming 》一书（Addison-Wesley, 2004 ）。在接下来两节中给出的许多思想都是来自本书的内容。

任务分解
    当你深入思考并发算法时，会发现任何一种并发算法都可以被视为由一组并发任务构成。有些任务可以被表示为代码中的独立函数调用。有些任务可以被表示为能够以任意顺序执行的循环迭代。还有些任务可以被表示为一组串行代码，并且这些代码都可以被分解和重构为独立计算。在所有这些情况中，你都必须识别出其中包含的任务，并将串行代码分解为可并发执行的工作。如果你对源代码以及代码执行的计算非常熟悉，那么可以通过分析代码找出这些独立的计算。
    我已经提到过，任务分解（或者说任何转换为并发代码的过程）的目标是找出那些完全独立的计算。然而，在串行计算的各部分代码之间几乎都存在着某种程度的交互。这些交互也称为依赖性（Dependency）。在代码能够并行运行之前，你必须首先满足或者消除
这些依赖性。“哪些算法不能并行”一节将介绍一些依赖性以及如何消除这些依赖性。
    你将会发现，在大多数情况中都可以找出位于并发计算起始阶段的独立任务。在应用程序已经定义了任务，创建了线程并将任务分配到各个线程上之后（稍后将进一步介绍这些步骤），接下来几乎每个并发应用程序都会等待这些并发任务执行完成。为什么？让我们重新思考最初的串行代码。串行算法在完成上一个步骤之前，是不会进入到后续步骤的。这就是为什么我们将其称为串行执行的原因。通常，我们在并发代码中需要保持这种执行顺序，以在并发代码中能够维持串行一致性（即在输入相同的数据集时产生与串行代码相同的结果）。
    在执行并发工作时，一种最基本的模式就是，由主线程或者进程线程定义和准备好任务，然后创建一些新线程来执行这些任务，并等待直到所有线程执行完成。这种模式还有其他许多变化形式。在并行执行中，所有线程是否都是在应用程序内部创建和结束的？当线程执行完所分配的任务时，是否可以被置入“睡眠”状态，而当新任务到达时又被“唤醒”？当并发任务启动后，主线程为什么不参与到任务的执行中，而是被阻塞？要实现上述种种方式，只需要简单地改变编程逻辑，但它们仍然都遵循基本的模式，包括准备任务，将任务分配到各个线程执行，并且在执行下一步计算之前确保所有任务都已经完成。
    是否可以无须等待整个任务集合执行完成而直接进入到下一个计算阶段？当然可以。我们来考虑一个搜索算法。如果每个任务都是在整个数据空间的某个子空间中进行搜索，那么当你已经找到了符合条件的数据项时，是否还有必要继续搜索下去？在串行代码中很可能会停止搜索，那么为什么在并发任务中要继续浪费执行资源而又不产生任何有价值的结果？ 如果要在预定的结束位置之前终止线程执行，我们需要增加一些编程逻辑以及开销。线程需要定期检查任务的状态以判断是继续搜索还是结束。如果搜索算法是要找出所有符合条件的数据项，那么每个线程都需要处理完所有被分配的数据项，而无须考虑提前结束。还有一些情况是，随着计算的进行， 将动态地产生新的任务。例如，如果是对某个树形结构进行遍历并对每个节点执行某种计算，那么可以将任务设置为对以当前节点为根节点的子树进行遍历。对于二叉树而言，在每个内部节点上最多会创建两个任务。对这些新任务进行封装并将它们分配到各个线程上的机制就是一种累加式编程（Additional Programming）。
    在任何一种任务分解设计中，你需要考虑3个关键的要素：
    . 什么是需要计算的任务以及如何定义它们？
    . 在任务之间存在哪些依赖性以及如何满足这些依赖性？
    . 如何将任务分配到线程？
    在接下来的小节中将进一步介绍这些要素。
    什么是需要计算的任务以及如何定义它们
    找出应用程序中独立计算的难易程度与你对代码以及代码执行计算的理解程度成正比。就我所知，没有任何一种流程、公式或者技巧能够立即告诉我们在哪些位置存在独立计算。对于应用程序中可能包含独立计算的地方，你需要在脑海里模拟两个并行的执行流，以判断这些地方的代码是否彼此独立（或者是否存在容易处理的依赖性）。
    对于给定的源代码，可以模拟代码的多线程并发执行，这种技术在设计并发算法以及证明这些算法的正确性上（参见第3章的内容）给我带来了极大的帮助。掌握这种技术需要一定的练习，但正如其他需要通过练习才能掌握的技术一样，你练习得越多，使用起来就越能得心应手。我将在本书中介绍我是如何掌握并发设计技术的，然后你就可以开始应用这些技术自行设计并发算法。

提示
虽然在识别独立计算时没有任何“秘笈”，但在识别循环迭代中的独立计算时却存在一个例外。如果你怀疑在某个循环中存在着独立的迭代（即这些迭代可以用任何顺序执行），那么可以尝试以逆序来执行这些循环迭代。如果应用程序仍然能够产生相同的结果，那么这些迭代就极有可能是独立的并且可以被分解为多个任务执行。需要注意的是，在并发执行迭代时，仍然可能会暴露出一些“隐藏的”依赖性问题——例如，当以串行方式来执行循环时，某个变量在迭代过程中的临时值不会产生破坏，即使在逆序串行执行情况下也是如此。

要想获得事半功倍的效果，你应该一开始就将重点放在应用程序中计算密集的代码部分。也就是，分析那些计算量最大或者消耗执行时间最多的代码。你当然希望在转换、调试以及调优并发代码后获得的性能提升与付出努力之间的比值越高越好。（我承认我是个比较懒的程序员——只要能够通过最少的工作获得最好的结果，我就会选择这种方式。）
当你找出了可以并发执行的串行代码后，在将代码分解为多个任务时记得要遵循以下两个原则。
. 任务的数量最少应该等于线程（或者处理器核）的数量。
. 在每个任务中的计算量（即粒度）必须足够大，以弥补在管理这些任务和线程时付出的开销。
第一个原则是为了确保在应用程序的执行过程中不会出现空闲的线程（或者空闲的处理器核）。如果根据线程的数量来设置任务数量，那么应用程序就能更好地应对执行平台发生变化的情况。通常，任务的数量最好要多于线程的数量。这将使得在把任务调度到线程时更加灵活，从而获得更好的负载均衡。当每个任务的执行时间并不完全相同或者任务的执行时间不可测时，尤其应该遵循这个原则。
第二个原则是为了确保从应用程序的并发执行中获得尽可能多的性能提升。在任务中包含的计算量称为粒度（Granularity）。任务中的计算量越大，那么粒度也就越大；如果计算量越小，那么粒度也就越小。粗粒度（Coarse-Grained）和细粒度（Fine-Grained） 这两个术语分别用来描述大粒度和小粒度这两种情况。任务的粒度必须足够大，从而使对任务和线程进行管理的代码只占整个并行执行代码的很小一部分。如果任务过小，那么在实现并发算法时带来的开销，包括封装任务，将任务分配到线程，对任务计算完成后得到的结果进行处理，以及其他必要的线程协调和管理等功能，将抵销甚至超过将算法放在多核处理器上运行所带来的性能提升。

提示
粒度的另一种定义是：在执行同步操作之前完成的计算量。两个同步操作之间的时间间隔越长，那么粒度就越粗。细粒度并发中存在的潜在危险是，无法将足够多的工作分配到线程上以弥补在使用线程时带来的额外开销（同步开销）。如果增加线程的数量，但计算量并不发生变化，那么只会使问题进一步恶化。粗粒度并发的额外开销相对较低，并且更容易随着线程数量的增加而实现可伸缩性。

考虑这种情况，在两种不同的任务分解情况中，每个任务的额外计算时间都是相同的。如果在一种方式中某个任务被分解为16 个子任务，而在另一种方式中被分解为4个任务，那么在4核处理器和4个线程的情况下，哪种分解方式将运行得更快？图2-1 给出了两种任务分解方式以及各自的执行和额外开销。

图2-1：任务粒度示例
你可以把图2-1 中每个方框的高度视作为执行相应计算所需要的时间总量。图2-1a 为细粒度分解，其中包含了许多小任务——每个任务都需要独立的计算开销，这种方式比图2-1b 中的粗粒度分解方式要运行更长的时间，其中粗粒度将相同的工作分解为更少但却更大的子任务。更大的任务还可以带来其他性能优化（例如，重用缓存、更高效的内存访问模式等），在串行算法中通常会包含这些性能优化。
你要努力在这两个原则之间实现一种平衡。对于固定数量的工作，定义的任务越大，那么分配到线程的任务数量就越少。你将发现，为了满足第二个原则（这个原则也是二者中相对更为重要的原则），有时候需要使任务数量小于线程数量。由于编写和运行并发代码的主要目的就是为了减少执行时间，因此一个没有使用全部处理器核的应用程序，比一个由于使用了全部处理器核但却导致性能更差的应用程序要好。
最后，不要害怕对任务分解方式进行反复修改。如果最初的分解方式不能满足这个原则，那么你应该考虑其他分解方式。同样，如果你发现并没有获得预期的性能提升，那么就可能需要重新定义任务、所需要使用的线程数量，以及将这些任务分配到线程上的方式。

任务之间存在哪些依赖性以及如何满足这些依赖性
在任务之间存在两种类型的依赖性。第一种是顺序依赖性（Order Dependency），指的是某个任务依赖于另一个任务的计算结果。这种依赖性可以是一种直接需求，如使用前面的计算结果作为后续任务的输入，或者也可能是后续任务和前面任务需要更新同一个内存位置，并且你必须确保在执行后续的更新操作之前，必须首先完成前面的所有更新操作。这两种情况都表示在任务之间存在潜在的数据竞争，这正是我们需要避免的问题。
例如，假设我们正在建一座房子，在搭建屋顶时包括在墙上搭起椽梁，钉好天花板和铺上瓦片等任务。这3个任务之间的依赖性就是顺序依赖性。在天花板没有被钉好之前是不能铺瓦片的，同样在没有架好椽梁之前也是不能钉天花板的。因此，你不需要雇3个施工队来并行做这三个任务，而只需雇一个施工队按照顺序依次完成这3个任务（在每个步骤之中包含有并行性，此外一些其他任务，如安装屋顶与安装电线、开关和干墙等是可以独立进行的）。
为了满足执行顺序的限制，在调度任务时需要将有顺序依赖性的任务调度到同一个线程上，并确保线程以正确的顺序来执行这些任务。我们在编写串行代码时已经隐含地考虑了顺序依赖性。因此，串行算法应该用于帮助我们如何正确地将计算分解为多个任务以及如何将这些任务分配到线程。然而，有时候即使对任务进行分组并调度到相应的线程上执行后，在线程之间仍然会存在顺序依赖性的限制。在这种情况下，如果无法对任务重新分组或者这么做会严重降低性能，那么你就必须通过某种形式的同步来确保正确的执行顺序。
第二种类型的依赖性是数据依赖性（Data Dependency）。识别潜在的数据依赖性非常简单： 只需找出位于赋值运算符左边的变量。数据竞争的必要条件是，至少有一个线程对变量执行写入操作。我们要找出对同一个变量的并发赋值操作，以及对并发读取变量的更新操作。当然，如果在变量中使用指向内存位置的指针，那么可能会使得识别过程更加复杂。有些工具（将在第11 章中介绍）可以帮助我们找出代码中一些无法轻易发现的数据依赖性。
解决数据依赖性可能比解决执行顺序依赖性要更为复杂。对于后者而言，串行代码中的执行顺序就是一个可供参考的解决方案；对于前者而言，如果在编写串行代码时假设程序将在单线程的环境下执行，那么很可能会出现问题。
如果你幸运地发现在代码中不存在依赖性，这种情况也称为理想并行（Enchantlingly Parallel），那么你可以跳到后面学习关于调度的内容。如果你不够幸运，那么就要对依赖性进行分析以判断是否可以消除它们（例如，递归变量（Recurrence Variable）或者归纳变量（Induction Variable）等情况）或者被独立出来（例如，归约计算（Reduction Computation）情况）。在许多情况下，有许多方法可以用来解决这些依赖性。我们将在“哪些算法不能并行”一节中对这两种依赖性以及解决它们的方法进行详细介绍。
现在，让我们来看看解决任务之间数据冲突的两种最简单方法。在这些方法中都使用了局部变量并且增加了互斥代码。考虑在示例2-1 中给出的伪码（如果你生活在芝加哥或者纽约，那么在计算人口差值时可以用其他地名来代替，如洛杉矶）。
示例2-1 ：使用共享变量的伪码
popDiff = abs(Population[MyTown] -Population[NewYork]);
DoSomething(popDiff, MyTown, NewYork);
popDiff = abs(Population[MyTown] -Population[Chicago]);
DoSomething(popDiff, MyTown, Chicago);
如果对函数DoSomething() 的并发调用是线程安全的（即在并发调用这个函数时不会产生任何副作用或者依赖性），那么就可以将前两行代码放到一个线程上执行，而后两行代码放到另一个线程上执行。虽然这将会在popDiff 变量上产生数据竞争， 但由于这个变量只是被作为一个临时变量，因此只需为每个线程都分配一个局部副本就可以解决这个问题。
根据在实现并发算法所使用的线程模型，可以有几种不同的方式来创建一些只能由单个线程访问的变量。例如，如果在线程执行的函数内部声明了一个变量，那么这些变量对于调用线程来说就都是局部变量。另一种方式是从线程栈中直接分配空间（通过alloca()函数）。在OpenMP 中定义了private 子句来为并行区域（Parallel Region）中的每个线程生成变量的局部副本。在Windows 线程和POSIX 线程中包含了线程局部存储（Thread-Local Storage,TLS）API ，这些API将分配内存来保存变量的副本，每个线程保存一个，并且线程只能访问属于自身的副本。

提示
TLS API 非常“烦琐”。我并不建议在单个函数中用TLS 来替代局部变量。如果通过TLS API 来分配和访问变量，那么这些变量在不同的函数调用之间将保持不变。如果你需要获得某个变量的局部副本，并且当线程调用不同函数或者对同一个函数多次调用时需要能够访问这个变量，那么就可以通过TLS 机制来实现这个私有副本，它的值将在函数调用期间保持不变。

当所有这些方式都行不通，或者当你无法获得共享变量的局部副本，或者出现了在“哪些算法不能并行”一节中给出的通过各种转换方式都无法消除的数据依赖性时，剩下的唯一一种方法就是在共享变量上实现互斥访问。在大多数情况下，只需使用一个锁或者互斥体就足够了。在某些情况下，你或许需要使用稍显复杂的原子操作（Atomic Operation 。在不同的线程模型中可能需要不同的同步对象，而不同的算法也有不同的保护要求。
当然，你希望将同步方法对性能的影响保持在最低的限度，因为在最初的串行代码中并不存在这种同步机制带来的开销。这意味着你需要尝试多种方法，甚至修改最初的算法或者数据结构，才能获得一个更好的同步对象。作为一个程序员，你需要为所遇到的每种情况都找到最优的方法。

如何将任务分配到线程
任务必须被分配到线程上执行。或许这句话更正确的表达方式是，线程必须知道该执行哪些任务。通常，你要确保各个线程完成的计算量基本相等。也就是，各个线程之间的（计算）负载必须是均衡的。我们可以通过两种不同的方式将任务分配到线程：静态调度（Static Scheduling）和动态调度（Dynamic Scheduling）。

提示
如果使用OpenMP 中的工作共享（Work-Sharing）结构和Intel Threading Building Blocks(TBB，Intel 线程物构模块)中的Parallel 系列算法下，那么将任务分配到线程的实际操作是在“幕后”完成的。不过，程序员在某种程度上也可以介入这种分配操作。即使你在编写并发代码时只使用了这两个库中的某一个，也应该仔细阅读本节中的建议，这样能够帮助你更好地对应用程序中的任务分配过程进行调整。

在静态调度中，对任务的分解是在计算开始时完成的，并且在计算过程中不会发生变化。在编写并发代码时，如果可能的话，应该尽量采用静态调度方式。这是最简单的编程方式，并且带来的开销也是最小的。
在实现静态调度方式时，按照机制和代码逻辑，需要为每个线程指定一个唯一的标识号，如果有N个线程，那么标识号的取值范围就是[0, N-1] 。在创建线程时，这个标识号可以根据线程的创建顺序来分配（在后面章节的几个示例代码中将包括生成唯一标识号的代码）。如果任务是一组独立的函数调用或者串行代码段，那么可以将这些调用或者代码段分解为多个子任务，并且根据线程的ID 分配给各个线程（例如，通过switch 语句）。如果任务是循环迭代，那么可以将迭代的总数量除以线程数量，并将得到迭代子区间分配到各个线程上，此时可以再次根据线程的ID 来分配。在这种情况下，你需要增加额外的代码来计算循环边界的起始值和结束值，以确定每个线程需要执行的迭代区间。
在将循环迭代分解为多个区间时，你需要确保各个线程执行的迭代区间之间不会重叠，而全部线程将覆盖整个循环迭代区间。如果多个线程将某次迭代执行多次，或者没有执行某些迭代，那么都将得不到正确的结果。另一种分解循环迭代的方法是，将线程的ID作为循环迭代的起始值，并且下一次迭代的序号为上一次迭代序号加上线程数量，而不是1。例如，假定有两个线程，那么其中一个线程将执行奇数序号的迭代，而另一个线程将执行偶数序号的迭代。显然，如果循环迭代不是从0开始并且每次的递增量也不是1，那么就需要对循环的起始位置和每个线程执行的下一次迭代进行调整。不过，要实现N个线程中每个线程执行每隔N次的迭代，比将迭代集合分解为独立子区间的代码改动要更少。
最适合使用静态调度方式的情况是，每个任务的计算量相同，或者可以在计算开始时预测出来。如果任务之间的计算量是可变的或者是不可预测的，那么最好使用动态调度方式。
在动态调度方式中，将随着计算的执行逐步地将任务分配到各个线程。动态调度方式的主要目的是，努力使得线程之间的负载达到均衡状态。在将任务分配到线程时将带来一定的开销，包括执行额外的编程逻辑来实现任务分配以及将新任务交给线程。
有许多不同的方式可以实现以动态方式将任务调度到线程，但它们都要求任务的数量要多于线程的数量。最简单的实现方式就是对任务建立索引。通过一个共享的计数器来跟踪并分配下一个需要执行的任务。当找到一个新任务时，线程将以互斥方式来访问计数器，将计数器的值复制到一个局部变量，然后递增计数器的值并传给下一个线程。
另一种简单的动态调度方法是构造一个共享容器（通常是一个队列），在容器中包含了所有任务。当一个任务完成之后，由线程从中提取出一个新任务。我们必须将任务（或者对任务的描述信息）封装到某种结构中以压入到队列。线程之间必须通过互斥的方式来访问队列，以确保每个线程获得不同的任务并且不会由于共享容器被破坏而导致任务丢失。
如果在将任务分配到线程之前需要进行某种预处理，或者如果在计算开始时无法知道关于任务的信息，那么就可能需要采用一些更复杂的调度方法。你可以预留一个线程来为每个任务执行预处理操作，或者接受新的任务。如果其他执行计算的线程需要与这个预留线程进行通信以接受下一个任务，那么这就是一种“老板/工人”算法。如果通过一个共享容器在准备任务的线程和执行任务的线程之间分配任务，那么就是一种“生产者/消费者”方法。我在第1章中简要地提到了这些方法。

示例：数值积分
到目前为止，我们已经了解了定义和实现任务分解的方法，现在就通过一个非常简单的应用程序来实现这些方法：在程序中将计算常量PI 的近似值。我们并不需要关心如何通过多线程来实现这种并发，而是要找出需要做出的各种设计决策，以及在实现时需要考虑的其他因素。
数值积分是一种计算位于函数曲线之下区域面积的近似方法，尤其适用于一些无法计算精确值的情况。例如，常量PI 的值可以由以下公式定义。然而，我们不需要精确地计算这个数值，而是可以通过积分来近似计算：

在示例2-2 中的代码实现了一种基于中点矩形的数值积分方法来求解上述积分。要计算位于函数曲线之下面积的近似值，我们必须计算一组矩形（num_rects）的面积，找到每个矩形的中点（mid）并且计算该矩形的高度（height），其中高度值就等于函数在这个中点上的值。我们将所有矩形的高度相加（sum），然后将sum 乘以矩形的宽度（width） 就近似得到总面积值（area），这个值也就是PI 的值。
我没有给出这段代码的多线程版本，但读者可以自行根据后面介绍的任务分解方式来尝试实现代码的多线程版本。
示例2-2 ：计算PI 近似值的数值积分代码
static long num_rects=100000;
void main()
{
  int i;
  double mid, height, width, sum = 0.0;
  double area;

  width = 1.0/(double) num_rects;
  for (i = 0; i < num_rects; i++){
      mid = (i + 0.5) * width;
      height = 4.0/(1.0 + mid*mid);
      sum += height;
  }

  area = width * sum;
  printf("Computed pi = %f\n",area);
  }

在这个简单的应用程序中，哪些是独立的任务？对各个矩形高度的计算是彼此独立的。此外，还要注意到执行这些计算的循环占据了整个应用程序计算时间的绝大部分。这个循环是一个执行热点，因此你应该对这个位置上的独立计算进行分析。
在这些任务之间是否存在依赖性，如果存在，我们如何来满足它们？在每次迭代中，mid 和height 这两个变量都被分配不同的值。如果每个线程都有一个局部副本，那么就可以在该线程执行迭代的过程中使用这个副本。同样，迭代变量i在每次迭代中也被更新。每个线程同样需要该变量的一个局部副本，以避免与其他线程执行的迭代发生相互干扰。变量sum 在每次迭代中也被更新，但由于这个变量在循环的外部被使用，因此我们不能在每个线程中为这个变量分配一个局部副本，因为在线程执行完成后，这个副本将被抛弃而无法继续在循环外部使用。这种情况被称之为归约（Reduction ），在后面的“哪些算法不能并行”一节中将介绍解决这种情况的方法。一种快捷但却并非最优的方法是，在更新sum 的代码行周围放置一个同步对象，这样每次只有一个线程会写入这个变量。
如何将任务分配到线程？如果将循环迭代作为任务，那么我们将根据线程的ID 值将不同范围的迭代区间分配到各个线程。另一种方式就是，我们可以让线程执行交错的迭代，迭代之间的间隔为线程的数量。由于在循环中没有被索引的数组元素，也就不存在缓存问题（译者注：如果使用了数组元素，那么这种方式将使得线程发生缓存缺失的情况增多），因此我建议使用后一种方法。
最后一个需要考虑的因素是，将各个独立的计算结果相加起来并存储在某个内存位置以输出。这将直接取决于sum 的归约计算方式。

数据分解
在开始介绍数据分解（Data Decomposition ）之前，我希望你没有跳过之前介绍任务分解节而直接阅读本节内容。在那之前介绍任务分解节中包含了许多非常有用的内容，我希望你已经阅读并且理解了全部的内容。其中有许多内容都可以直接应用到数据分解中，因此在这里将不会再次重复。即便你认为自己在今后的编程工作中只会遇到数据分解问题，也还是要阅读之前介绍任务分解。只有这样你才能更好地理解在这两种分解方法之间存在的一些共同问题。
在开始分析如何将一个串行程序转换为对应的并发程序时，你要找出的第一个计算特征就是：程序中的大部分执行时间都被消耗在对一个或者多个大型数据结构中的所有元素执行更新操作上。如果这些更新操作是彼此独立的，那么应用程序的并发性就可以表示为，将数据结构分解为多个部分，并将这些部分以及相应的更新计算（任务）分配到各个线程上。这种对大型数据结构进行分解并将分解后的各部分数据分配到线程上的方法就称为数据分解。在Mattson 的《Patterns for Parallel Programming 》一书中，这种方法也被称之为“几何分解（Geometric Decomposition ）”。
如何将数据结构分解为连续的数据子区间，或者说数据“块（Chunk ）”，这要取决于数据结构的类型。在数据分解模式中，最常见的数据结构就是数组。你可以按照数组的某一维或者若干维来分解数组。而一些在内部使用了数组的结构（例如，采用邻接矩阵（Adjacency Matrix ）来实现的图）同样可以被分解为数据块。这完全取决于计算的流程是什么以及每个数据块处理过程的独立程度如何。
表结构（List ）也属于可分解的数据结构，但需要存在一种简单的方式可以找出和访问子链表中的离散元素。对于链表（Linked List ）来说，这就要求存在一些索引指针指向链表中不同的入口点。例如，假定有一个包含了人名的链表，按照字母顺序排序，对于每个字母来说，都有一个外部指针指向第一个以该字母作为起始字母的人名。如果并发代码需要自行构造这些外部引用，那么就会带来一定的开销，因此要确保有足够的计算量来弥补这种额外的开销。否则，就应该考虑换一种数据结构或者采取其他方式来实现并发。
无论采取何种方式，将数据结构分解为多个数据块都意味着将整体计算分解为多个任务，每个任务都将处理一个数据块中的所有元素，并且将这些任务分配到不同的线程上。然后，这些任务将并发执行，并且每个任务都将更新与之相关的数据块。数据块中的数据是安全的，因为其他任务不会更新它们。然而，如果在更新计算中需要使用来自邻接数据块的数据，那么就必须在任务之间共享数据。当从邻接数据块中访问或者提取数据时，需要在线程之间进行协调。
在任务分解中，需要考虑的重要因素之一是负载均衡，尤其当使用变长的数据块时。如果数据结构采用了一种规则的组织方式，并且在这个结构中每个元素上的计算时间大致相等，那么就可以通过一种高效的方式将数据结构分解为包含相同数量元素的数据块。如果数据结构的组织方式并不规则，或者数据结构中每个元素的计算量不相等或者不可测，那么要确保分解后各个任务的执行时间大致相等则远非一项简单的工作。在这种情况下，你或许应该考虑采用一种动态的方式将数据块调度到线程。
下面将介绍在成功的数据分解方式中需要包含的一些关键要素。在该节中还提到了如何对邻接数据进行共享以在多个数据块的计算之间实现最佳负载均衡。在设计任何一种任务分解时，你需要考虑3个关键的要素分别是：
. 如何将数据分解为数据块？
. 如何确保每个处理数据块的任务能够在更新操作中访问到所需要的数据？
. 如何将数据块分配到各个线程？
在接下来的章节中将依次介绍这些要素。

如何将数据分解为数据块
将全局数据结构分解为数据块是在设计数据分解方式时的核心要素。数据块的分解机制主要取决于数据结构的类型。我将分别以一维数组和二维数组为例来进行说明。在这些示例中采用的思想只需稍加修改就可以应用到其他数据结构。
由于每个数据块都有一个相关的任务，因此在任务分解中定义任务时采取的准则同样可以被应用于数据分解中数据块的定义。特别是，要确保每个线程至少被分配到一块数据（越多越好），并且确保该数据块的计算量足以弥补将其作为一个独立数据块所需要的开销。（现在你是否觉得在开始本节之前首先学习了任务分解一节是有帮助的？）
对于数组来说，你可以将数组分解为单独的元素、行或者列，以及多行或者多列，或者包含多行和多列且不重叠的子区间。图2-2 给出了将一个4×4的数组分解为数据块的几种不同方式。

图2-2：数组分解示例
每个任务中的计算量与数据块中元素的数量是直接相关的。在前面已经提到，这称为数据分解的粒度，它与我们在定义任务时提到的粒度的含义是完全一样的。
然而，在将数据结构分解为数据块时，你还必须多考虑一个因素，就是数据块的形状。
数据块的形状决定着哪些数据块是邻接的，以及在数据块的计算过程中如何交换数据。假定我们需要在每个数据块之间跨越数据块的边界来交换数据（“交换（Exchange）”
这个术语的含义是，从某个数据块之外的其他数据块中提取数据并将数据用于该数据块内部元素的更新操作中）。如果降低整体边界的大小，那么就能减少在更新数据元素时需要交换的数据量；如果降低与某个数据块共享边界的数据块数量，那么将降低编码和执行交换操作的复杂性。
事实上，粗粒度将破坏数据块的形状。在数据块中包含的数据元素越多，那么就可能有越多的元素需要与邻接数据进行交换，因此在执行数据交换上的开销也就越多。在确定如何对需要数据交换的大型数据结构进行分解时，经验法则之一就是努力将体积与表面积比（Volume-to-Surface ratio）最大化。体积（Volume）指的是计算的粒度，而表面积是需要交换数据的数据块边界。图2-3 说明了将一个4×8的数据结构分解为数据块的两种不同方式。数据块中包含的元素数量是相同的（16），但左边分解模式得到的结果有8个元素共享边界，而右边分解模式得到的结果只有4个元素共享边界。如果在更新每个数据块时需要跨越边界访问其他数据块中的数据，那么右侧分解模式中数据交换次数将更少。

图2-3：体积与表面积比的示例
如果数组的组织形式不规则，那么可能生成不规则形状的数据块。在处理不规则形状的数据块时要保持更高的警惕，以确保获得良好的负载均衡，以及尽可能获得更高的粒度以减轻不必要计算开销对性能带来的影响。
在考虑了数据块的粒度以及形状对任务之间数据交换的影响之后，你或许需要修改分解策略。在将数据结构分解为数据块时采取的方式将决定着是否需要访问其他数据块中的数据。在后面阐述了关于访问邻接数据的一些问题，当你确定如何以最优的方式将数据结构分解为数据块时，将需要考虑这些问题。

如何确保处理每个数据块的任务在执行更新操作时能够访问到所需要的数据
通常，在使用数据分解模式的并发算法中，对数据块中的元素进行更新是主要的计算工作。很少有应用程序只从数据结构中读取数据而不执行更新操作。即使在这些情况中，在应用程序能够读取数据之前，必须首先创建数据并且对数据结构中保存这些数据的元素进行更新。我认为，对于只需输入数据然后仅将数据用于其他计算的应用程序来说，在设计并发代码时应该优先采用任务分解模式。
如果在数据块本身中包含了执行更新操作时需要的所有数据，那么就无须协调任务之间的数据交换。当所需的数据位于邻接数据块中时，将出现一种更值得注意的情况。在这种情况中，我们必须找到高效的方式以在邻接的数据块中交换数据。我们很容易想到有两种方法可行：将数据从邻接数据块中复制到任务（线程）本地的数据结构中，或者在需要时才从邻接数据块中访问数据。让我们来分析这两种方法各自的优缺点。
在复制数据这种方法中，最明显的缺点就是每个任务都需要额外的本地内存来存储数据副本。不过，在复制了这些数据后，在任务之间就无须通过竞争或者同步来访问这些副本。如果在执行更新操作之前就可以访问到数据，并且这些数据在被复制或者执行更新计算的过程中不会发生变化，那么就最适合使用复制数据方法。这可能需要在任务之间进行一些初始的协作以确保在任务开始执行更新操作之前，所有复制操作都已经结束。
用于保存副本数据的内存资源称为重影单元（Ghost Cell）。这些单元是邻接数据块中的数据在本地数据块中的映像（Image）。例如，考虑在图2-3b 中的数据分解。如果对某个元素的更新计算需要来自与该元素同一行的左右两个元素，那么就需要访问邻接数据块边界处的一整列元素。在将这些数据元素复制到重影单元后，在访问这些数据时就不会干扰到邻接数据块的更新操作。图2-4 给出了分配好的重影单元，以及在线程中为了填充这些单元而执行的复制操作。

图2-4：使用重影单元保留从相邻数据块的复制数据
在使用复制数据方法时，另一个要考虑的因素就是需要执行多少次复制操作。这完全取决于更新计算本身。例如，在迭代算法中是否需要重复的副本，这个算法需要经过多次更新操作才能求解出答案？或者说，只有在计算开始时才需要数据副本？需要执行的复制操作次数越多，那么就会给更新计算带来越大的开销负担。然后就是需要复制的数据量。如果复制操作过多，或者被复制的数据量过大，那么就应该考虑直接从邻接数据块中访问所需要的数据。
“根据需要来访问数据”则充分利用了线程之间的共享内存通信以及最初串行算法的逻辑。同时，你还可以将任务之间的协调操作推迟到只有被需要时才执行。然而，这种方式的缺点在于，必须确保在正确的时间获得正确的数据。位于邻接数据块中的数据元素可能正处于被更新的过程中。如果需要的是邻接数据块中元素的“旧”值，那么代码如何确保这些值不是“新”值？要回答这个问题，或者要知道我们是否必须处理这种情况，就需要分析在与邻接数据块之间交换数据过程中可能发生的交互，以及本地数据块元素上执行的更新操作。
如果所有数据在任务开始执行时就已准备就绪，并且在更新计算中不会发生变化，那么这种解决方案实现起来就更容易，并且执行起来也更高效。你可以复制相对较少的数据到重影单元中，或者通过共享内存来访问不会发生变化的数据。当复制非本地的数据时，在执行更新计算之前首先增加一个数据收集（交换）的阶段。我们要努力减少数据收集阶段的执行时间，因为在最初的串行代码中并不包含这部分开销。
如果在执行更新计算期间需要访问（或者复制）非本地的数据，那么就需要添加相应的代码来确保找到正确的数据。将数据交换和更新计算混合在一起将使应用程序的逻辑变得复杂，尤其是在确保要获得正确的数据时。不过，在串行程序中可能同样存在这种需求，此时要想正确地并发访问数据，只需尽量遵循串行算法即可。
例如，如果对一个金属板的热量分布进行建模，那么可以用一个二维数组来模拟金属板，在数组中包含的值是位于各个位置点上的当前温度。在计算的每次递进步骤中，每个位置上的新温度值等于该位置上的当前温度以及一组邻接单元温度的平均值。由于在计算过程中将更新单元位置的当前温度，并且对需要使用该单元值的其他单元进行调整，因此在串行代码中将定义一个新温度数组和一个旧温度数组。旧温度数组中的值将被用于更新新温度数组中的值。这两个数组的角色将在下一次迭代过程中相互交换。在并发版本的应用程序中， 将（只会）读取旧温度数组中的值以更新新温度数组中的当前值。这样，在访问旧温度数据时就无需同步，并且只需对串行代码进行很少的修改就可以实现代码的并发版本。

如何将数据块（和任务）分配到各个线程
在任务分解中，处理数据块的任务可以通过静态或者动态的方式被分配到线程。静态调度是最简单的方式，因为在数据交换中所需的协调操作在计算开始时就被确定下来。当各个任务中的计算量是一致的并且可预测时，静态调度是最合适的方式。如果每个数据块中的计算量都不相同，那么要想获得良好的负载均衡性，就需要使用动态调度方式。
这不仅要求任务的数量多于线程的数量，并且同时也使得数据交换操作以及对这些操作的协调和调度变得更为复杂。
细心的读者可能已经发现，在前面几页的讨论内容中，我使用的是“任务”这个术语，而不是“线程”。我这么做是有目的的。任务是由数据结构的分解方式来定义的，它表示的是与其他任务之间的交互，但并没有考虑分配哪个线程来执行哪个任务。此外，如果采用动态调度任务的方式，那么任务的数量必须大于线程的数量。在这种情况中，所有任务不可能同时并行运行。在某些情况中，你可能会发现某个任务需要来自另一个任务的数据，而这个任务还没有被分配到线程上执行。这种情况将并发设计的复杂度提升了一个等级，我将把如何避免这种情况的问题留给读者来解决。

示例：有限格网上的生命游戏
Conway 提出的生命游戏（Game of Life）模拟的是元胞内生命有机体的诞生与消亡的过程，其中元胞（Cell）被组织为格网（Grid）的形式。每个元胞要么为空，或者包含了一个存活的有机体。包含有机体的元胞被称之为“存活的”，而空元胞则被称之为“死亡的”。（请参见图2-5中存活元胞和死亡元胞的格网示例）。在图中描绘了随着时间的递进，有机体的诞生和消亡的过程。更详细的信息请参见《Wheels, Life, and Other Mathematical Amusementsby Martin Gardner》(Freeman & Co., 1983) 一书，或者在该书之后的其他大量参考文献。

图2-5：生命游戏示例：黑点表示活着的元胞
元胞的状态将根据以下规则从上一代进化到下一代：
. 每个元胞有8个邻接元胞，分别与该元胞在水平，垂直和对角线等方向上邻接。
. 如果一个元胞是存活的，但有4个以上的邻接元胞中存活的，那么这个元胞将在进化到下一代时由于饥饿或者拥挤而死亡。
. 如果元胞是存活的并且只有2个或者3个邻接元胞是存活的，那么它在下一代中将仍然是存活的。
. 如果一个元胞死亡了，并且有3个邻接元胞是存活的，那么在下一代中死亡的元胞将重新变成存活的。其他死亡元胞在下一代中将仍然是处于死亡状态。
. 所有诞生和死亡的过程都是在同时发生的。这意味着，即使一个元胞在下一代中将变为死亡元胞，但在使邻接元胞诞生的过程中，仍然被作为存活元胞。
从理论上来说，格网应该是无界的，但由于计算机平台上的内存容量是有限的，因此格网的大小通常是有限的。一个非常大的二维数组可以容纳模拟过程中当前代以及后续代的值。判断某个元胞是否存活，死亡或者诞生的计算与其他元胞的计算是独立的。因此，在有了非常大的二维数组以及对数组中元素的更新操作后，生命游戏的模拟过程就非常适合于采用数据分解设计。
在示例2-3 中给出了在从当前代进化到下一代时对每个元胞状态进行更新的代码。假设Grid 是一个二维数组，可以保存用户自定义的常量值ALIVE 和DEAD 。格网数组行索引的取值范围为0～N+1 ，列索引的取值范围为0～M+1 。多出的行和列中的元胞在更新操作中将不被计入，它们被认为是元胞格网的边界，在它们中包含的有机体都是死亡的（可以将它比作为一面充满毒气的墙，只要吸入就会死亡）。通过增加这些边界元胞，就不需要对格网边界做特殊处理。在统计了某个元胞的邻接元胞状态后，就可以根据上面给定的规则来确定该元胞在下一代中的状态。与我在前面的示例2-2 中没有给出代码的多线程版本一样，但读者可以自行根据后面的讨论来尝试实现多线程版本的代码。
示例2-3 ：生命游戏函数，根据当前代的状态计算下一代的状态
void computeNextGen (Grid curr, Grid next, int N, int M)
{
    int count;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            count = 0;
            if (curr[i-1][j-1] == ALIVE) count++;// 西北方向邻接元胞
            if (curr[i-1][j] == ALIVE) count++; // 正北方向邻接元胞
            if (curr[i-1][j+1] == ALIVE) count++; // 东北方向邻接元胞
            if (curr[i][j-1] == ALIVE) count++; // 正西方向邻接元胞
            if (curr[i][j+1] == ALIVE) count++; // 正东方向邻接元胞
            if (curr[i+1][j-1] == ALIVE) count++; // 西南方向邻接元胞
            if (curr[i+1][j] == ALIVE) count++; // 正南方向邻接元胞
            if (curr[i+1][j+1] == ALIVE) count++; // 东南方向邻接元胞

            if (count <= 1 || count >= 4)
                next[i][j] = DEAD;
            else if (curr[i][j] == ALIVE && (count == 2 || count == 3))
                next[i][j] = ALIVE;
            else if (curr[i][j] == DEAD && count == 3)
                next[i][j] = ALIVE;
            else next[i][j] = DEAD;
        }
    }
    return;
}

在这个应用程序中，什么是大型的数据结构，以及如何将这个数据结构分解为数据块？我在前面已经介绍了，可以将格网分解为多个数据块，并将每个数据块上的任务分配到不同的线程。什么是最优的分解方式呢？请参考图2-5，同时思考的范围可以更大一些。
一些很自然想到的分解方法包括：按行分组、按列分组或者按块分组。你需要计算出在每种分解方法中需要哪些数据交换，并由计算结果来决定采用何种方式。
其他需要考虑的因素包括，格网在内存中的布局（在串行代码中可能已经考虑了这个因素）以及每种分解模式可能对内存布局带来的负面影响。此外，在实现并发版本时所需增加和修改的代码函数也是一个影响你决策的因素。如果按行进行分解，那么需要修改i循环，如果按列进行分解，则需要修改j循环，而如果按块进行分解，则需要修改i循环和j循环。
对于选定的数据分解方式，在任务之间需要交换哪些数据以及如何实现这种数据交换？由于你需要访问元胞的所有8个邻接元胞，如果某个邻接元胞位于不同的数据块，那么就需要某种形式的数据交换。然而，在代码中使用了curr 变量来统计邻接元胞的数量，并且这个变量是只读的。每个任务都可以在需要时访问这个数据，而无需担心获得错误的值或者与其他任务发生数据竞争。另一方面，如果在计算下一代的规则中允许我们对正被统计的邻接元胞进行修改，那么最好将数据从其他数据块复制到本地的重影元胞中。如果不这么做，那么并发代码执行得到的结果将与串行代码执行得到的结果不同。
如何将数据块分配到各个任务？由于你可以在设计时确定任何格点和任何元胞集合的计算量，因此可以采用静态的分配方式。事实上，我建议数据块的数量应该等于可用线程的数量。
任务之间存在哪些依赖性？这个问题来源于我们对任务分解方式的讨论，并且超出了数据块之间数据交换的讨论范围。这个问题的答案是来自于串行代码以及必要的修改（来自于你之前做出的所有设计决策）。count 是一个临时工作变量，因此需要在每个线程中定义一个本地副本。每个线程还需要这两个循环迭代变量的副本。全局变量数组是安全的，因为curr 是只读的，并且对下一个格点中元素的更新操作将不会重叠。

并发设计模型起步
在设计任务分解或者数据分解等模式时，通常没有明确的步骤可供遵循。当考虑如何回答你所选择的设计模型中的各个设计要素时，有些决策需要基于后面一些问题的答案以及之前的一些答案。我希望你能从每个示例的讨论中领悟其中的思想。尽管我必须依次写下这些问题，但你可以每次考虑多项事情，以设计出高效的并发解决方案。
设计要素记分卡
对于在从第6章～第10 章中讨论的大多数算法，我都将给出一个“设计要素记分卡”来讨论并发算法及其实现中的4个关键要素。这些要素是在Mattson 的《Patterns for Parallel Programming 》一书中提出的，并发程序员在使用本书中给出的并行编程模式来设计和实现并行应用程序时，需要始终记住这些要素所构成的标准。在这里，我将重新定义这些术语，它们的含义与Mattson 最初给出的定义略有不同。稍后将给出我对这些术语的解释。
我认为编写并发算法的程序员应该始终记住每一个关键要素，及它们对于彼此的重要性，以及在设计和实现并发算法时如何在它们之间进行权衡。在后面章节中，在讨论完每种算法后，都将在“设计要素记分卡”中给出该算法和代码的各项优势和权衡因素。
效率
并发应用程序必须快速运行并且充分利用计算资源。对于并发算法而言，效率意味着要分析为了确保代码正确执行而增加的计算开销，在不同的线程安排方式或任务组织模式下程序工作的好坏，以及与多线程应用程序相关的其他问题。
简单性
并发算法越简单，那么就更容易编写、调试、验证和维护。对于通过修改串行代码得到的并发代码来说，简单性将侧重于并发代码相对于串行代码所增加的代码量，以及最初的串行算法中有多少结构可以保持不变。
可移植性
本书的目标之一是，尽可能与现有的线程模型以及选择何种模型来实现并发算法保持无关。在对可移植性的讨论中将分析在使用不同的线程模型时将要遇到的各种权衡。虽然本书主要是讨论多线程代码的设计与开发，但在可移植性中讨论的事项之一将是算法的分布式内存变化形式。
可伸缩性
由于随着时间的推移，处理器核的数量只会增长而不会减少，因此并发应用程序应该能够在不同数量线程、处理器核以及数据集规模的情况下都能表现出高效的行为。可伸缩性指的是，随着处理器核数量或者数据集规模的变化，给定的并发算法将表现出怎样的行为。

我对这些要素的一些看法
对于我来说，可伸缩性是这4个要素中最重要的要素，效率则位于第二。这意味着，我通常在设计算法时，会优先考虑当处理器核与线程数量增加时维持并发算法的性能，而这或许会降低算法的简单性或者可移植性。要获得这种可伸缩性，算法及其实现必须是高效的，因此这是我的次要目标。
我曾经遇到过许多次这样的情况，我编写的某个并发应用程序的可伸缩性发生剧烈的波动。这通常是因为算法的不同需求以及所选线程模型的各种特性而造成的。在这些情况中，我会问我自己，是否值得再付出一些努力来找到另外一种可伸缩性更好的方法（这种方法可能并不存在），或者换一种不同的线程或者设计模型来重新编写整个程序。在应对并发算法时，你需要面对一些权衡因素。

在接下来的章节中，我们将分析许多可以并发执行的东西。不过，在我们讨论这些内容之前，我希望首先告诉你并不是所有东西都可以并行执行。我不想你把时间浪费在冥思苦想，反复翻阅本书和其他介绍并行算法的书，在凌晨打电话给朋友或者同事（或者我）来帮你分析并行解决方案，尤其是当这些并发解决方案并不存在时。

提示
在Fred Brooks1995 年撰写的《The Mythical Man-Month：Essays on Software Engineering 》(Addison-Wesley Professional) 一书中给出了一个著名的无法并行的情况：人类的十月怀胎是一个串行过程—— 即使你分配9名女性来做这项工作，也不可能在1个月后得到一名婴儿。
另一方面，如果你想要在最短的时间内让一只棒球队从组建到进入Wrigley Field 棒球馆，那么可以雇用9名女性（如果想拥有一位指定击球员（Designated Hitter）的话，那么需要雇用10 名女性）。这将在9个月之后给你一支全新的棒球队。如果让一位女性去做所有这些工作，那么将需要大约9年的时间，不包括双胞胎，并且当接球手刚出生（第9个出生）时，投手（第一个出生）将正开始她的少年棒球联盟（Little League ）职业生涯。

带有状态的算法
第一种无法并发执行的代码就是包含有某个状态的算法、函数或者过程。也就是说，需要从上一次执行保持到下一次执行的某个东西。例如，随机数产生器的种子值或者I/O 操作中的文件指针都可以被视作为状态。带有状态的算法不能直接被转换为并发形式，当你遇到这种代码时，在考虑并发性时要提高警惕。不过，你可以采取一些步骤来将代码修改为线程安全的，这或许是足够的。
你可以通过增加某种形式的同步或者将代码编写为可重入的（也就是，可以在代码运行时再次进入到代码中而不会产生负面作用），以使得包含状态的代码成为线程安全的代码。前者将把采用了同步的代码的并发执行过程串行化（然而在没有并发运行时将增加不必要的开销），而当在代码中包含了对全局变量的更新操作时，后者则可能无法实现， 如果在线程之间并不共享包含状态的变量，那么可以通过TLS 来消除这种依赖性。
在使用TLS 的情况下，每个线程都将获得状态变量的一个独立副本（在所有线程中采用完全相同的方式来访问），以确保不会在这些变量上发生数据竞争。这样，每个线程都将拥有一个不同的随机数种子值，并且使用相同的代码来生成一系列数值，而又不会与其他线程的种子值发生相互干扰。

递推
在循环中的递推关系（Recurrence Relation ）需要将某些信息从上一次迭代送入到下一次迭代。一些主要的递推示例包括时域递进循环（Time-Stepping Loop ）和收敛循环(Convergence Loop) 。无论我们如何努力，都无法计算出多线程在并发执行时的未来时间步骤。
在示例2-4 中给出了一个简单的递推代码示例。代码中递推为，在计算中要读取在前一次迭代中计算得到的元素a[i-1] 。
示例2-4 ：数组访问上的递推关系
for (i = 1; i < N; i++)
    a[i] = a[i-1] + b[i];
然而，大多数递推关系都无法被修改为并发代码。前缀求和（Prefix Sum ）是一种特殊的递推，它可以并发运行（参见第6章了解关于前缀扫描并发算法的更详细内容）。
如果你发现某个递推关系是代码中的执行热点，那么要在包含递推执行的调用树中的“更高”层次进行分析。在该位置上尽可能多线程化。

归纳变量
归纳变量（Induction Variable ）是指，在每经过一次循环时都会递增的变量。通常，这些变量与循环迭代器变量之间并不存在一一映射关系。在示例2-5 中给出的代码中包含了两个归纳变量，分别是i1 和i2。
示例2-5 ：归纳变量
i1 = 4;
i2 = 0;
for (k = 1; k < N; k++) {
    B[i1++] = function1(k,q,r);
    i2 += k;
    A[i2] = function2(k,r,q);
}
从代码中可以看出，即使对function1() 和function2() 的调用是彼此独立的，但如果不对上面的串行代码做彻底的修改，我们仍然无法将这段代码转换为并发代码。特别是，你需要将数组索引的递增表达式替换为一种只基于循环迭代变量值的计算。
如果没有足够的警惕，那么我相信你很可能将循环中的第一条语句重写为示例2-6 中的形式。
示例2-6 ：修改第一个归纳变量的递增计算
B[k+4] = function1(k,q,r);
第二个变量有些复杂。看看你能否自行找出对第二个变量的解决方案。我将在下一段的末尾给出答案。
比示例2-5 中代码更糟糕的情况是，在归纳变量中包含了条件递增计算。例如，假定你需要在某个列表中搜索，并且将所有包含某种属性的元素复制出来，如唱片发行数量超过Pink Floyd 的所有唱片艺术家。我们假设这个列表是通过某个支持随机访问的数据结构来实现的；否则，如果使用的是一个链表或者基于指针的数据结构，那么我们在如何高效地对数据进行并发访问上将遇到问题。现在，循环索引变量在数据项的完整集合中运行，并且只有当我们找到一个符合标准的数据项时才会递增归纳变量，以将这个数据项保存在第二个数组中（由该归纳变量来索引）。在循环索引值和归纳变量值之间没有闭型关系（Closed-Form Relation ）。
你能否找出如何设置示例2-5 中第二个归纳变量？它只是从1到当前k之间所有整数的和。这样，你可以在并发版本的循环中使用示例2-7 中的代码。
示例2-7 ：修改第二个归纳变量的递增计算
i2 = (k*k + k)/2;
A[i2] = function2(k,r,q);
当然，这是一个我们人为构造的示例。你遇到的情况可能并非如此简单。

归约
归约（Reduction）计算是指将一组数据（通常是一个数组）通过某种符合操作归约为一个简单的标量值。要消除这种依赖性，计算必须是可结合的和可交换的，如加法计算，乘法计算以及其他逻辑计算。在示例2-8 代码中的循环将计算数组c中所有元素的总和，并找出数组中最大的元素（最大值）。
示例2-8 ：归约代码
sum = 0;
big = c[0];
for (i = 0; i < N; i++) {
    sum += c[i];
    big = (c[i] > big ? c[i] :big); // 值最大的元素
}
初看上去，循环无法被修改为并发执行。每个元素都被一次增加到总值，并且与到目前位置找到的最大元素进行比较，并在大于时替换原有的最大值。整个计算是按照索引变量i的递增顺序来进行的。不过，我们注意到，如果以逆序来运行循环，得到的结果（在取整和截断的范围之内）将是完全一样的（我在本章的前面提到过，如果循环能够逆序运行，那么就很可能被并发执行）。如果充分利用所涉及运算符的可结合性，那么你就能实现归约算法的并发版本。将循环迭代分解到可用的线程上，并且计算本地存储中的部分结果（之前示例中的加和以及最大值）。接下来，将每个部分结果融合为总体结果，注意要同步对共享变量的访问。当然，如果你采用OpenMP 或者Intel TBB 来将循环线程化，那么只需使用reduction 语句或者parallel_reduce 算法。

循环体间依赖性
最后一个对编写并发应用程序造成问题的示例被称之为循环体间依赖性（Loop-Carried Dependence）。如果在当前的迭代中需要使用之前迭代的计算结果，那么就会出现这种依赖性。通常，这种情况表现为，在赋值计算的左边和右边都使用了数组中的同一个元素，并且在右边有一个向后引用。显然，这种循环的迭代操作并非是完全独立的。在示例2-9 给出的代码中将更新数组a和b的元素，但在更新a的元素时需要依赖数组b中之前被更新的元素。
示例2-9 ：循环体间依赖性代码
for (k = 5; k < N; k++) {
    b[k] = DoSomething(k);
    a[k] = b[k-5] + MoreStuff(k);
}
如果将这种循环迭代分解为多个任务，那么将需要额外的同步操作以确保后向引用在被用于当前迭代操作的计算时已经被计算出来了。递推是一种特殊的循环体间依赖性，其中后向引用正是前一次迭代。没有任何方法能够有效地将这种循环迭代并发执行，因为在等待后向引用被求解出来时需要耗费大量的同步操作。
例如，如果后向引用跨越了5次迭代（如示例2-9 所示），那么你在将循环迭代分解为块时需要在每个块中包含5次迭代操作。当第一块的第一次迭代操作执行完成后，在第二块中的第一次迭代操作就可以开始执行，这是因为第二块中第一次迭代操作（即第6次迭代）的依赖性已经得到了满足。你可以按照这种方式将循环块和线程链接起来，但需要对代码进行较大的修改并增加必要的同步操作，以确保在每个迭代操作开始执行之前，所有先决依赖性都得到满足。

一些不太常见的循环体间依赖性
在示例2-10 代码中的循环无法并行执行，因为wrap 的值需要从上一次迭代传递到下一次迭代。这种循环体间依赖性并不遵循常见的形式，即包含明显的后向引用，因为后向引用被“隐藏”在wrap 变量中。
示例2-10 ：非典型循环体间依赖性
wrap = a[0] * b[0];
for (i = 1; i < N; i++) {
    c[i] = wrap;
    wrap = a[i] * b[i];
    d[i] = 2 * wrap;
}
幸运的是，你可以对上面这段简单的代码进行重构，在每次循环迭代操作使用wrap 之前首先定义wrap ，这样生成的循环迭代操作就可以并发执行。这是可以实现的，因为你可以只基于循环迭代器变量的值来为wrap 赋正确的值。示例2-11 给出了重构后的代码。
示例2-11 ：修改后的循环体间依赖性
for (i = 1; i < N; i++) {
    wrap = a[i-1] * b[i-1];
    c[i] = wrap;
    wrap = a[i] * b[i];
    d[i] = 2 * wrap;
    }
如果不考虑实现这个循环的一些重复性代码（初始化、递增以及测试循环迭代变量），你将注意到，在修改后的代码中将执行4N条语句，而不是示例2-10 中的3N+1条语句。
将现有的算法改写为某种低效的形式以获得更好的并发性，这有时候是必要的工作。然而，注意也不要与最初的算法相差得太远。很少有高效的串行算法会增加开销（当与之前示例中循环体中的语句数量相比时就可以看到）。

本章将介绍线程化方法中的最后两个主题。第一个主题是分析并发算法在什么情况下能正确地运行，或者至少能够对如何设计一个无错的并发算法有了正确的想法。第二个主题将讨论一些衡量并发代码执行性能的方法。最后，我还将给出一些简短的历史回顾（不必担心--这部分内容很短，它与本书的主题直接相关，而且了解一些来龙去脉总归是有益的）。

在M. Ben-Ari 2006 年撰写的《Principles of Concurrent and Distributed Programming, Second Edition》(Addison-Wesley) 一书中，他定义了一种抽象机制从形式化上验证并发算法的正确性及其他属性。与计算机科学中针对硬件的理论抽象不同的是，Ben-Ari 提出的抽象是专门针对并发程序的执行方式。在这里，我并不想对这种抽象做完整的介绍。
我建议你阅读Ben-Ari 的相关书籍来了解相关的详细内容以及并发算法设计中的其他知识。我在本章中介绍的内容将足以使你了解并发抽象的基本原则和思想以及如何证明并发算法的正确性。
对于那些不想详细了解算法形式化证明的读者来说（以及对于那些想了解但却又不得不重新拿起书本的读者来说），我向你们保证，虽然这是并发算法设计中的关键部分之一，但它或许并不像你想象中的那么糟糕。如果在设计并发算法时花费的努力越多，那么在跟踪一些奇怪错误（例如，某些错误只有在星期四并且日期为质数的日子才会出现）上所花的时间就会越少。这很好地印证了“磨刀不误砍柴工”这句话。
有些并发错误是很浅显的，你可以轻易地避开它们。而有些错误则是复杂的，它们只会在非常罕见和特殊的情况下才会出现。我们是否需要处理这些“罕见的”情况？当然需要。在熟悉了Ben-Ari 提出的方法并且在设计并发算法时反复实践这些方法后，你就更能发现那些被你同事疏忽的特殊情况。此外，在本书后面的章节中，我都将采用Ben-Ari 介绍的技术。因此，如果你没有阅读接下来的内容，那么在后面将很难理解我要讲解的内容。
Ben-Ari 提出的并发抽象的第一个要点是，程序是由多条原子语句（Atomic Statement） 组成的。原子语句是指不能进一步分解为更小指令的语句，它在执行完成之前是不能被中断的。其结果就是，对于某种粒度上的代码来说，操作系统将不能中断该粒度上代码的执行，而是必须等待代码执行完成之后才能对执行原子语句的进程进行相关操作。对于并发抽象来说，我们可以选择不同级别的原子性，包括单条机器指令，单条汇编语句代码，以及单条高级语言源代码。我们应该选择最有意义的，最容易使用的以及最适合于抽象算法的原子执行级别。在大多数情况下都可以选择单行源代码级别。而在少量情况中还可以考虑选择汇编语言级别。
并发抽象的第二个要点是，并发程序是两个或多个线程中原子语句的交替执行（Interleaving）。我发现假设并发算法在单核上执行是更容易分析和理解的。这样在单核处理器上，操作系统将通过某种交替方式将线程换入/换出处理器。然而，要想分析在不同处理器核上并行运行的两个线程之间的临时关系，则需要付出很大的努力，有时候几乎会抵消采用并发执行所带来的收益。
操作系统以一种不确定的方式来调度线程，因此我们既无法预测多个线程中原子语句的准确执行顺序，也无法确保程序在不同的执行过程中将保持相同的顺序。因此，要想证明或者验证并发算法的某些属性（如正确性），我们必须证明这些属性对于两个或多个线程中原子语句的所有交替执行方式来说都是成立的。
如果此时停下来思考一下，你很快会意识到，所需要验证的交替执行方式数量将成几何级数增长。例如，如果有两个线程，T0 和T1 ，每个线程包含两条语句，s1 和s2，那么这些原子语句总共有6种不同的交替执行方式。在图3-1 中给出了这4条原子语句的交替执行方式。

图3-1：2个线程中4条语句的所有交替执行方式

如果在每个线程中包含了3条语句，那么将产生20 种不同的交替执行方式，而如果包含了4条语句，那么将产生70 种不同的交替方式。这还只是2个线程的情况。读者可以想象一下3个、4个或者8个线程的情况。程序员此时应该怎么做？
通常，虽然你会发现许多不同的交替执行方式，但只有其中一些与证明算法是否具备某些属性的过程是相关的。在图3-1 中给出的所有交替执行中，我们只需考虑当线程T1 的s2 语句紧跟在线程T0 的s1 语句之后的情况。包含这种情况的交替执行方式只有一种（左起第5种）。当然，对于那些没有被形式化验证的交替执行方式，你需要有充分的理由来证明可以不用考虑它们。你不能简单地忽略它们，或者因为它们看上去过于烦琐或者困难而不予考虑。
并发抽象的最后一个要点就是，假设某个线程的所有语句肯定会在某次交替执行中被运行。这是并发抽象的公平性属性。当运行多个进程时，操作系统将为每个进程分配一个时间片以在处理器上执行。如果某些进程的执行优先级较低，那么它们被调度到CPU 上执行的频率将低于系统中其他进程的频率。但操作系统是公平的，它最终肯定会为每个线程都分配一定的执行时间。因此，并发抽象遵循的思想是，线程肯定会在某个时刻被调度执行，即使只执行一条原子语句。尽管并发计算的当前状态可能无法使线程完成某种有用的计算，如其他线程的状态可能使某个线程不能中断自旋等待（spin-wait）循环，但这只是算法的一个属性，而并非并发抽象的缺陷。
总的来说，在我们用来验证并发算法是否包含某些属性的Ben-Ari 并发抽象中，共包含了4个要点：
. 程序是由一组原子语句组成的。
. 并发程序是两个或多个线程中原子语句的交替执行。
. 在验证某个并发算法中某些属性是否成立时，必须给出原子语句的所有交替执行方式。
. 在任何一种交替执行中，都不能排除任何一个线程中的语句。
Ben-Ari 在验证并发抽象的属性时采用了更为深入的形式化方式。他展示了如何通过状态图（State Diagram）和（交替执行）场景（Scenario）等工具来形式化验证并发算法的属性。即使你对算法的形式化证明不感兴趣，但我仍然建议你阅读Ben-Ari书中的相关章节（如果不想买书的话，看看是否可以从图书馆中借到），以更为全面地理解如何对并发算法进行验证的思想。
在本章接下来的内容中，我们将介绍并发编程中一个常见问题以及针对该问题的解决方案，从而具体地阐述如何使用这种并发抽象。我会努力给出一种完整的解决方案，但你也会看到，每种解决方案都缺少一些必要的属性。在每次分析算法时，我会使用某种快速并且松散的原子语句粒度。不过，在分析中还是会包含足够详细和严谨的内容来说明，所有算法尝试都有可能由于某些原因而失败，而最终的算法解决方案能够在所有情况中正确运行。

临界区是指并发算法中的一段代码，在这段代码中将访问并且更新一些共享变量。因此，我们要避免在这些共享变量上发生数据竞争。对于共享变量的所有访问，包括读取或者写入，都必须被限制为每次只有一个线程执行临界区中的代码。在本节介绍了互斥（Mutal Exclusion ）属性的一种实现方式，这种方式无须使用在线程模型中定义的各种同步对象或者原语（Primitive ）。我更倾向于用“临界域（Critical Region ）”这个术语来表示这种代码段，因为在Windows 线程库中定义了一种同步对象CRITICAL_SECTION，这个对象可以用来实现临界域中的互斥行为。我将尽可能地避免在这两个术语之间产生混淆。虽然我在介绍这个问题是采用了传统的名字，但在本书的其他部分中将用临界域来表示这种代码段。
这个问题的解决方案必须确保以下两种属性在所有情况下都能成立：
1. 代码必须实现互斥行为。当有一个线程正在临界域中执行时，其他线程将不允许进入该临界域。此外，如果有多个线程同时请求进入临界域并且当前在临界域中没有任何线程在执行，那么只能允许一个线程进入该临界域。
2. 如果一个线程不在临界域中执行，那么该线程不能阻止其他线程进入该临界域。
接下来，我们将逐步给出一些算法，并最终形成一种完善的算法，这种算法也被称之为Dekker 算法。Ben-Ari 用了整整一章的内容来说明如何使用他提出的并发抽象，从最初的构想不断细化直至最终演变为Dekker 算法。他给出的算法过程与我在这里将要给出的算法过程略有差异。
我只考虑两个线程竞争临界域的情况，因为Dekker 算法只适用于两个线程的情况，并且这也有利于问题的简化。其中一个线程将执行ThreadZero() 函数，而另一个线程将执行ThreadOne() 函数。在对这些示例进行分析的过程中，我将把这些线程分别命名为T0 和T1。
在伪码示例中，临界域将通过调用函数CriticalRegionZero 和CriticalRegionOne来表示。假设这两个临界域将访问同一个共享变量，并且必须以互斥的方式执行。当一个线程不在临界域中时，必须执行其他需要完成的计算（OtherStuffZero,OtherStuffOne）。
这个练习的目的并不是要实现一种解决“临界区问题”的方法。我们可以很容易地通过同步对象来限制进入临界域代码的线程数量。我们实现Dekker 算法的目的是为了说明如何通过Ben-Ari 提出的并发抽象来验证并发算法的正确性。

第一次尝试
在示例3-1 中给出了对算法的第一次尝试，该算法将实现进入临界域时的互斥行为。
示例3-1 ：第一次尝试
int threadNumber = 0;

void ThreadZero()
{
    while (TRUE) do {
while (threadNumber == 1) do {} // 自旋等待
        CriticalRegionZero;
        threadNumber = 1;
        OtherStuffZero;
    }
}

void ThreadOne()
{
    while (TRUE) do {
while (threadNumber == 0) do {} // 自旋等待
        CriticalRegionOne;
        threadNumber = 0;
        OtherStuffOne;
    }
}
在第一次尝试中使用了一个全局变量，threadNumber ，这个变量用来表示哪个线程将进入临界域。该全局变量的值初始为0，表示允许T0 首先访问临界域。在进入临界域之前，线程必须首先要查看threadNumber 的值，以判断它自己是否可以进入。如果可以进入，那么该线程将进入临界域，并且在退出时修改threadNumber 的值以允许另一个线程进入。如果threadNumber 的值与线程的标识不匹配，那么该线程将执行自旋等待，直到另一个线程在临界域中执行完毕并且修改threadNumber 的值。
假设这两个线程在单核处理器上执行，并且它们将分别被交换到处理器上执行，那么在示例3-1 的执行顺序可能为如下：
1. T1 到达while 循环。
2. T1 等待，因为threadNumber == 0 。
3. T0 到达while 循环。
4. T0 继续执行，因为threadNumber == 0 。
5. T0 进入到临界域。
6. T0 退出临界域，并且执行threadNumber =1 。
7. T1 进入到临界域。
在这里你可以自行尝试其他交替执行方式。如果T0 首先在CPU 上执行并进入临界域，那么将发生什么情况？当T0 正在执行时，T1 能否获得对临界域的访问权？合上书本（记得放好书签），去吃点东西，在阅读我给出的分析之前首先自己去思考这种情况。
然后回来继续往下读。
如果T0 首先执行，即使它只是在T1 被允许在处理器上执行之前执行了while 循环的起始部分，那么T1 仍然将进入自旋等待循环。事实上，对于任何首先执行T0 ，然后等T0 设置threadNumber 之后再执行T1 的交替执行方式来说，都属于这种情况。在T0 执行了设置共享变量的语句后，T1 将可以访问临界域，而T0 将被阻塞。
于是，互斥行为就得到了保证。每次只有一个线程被允许进入临界域，而另一个线程只有在临界域中的线程执行完成并且将threadNumber 设置为相应的值之后才可以进入临界域。
那么，当T1 进入临界域，执行相关的计算，退出临界域，然后再次需要在T0 进入临界域之前重新进入临界域，将会出现怎样的情况？ 此时T1 将无法重新进入临界域，直到T0 执行完OtherStuffZero ，离开临界域并且重置threadNumber 标志。现在发生的情况是，一个不在临界域中的线程使另一个线程无法进入。这就违背了正确解决方案所必须具备的第2个属性。
在示例3-1 中提出的简单解决方案中，其实是在线程进入和退出临界域上强制施加了一种严格的交替顺序。任何违背这种严格交替方式的线程都会被阻塞，并且必须进入自旋等待，直到另一个线程修改threadNumber 标志的值。如果某个线程在另一个线程完成之前被结束了（例如，由于设计的原因，无论是无意的还是恶意的），那么问题将变得复杂。如果尚未结束的线程尝试进入临界域，而已结束的线程却没有修改threadNumber 标志的值，那么这会造成一个死锁。
这是一种不可接受的状态。让我们来看看在下一次尝试中能否做得更好。

第二次尝试
为了解决“临界区问题”的第一种解决方案中的严格交替执行问题，在第二种解决方案中使用了一个全局标志（每个线程一个），用来表示某个线程是否正在临界域中执行。在示例3-2 中给出了第二次尝试的伪码。
示例3-2 ：第二次尝试
int Thread0inside = 0;
int Thread1inside = 0;

void ThreadZero()
{
    while (TRUE) do {
while (Thread1inside) do {} // 自旋等待
        Thread0inside = 1;
        CriticalRegionZero;
        Thread0inside = 0;
        OtherStuffZero;
    }
}

void ThreadOne()
{
    while (TRUE) do {
        while (Thread0inside) do {}
        Thread1inside = 1;
        CriticalRegionOne;
        Thread1inside = 0;
        OtherStuffOne;
    }
}
与第一次尝试中的代码一样，这两个线程将分别执行两个函数。两个状态标志Thread0inside 和Thread1inside 分别表示相应的线程正在临界域中执行。在进入临界域之前，线程将首先检查另一个线程的状态。如果状态标志表示另一个线程已经在临界域中执行，那么这个尝试进入的线程将执行自旋等待，直到临界域中的线程退出并且重置它的状态标志。如果另一个线程的状态标志表示该线程没有运行临界域中的代码，那么尝试进入临界域的线程将设置它自己的状态标志，执行临界域中的代码，然后在退出时重置这个状态标志以表示它不再位于临界域中。
这种方法解决了严格交替中存在的问题：T1 可以无限次地进入和退出临界域，除非T0 已经位于临界域中。如果某个线程位于临界域中，那么它的状态标志将反映出这种状态，而另一个尝试进入的线程将一直处于临界域之外，直到位于临界域中线程退出并且重置它的状态标志。
当已经有一个线程位于临界域中时，上述算法能够保证互斥行为，但却会出现一种比饥饿（Starvation ）更糟糕的问题，就是该算法无法保证通常情况下的互斥行为。考虑以下线程T0 和T1 之间的交替执行，它很好地说明了两个线程如何能够同时进入到临界域：
1. T0 在while 循环条件中测试Thread1inside 。
2. T0 发现Thread1inside == 0 （条件为FALSE ）。
3. T1 在while 循环条件中测试Thread0inside 。
4. T1 发现Thread0inside == 0 （条件为FALSE ）。
5. T0 进入到临界域。
6. T1 进入到临界域。
上述交替执行方式告诉我们，第二种解决方案无法确保每次只有一个线程位于临界域中。修复这个问题的简单方式之一是，当一个线程执行while 循环测试时，不允许另一个线程访问其while 循环的条件表达式。

第三次尝试
我将第二次尝试中使用的线程称之为“自私的”线程。在进入临界域之前，线程将设置它的状态标志以宣告它正在进入临界域。在两个线程之间的唯一协调就是在进入临界域之前检查另一个线程的状态。在第三次尝试中，我将使用更“有礼貌的”线程，这些线程将考虑其他线程是否有意进入临界域。在示例3-3 中给出了第三次尝试的伪码。
示例3-3 ：第三次尝试
int Thread0WantsToEnter = 0;
int Thread1WantsToEnter = 0;

void ThreadZero()
{
    while (TRUE) do {
        Thread0WantsToEnter = 1;
while (Thread1WantsToEnter) do {} // 自旋等待
    CriticalRegionZero;
    Thread0WantsToEnter = 0;
    OtherStuffZero;
    }
}

void ThreadOne()
{
    while (TRUE) do {
        Thread1WantsToEnter = 1;
        while (Thread0WantsToEnter) do {}
        CriticalRegionOne;
        Thread1WantsToEnter = 0;
        OtherStuffOne;
    }
}
在这次尝试中，每个线程都通过设置相应的标志来宣告自己希望进入临界域。然而，在进入临界域之前，线程将首先判断其他线程是否也希望进入临界域。如果发现另一个线程也希望进入临界域，那么第一个线程将进入自旋等待循环，直到第二个线程执行临界域（满足它进入临界域的请求）并且重置它的标志值。否则，如果发现另一个线程并不打算进入临界域，那么该线程则将进入临界域并且在退出时重置它的标志。
等等，先停一下！这难道不是和第二次尝试一样吗？只不过是换了个名字而已？确实不一样，但我对你有这种想法并不感到吃惊。请回到示例3-2 并仔细观察。在第二次尝试和第三次尝试之间的差异在于，在设置线程自身状态标志和测试另一个线程标志的顺序上有所不同。在第二次尝试中，while 测试是在设置线程的标志之前执行的；在第三次尝试中，while 测试是在设置线程的标志之后进行的。
为了说明该算法的执行过程，假设T1 正在执行OtherStuffOne 。当T0 希望进入临界域时，它首先将Thread0WantsToEnter 设置为1，然后查看Thread1WantsToEnter 的值以判断T1 是否有意进入临界域， 结果T0 将进入临界域。在T1 完成了其他计算并且需要访问临界域时，它将把Thread1WantsToEnter 设置为1，然后查看Thread0WantsToEnter 的值，它发现这个值仍然为1。这将使T1 置入自旋等待循环，直到T0 退出临界域并且将Thread0WantsToEnter 重置为0。

提示
将标志设置为1的情况不仅包括当线程希望进入临界域时，而且还包含当线程正在临界域中执行时。由于线程并不知道这个标志究竟是表示有进入临界域的意愿，还是表示另一个线程当前正在临界域中执行，因此它们必须假设这个标识表示后一种含义，即另一个线程正在临界域中执行。
当一个线程正处于临界域中时，上述算法能确保互斥行为，并且线程可以以任何执行顺序来进入和离开临界域。然而，在这种方式中存在一个问题，我希望你已经发现了这个问题。如果还没有发现，那么可以来看下面的线程执行序列：
1. T0 设置Thread0WantsToEnter =1 。
2. T1 设置Thread1WantsToEnter =1 。
3. T0 在while 循环条件中测试Thread1WantsToEnter 。
4. T0 发现Thread1WantsToEnter == 1 （条件为TRUE ）。
5. T0 执行自旋等待。
6. T1 在while 循环条件中测试Thread0WantsToEnter 。
7. T1 发现Thread0WantsToEnter == 1 （条件为TRUE ）。
8. T1 执行自旋等待。
这种情况使我想起了20 世纪40 、50 年代左右华纳兄弟出版的卡通短片中的两只地鼠，Mac 和Tosh 。这两只地鼠彼此都非常礼貌和谦让。例如，当它们都想穿过一道门时，它们都会侧身让对方先过去。它们会说，“你先过”，“不，还是你先过吧”。
在测试另一个线程是否希望进入临界域之前，线程T0 和T1 可以同时宣告希望进入临界域。在这种情况下，这两个线程都将进入到自旋等待循环，并且永远无法重置标志来使得另一个线程进入临界域。这是一种典型的死锁情况。每个线程都在等待一个永远也不会发生的事件（即另一个线程重置希望进入临界域的标志）。
要避免这种死锁情况，我们必须从一开始就防止形成死锁的4个必要条件（参见下面的“形成死锁的4个必要条件”）中的某一个条件发生。要解决这个问题，我们需要找到某种方式来打破导致这个问题的自旋等待循环。在第4次尝试中将采用这种方法。

形成死锁的4个必要条件
如果要在两个或者多个线程与一组相互要求的资源之间形成死锁，那么必须满足4个条件。在文章“Sequencing tasks in multiprocess systems to avoid deadlocks” (在1970 Eleventh Annual Symposium on Switching and Automata Theory 的会议记录)中，E. G. Coffman, Jr. 和A. Shoshani 等人首先给出了以下4 个条件：
互斥：某个资源要么可用，要么每次被不超过一个的线程持有。
持有和等待：已经持有某些资源的线程试图再持有其他一些资源。
不可抢占：当一个线程持有某个资源时，只有当这个线程主动释放时，该资源才能够由其他线程获得。
循环等待：存在一个线程循环链，其中一些线程请求的资源由循环链中的下一个线程所持有。
要想防止死锁问题的发生，必须打破这4个条件中的某一个。有多种不同的方式都可以防止一个或者多个条件的发生。在介绍操作系统理论的书籍中通常都会对死锁以及如何防止死锁进行讨论。

第4次尝试
在第4次尝试中将采用与前面算法中相同的“礼貌”线程，但它消除了第3次尝试中的“持有并等待”这个死锁条件。在示例3-4 中给出的伪码中消除了两个线程之间的死锁。
示例3-4 ：第4次尝试
int Thread0WantsToEnter = 0;
int Thread1WantsToEnter = 0;

void ThreadZero()
{
    while (TRUE) do {
        Thread0WantsToEnter = 1;
while (Thread1WantsToEnter) do { // 并非一个自旋等待
        Thread0WantsToEnter = 0;
        delay(someRandomCycles);
        Thread0WantsToEnter = 1;
        }
    CriticalRegionZero;
    Thread0WantsToEnter = 0;
    OtherStuffZero;
    }
}

void ThreadOne()
{
    while (TRUE) do {
        Thread1WantsToEnter = 1;
        while (Thread0WantsToEnter) do {
            Thread1WantsToEnter = 0;
            delay(someRandomCycles);
            Thread1WantsToEnter = 1;
        }
        CriticalRegionOne;
        Thread1WantsToEnter = 0;
        OtherStuffOne;
    }
}
和之前算法中一样，当一个线程想要进入临界域时，它将设置相关的愿望标志（Desire Flag），然后判断另一个线程的愿望标志的状态。如果另一个线程并不希望访问临界域，那么该线程将进入临界域。然而，如果另一个线程想要进入临界域（或者已经处于临界域中），那么最初的线程将进入while 循环。这并不像我们在前面看到的只是执行一个自旋循环。相反，while 循环中的一个迭代操作将重置线程的愿望标志，将线程延迟随机数量的指令周期，将愿望标志设置为1，并且在while 条件表达式中将另一个线程的愿望标志状态重置为1。
在经过上述修改后，如果两个线程都首先设置与它们相关的愿望标志，然后再去判断另一个标志的状态，那么线程之间将不会形成死锁。其中一个线程在设置其愿望标志以及发现另一个线程（处于被延迟状态）不希望进入临界域之前，应该获得一个更短的延迟时间。当然，也有可能每个线程在每次的随机延迟时间完全相同，那么这种情况就与第三次尝试中的情况完全相同。然而，发生这种情况的概率，就好像两个赌博转盘每次旋转后都得到相同结果的概率。
与第3次尝试一样，当一个线程正处于临界域中时，这种算法将确保互斥行为，并且线程可以以任何执行顺序来进入和离开临界域。通过使用一种随机的仲裁机制可以避免导致死锁的情况，这种仲裁将决定哪个线程应该获准进入临界域。不过，在这种尝试中仍然包含了一个问题将破坏线程的执行。在以下的线程交替执行方式中说明了这个潜在的问题：
1. T0 进入到临界域。
2. T1 设置Thread1WantsToEnter =1。
3. T1 发现T0 已经处于临界域中。
4. T1 将重置Thread1WantsToEnter = 0, 并且延迟。
5. T0 退出临界域。
6. T0 快速执行OtherStuffZero。
7. T0 访问临界域。
8. T1 设置Thread1WantsToEnter =1。
9. T1 在while 条件表达式中测试Thread0WantsToEnter，并且发现T0 位于临界域中。
10. T1 将重置Thread1WantsToEnter = 0, 并且延迟。
11. T0 退出临界域。
12. T0 快速执行OtherStuffZero。
13. T0 访问临界域。
你能否理解上述交替执行分析？在看到我给出的交替执行方式之前，你是否已经想到了一个线程可能使另一个线程永远都无法进入到临界域？这种行为被称之为饥饿（Starvation）。这种交替执行方式将无休止地进行下去，而T1 将永久地处于饥饿状态。
这是否违背了一个正确解决方案所应具备的属性？不完全是。T1 的这种饥饿和不公平并不是由于T0 导致的，而是由于操作系统的调度方式造成的。虽然我认同在这种算法中发生线程饥饿情况的概率非常小，但却仍然是有可能发生的，因此我们要尽可能地避免这种情况。
当对线程化算法以及算法中线程之间交互的进行分析时，你不能假设算法会在某种特定的速率下执行。在对称多处理器系统（Symnetric Multiprocessor System）中，多个处理器可能并不拥有相同的时钟频率，而未来的多核处理器也可能不会在同一个封装（Package）中包含同构的核。更不要说分配到各个线程的计算量通常是各不相同的。因此，你必须分析多个线程的所有可能交替执行方式，以证明你得到的是一个正确的并发算法。