譯者序
前言
第1章　導(dǎo)論1
1.1　共享對(duì)象和同步2
1.2　一則寓言故事4
1.2.1　互斥協(xié)議的特性6
1.2.2　故事的寓意7
1.3　生產(chǎn)者-消費(fèi)者問(wèn)題7
1.4　讀者-寫者問(wèn)題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)于死鎖的說(shuō)明22
2.5　過(guò)濾鎖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ā)對(duì)象36
3.1　并發(fā)性和正確性36
3.2　串行對(duì)象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　無(wú)等待性48
3.8.2　無(wú)鎖性49
3.8.3　無(wú)阻塞性49
3.8.4　阻塞演進(jìn)條件50
3.8.5　演進(jìn)條件的特征描述50
3.9　評(píng)析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　無(wú)阻塞快照71
4.3.2　無(wú)等待快照73
4.3.3　正確性證明75
4.4　章節(jié)注釋76
4.5　練習(xí)題77
第5章　同步操作原語(yǔ)的相對(duì)能力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　多重賦值對(duì)象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　無(wú)鎖的通用構(gòu)造100
6.4　無(wú)等待的通用構(gòu)造103
6.5　章節(jié)注釋107
6.6　練習(xí)題108
第二部分　應(yīng)用實(shí)踐
第7章　自旋鎖和爭(zhēng)用112
7.1　實(shí)際問(wèn)題的研究112
7.2　易失性字段和原子對(duì)象114
7.3　測(cè)試-設(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　鎖的選擇說(shuō)明138
7.11　章節(jié)注釋138
7.12　練習(xí)題139
第8章　管程和阻塞同步141
8.1　引言141
8.2　管程鎖和條件141
8.2.1　條件142
8.2.2　喚醒丟失的問(wèn)題145
8.3　讀取-寫入鎖146
8.3.1　簡(jiǎn)單的讀取-寫入鎖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　樂(lè)觀同步163
9.7　惰性同步167
9.8　非阻塞同步170
9.9　討論175
9.10　章節(jié)注釋176
9.11　練習(xí)題176
第10章　隊(duì)列、內(nèi)存管理和ABA問(wèn)題178
10.1　引言178
10.2　隊(duì)列179
10.3　有界部分隊(duì)列179
10.4　無(wú)界完全隊(duì)列183
10.5　無(wú)鎖的無(wú)界隊(duì)列184
10.6　內(nèi)存回收和ABA問(wèn)題187
10.6.1　簡(jiǎn)單的同步隊(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　無(wú)鎖的無(wú)界棧196
11.3　消除198
11.4　消除退避棧199
11.4.1　無(wú)鎖交換機(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　衍射樹(shù)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　無(wú)鎖的哈希集249
13.3.1　遞歸有序拆分249
13.3.2　BucketList類252
13.3.3　LockFreeHashSet類253
13.4　開(kāi)放地址哈希集255
13.4.1　布谷鳥(niǎo)哈希算法255
13.4.2　并發(fā)布谷鳥(niǎo)算法257
13.4.3　帶狀并發(fā)布谷鳥(niǎo)哈希算法261
13.4.4　可細(xì)化的并發(fā)布谷鳥(niǎo)哈希算法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　無(wú)鎖的并發(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　基于樹(shù)的有界優(yōu)先級(jí)隊(duì)列287
15.4　基于堆的無(wú)界優(yōu)先級(jí)隊(duì)列290
15.4.1　順序堆290
15.4.2　并發(fā)堆292
15.5　基于跳躍鏈表的無(wú)界優(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　無(wú)界工作竊取雙端隊(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　語(yǔ)義反向屏障348
18.4　組合樹(shù)屏障349
18.5　靜態(tài)樹(shù)屏障352
18.6　終止檢測(cè)屏障353
18.7　章節(jié)注釋356
18.8　練習(xí)題357
第19章　樂(lè)觀主義和手動(dòng)內(nèi)存管理363
19.1　從Java過(guò)渡到C++363
19.2　樂(lè)觀主義和顯式回收364
19.3　保護(hù)掛起的操作365
19.4　用于管理內(nèi)存的對(duì)象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　鎖的問(wèn)題376
20.1.2　明確預(yù)測(cè)的問(wèn)題377
20.1.3　非阻塞算法的問(wèn)題378
20.1.4　可組合性問(wèn)題379
20.1.5　總結(jié)380
20.2　事務(wù)性編程380
20.2.1　事務(wù)性編程示例381
20.3　事務(wù)性編程的硬件支持382
20.3.1　硬件預(yù)測(cè)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