本書由G?del獎(jiǎng)得主領(lǐng)銜撰寫，主要討論共享存儲(chǔ)通信方式下的多處理器并發(fā)程序設(shè)計(jì)。首先介紹基本原理，分析異步并發(fā)環(huán)境中的可計(jì)算問題，包括相關(guān)度量標(biāo)準(zhǔn)和方法。然后開展應(yīng)用實(shí)踐，側(cè)重于并發(fā)程序的性能分析。每一章討論一種特定的并發(fā)數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)模式或算法技巧。第2版對數(shù)據(jù)并行、事務(wù)性編程、存儲(chǔ)管理等內(nèi)容做了重點(diǎn)更新和擴(kuò)充，并采用C++語言重構(gòu)相關(guān)示例，更加關(guān)注底層機(jī)制。本書適合作為高等院校計(jì)算機(jī)相關(guān)專業(yè)的課程教材，也適合作為業(yè)界技術(shù)人員的參考書籍。
譯者序
前言
第1章 導(dǎo)論1
1.1 共享對象和同步2
1.2 一則寓言故事4
1.2.1 互斥協(xié)議的特性6
1.2.2 故事的寓意7
1.3 生產(chǎn)者-消費(fèi)者問題7
1.4 讀者-寫者問題9
1.5 并行化的嚴(yán)酷現(xiàn)實(shí)10
1.6 并行程序設(shè)計(jì)11
1.7 章節(jié)注釋12
1.8 練習(xí)題12
第一部分 基本原理
第2章 互斥16
2.1 時(shí)間和事件16
2.2 臨界區(qū)16
2.3 雙線程解決方案19
2.3.1 LockOne類19
2.3.2 LockTwo類20
2.3.3 彼得森鎖21
2.4 關(guān)于死鎖的說明22
2.5 過濾鎖23
2.6 公平性25
2.7 蘭波特的面包房鎖算法25
2.8 有界時(shí)間戳27
2.9 存儲(chǔ)單元數(shù)量的下界29
2.10 章節(jié)注釋32
2.11 練習(xí)題32
第3章 并發(fā)對象36
3.1 并發(fā)性和正確性36
3.2 串行對象38
3.3 順序一致性39
3.3.1 順序一致性與實(shí)時(shí)次序41
3.3.2 順序一致性是非阻塞的41
3.3.3 可組合性42
3.4 線性一致性43
3.4.1 可線性化點(diǎn)43
3.4.2 線性一致性和順序一致性43
3.5 靜態(tài)一致性44
3.5.1 靜態(tài)一致性的特性44
3.6 形式化定義44
3.6.1 歷史記錄45
3.6.2 線性一致性46
3.6.3 線性一致性滿足可組合性47
3.6.4 線性一致性是非阻塞的47
3.7 內(nèi)存一致性模型47
3.8 演進(jìn)條件48
3.8.1 無等待性48
3.8.2 無鎖性49
3.8.3 無阻塞性49
3.8.4 阻塞演進(jìn)條件50
3.8.5 演進(jìn)條件的特征描述50
3.9 評析51
3.10 章節(jié)注釋52
3.11 練習(xí)題52
第4章 共享存儲(chǔ)器基礎(chǔ)57
4.1 寄存器空間58
4.2 寄存器構(gòu)造62
4.2.1 MRSW安全寄存器63
4.2.2 MRSW常規(guī)布爾寄存器63
4.2.3 MRSW常規(guī)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 章節(jié)注釋76
4.5 練習(xí)題77
第5章 同步操作原語的相對能力80
5.1 共識(shí)數(shù)80
5.1.1 狀態(tài)和價(jià)81
5.2 原子寄存器82
5.3 共識(shí)性協(xié)議84
5.4 FIFO隊(duì)列85
5.5 多重賦值對象87
5.6 讀取-修改-寫入操作90
5.7 Common2 RMW操作91
5.8 compareAndSet操作92
5.9 章節(jié)注釋93
5.10 練習(xí)題94
第6章 共識(shí)性的通用性99
6.1 引言99
6.2 通用性99
6.3 無鎖的通用構(gòu)造100
6.4 無等待的通用構(gòu)造103
6.5 章節(jié)注釋107
6.6 練習(xí)題108
第二部分 應(yīng)用實(shí)踐
第7章 自旋鎖和爭用112
7.1 實(shí)際問題的研究112
7.2 易失性字段和原子對象114
7.3 測試-設(shè)置鎖115
7.4 指數(shù)退避算法117
7.5 隊(duì)列鎖119
7.5.1 基于數(shù)組的鎖119
7.5.2 CLH隊(duì)列鎖121
7.5.3 MCS隊(duì)列鎖123
7.6 時(shí)限隊(duì)列鎖125
7.7 層級(jí)鎖127
7.7.1 層級(jí)退避鎖128
7.7.2 同類群組鎖129
7.7.3 同類群組鎖的實(shí)現(xiàn)130
7.8 復(fù)合鎖132
7.9 線程單獨(dú)運(yùn)行的快速路徑137
7.10 鎖的選擇說明138
7.11 章節(jié)注釋138
7.12 練習(xí)題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 信號(hào)量151
8.6 章節(jié)注釋151
8.7 練習(xí)題152
第9章 鏈表：鎖的作用155
9.1 引言155
9.2 基于鏈表的集合156
9.3 并發(fā)推理157
9.4 粗粒度同步159
9.5 細(xì)粒度同步160
9.6 樂觀同步163
9.7 惰性同步167
9.8 非阻塞同步170
9.9 討論175
9.10 章節(jié)注釋176
9.11 練習(xí)題176
第10章 隊(duì)列、內(nèi)存管理和ABA問題178
10.1 引言178
10.2 隊(duì)列179
10.3 有界部分隊(duì)列179
10.4 無界完全隊(duì)列183
10.5 無鎖的無界隊(duì)列184
10.6 內(nèi)存回收和ABA問題187
10.6.1 簡單的同步隊(duì)列190
10.7 雙重?cái)?shù)據(jù)結(jié)構(gòu)192
10.8 章節(jié)注釋194
10.9 練習(xí)題194
第11章 棧和消除196
11.1 引言196
11.2 無鎖的無界棧196
11.3 消除198
11.4 消除退避棧199
11.4.1 無鎖交換機(jī)199
11.4.2 消除數(shù)組201
11.5 章節(jié)注釋204
11.6 練習(xí)題204
第12章 計(jì)數(shù)、排序和分布式協(xié)作208
12.1 引言208
12.2 共享計(jì)數(shù)208
12.3 軟件組合209
12.3.1 概述209
12.3.2 一個(gè)擴(kuò)展的實(shí)例215
12.3.3 性能和健壯性216
12.4 靜態(tài)一致池和計(jì)數(shù)器217
12.5 計(jì)數(shù)網(wǎng)絡(luò)217
12.5.1 可計(jì)數(shù)網(wǎng)絡(luò)218
12.5.2 雙調(diào)計(jì)數(shù)網(wǎng)絡(luò)219
12.5.3 性能和流水線227
12.6 衍射樹228
12.7 并行排序231
12.8 排序網(wǎng)絡(luò)231
12.8.1 設(shè)計(jì)一個(gè)排序網(wǎng)絡(luò)232
12.9 樣本排序234
12.10 分布式協(xié)作235
12.11 章節(jié)注釋236
12.12 練習(xí)題237
第13章 并發(fā)哈希和固有并行240
13.1 引言240
13.2 封閉地址哈希集241
13.2.1 粗粒度哈希集243
13.2.2 帶狀哈希集244
13.2.3 可細(xì)化的哈希集246
13.3 無鎖的哈希集249
13.3.1 遞歸有序拆分249
13.3.2 BucketList類252
13.3.3 LockFreeHashSet類253
13.4 開放地址哈希集255
13.4.1 布谷鳥哈希算法255
13.4.2 并發(fā)布谷鳥算法257
13.4.3 帶狀并發(fā)布谷鳥哈希算法261
13.4.4 可細(xì)化的并發(fā)布谷鳥哈希算法262
13.5 章節(jié)注釋265
13.6 練習(xí)題265
第14章 跳躍鏈表和平衡查找266
14.1 引言266
14.2 順序跳躍鏈表266
14.3 基于鎖的并發(fā)跳躍鏈表268
14.3.1 概述268
14.3.2 算法269
14.4 無鎖的并發(fā)跳躍鏈表275
14.4.1 概述275
14.4.2 算法277
14.5 并發(fā)跳躍鏈表283
14.6 章節(jié)注釋284
14.7 練習(xí)題284
第15章 優(yōu)先級(jí)隊(duì)列286
15.1 引言286
15.1.1 并發(fā)優(yōu)先級(jí)隊(duì)列286
15.2 基于數(shù)組的有界優(yōu)先級(jí)隊(duì)列286
15.3 基于樹的有界優(yōu)先級(jí)隊(duì)列287
15.4 基于堆的無界優(yōu)先級(jí)隊(duì)列290
15.4.1 順序堆290
15.4.2 并發(fā)堆292
15.5 基于跳躍鏈表的無界優(yōu)先級(jí)隊(duì)列297
15.6 章節(jié)注釋299
15.7 練習(xí)題300
第16章 調(diào)度和工作分配302
16.1 引言302
16.2 并行化分析308
16.3 多處理器的實(shí)際調(diào)度311
16.4 工作分配312
16.4.1 工作竊取312
16.4.2 讓步和多道程序設(shè)計(jì)313
16.5 工作竊取雙端隊(duì)列314
16.5.1 有界工作竊取雙端隊(duì)列314
16.5.2 無界工作竊取雙端隊(duì)列318
16.5.3 工作交易321
16.6 章節(jié)注釋322
16.7 練習(xí)題323
第17章 數(shù)據(jù)并行326
17.1 MapReduce328
17.1.1 MapReduce框架328
17.1.2 基于MapReduce的Word-Count應(yīng)用程序330
17.1.3 基于MapReduce的KMeans應(yīng)用程序331
17.1.4 MapReduce的實(shí)現(xiàn)332
17.2 流計(jì)算334
17.2.1 基于流的WordCount應(yīng)用程序335
17.2.2 基于流的KMeans應(yīng)用程序336
17.2.3 實(shí)現(xiàn)聚合運(yùn)算的并行化338
17.3 章節(jié)注釋340
17.4 練習(xí)題341
第18章 屏障347
18.1 引言347
18.2 屏障的實(shí)現(xiàn)348
18.3 語義反向屏障348
18.4 組合樹屏障349
18.5 靜態(tài)樹屏障352
18.6 終止檢測屏障353
18.7 章節(jié)注釋356
18.8 練習(xí)題357
第19章 樂觀主義和手動(dòng)內(nèi)存管理363
19.1 從Java過渡到C++363
19.2 樂觀主義和顯式回收364
19.3 保護(hù)掛起的操作365
19.4 用于管理內(nèi)存的對象366
19.5 遍歷鏈表367
19.6 風(fēng)險(xiǎn)指針369
19.7 基于周期的內(nèi)存回收372
19.8 章節(jié)注釋374
19.9 練習(xí)題375
第20章 事務(wù)性編程376
20.1 并發(fā)程序設(shè)計(jì)面臨的挑戰(zhàn)376
20.1.1 鎖的問題376
20.1.2 明確預(yù)測的問題377
20.1.3 非阻塞算法的問題378
20.1.4 可組合性問題379
20.1.5 總結(jié)380
20.2 事務(wù)性編程380
20.2.1 事務(wù)性編程示例381
20.3 事務(wù)性編程的硬件支持382
20.3.1 硬件預(yù)測382
20.3.2 基本緩存一致性382
20.3.3 事務(wù)緩存一致性383
20.3.4 硬件支持的局限性384
20.4 事務(wù)性鎖消除384
20.4.1 討論386
20.5 事務(wù)性內(nèi)存387
20.5.1 運(yùn)行時(shí)調(diào)度388
20.5.2 顯式自我中止388
20.6 軟件事務(wù)389
20.6.1 使用所有權(quán)記錄的事務(wù)390
20.6.2 基于值驗(yàn)證的事務(wù)394
20.7 硬件事務(wù)和軟件事務(wù)的有機(jī)結(jié)合396
20.8 事務(wù)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)397
20.9 章節(jié)注釋397
20.10 練習(xí)題398
附錄A 軟件基礎(chǔ)399
附錄B 硬件基礎(chǔ)417
參考文獻(xiàn)428
書單推薦
