多处理器编程的艺术（英文版·原书第2版）

本书由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） 理海大学计算机科学教授。他拥有罗切斯特大学计算机科学博士学位。

PrefaceAcknowledgmentsSuggestedwaystoteachtheartofmultiprocessorprogrammingCHAPTER 1 Introduction .................................... 1 1.1 Sharedobjectsandsynchronization .................... 3 1.2 Afable ......................................... 6 1.2.1 Propertiesofamutualexclusionprotocol .......... 8 1.2.2 Themoral .................................. 9 1.3 Theproducer–consumerproblem...................... 9 1.4 Thereaders–writersproblem ......................... 11 1.5 Theharshrealitiesofparallelization.................... 12 1.6 Parallelprogramming .............................. 14 1.7 Chapternotes..................................... 15 1.8 Exercises........................................ 15 PART 1 Principles CHAPTER2 Mutual exclusion ............................... 21 2.1 Timeandevents................................... 21 2.2 Criticalsections................................... 22 2.3 Two-threadsolutions ............................... 25 2.3.1 TheLockOne class ............................ 25 2.3.2 TheLockTwo class ............................ 26 2.3.3 ThePetersonlock ............................ 27 2.4 Notesondeadlock ................................. 29 2.5 Thefilterlock .................................... 30 2.6 Fairness......................................... 33 2.7 Lamport’sBakeryalgorithm ......................... 34 2.8 Boundedtimestamps ............................... 35 2.9 Lowerboundsonthenumberoflocations ............... 39 2.10Chapternotes..................................... 41 2.11 Exercises........................................ 42 CHAPTER 3 Concurrent objects ............................. 49 3.1 Concurrencyandcorrectness ......................... 49 3.2 Sequentialobjects ................................. 52 3.3 Sequentialconsistency.............................. 53 3.3.1 Sequentialconsistencyversusreal-timeorder ....... 55 3.3.2 Sequentialconsistencyisnonblocking............. 56 3.3.3 Compositionality............................. 57 3.4 Linearizability .................................... 58 3.4.1 Linearizationpoints .......................... 58 3.4.2 Linearizabilityversussequentialconsistency ........ 59 3.5 Quiescentconsistency .............................. 59 3.5.1 Propertiesofquiescentconsistency ............... 60 3.6 Formaldefinitions ................................. 60 3.6.1 Histories ................................... 60 3.6.2 Linearizability............................... 61 3.6.3 Linearizabilityiscompositional.................. 63 3.6.4 Linearizabilityisnonblocking ................... 63 3.7 Memoryconsistencymodels ......................... 64 3.8 Progressconditions ................................ 64 3.8.1 Wait-freedom ............................... 65 3.8.2 Lock-freedom ............................... 65 3.8.3 Obstruction-freedom .......................... 66 3.8.4 Blockingprogressconditions ................... 67 3.8.5 Characterizingprogressconditions ............... 67 3.9 Remarks ........................................ 68 3.10 Chapternotes..................................... 69 3.11 Exercises........................................ 70 CHAPTER 4 Foundations of shared memory ................. 75 4.1 Thespaceofregisters .............................. 76 4.2 Registerconstructions .............................. 81 4.2.1 SafeMRSWregisters ......................... 82 4.2.2 AregularBooleanMRSWregister ............... 83 4.2.3 AregularM-valuedMRSWregister .............. 84 4.2.4 AnatomicSRSWregister ...................... 85 4.2.5 AnatomicMRSWregister ..................... 87 4.2.6 AnatomicMRMWregister..................... 90 4.3 Atomicsnapshots ................................. 92 4.3.1 Anobstruction-freesnapshot.................... 92 4.3.2