多處理器編程的藝術, 2/e (The Art of Multiprocessor Programming, 2/e)

譯者序
前言
第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.1 LockOne類19
2.3.2 LockTwo類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.1 MRSW安全寄存器63
4.2.2 MRSW常規布爾寄存器63
4.2.3 MRSW常規M-值寄存器64
4.2.4 SRSW原子寄存器65
4.2.5 MRSW原子寄存器67
4.2.6 MRMW原子寄存器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.4 FIFO隊列85
5.5 多重賦值對象87
5.6 讀取-修改-寫入操作90
5.7 Common2 RMW操作91
5.8 compareAndSet操作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.2 CLH隊列鎖121
7.5.3 MCS隊列鎖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.2 BucketList類252
13.3.3 LockFreeHashSet<T>類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.1 MapReduce328
17.1.1 MapReduce框架328
17.1.2 基於MapReduce的Word-Count應用程序330
17.1.3 基於MapReduce的KMeans應用程序331
17.1.4 MapReduce的實現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