齣版者的話
譯者序
前言
教學建議
第1章 引言 1
1.1 共享對象和同步 2
1.2 生活實例 4
1.2.1 互斥特性 6
1.2.2 道德 7
1.3 生産者-消費者問題 7
1.4 讀者-寫者問題 9
1.5 並行的睏境 9
1.6 並行程序設計 11
1.7 本章注釋 11
1.8 習題 11
第一部分 原 理
第2章 互斥 14
2.1 時間 14
2.2 臨界區 14
2.3 雙綫程解決方案 16
2.3.1 LockOne類 16
2.3.2 LockTwo類 17
2.3.3 Peterson鎖 18
2.4 過濾鎖 19
2.5 公平性 21
2.6 Bakery算法 21
2.7 有界時間戳 23
2.8 存儲單元數量的下界 25
2.9 本章注釋 27
2.10 習題 28
第3章 並發對象 31
3.1 並發性與正確性 31
3.2 順序對象 33
3.3 靜態一緻性 34
3.4 順序一緻性 35
3.5 可綫性化性 38
3.5.1 可綫性化點 38
3.5.2 評析 38
3.6 形式化定義 38
3.6.1 可綫性化性 39
3.6.2 可綫性化性的復閤性 40
3.6.3 非阻塞特性 40
3.7 演進條件 41
3.8 Java存儲器模型 43
3.8.1 鎖和同步塊 44
3.8.2 volatile域 44
3.8.3 final域 44
3.9 評析 45
3.10 本章注釋 46
3.11 習題 46
第4章 共享存儲器基礎 50
4.1 寄存器空間 50
4.2 寄存器構造 54
4.2.1 MRSW安全寄存器 55
4.2.2 MRSW規則布爾寄存器 55
4.2.3 M-值MRSW規則寄存器 56
4.2.4 SRSW原子寄存器 57
4.2.5 MRSW原子寄存器 59
4.2.6 MRMW原子寄存器 60
4.3 原子快照 62
4.3.1 無障礙快照 63
4.3.2 無等待快照 64
4.3.3 正確性證明 66
4.4 本章注釋 67
4.5 習題 67
第5章 同步原子操作的相對能力 70
5.1 一緻數 70
5.2 原子寄存器 72
5.3 一緻性協議 74
5.4 FIFO隊列 74
5.5 多重賦值對象 77
5.6 讀-改-寫操作 79
5.7 Common2 RMW操作 80
5.8 compareAndSet()操作 81
5.9 本章注釋 82
5.10 習題 83
第6章 一緻性的通用性 87
6.1 引言 87
6.2 通用性 88
6.3 一種通用的無鎖構造 88
6.4 一種通用的無等待構造 91
6.5 本章注釋 95
6.6 習題 95
第二部分 實 踐
第7章 自鏇鎖與爭用 98
7.1 實際問題 98
7.2 測試-設置鎖 100
7.3 再論基於TAS的自鏇鎖 102
7.4 指數後退 102
7.5 隊列鎖 104
7.5.1 基於數組的鎖 104
7.5.2 CLH隊列鎖 106
7.5.3 MCS隊列鎖 107
7.6 時限隊列鎖 110
7.7 復閤鎖 112
7.8 層次鎖 118
7.8.1 層次後退鎖 118
7.8.2 層次CLH隊列鎖 119
7.9 由一個鎖管理所有的鎖 123
7.10 本章注釋 123
7.11 習題 124
第8章 管程和阻塞同步 126
8.1 引言 126
8.2 管程鎖和條件 126
8.2.1 條件 127
8.2.2 喚醒丟失問題 130
8.3 讀者-寫者鎖 131
8.3.1 簡單的讀者-寫者鎖 131
8.3.2 公平的讀者-寫者鎖 132
8.4 我們的可重入鎖 134
8.5 信號量 135
8.6 本章注釋 136
8.7 習題 136
第9章 鏈錶：鎖的作用 139
9.1 引言 139
9.2 基於鏈錶的集閤 140
9.3 並發推理 141
9.4 粗粒度同步 142
9.5 細粒度同步 143
9.6 樂觀同步 146
9.7 惰性同步 149
9.8 非阻塞同步 153
9.9 討論 157
9.10 本章注釋 157
9.11 習題 158
第10章 並行隊列和ABA問題 159
10.1 引言 159
10.2 隊列 160
10.3 部分有界隊列 160
10.4 完全無界隊列 163
10.5 無鎖的無界隊列 164
10.6 內存迴收和ABA問題 166
10.7 雙重數據結構 170
10.8 本章注釋 172
10.9 習題 172
第11章 並發棧和消除 174
11.1 引言 174
11.2 無鎖的無界棧 174
11.3 消除 176
11.4 後退消除棧 176
11.4.1 無鎖交換機 177
11.4.2 消除數組 179
11.5 本章注釋 181
11.6 習題 181
第12章 計數、排序和分布式協作 184
12.1 引言 184
12.2 共享計數 184
12.3 軟件組閤 185
12.3.1 概述 185
12.3.2 一個擴展實例 190
12.3.3 性能和健壯性 191
12.4 靜態一緻池和計數器 192
12.5 計數網 192
12.5.1 可計數網 193
12.5.2 雙調計數網 194
12.5.3 性能和流水綫 201
12.6 衍射樹 201
12.7 並行排序 204
12.8 排序網 204
12.9 樣本排序 207
12.10 分布式協作 208
12.11 本章注釋 208
12.12 習題 209
第13章 並發哈希和固有並行 212
13.1 引言 212
13.2 封閉地址哈希集 213
13.2.1 粗粒度哈希集 214
13.2.2 空間分帶哈希集 215
13.2.3 細粒度哈希集 217
13.3 無鎖哈希集 219
13.3.1 遞歸有序劃分 219
13.3.2 BucketList類 222
13.3.3 LockFreeHashSet<T>類 223
13.4 開放地址哈希集 225
13.4.1 Cuckoo哈希 225
13.4.2 並發Cuckoo哈希 226
13.4.3 空間分帶的並發Cuckoo哈希 230
13.4.4 細粒度的並發Cuckoo哈希集 231
13.5 本章注釋 233
13.6 習題 234
第14章 跳錶和平衡查找 235
14.1 引言 235
14.2 順序跳錶 235
14.3 基於鎖的並發跳錶 236
14.3.1 簡介 236
14.3.2 算法 238
14.4 無鎖並發跳錶 243
14.4.1 簡介 243
14.4.2 算法細節 245
14.5 並發跳錶 251
14.6 本章注釋 251
14.7 習題 251
第15章 優先級隊列 253
15.1 引言 253
15.2 基於數組的有界優先級隊列 253
15.3 基於樹的有界優先級隊列 254
15.4 基於堆的無界優先級隊列 256
15.4.1 順序堆 256
15.4.2 並發堆 258
15.5 基於跳錶的無界優先級隊列 262
15.6 本章注釋 264
15.7 習題 265
第16章 異步執行、調度和工作分配 266
16.1 引言 266
16.2 並行分析 271
16.3 多處理器的實際調度 273
16.4 工作分配 274
16.4.1 工作竊取 275
16.4.2 屈從和多道程序設計 275
16.5 工作竊取雙端隊列 276
16.5.1 有界工作竊取雙端隊列 276
16.5.2 無界工作竊取雙端隊列 279
16.5.3 工作平衡 282
16.6 本章注釋 283
16.7 習題 284
第17章 障礙 287
17.1 引言 287
17.2 障礙實現 288
17.3 語義換嚮障礙 288
17.4 組閤樹障礙 289
17.5 靜態樹障礙 291
17.6 終止檢測障礙 293
17.7 本章注釋 295
17.8 習題 296
第18章 事務內存 302
18.1 引言 302
18.1.1 關於鎖的問題 302
18.1.2 關於compareAndSet()的問題 303
18.1.3 關於復閤性的問題 304
18.1.4 我們能做什麼 305
18.2 事務和原子性 305
18.3 軟事務內存 306
18.3.1 事務和事務綫程 309
18.3.2 僵屍事務和一緻性 310
18.3.3 原子對象 311
18.3.4 如何演進 311
18.3.5 爭用管理器 312
18.3.6 原子對象的實現 314
18.3.7 無乾擾原子對象 315
18.3.8 基於鎖的原子對象 318
18.4 硬事務內存 323
18.4.1 緩存一緻性 324
18.4.2 事務緩存一緻性 324
18.4.3 改進 325
18.5 本章注釋 325
18.6 習題 326
第三部分 附 錄
附錄A 軟件基礎 328
附錄B 硬件基礎 340
參考文獻 350
索引 359
· · · · · · (收起)