本书从原理和实践两个方面全面阐述了多处理器编程的指导原则，包含编制高效的多处理器程序所必备的算法技术。此外，附录提供了采用其他程序设计语言包(如c#、c及c++的pthreads库)进行编程的相关背景知识以及硬件基础知识。
多处理器编程的艺术（修订版）
The Art of Multiprocessor Programming
Revised First Edition
（美） Maurice Herlihy 布朗大学 Nir Shavit 麻省理工学院 著 金海 胡侃(华中科技大学) 译
工业界称为多核的多处理器机器正迅速地渗入计算的各个领域。多处理器编程要求理解新型计算原理、算法及编程工具，至今很少有人能够精通这门编程艺术。
现今，大多数工程技术人员都是通过艰辛的反复实践、求助有经验的朋友来学习多处理器编程技巧。这本最新的权威著作致力于改变这种状况，作者全面阐述了多处理器编程的指导原则，介绍了编制高效的多处理器程序所必备的算法技术。了解本书所涵盖的多处理器编程关键问题将使在校学生以及相关技术人员受益匪浅。
本书特色
本修订版结合2008年第1版出版以来课堂教学和读者反馈的勘误和修改意见，对全书进行了多方面的修订和更新。
循序渐进地讲述共享存储器多线程编程的基础知识。
详细解释当今多处理器硬件对并发程序设计的支持方式。
全面考察主流的并发数据结构及其关键设计要素。
从简单的锁机制到最新的事务内存系统，独立、完整地阐述了同步技术。
给出大量利用Java并发工具包编写的可完全执行的Java实例。
附录提供了采用其他程序设计语言和包（如C#、C及C++的Pthreads库）进行编程的相关背景知识以及硬件基础知识。
作者简介
Maurice Herlihy 哈佛大学的数学学士和麻省理工学院的计算机科学博士，目前为美国布朗大学计算机科学系教授，曾工作于卡内基-梅隆大学和DEC剑桥实验室。他是美国ACM会士，2003年分布式计算领域Dijkstra奖获得者。
Nir Shavit 以色列希伯来大学的计算机科学博士，目前为麻省理工学院电子工程和计算机科学系教授、以色列特拉维夫大学计算机科学系教授。1999~2011年期间，他担任Sun实验室的技术人员。
两位作者在2004年获得了理论计算机领域最高奖——哥德尔奖（G?del Prize），2012年他们共享了分布式计算领域的Edsger W. Dijkstra奖，40多年来他们一起合作，从事并行和分布式计算教学和研发工作。
本书可以作为高年级本科生的教材，也可以作为相关技术人员的参考书。
读者应具备一定的离散数学基础知识，能够理解“大O”符号的含义，以及它在NP完全问题中所起的作用；熟悉计算机系统的基本组成部件，如处理器、线程、高速缓存等；为了能够理解书中的实例，还需要具备初步的Java知识。（在使用这些高级程序设计语言之前，本书阐述了语言的相关特征。）书中提供两个附录以供读者参考：附录A包含程序设计语言的相关知识，附录B给出了多处理器硬件系统结构的相关内容。
本书前三分之一涵盖并发程序设计的基本原理，阐述并发程序设计的编程思想。就像掌握汽车驾驶技术、烹饪食物和品尝鱼子酱一样，并发思维也需要培养，需要适当的努力才能学好。希望立刻动手编程的读者可以跳过这部分的大多数内容，但仍需阅读第2章及第3章的内容，这两章包含了理解本书其他部分所必不可少的基本知识。
在原理部分中，首先讨论了经典的互斥问题（第2章），包括诸如公平性和死锁这样的基本概念，这对于理解并发程序设计的难点尤为重要。然后，结合并发执行和并发设计中可能出现的各种情形和开发环境，给出了并发程序正确性的定义（第3章）。接着，研究了对并发计算至关重要的共享存储器的性质（第4章）。最后，介绍了几种为实现高并发性数据结构而使用的同步原语（第5、6章）。
对于每一位渴望真正掌握多处理器编程艺术的程序设计人员来说，花上一定的时间去解决本书第一部分所提及的问题是很有必要的。虽然这些问题都是理想化的，但它们为编写高效的多处理器程序提供了非常有益的编程思想。尤为重要的是，通过在问题解决中获取的思维方式，能够避免出现那些初次编写并发程序的设计人员普遍易犯的错误。
接下来的三分之二讲述并发程序设计的具体实践。每章都有一个相应主题，阐明一种特定的程序设计模式或者算法技巧。第7章从系统和语言这两个不同的抽象层面，讨论争用及自旋锁的概念，强调了底层系统结构的重要性，指出对于自旋锁性能的理解必须建立在对多处理器层次存储结构充分理解的基础上。第8章涉及等待及管程锁的概念，这是一种常用的同步用语（特别是在Java中）。第16章包括并行性及工作窃取问题，第17章则介绍了障碍技术，这种技术往往在具有并发结构的应用中得以广泛的使用。
其他章节讲述各种类型的并发数据结构。它们均以第9章的概念为基础，因此建议读者在阅读其他章节之前首先阅读第9章的内容。该章采用链表结构来阐明各种类型的同步模式，包括粗粒度锁、细粒度锁及无锁结构。第10章则借助于FIFO队列说明在使用同步原语时可能出现的ABA问题，第11章通过栈描述了一种重要的同步模式—消除，第13章通过哈希映射阐述如何利用固有并行进行算法设计。高效率的并行查找技术则借助于跳表来阐述（第14章），而如何通过降低正确性标准来获得更高的性能则通过优先级队列进行了阐述（第15章）。
最后，第18章介绍了在并发问题的研究中新出现的事务方法，可以确信这种方法在不远的将来会变得越来越重要。
并发性的重要性还没有得到人们的广泛认可。在此，引用《纽约时报》1989年关于IBM PC中新型操作系统的一段评论：
真正的并发（当你唤醒并使用另一个程序时原来的程序仍继续运行）是非常令人振奋的，但对于普通使用者来说用处却很小。您能有几个程序在执行时需要花费数秒甚至更多的时间呢？
致谢
感谢Doug Lea、Michael Scott、Ron Rivest、Tom Corman、Radia Perlman、George Varghese 和Michael Sipser在本书出版过程中所做的努力和给予的帮助。
感谢在本书的起草和修订过程中，向我们提供了大量宝贵意见的所有学生、同事和朋友：Yehuda Afek，Shai Ber，Martin Buchholz，Vladimir Budovsky，Christian Cachin，Cliff Click，Yoav Cohen, Dave Dice，Alexandra Fedorova，Pascal Felber，Christof Fetzer，Shafi Goldwasser，Rachid Guerraoui，Tim Harris，Danny Hendler，Maor Hizkiev，Eric Koskinen，Christos Kozyrakis，Edya Ladan，Doug Lea，Oren Lederman，Pierre Leone，Yossi Lev，Wei Lu，Victor Luchangco，Virendra Marathe，John Mellor-Crummey，Mark Moir，Dan Nussbaum，Kiran Pamnany，Ben Pere，Torvald Riegel，Vijay Saraswat，Bill Scherer，Warren Schudy，Michael Scott，Ori Shalev，Marc Shapiro，Yotam Soen，Ralf Suckow，Seth Syberg，Alex Weiss和Zhenyuan Zhao。同时，也向在这里没有提及的许多朋友表示道歉和感谢。
感谢Mark Moir、Steve Heller和Sun公司的Scalable Synchronization小组成员，他们为本书的撰写提供了巨大的支持和帮助。
感谢提出勘误帮助我们改进本书的所有朋友：Rajeev Alur, Matthew Allen, Karolos Antoniadis, Cristina Basescu, Liran Barsisa, Igor Berman, Konstantin Boudnik, Bjoern Brandenburg, Martin Buchholz, Kyle Cackett, Mario Calha, Michael Champigny, Neill Clift, Eran Cohen, Daniel B. Curtis, Gil Danziger, Venkat Dhinakaran, David Dice, Wan Fokkink, David Fort, Robert P. Goddard, Brian Goetz, Bart Golsteijn, K. Gopinath, Enes Goktas, Jason T. Greene, Dan Grossman, Tim Halloran, Muhammad Amber Hassaan, Matt Hayes, Francis Hools, Ben Horowitz, Barak Itkin, Paulo Janotti, Kyungho Jeon, Ahmed Khademzadeh, Irena Karlinsky, Habib Khan, Omar Khan, Namhyung Kim, Guy Korland, Sergey Kotov, Doug Lea, Yossi Lev, Adam MacBeth, Kevin Marth, Adam Morrison, Adam Weinstock, Mike Maloney, Tim McIver, Sergejs Melderis, Bartosz Milewski, Mark Moir, Adam Morrison, Victor Luchangco, Jose Pedro Oliveira, Dale Parson, Jonathan Perry, Amir Pnueli, Pat Quillen, Binoy Ravindran, Roei Raviv, Sudarshan Raghunathan, Jean-Paul Rigault, Michael Rueppel, Mohamed M. Saad, Assaf Schuster, Marc Shapiro, Nathar Shah, Huang-Ti Shih, Joseph P. Skudlarek, James Stout, Mark Summer.field, Deqing Sun, Seth Syberg, Fuad Tabba, Binil Thomas, John A Trono, Thomas Weibel, Adam Weinstock, Jaeheon Yi, Zhenyuan Zhao, Ruiwen Zuo, Chong Xing。
计算机\硬件
工业界称为多核的多处理器机器正迅速地渗入计算的各个领域。多处理器编程要求理解新型计算原理、算法及编程工具，至今很少有人能够精通这门编程艺术。
现今，大多数工程技术人员都是通过艰辛的反复实践、求助有经验的朋友来学习多处理器编程技巧。这本最新的权威著作致力于改变这种状况，作者全面阐述了多处理器编程的指导原则，介绍了编制高效的多处理器程序所必备的算法技术。了解本书所涵盖的多处理器编程关键问题将使在校学生以及相关技术人员受益匪浅。
本书特点
本修订版结合2008年第1版出版以来课堂教学和读者反馈的勘误和修改意见，对全书进行了多方面的修订和更新。
循序渐进地讲述共享存储器多线程编程的基础知识。
详细解释当今多处理器硬件对并发程序设计的支持方式。
全面考察主流的并发数据结构及其关键设计要素。
从简单的锁机制到最新的事务内存系统，独立、完整地阐述了同步技术。
利用Java并发工具包编写的可完全执行的Java实例。
附录提供了采用其他程序设计语言和包（如C#、C及C++的PThreads库）进行编程的相关背景知识以及硬件基础知识。
（美）Maurice Herlihy 布朗大学 Nir Shavit 麻省理工学院 著：Maurice Herlihy 哈佛大学的数学学士和麻省理工学院的计算机科学博士，目前为美国布朗大学计算机科学系教授，曾工作于卡内基-梅隆大学和DEC剑桥实验室。他是美国ACM会士，2003年分布式计算领域Dijkstra奖获得者。 Nir Shavit 以色列希伯来大学的计算机科学博士，目前为麻省理工学院电子工程和计算机科学系教授、以色列特拉维夫大学计算机科学系教授。1999~2011年期间，他担任Sun实验室的技术人员。 两位作者在2004年获得了理论计算机领域最高奖——哥德尔奖（G?del Prize），2012年他们共享了分布式计算领域的Edsger W. Dijkstra奖，40多年来他们一起合作，从事并行和分布式计算教学和研发工作。 加作者照片，从978-7-111-41233-5的封底复制加978-7-111-41233-5的小封面、ISBN、定价（79.00元）
金海 胡侃 译：暂无简介
每逢我们在多处理器平台上进行编程时，往往会有这么一种感觉：即使已熟练掌握了系统提供的各种同步原语，但所编制的并行程序的实际性能似乎总有些差强人意，并不十分理想。究其原因，问题的根结在于多处理器编程应是一门科学和艺术完美结合的学科。若要在多处理器系统结构上编制出性能良好的并行程序，要求设计者不仅要精通多处理器系统结构、并行算法以及一些系统构建工具，还应能基于一种设计理念，充分发挥个人的想象空间，合理搭配这些知识和资源，从而和谐地构建完整的系统，使设计者能比底层硬件和操作系统“做得更好”。也就是说，在编写多处理器程序时，要能同时从宏观和微观两种角度分析问题，并能在这两种角度之间灵活地转换。
自20世纪中叶第一台通用电子计算机研制成功以来，程序的编制大多是基于顺序计算模型的，程序的执行过程是操作的有序序列。由于顺序计算机能够用图灵机精确地描述，因此顺序计算的编程能在一组易于理解且完备定义的抽象之上进行，而不需要了解底层的细节。近年来，尽管单处理器仍在发展，但由于指令级并行的开发空间正在减少，再加上散热等问题限制了时钟频率的继续提高，所以单处理器发展的速度正在减缓，这最终导致了起源于在单独一个晶片上设计多个内核的多处理器系统结构的出现。多处理器系统结构允许多个处理器执行同一个程序，共享同一程序的代码和地址空间，并利用并行技术来提高计算效率。在这种计算模型中，并发程序的执行可以看做是多个并发线程对一组共享对象的操作序列，为了在这种异步并发环境中获得更好的性能，底层系统结构的细节需要呈现给设计者。
作为一名优秀的程序设计员，在编写多处理器程序之前首先应弄清楚：多处理器计算机的能力和限制是什么；在异步并发计算模型中什么问题是可解决的，什么问题是不可解决的；是什么使得某些问题很难计算，而又使另一些问题容易计算。这要求设计者具备一定的多核并行计算理论基础知识，掌握多处理器系统结构上并发计算模型的可计算性理论及复杂性理论。其次，应掌握基本的多核平台上的并行程序设计技术，包括并行算法、同步原语以及各种多核系统结构。
Maurice Herlihy 教授和 Nir Shavit教授在并发程序设计领域具有很深的造诣，并拥有40年以上一起从事并发程序设计教学的合作经验。他们对多处理器并行程序设计技术做出了巨大的贡献，并因此而成为2004年ACM/EATCS哥德尔奖和2012年分布式计算领域Dijkstra奖的共同获得者。这本由他们合著的专著致力于解决如何采用更好的并行算法来克服多核并发程序并行度低的问题。
Amdahl定律早已明确地告诉我们，从程序本身可获得的并行度是有限的，加速比的提高主要取决于程序中必须增加的串行执行部分，而这部分又往往包含着具有相对较高开销的通信和协作。因此，在多处理器系统结构上，如何提高程序中必须串行部分的并行度，以及降低并行处理器中远程访问的时延是我们目前面临的两大技术挑战。这些问题的有效解决，必须依靠软件技术和硬件技术的改进和发展。本书则侧重于对前一个挑战的研究。
作者先从宏观的抽象角度出发，在一个理想化的共享存储器系统结构中研究各种并行算法的可计算性及正确性。通过对这些经典算法的推理分析，向读者揭示了现代协作范例和并发数据结构中所隐藏的核心思想，使读者学会如何分析饥饿和死锁等微妙的活性问题，深层次地研究现代硬件同步原语所应具有的能力及其特性。随后，从微观的实际角度出发，针对当今主流的多处理器系统结构，设计了一系列完美高效的并行算法及并发数据结构，并对各种算法的效率及其机理进行了分析。所有的设计全部采用Java程序设计语言详细地描述，可以非常容易地将它们扩展到实际应用中。
本书的前6章讲述了多处理器程序设计的原理部分，着重于异步并发环境中的可计算性问题，借助于一个理想化的计算模型来阐述如何描述和证明并行程序的实际执行行为。由于其自身的特点，多处理器程序的正确性要比顺序执行程序的正确性复杂得多，书中为我们展现了一系列不同的辅助论证工具，令人有耳目一新之感。随后的11章阐述了多处理器程序设计的实践部分。由于在多处理器环境中编写程序时，底层系统结构的细节并不像编写顺序程序那样被完全隐藏在一种编程抽象中，因此，本书附录B介绍了多处理器硬件的基础知识。最后的第18章介绍了当今并发问题研究中最先进的事务方法，可以预言这种方法在今后的研究中将会越来越重要。
感谢王振飞博士在本书第13～18章翻译中所做的工作，感谢胡丽婷、袁昊、耿玮、蔡硕、张亮同学在本书翻译的初始资料整理中所给予的帮助。
出版者的话
译者序
前言
教学建议
第1章 引言 1
1.1 共享对象和同步 2
1.2 生活实例 4
1.2.1 互斥特性 6
1.2.2 道德 7
1.3 生产者-消费者问题 7
1.4 读者-写者问题 9
1.5 并行的困境 9
1.6 并行程序设计 11
1.7 本章注释 11
1.8 习题 11
第一部分 原 理
第2章 互斥 14
2.1 时间 14
2.2 临界区 14
2.3 双线程解决方案 16
2.3.1 LockOne类 16
2.3.2 LockTwo类 17
2.3.3 Peterson锁 18
2.4 过滤锁 19
2.5 公平性 21
2.6 Bakery算法 21
2.7 有界时间戳 23
2.8 存储单元数量的下界 25
2.9 本章注释 27
2.10 习题 28
第3章 并发对象 31
3.1 并发性与正确性 31
3.2 顺序对象 33
3.3 静态一致性 34
3.4 顺序一致性 35
3.5 可线性化性 38
3.5.1 可线性化点 38
3.5.2 评析 38
3.6 形式化定义 38
3.6.1 可线性化性 39
3.6.2 可线性化性的复合性 40
3.6.3 非阻塞特性 40
3.7 演进条件 41
3.8 Java存储器模型 43
3.8.1 锁和同步块 44
3.8.2 volatile域 44
3.8.3 final域 44
3.9 评析 45
3.10 本章注释 46
3.11 习题 46
第4章 共享存储器基础 50
4.1 寄存器空间 50
4.2 寄存器构造 54
4.2.1 MRSW安全寄存器 55
4.2.2 MRSW规则布尔寄存器 55
4.2.3 M-值MRSW规则寄存器 56
4.2.4 SRSW原子寄存器 57
4.2.5 MRSW原子寄存器 59
4.2.6 MRMW原子寄存器 60
4.3 原子快照 62
4.3.1 无障碍快照 63
4.3.2 无等待快照 64
4.3.3 正确性证明 66
4.4 本章注释 67
4.5 习题 67
第5章 同步原子操作的相对能力 70
5.1 一致数 70
5.2 原子寄存器 72
5.3 一致性协议 74
5.4 FIFO队列 74
5.5 多重赋值对象 77
5.6 读-改-写操作 79
5.7 Common2 RMW操作 80
5.8 compareAndSet()操作 81
5.9 本章注释 82
5.10 习题 83
第6章 一致性的通用性 87
6.1 引言 87
6.2 通用性 88
6.3 一种通用的无锁构造 88
6.4 一种通用的无等待构造 91
6.5 本章注释 95
6.6 习题 95
第二部分 实 践
第7章 自旋锁与争用 98
7.1 实际问题 98
7.2 测试-设置锁 100
7.3 再论基于TAS的自旋锁 102
7.4 指数后退 102
7.5 队列锁 104
7.5.1 基于数组的锁 104
7.5.2 CLH队列锁 106
7.5.3 MCS队列锁 107
7.6 时限队列锁 110
7.7 复合锁 112
7.8 层次锁 118
7.8.1 层次后退锁 118
7.8.2 层次CLH队列锁 119
7.9 由一个锁管理所有的锁 123
7.10 本章注释 123
7.11 习题 124
第8章 管程和阻塞同步 126
8.1 引言 126
8.2 管程锁和条件 126
8.2.1 条件 127
8.2.2 唤醒丢失问题 130
8.3 读者-写者锁 131
8.3.1 简单的读者-写者锁 131
8.3.2 公平的读者-写者锁 132
8.4 我们的可重入锁 134
8.5 信号量 135
8.6 本章注释 136
8.7 习题 136
第9章 链表：锁的作用 139
9.1 引言 139
9.2 基于链表的集合 140
9.3 并发推理 141
9.4 粗粒度同步 142
9.5 细粒度同步 143
9.6 乐观同步 146
9.7 惰性同步 149
9.8 非阻塞同步 153
9.9 讨论 157
9.10 本章注释 157
9.11 习题 158
第10章 并行队列和ABA问题 159
10.1 引言 159
10.2 队列 160
10.3 部分有界队列 160
10.4 完全无界队列 163
10.5 无锁的无界队列 164
10.6 内存回收和ABA问题 166
10.7 双重数据结构 170
10.8 本章注释 172
10.9 习题 172
第11章 并发栈和消除 174
11.1 引言 174
11.2 无锁的无界栈 174
11.3 消除 176
11.4 后退消除栈 176
11.4.1 无锁交换机 177
11.4.2 消除数组 179
11.5 本章注释 181
11.6 习题 181
第12章 计数、排序和分布式协作 184
12.1 引言 184
12.2 共享计数 184
12.3 软件组合 185
12.3.1 概述 185
12.3.2 一个扩展实例 190
12.3.3 性能和健壮性 191
12.4 静态一致池和计数器 192
12.5 计数网 192
12.5.1 可计数网 193
12.5.2 双调计数网 194
12.5.3 性能和流水线 201
12.6 衍射树 201
12.7 并行排序 204
12.8 排序网 204
12.9 样本排序 207
12.10 分布式协作 208
12.11 本章注释 208
12.12 习题 209
第13章 并发哈希和固有并行 212
13.1 引言 212
13.2 封闭地址哈希集 213
13.2.1 粗粒度哈希集 214
13.2.2 空间分带哈希集 215
13.2.3 细粒度哈希集 217
13.3 无锁哈希集 219
13.3.1 递归有序划分 219
13.3.2 BucketList类 222
13.3.3 LockFreeHashSet
13.4 开放地址哈希集 225
13.4.1 Cuckoo哈希 225
13.4.2 并发Cuckoo哈希 226
13.4.3 空间分带的并发Cuckoo哈希 230
13.4.4 细粒度的并发Cuckoo哈希集 231
13.5 本章注释 233
13.6 习题 234
第14章 跳表和平衡查找 235
14.1 引言 235
14.2 顺序跳表 235
14.3 基于锁的并发跳表 236
14.3.1 简介 236
14.3.2 算法 238
14.4 无锁并发跳表 243
14.4.1 简介 243
14.4.2 算法细节 245
14.5 并发跳表 251
14.6 本章注释 251
14.7 习题 251
第15章 优先级队列 253
15.1 引言 253
15.2 基于数组的有界优先级队列 253
15.3 基于树的有界优先级队列 254
15.4 基于堆的无界优先级队列 256
15.4.1 顺序堆 256
15.4.2 并发堆 258
15.5 基于跳表的无界优先级队列 262
15.6 本章注释 264
15.7 习题 265
第16章 异步执行、调度和工作分配 266
16.1 引言 266
16.2 并行分析 271
16.3 多处理器的实际调度 273
16.4 工作分配 274
16.4.1 工作窃取 275
16.4.2 屈从和多道程序设计 275
16.5 工作窃取双端队列 276
16.5.1 有界工作窃取双端队列 276
16.5.2 无界工作窃取双端队列 279
16.5.3 工作平衡 282
16.6 本章注释 283
16.7 习题 284
第17章 障碍 287
17.1 引言 287
17.2 障碍实现 288
17.3 语义换向障碍 288
17.4 组合树障碍 289
17.5 静态树障碍 291
17.6 终止检测障碍 293
17.7 本章注释 295
17.8 习题 296
第18章 事务内存 302
18.1 引言 302
18.1.1 关于锁的问题 302
18.1.2 关于compareAndSet()的问题 303
18.1.3 关于复合性的问题 304
18.1.4 我们能做什么 305
18.2 事务和原子性 305
18.3 软事务内存 306
18.3.1 事务和事务线程 309
18.3.2 僵尸事务和一致性 310
18.3.3 原子对象 311
18.3.4 如何演进 311
18.3.5 争用管理器 312
18.3.6 原子对象的实现 314
18.3.7 无干扰原子对象 315
18.3.8 基于锁的原子对象 318
18.4 硬事务内存 323
18.4.1 缓存一致性 324
18.4.2 事务缓存一致性 324
18.4.3 改进 325
18.5 本章注释 325
18.6 习题 326
第三部分 附 录
附录A 软件基础 328
附录B 硬件基础 340
参考文献 350
索引 359
