莫裡斯·赫利希（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） 理海大學計算機科學教授。他擁有羅切斯特大學計算機科學博士學位。

譯者序
前言
第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.1LockOne類19
2.3.2LockTwo類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
3.10章節注釋52
3.11練習題52
第4章共享存儲器基礎57
4.1寄存器空間58
4.2寄存器構造62
4.2.1MRSW安全寄存器63
4.2.2MRSW常規布爾寄存器63
4.2.3MRSW常規M-值寄存器64
4.2.4SRSW原子寄存器65
4.2.5MRSW原子寄存器67
4.2.6MRMW原子寄存器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.4FIFO隊列85
5.5多重賦值對像87
5.6讀取-修改-寫入操作90
5.7Common2 RMW操作91
5.8compareAndSet操作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練習題1
第二部分應用實踐
第7章自旋鎖和爭用112
7.1實際問題的研究112
7.2易失性字段和原子對像114
7.3測試-設置鎖115
7.4指數退避算法117
7.5隊列鎖119
7.5.1基於數組的鎖119
7.5.2CLH隊列鎖121
7.5.3MCS隊列鎖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章計數、排序和分布式協作
12.1引言
12.2共享計數
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.2BucketList類252
13.3.3LockFreeHashSet類253
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並行化分析3
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.1MapReduce328
17.1.1MapReduce框架328
17.1.2基於MapReduce的Word-Count應用程序330
17.1.3基於MapReduce的KMeans應用程序331
17.1.4MapReduce的實現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

自十年前本書第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章上。後，對於授課內容，教師當然應該考慮學生的興趣和背景。