本书由G?del奖得主领衔撰写，主要讨论共享存储通信方式下的多处理器并发程序设计。首先介绍基本原理，分析异步并发环境中的可计算问题，包括相关度量标准和方法。然后开展应用实践，侧重于并发程序的性能分析。每一章讨论一种特定的并发数据结构、程序设计模式或算法技巧。第2版对数据并行、事务性编程、存储管理等内容做了重点更新和扩充，并采用C++语言重构相关示例，更加关注底层机制。本书适合作为高等院校计算机相关专业的课程教材，也适合作为业界技术人员的参考书籍。

莫里斯·赫利希（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） 理海大学计算机科学教授。他拥有罗切斯特大学计算机科学博士学位。

译者序<br/>前言<br/>第1章　导论1<br/>1.1　共享对象和同步2<br/>1.2　一则寓言故事4<br/>1.2.1　互斥协议的特性6<br/>1.2.2　故事的寓意7<br/>1.3　生产者-消费者问题7<br/>1.4　读者-写者问题9<br/>1.5　并行化的严酷现实10<br/>1.6　并行程序设计11<br/>1.7　章节注释12<br/>1.8　练习题12<br/>第一部分　基本原理<br/>第2章　互斥16<br/>2.1　时间和事件16<br/>2.2　临界区16<br/>2.3　双线程解决方案19<br/>2.3.1　LockOne类19<br/>2.3.2　LockTwo类20<br/>2.3.3　彼得森锁21<br/>2.4　关于死锁的说明22<br/>2.5　过滤锁23<br/>2.6　公平性25<br/>2.7　兰波特的面包房锁算法25<br/>2.8　有界时间戳27<br/>2.9　存储单元数量的下界29<br/>2.10　章节注释32<br/>2.11　练习题32<br/>第3章　并发对象36<br/>3.1　并发性和正确性36<br/>3.2　串行对象38<br/>3.3　顺序一致性39<br/>3.3.1　顺序一致性与实时次序41<br/>3.3.2　顺序一致性是非阻塞的41<br/>3.3.3　可组合性42<br/>3.4　线性一致性43<br/>3.4.1　可线性化点43<br/>3.4.2　线性一致性和顺序一致性43<br/>3.5　静态一致性44<br/>3.5.1　静态一致性的特性44<br/>3.6　形式化定义44<br/>3.6.1　历史记录45<br/>3.6.2　线性一致性46<br/>3.6.3　线性一致性满足可组合性47<br/>3.6.4　线性一致性是非阻塞的47<br/>3.7　内存一致性模型47<br/>3.8　演进条件48<br/>3.8.1　无等待性48<br/>3.8.2　无锁性49<br/>3.8.3　无阻塞性49<br/>3.8.4　阻塞演进条件50<br/>3.8.5　演进条件的特征描述50<br/>3.9　评析51<br/>3.10　章节注释52<br/>3.11　练习题52<br/>第4章　共享存储器基础57<br/>4.1　寄存器空间58<br/>4.2　寄存器构造62<br/>4.2.1　MRSW安全寄存器63<br/>4.2.2　MRSW常规布尔寄存器63<br/>4.2.3　MRSW常规M-值寄存器64<br/>4.2.4　SRSW原子寄存器65<br/>4.2.5　MRSW原子寄存器67<br/>4.2.6　MRMW原子寄存器69<br/>4.3　原子快照71<br/>4.3.1　无阻塞快照71<br/>4.3.2　无等待快照73<br/>4.3.3　正确性证明75<br/>4.4　章节注释76<br/>4.5　练习题77<br/>第5章　同步操作原语的相对能力80<br/>5.1　共识数80<br/>5.1.1　状态和价81<br/>5.2　原子寄存器82<br/>5.3　共识性协议84<br/>5.4　FIFO队列85<br/>5.5　多重赋值对象87<br/>5.6　读取-修改-写入操作90<br/>5.7　Common2 RMW操作91<br/>5.8　compareAndSet操作92<br/>5.9　章节注释93<br/>5.10　练习题94<br/>第6章　共识性的通用性99<br/>6.1　引言99<br/>6.2　通用性99<br/>6.3　无锁的通用构造100<br/>6.4　无等待的通用构造103<br/>6.5　章节注释107<br/>6.6　练习题108<br/>第二部分　应用实践<br/>第7章　自旋锁和争用112<br/>7.1　实际问题的研究112<br/>7.2　易失性字段和原子对象114<br/>7.3　测试-设置锁115<br/>7.4　指数退避算法117<br/>7.5　队列锁119<br/>7.5.1　基于数组的锁119<br/>7.5.2　CLH队列锁121<br/>7.5.3　MCS队列锁123<br/>7.6　时限队列锁125<br/>7.7　层级锁127<br/>7.7.1　层级退避锁128<br/>7.7.2　同类群组锁129<br/>7.7.3　同类群组锁的实现130<br/>7.8　复合锁132<br/>7.9　线程单独运行的快速路径137<br/>7.10　锁的选择说明138<br/>7.11　章节注释138<br/>7.12　练习题139<br/>第8章　管程和阻塞同步141<br/>8.1　引言141<br/>8.2　管程锁和条件141<br/>8.2.1　条件142<br/>8.2.2　唤醒丢失的问题145<br/>8.3　读取-写入锁146<br/>8.3.1　简单的读取-写入锁146<br/>8.3.2　公平的读取-写入锁148<br/>8.4　可重入锁150<br/>8.5　信号量151<br/>8.6　章节注释151<br/>8.7　练习题152<br/>第9章　链表：锁的作用155<br/>9.1　引言155<br/>9.2　基于链表的集合156<br/>9.3　并发推理157<br/>9.4　粗粒度同步159<br/>9.5　细粒度同步160<br/>9.6　乐观同步163<br/>9.7　惰性同步167<br/>9.8　非阻塞同步170<br/>9.9　讨论175<br/>9.10　章节注释176<br/>9.11　练习题176<br/>第10章　队列、内存管理和ABA问题178<br/>10.1　引言178<br/>10.2　队列179<br/>10.3　有界部分队列179<br/>10.4　无界完全队列183<br/>10.5　无锁的无界队列184<br/>10.6　内存回收和ABA问题187<br/>10.6.1　简单的同步队列190<br/>10.7　双重数据结构192<br/>10.8　章节注释194<br/>10.9　练习题194<br/>第11章　栈和消除196<br/>11.1　引言196<br/>11.2　无锁的无界栈196<br/>11.3　消除198<br/>11.4　消除退避栈199<br/>11.4.1　无锁交换机199<br/>11.4.2　消除数组201<br/>11.5　章节注释204<br/>11.6　练习题204<br/>第12章　计数、排序和分布式协作208<br/>12.1　引言208<br/>12.2　共享计数208<br/>12.3　软件组合209<br/>12.3.1　概述209<br/>12.3.2　一个扩展的实例215<br/>12.3.3　性能和健壮性216<br/>12.4　静态一致池和计数器217<br/>12.5　计数网络217<br/>12.5.1　可计数网络218<br/>12.5.2　双调计数网络219<br/>12.5.3　性能和流水线227<br/>12.6　衍射树228<br/>12.7　并行排序231<br/>12.8　排序网络231<br/>12.8.1　设计一个排序网络232<br/>12.9　样本排序234<br/>12.10　分布式协作235<br/>12.11　章节注释236<br/>12.12　练习题237<br/>第13章　并发哈希和固有并行240<br/>13.1　引言240<br/>13.2　封闭地址哈希集241<br/>13.2.1　粗粒度哈希集243<br/>13.2.2　带状哈希集244<br/>13.2.3　可细化的哈希集246<br/>13.3　无锁的哈希集249<br/>13.3.1　递归有序拆分249<br/>13.3.2　BucketList类252<br/>13.3.3　LockFreeHashSet<T>类253<br/>13.4　开放地址哈希集255<br/>13.4.1　布谷鸟哈希算法255<br/>13.4.2　并发布谷鸟算法257<br/>13.4.3　带状并发布谷鸟哈希算法261<br/>13.4.4　可细化的并发布谷鸟哈希算法262<br/>13.5　章节注释265<br/>13.6　练习题265<br/>第14章　跳跃链表和平衡查找266<br/>14.1　引言266<br/>14.2　顺序跳跃链表266<br/>14.3　基于锁的并发跳跃链表268<br/>14.3.1　概述268<br/>14.3.2　算法269<br/>14.4　无锁的并发跳跃链表275<br/>14.4.1　概述275<br/>14.4.2　算法277<br/>14.5　并发跳跃链表283<br/>14.6　章节注释284<br/>14.7　练习题284<br/>第15章　优先级队列286<br/>15.1　引言286<br/>15.1.1　并发优先级队列286<br/>15.2　基于数组的有界优先级队列286<br/>15.3　基于树的有界优先级队列287<br/>15.4　基于堆的无界优先级队列290<br/>15.4.1　顺序堆290<br/>15.4.2　并发堆292<br/>15.5　基于跳跃链表的无界优先级队列297<br/>15.6　章节注释299<br/>15.7　练习题300<br/>第16章　调度和工作分配302<br/>16.1　引言302<br/>16.2　并行化分析308<br/>16.3　多处理器的实际调度311<br/>16.4　工作分配312<br/>16.4.1　工作窃取312<br/>16.4.2　让步和多道程序设计313<br/>16.5　工作窃取双端队列314<br/>16.5.1　有界工作窃取双端队列314<br/>16.5.2　无界工作窃取双端队列318<br/>16.5.3　工作交易321<br/>16.6　章节注释322<br/>16.7　练习题323<br/>第17章　数据并行326<br/>17.1　MapReduce328<br/>17.1.1　MapReduce框架328<br/>17.1.2　基于MapReduce的Word-Count应用程序330<br/>17.1.3　基于MapReduce的KMeans应用程序331<br/>17.1.4　MapReduce的实现332<br/>17.2　流计算334<br/>17.2.1　基于流的WordCount应用程序335<br/>17.2.2　基于流的KMeans应用程序336<br/>17.2.3　实现聚合运算的并行化338<br/>17.3　章节注释340<br/>17.4　练习题341<br/>第18章　屏障347<br/>18.1　引言347<br/>18.2　屏障的实现348<br/>18.3　语义反向屏障348<br/>18.4　组合树屏障349<br/>18.5　静态树屏障352<br/>18.6　终止检测屏障353<br/>18.7　章节注释356<br/>18.8　练习题357<br/>第19章　乐观主义和手动内存管理363<br/>19.1　从Java过渡到C++363<br/>19.2　乐观主义和显式回收364<br/>19.3　保护挂起的操作365<br/>19.4　用于管理内存的对象366<br/>19.5　遍历链表367<br/>19.6　风险指针369<br/>19.7　基于周期的内存回收372<br/>19.8　章节注释374<br/>19.9　练习题375<br/>第20章　事务性编程376<br/>20.1　并发程序设计面临的挑战376<br/>20.1.1　锁的问题376<br/>20.1.2　明确预测的问题377<br/>20.1.3　非阻塞算法的问题378<br/>20.1.4　可组合性问题379<br/>20.1.5　总结380<br/>20.2　事务性编程380<br/>20.2.1　事务性编程示例381<br/>20.3　事务性编程的硬件支持382<br/>20.3.1　硬件预测382<br/>20.3.2　基本缓存一致性382<br/>20.3.3　事务缓存一致性383<br/>20.3.4　硬件支持的局限性384<br/>20.4　事务性锁消除384<br/>20.4.1　讨论386<br/>20.5　事务性内存387<br/>20.5.1　运行时调度388<br/>20.5.2　显式自我中止388<br/>20.6　软件事务389<br/>20.6.1　使用所有权记录的事务390<br/>20.6.2　基于值验证的事务394<br/>20.7　硬件事务和软件事务的有机结合396<br/>20.8　事务数据结构设计397<br/>20.9　章节注释397<br/>20.10　练习题398<br/>附录A　软件基础399<br/>附录B　硬件基础417<br/>参考文献428