多處理器編程的藝術(原書第2版)

譯者序
前言
第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評析51
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.7Common2RMW操作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練習題108

第二部分應用實踐
第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章計數、排序和分散式協作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.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並行化分析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.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
參考文獻4

自十年前本書第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節的內容。

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