多處理器編程的藝術（原書第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