本书由G?del奖得主领衔撰写，主要讨论共享存储通信方式下的多处理器并发程序设计。首先介绍基本原理，分析异步并发环境中的可计算问题，包括相关度量标准和方法。然后开展应用实践，侧重于并发程序的性能分析。每一章讨论一种特定的并发数据结构、程序设计模式或算法技巧。第2版对数据并行、事务性编程、存储管理等内容做了重点更新和扩充，并采用C++语言重构相关示例，更加关注底层机制。本书适合作为高等院校计算机相关专业的课程教材，也适合作为业界技术人员的参考书籍。
G?del奖得主领衔撰写，被世界各地的大学选作教材
自十年前本书第1版问世以来，已成为世界各地大学的本科生课程和研究生课程的主要教材，同时也成为各种不同规模公司的技术人员的重要参考书。更值得欣慰的是，本书也帮助读者在多处理器程序设计方面进入了新的境界。本书第2版的目标是通过提供新增的章节以及更新的内容来延续这种“良性循环”。我们的目标与第1版相同：为高年级本科生的相关课程提供教材，同时也为技术人员提供相关的参考资料。
章节结构
本书的第一部分涵盖并发程序设计的基本原理，向读者展示如何站在并发程序员的角度思考问题，同时培养读者的基本技能，例如理解各种操作“发生”的时机，考虑所有可能的交互，以及识别可能影响进程演进的障碍。就像许多技能（例如驾驶车辆、烹饪食物或者品鉴鱼子酱）一样，并发思维的能力也需要加以培养，并且可以通过适当的努力来获取。迫不及待想要直接开始程序设计的读者可以跳过第一部分中的大多数内容，但是仍然需要阅读第2章和第3章，因为这两章涵盖了理解本书其余部分所必备的基本知识。
首先我们讨论了经典的互斥（mutual exclusion）问题（第2章）。第2章对于理解并发程序设计所面临的挑战是至关重要的，其中涵盖公平性和死锁等基本概念。其次我们讨论了并发程序正确性的含义（第3章）。我们讨论了几种替代条件，以及在何种情况下可能需要使用哪一种条件。我们还研究了对并发计算至关重要的共享存储（shared memory）的特性（第4章），并讨论为了实现高度并发的数据结构所需要的几种同步原语（第5章和第6章）。
我们认为想要真正掌握多处理器程序设计技术，读者需要花费一定的时间来解决本书第一部分中提出的问题。虽然这些问题都是理想化的，但是读者仍然可以从中提炼出编写高效的多处理器程序所需的思维方式。尤为重要的是，从第一部分中提炼出的思维方式，能帮助几乎所有的新手程序员在初次编写并发程序时引以为鉴，从而避免易犯的常见错误。
本书的第二部分讲述并发程序设计的应用实践。在第二部分的大部分章节中，示例均采用Java语言来实现，因为这样可以避免陷入底层细节的泥潭。然而，在第2版中扩展了这方面的内容，增加了一些对于底层问题的讨论，这些问题对于理解多处理器系统以及有效地进行程序设计是至关重要的。我们将采用C++语言编写的示例来阐述这些底层问题。
第二部分的每一章都包含一个相应的主题，用于阐述一种特定的程序设计模式或者一种算法技巧。第7章阐述自旋锁（spin lock）和争用（contention）的概念，并强调底层体系结构的重要性—只有理解了多处理器内存的层次结构，才能理解自旋锁的性能。第8章阐述管程锁（monitor lock，或称监视器锁、监管锁）和等待（waiting）的概念，这是一种常见的同步模式。
本书许多章节都涉及并发数据结构。第9章阐述链表（linked list）。链表演示了各种不同类型的同步模式，包括粗粒度锁结构、细粒度锁结构以及无锁结构。后续章节均以第9章的概念为基础，因此建议读者阅读第9章的内容后再阅读其后各章节的内容。先进先出（FIFO）队列演示了使用原子同步原语时可能出现的“ABA问题”（第10章），栈（stack）演示了一种称为消除（elimination）的重要同步模式（第11章），哈希映射（hash map，或称散列图、哈希图）演示了如何利用自然并行性实现算法设计（第13章），跳跃链表（skip list，简称跳表）数据结构演示了高效的并行搜索算法（第14章），优先级队列（priority queue）演示了有时降低正确性以提高性能的设计理念（第15章）。
本书还讨论了并发计算中的其他基本问题。第12章讨论了计数和排序，这两个经典问题的并发解决方案有细微的不同。并发程序设计的一项基本技能是将程序分解为可并行化的任务，并组织协调各子任务的执行。本书将讨论实现该目标的几种方法，包括调度和工作分配（第16章）、数据并行（第17章）、屏障（barrier，第18章）、事务性编程（第20章）。并发程序的另一个重要挑战是内存管理，本书将在第19章讨论如何手动回收内存。因为Java语言提供的是自动内存管理，所以本书采用C++语言来阐述这些问题。
第16章以及后续章节大多都是第2版中的新内容：第17章和第19章是全新内容，第16章和第20章与第1版相比有了实质性的更新。尤其需要注意的是，第20章现在包含了事务性编程的硬件原语以及软件策略，并且书中示例均采用C++语言进行了重构，这使我们能够关注较低层的机制。
从理论上而言，理论和实践并没有什么区别。但在实践中，二者存在着重大差异。
虽然这句话的来历尚不明确，但与本书的主题息息相关。为了获得最佳的学习效果，读者必须理论结合实践：将学习书中的概念性内容与真正动手编写实际的多处理器系统程序相结合。
预备知识
第2版所需的预备知识与第1版基本相同。为了理解算法及其性质，读者需要具备一定的离散数学基础知识，能够理解“大O”符号的含义，以及它在NP完全（NP-complete）问题中所起的作用。读者还需要具备一定的数据结构知识，例如栈、队列、列表、平衡树和哈希表等。熟悉基本的计算机体系结构和系统架构（例如处理器、线程和高速缓存）也有助于本书的学习。虽然选修一门关于操作系统或者计算机组成的课程就能满足要求，但两者都不是必需的，很多大学在没有讲解上述预备知识的情况下也成功地使用本书作为教材。
为了更好地理解书中的示例，还要求读者具备初步的Java或者C++知识。在需要深入理解程序设计语言的高级功能或者深入理解硬件时，我们将首先给出相关的解释。有关程序设计语言构造以及多处理器硬件体系结构的更多细节，可以分别参考附录A和附录B。
致谢
感谢我们的同事、学生和朋友在本书编写的过程中提供了指导、意见和建议，包括Yehuda Afek、Shai Ber、Hans Boehm、Martin Buchholz、Vladimir Budovsky、Christian Cachin、Cliff Click、Yoav Cohen、Tom Cormen、Michael Coulombe、Dave Dice、Alexandra Fedorova、Pascal Felber、Christof Fetzer、Rati Gelasvili、Mohsen Ghaffari、Brian Goetz、Shafi Goldwasser、Rachid Guerraoui、Tim Harris、Will Hasenplaugh、Steve Heller、Danny Hendler、Maor Hizkiev、Alex Kogan、Justin Kopinsky、Hank Korth、Eric Koskinen、Christos Kozyrakis、Edya Ladan、Doug Lea、Oren Lederman、Will Leiserson、Pierre Leone、Yossi Lev、Wei Lu、Virendra Marathe、Kevin Marth、Alex Matveev、John Mellor-Crummey、Mark Moir、Adam Morrison、Dan Nussbaum、Roberto Palmieri、Kiran Pamnany、Ben Pere、Radia Perlman、Torvald Riegel、Ron Rivest、Vijay Saraswat、Bill Scherer、Warren Schudy、Michael Scott、Ori Shalev、Marc Shapiro、Michael Sipser、Yotam Soen、Ralf Suckow、Seth Syberg、Joseph Tassarotti、John Tristan、George Varghese、Alex Weiss、Kelly Zhang和Zhenyuan Zhao。同时，也向在这里未提及的朋友表示歉意和感谢。
我们还要感谢许多为改进本书而反馈勘误的读者，包括Matthew Allen、Rajeev Alur、Karolos Antoniadis、Liran Barsisa、Cristina Basescu、Igor Berman、Konstantin Boudnik、Bjoern Brandenburg、Kyle Cackett、Mario Calha、Michael Champigny、Neill Clift、Eran Cohen、Daniel B. Curtis、Gil Danziger、Venkat Dhinakaran、Wan Fokkink、David Fort、Robert P. Goddard、Enes Goktas、Bart Golsteijn、K. Gopinath、Jason T. Greene、Dan Grossman、Tim Halloran、Muhammad Amber Hassaan、Matt Hayes、Francis Hools、Ben Horowitz、Barak Itkin、Paulo Janotti、Kyungho Jeon、Irena Karlinsky、Ahmed Khademzadeh、Habib Khan、Omar Khan、Namhyung Kim、Guy Korland、Sergey Kotov、Jonathan Lawrence、Adam MacBeth、Mike Maloney、Tim McIver、Sergejs Melderis、Bartosz Milewski、Jose Pedro Oliveira、Dale Parson、Jonathan Perry、Amir Pnueli、Pat Quillen、Sudarshan Raghunathan、Binoy Ravindran、Roei Raviv、Jean-Paul Rigault、Michael Rueppel、Mohamed M. Saad、Assaf Schuster、Konrad Schwarz、Nathar Shah、Huang-Ti Shih、Joseph P. Skudlarek、James Stout、Mark Summerfield、Deqing Sun、Fuad Tabba、Binil Thomas、John A Trono、Menno Vermeulen、Thomas Weibel、Adam Weinstock、Chong Xing、Jaeheon Yi和Ruiwen Zuo。
我们还要感谢Beula Christopher、Beth LoGiudice、Steve Merken以及Morgan Kaufmann出版公司的员工，感谢他们在本书出版过程中所给予的耐心和帮助。
教学建议
使用本书的内容进行多处理器程序设计课程的教学时，可以采用以下三种教学方案：
第一种教学方案是面向技术人员的短期课程，侧重于直接应用于解决实际问题的技术。
第二种教学方案是面向非计算机专业学生的课程（比第一种教学方案的课时要长），这类学生期望学习多处理器程序设计的基础知识，以及适用于自己专业领域的实用技术。
第三种教学方案是面向计算机专业学生的课程（课时为一个学期），适用于高年级的本科生或者研究生。
面向技术人员的教学方案
涵盖第1章，强调阿姆达尔定律（Amdahl’s law）及其含义。在第2章中，涵盖2.1节至2.4节以及2.7节，同时涵盖在2.9节中提到的不可解性证明（impossibility proof）的含义。在第3章中，跳过3.5节和3.6节。
涵盖第7章，7.7节、7.8节和7.9节除外。第8章涉及管程和可重入锁，对于一些技术人员而言可能并不陌生。跳过关于信号量描述的8.5节。
涵盖第9章和第10章，10.7节除外。涵盖11.1节和11.2节，跳过11.3节以及其后的内容。跳过第12章。
涵盖第13章和第14章。跳过第15章。涵盖第16章，16.5节除外。第17章是可选章节。在第18章中，讲授18.1节至18.3节。对于专注于C++的技术人员而言，第19章是不可或缺的内容，可以在第9章和10.6节之后讲述。第20章是可选章节。
面向非计算机专业学生的教学方案
涵盖第1章，特别强调阿姆达尔定律及其含义。在第2章中，涵盖2.1节至2.4节以
及2.6节和2.7节，涵盖在2.9节中提到的不可解性证明的含义。在第3章中，跳过3.6节的内容。
涵盖4.1节和4.2节以及第5章的内容。提及共识性的通用性这一知识点，但跳过第6章。
涵盖第7章，7.7节、7.8节和7.9节除外。涵盖第8章。
涵盖第9章和第10章，10.7节除外。涵盖第11章。跳过第12章。
涵盖第13章和第14章。跳过第15章。涵盖第16章和第17章。在第18章中，讲授18.1节至18.3节。对于专注于C++的技术人员来说，第19章是不可或缺的内容，可以在第9章和10.6节之后讲述。在第20章中，涵盖20.1节到20.3节的内容。
面向计算机专业学生的教学方案
本书配套网站（elsevier. com/books-and-journals/book-companion/9780124159501）上的教学幻灯片适用于一个学期的课程。
涵盖第1章和第2章（2.8节可选），以及第3章（3.6节可选）。涵盖第4章、第5章和第6章。在讲述第7章之前，有必要先回顾有关多处理器体系结构的基本知识（附录B）。
涵盖第7章（7.7节、7.8节和7.9节可选）。如果学生不熟悉Java监视器，并且没有学习过操作系统的相关课程，请涵盖第8章。涵盖第9章和第10章（10.7节可选）。涵盖第11章、第12章（12.7节、12.8节、12.9节可选）、第13章、第14章。
本书的其余章节可以根据专业需求进行选择性讲述。对于数学或者计算机科学专业的学生，应该增加讲述第15章以及第16章和第17章。对于数据科学专业的学生，可以跳过第15章，以便重点关注第16章、第17章和第18章。对于计算机工程专业的学生，重点应该放在第18章、第19章和第20章上。最后，对于授课内容，教师当然应该考虑学生的兴趣和背景。
计算机体系结构
本书由G?del奖（理论计算机领域最高荣誉）得主领衔撰写，第1版被世界各地的大学选作教材，同时成为技术人员的重要参考书。第2版紧跟技术趋势，涉及大量前沿研究成果，涵盖当前主流算法，可进一步帮助读者实现或改进并行算法，解决大数据时代的海量计算难题。
本书主要讨论共享存储通信方式下的多处理器并发程序设计。首先介绍基本原理，分析异步并发环境中的可计算问题，包括相关度量标准和方法。然后开展应用实践，侧重于并发程序的性能分析。每一章讨论一种特定的并发数据结构、程序设计模式或算法技巧，深入剖析锁问题，进而将其应用到不同的多处理器系统设计中。
第2版对数据并行、事务性编程、存储管理等内容做了重点更新和扩充，并采用C++语言重构相关示例，更加关注底层机制 。
[美]莫里斯·赫利希(Maurice Herlihy),[美]尼尔·沙维特(Nir Shavit),[美]维克多·卢昌科(Victor Luchangco),[美]迈克尔·斯皮尔(Michael Spear) 著：莫里斯·赫利希（Maurice Herlihy） 布朗大学计算机科学教授，曾任职于卡内基·梅隆大学和DEC公司剑桥实验室。他获得了包括Edsger W. Dijkstra奖（2003，2012）、ACM/EATCS Gödel奖（2004）、IEEE Wallace McDowell奖（2013）和Fulbright杰出讲席（2012）在内的众多荣誉。他是ACM会士，美国国家发明家科学院、美国国家工程院以及美国艺术与科学院院士。他拥有麻省理工学院计算机科学博士学位。
尼尔·沙维特（Nir Shavit） 麻省理工学院计算机科学教授，特拉维夫大学计算机科学教授，曾任职于Sun实验室和Oracle实验室。他与Maurice Herlihy分享了Edsger W. Dijkstra奖（2012）和ACM/EATCS Gödel奖（2004）。他拥有希伯来大学计算机科学博士学位。
维克多·卢昌科（Victor Luchangco） Algorand公司高级算法研究员，曾任职于Sun实验室和Oracle实验室。他拥有麻省理工学院计算机科学博士学位。
迈克尔·斯皮尔（Michael Spear） 理海大学计算机科学教授。他拥有罗切斯特大学计算机科学博士学位。
进入21世纪后，随着摩尔定律50年的统治生涯接近尾声，计算机CPU开始转向“多核”架构。现代处理器芯片都包含多个内核，从而具有强大的并行计算能力。如何充分利用“多核”处理器的并行计算能力来解决大数据时代的计算问题，是计算机科学家面临的挑战，也是广大程序员必须具备的技能和素养。
本书主要介绍共享存储通信方式下的多处理器并发程序设计所涉及的算法。全书分为两大部分。
第一部分包含第2章至第6章，涵盖多处理器并发程序设计的基本原理，讨论异步并发环境中的可计算问题。这一部分介绍了一系列用于分析推理并发程序的度量标准和方法，这些度量标准和方法将为后续章节讨论实际应用中对象和程序的正确性奠定基础。本书有关基本原理的章节将引导读者快速浏览并了解异步可计算性的理论，并尝试揭示各种各样的可计算性问题，以及如何使用硬件机制和软件机制来解决这些问题。
第二部分包含第7章至第20章，涵盖多处理器并发程序设计的应用实践，侧重于并发程序的性能分析。这一部分的每一章都对应一个主题，详细阐述该主题涉及的并发数据结构、程序设计模式，以及相应的算法技巧。借助这些并发数据结构和算法，读者可以充分理解锁涉及的知识和面临的问题，从而能够将学到的知识应用到特定的多处理器系统设计中。本部分主要采用Java程序设计语言提供实现代码，涉及手动存储管理的部分则采用C++语言。
附录A描述了理解本书的示例和编写并发程序所需的基本程序设计语言结构，包括Java、C++和C#。附录B则涵盖了编写高效并发算法和数据结构所需的多处理器体系结构的基本知识。建议读者先阅读附录A和附录B，并在阅读正文时参考附录中的相关内容。
本书提供了大量的练习题，读者可以通过练习题探索如何修改算法以适用于新的场景，从而巩固算法所展示的主要技术。
本书展现了多处理器编程的艺术，涉及大量并行算法的前沿研究成果。建议读者在阅读正文的同时，拓展阅读书后列出的原始参考文献。本书讨论的许多并行算法都是众多主流的程序设计语言（例如Java语言）所提供的算法，理解和掌握书中的理论以及应用，可以帮助读者正确使用程序设计语言所提供的并行算法，进而实现更有效的并行算法，从而解决大数据时代面临的海量计算难题。
本书是一本将理论和实践相结合的多处理器并行算法设计教程，是高年级本科生和研究生相关课程的经典教材，也是技术人员必备的参考资料。
本书由Maurice Herlihy、Nir Shavit、Victor Luchangco和Michael Spear共同撰写。Maurice Herlihy教授和Nir Shavit教授在并行程序设计领域长期从事研究和教学工作，具有很深的造诣，并共同成为2004年ACM/EATCS G?del奖获得者。他们合作的专著已经成为世界各地大学的本科生课程以及研究生课程的主要教材，同时也成为各种不同规模公司的技术人员的重要参考书。
本书由华东师范大学江红、余青松和余靖共同翻译。衷心感谢本书的编辑曲熠，她积极帮助我们筹划翻译事宜并认真审阅翻译稿件。翻译是一种再创造，同样需要艰辛的付出，感谢朋友、家人以及同事的理解和支持。在本书翻译的过程中，我们力求忠于原著，但由于时间和学识有限，且本书涉及各个领域的专业知识，故书中的不足之处在所难免，敬请诸位同行、专家和读者指正。
江红 余青松 余靖
2022年1月
译者序
前言
第1章 导论1
1.1 共享对象和同步2
1.2 一则寓言故事4
1.2.1 互斥协议的特性6
1.2.2 故事的寓意7
1.3 生产者-消费者问题7
1.4 读者-写者问题9
1.5 并行化的严酷现实10
1.6 并行程序设计11
1.7 章节注释12
1.8 练习题12
第一部分 基本原理
第2章 互斥16
2.1 时间和事件16
2.2 临界区16
2.3 双线程解决方案19
2.3.1 LockOne类19
2.3.2 LockTwo类20
2.3.3 彼得森锁21
2.4 关于死锁的说明22
2.5 过滤锁23
2.6 公平性25
2.7 兰波特的面包房锁算法25
2.8 有界时间戳27
2.9 存储单元数量的下界29
2.10 章节注释32
2.11 练习题32
第3章 并发对象36
3.1 并发性和正确性36
3.2 串行对象38
3.3 顺序一致性39
3.3.1 顺序一致性与实时次序41
3.3.2 顺序一致性是非阻塞的41
3.3.3 可组合性42
3.4 线性一致性43
3.4.1 可线性化点43
3.4.2 线性一致性和顺序一致性43
3.5 静态一致性44
3.5.1 静态一致性的特性44
3.6 形式化定义44
3.6.1 历史记录45
3.6.2 线性一致性46
3.6.3 线性一致性满足可组合性47
3.6.4 线性一致性是非阻塞的47
3.7 内存一致性模型47
3.8 演进条件48
3.8.1 无等待性48
3.8.2 无锁性49
3.8.3 无阻塞性49
3.8.4 阻塞演进条件50
3.8.5 演进条件的特征描述50
3.9 评析51
3.10 章节注释52
3.11 练习题52
第4章 共享存储器基础57
4.1 寄存器空间58
4.2 寄存器构造62
4.2.1 MRSW安全寄存器63
4.2.2 MRSW常规布尔寄存器63
4.2.3 MRSW常规M-值寄存器64
4.2.4 SRSW原子寄存器65
4.2.5 MRSW原子寄存器67
4.2.6 MRMW原子寄存器69
4.3 原子快照71
4.3.1 无阻塞快照71
4.3.2 无等待快照73
4.3.3 正确性证明75
4.4 章节注释76
4.5 练习题77
第5章 同步操作原语的相对能力80
5.1 共识数80
5.1.1 状态和价81
5.2 原子寄存器82
5.3 共识性协议84
5.4 FIFO队列85
5.5 多重赋值对象87
5.6 读取-修改-写入操作90
5.7 Common2 RMW操作91
5.8 compareAndSet操作92
5.9 章节注释93
5.10 练习题94
第6章 共识性的通用性99
6.1 引言99
6.2 通用性99
6.3 无锁的通用构造100
6.4 无等待的通用构造103
6.5 章节注释107
6.6 练习题108
第二部分 应用实践
第7章 自旋锁和争用112
7.1 实际问题的研究112
7.2 易失性字段和原子对象114
7.3 测试-设置锁115
7.4 指数退避算法117
7.5 队列锁119
7.5.1 基于数组的锁119
7.5.2 CLH队列锁121
7.5.3 MCS队列锁123
7.6 时限队列锁125
7.7 层级锁127
7.7.1 层级退避锁128
7.7.2 同类群组锁129
7.7.3 同类群组锁的实现130
7.8 复合锁132
7.9 线程单独运行的快速路径137
7.10 锁的选择说明138
7.11 章节注释138
7.12 练习题139
第8章 管程和阻塞同步141
8.1 引言141
8.2 管程锁和条件141
8.2.1 条件142
8.2.2 唤醒丢失的问题145
8.3 读取-写入锁146
8.3.1 简单的读取-写入锁146
8.3.2 公平的读取-写入锁148
8.4 可重入锁150
8.5 信号量151
8.6 章节注释151
8.7 练习题152
第9章 链表：锁的作用155
9.1 引言155
9.2 基于链表的集合156
9.3 并发推理157
9.4 粗粒度同步159
9.5 细粒度同步160
9.6 乐观同步163
9.7 惰性同步167
9.8 非阻塞同步170
9.9 讨论175
9.10 章节注释176
9.11 练习题176
第10章 队列、内存管理和ABA问题178
10.1 引言178
10.2 队列179
10.3 有界部分队列179
10.4 无界完全队列183
10.5 无锁的无界队列184
10.6 内存回收和ABA问题187
10.6.1 简单的同步队列190
10.7 双重数据结构192
10.8 章节注释194
10.9 练习题194
第11章 栈和消除196
11.1 引言196
11.2 无锁的无界栈196
11.3 消除198
11.4 消除退避栈199
11.4.1 无锁交换机199
11.4.2 消除数组201
11.5 章节注释204
11.6 练习题204
第12章 计数、排序和分布式协作208
12.1 引言208
12.2 共享计数208
12.3 软件组合209
12.3.1 概述209
12.3.2 一个扩展的实例215
12.3.3 性能和健壮性216
12.4 静态一致池和计数器217
12.5 计数网络217
12.5.1 可计数网络218
12.5.2 双调计数网络219
12.5.3 性能和流水线227
12.6 衍射树228
12.7 并行排序231
12.8 排序网络231
12.8.1 设计一个排序网络232
12.9 样本排序234
12.10 分布式协作235
12.11 章节注释236
12.12 练习题237
第13章 并发哈希和固有并行240
13.1 引言240
13.2 封闭地址哈希集241
13.2.1 粗粒度哈希集243
13.2.2 带状哈希集244
13.2.3 可细化的哈希集246
13.3 无锁的哈希集249
13.3.1 递归有序拆分249
13.3.2 BucketList类252
13.3.3 LockFreeHashSet
13.4 开放地址哈希集255
13.4.1 布谷鸟哈希算法255
13.4.2 并发布谷鸟算法257
13.4.3 带状并发布谷鸟哈希算法261
13.4.4 可细化的并发布谷鸟哈希算法262
13.5 章节注释265
13.6 练习题265
第14章 跳跃链表和平衡查找266
14.1 引言266
14.2 顺序跳跃链表266
14.3 基于锁的并发跳跃链表268
14.3.1 概述268
14.3.2 算法269
14.4 无锁的并发跳跃链表275
14.4.1 概述275
14.4.2 算法277
14.5 并发跳跃链表283
14.6 章节注释284
14.7 练习题284
第15章 优先级队列286
15.1 引言286
15.1.1 并发优先级队列286
15.2 基于数组的有界优先级队列286
15.3 基于树的有界优先级队列287
15.4 基于堆的无界优先级队列290
15.4.1 顺序堆290
15.4.2 并发堆292
15.5 基于跳跃链表的无界优先级队列297
15.6 章节注释299
15.7 练习题300
第16章 调度和工作分配302
16.1 引言302
16.2 并行化分析308
16.3 多处理器的实际调度311
16.4 工作分配312
16.4.1 工作窃取312
16.4.2 让步和多道程序设计313
16.5 工作窃取双端队列314
16.5.1 有界工作窃取双端队列314
16.5.2 无界工作窃取双端队列318
16.5.3 工作交易321
16.6 章节注释322
16.7 练习题323
第17章 数据并行326
17.1 MapReduce328
17.1.1 MapReduce框架328
17.1.2 基于MapReduce的Word-Count应用程序330
17.1.3 基于MapReduce的KMeans应用程序331
17.1.4 MapReduce的实现332
17.2 流计算334
17.2.1 基于流的WordCount应用程序335
17.2.2 基于流的KMeans应用程序336
17.2.3 实现聚合运算的并行化338
17.3 章节注释340
17.4 练习题341
第18章 屏障347
18.1 引言347
18.2 屏障的实现348
18.3 语义反向屏障348
18.4 组合树屏障349
18.5 静态树屏障352
18.6 终止检测屏障353
18.7 章节注释356
18.8 练习题357
第19章 乐观主义和手动内存管理363
19.1 从Java过渡到C++363
19.2 乐观主义和显式回收364
19.3 保护挂起的操作365
19.4 用于管理内存的对象366
19.5 遍历链表367
19.6 风险指针369
19.7 基于周期的内存回收372
19.8 章节注释374
19.9 练习题375
第20章 事务性编程376
20.1 并发程序设计面临的挑战376
20.1.1 锁的问题376
20.1.2 明确预测的问题377
20.1.3 非阻塞算法的问题378
20.1.4 可组合性问题379
20.1.5 总结380
20.2 事务性编程380
20.2.1 事务性编程示例381
20.3 事务性编程的硬件支持382
20.3.1 硬件预测382
20.3.2 基本缓存一致性382
20.3.3 事务缓存一致性383
20.3.4 硬件支持的局限性384
20.4 事务性锁消除384
20.4.1 讨论386
20.5 事务性内存387
20.5.1 运行时调度388
20.5.2 显式自我中止388
20.6 软件事务389
20.6.1 使用所有权记录的事务390
20.6.2 基于值验证的事务394
20.7 硬件事务和软件事务的有机结合396
20.8 事务数据结构设计397
20.9 章节注释397
20.10 练习题398
附录A 软件基础399
附录B 硬件基础417
参考文献428
