齣版者的話
譯者序
前言
作者簡介
第1章　引言 1
1.1　顯式內存釋放 1
1.2自動動態內存管理 3
1.3　垃圾迴收算法之間的比較 5
1.3.1　安全性 5
1.3.2　吞吐量 5
1.3.3　完整性與及時性 5
1.3.4　停頓時間 6
1.3.5　空間開銷 7
1.3.6　針對特定語言的優化 7
1.3.7　可擴展性與可移植性 8
1.4　性能上的劣勢 8
1.5　實驗方法 8
1.6　術語和符號 10
1.6.1　堆 10
1.6.2　賦值器與迴收器 11
1.6.3　賦值器根 11
1.6.4　引用、域和地址 11
1.6.5　存活性、正確性以及可達性 12
1.6.6　僞代碼 12
1.6.7　分配器 13
1.6.8　賦值器的讀寫操作 13
1.6.9　原子操作 13
1.6.10 集閤、多集閤、序列以及元組 14
第2章　標記–清掃迴收 15
2.1　標記–清掃算法 16
2.2　三色抽象 18
2.3　改進的標記–清掃算法 18
2.4　位圖標記 19
2.5　懶惰清掃 21
2.6　標記過程中的高速緩存不命中問題 24
2.7　需要考慮的問題 25
2.7.1　賦值器開銷 25
2.7.2　吞吐量 26
2.7.3　空間利用率 26
2.7.4　移動，還是不移動 26
第3章　標記–整理迴收 28
3.1　雙指針整理算法 29
3.2　Lisp 2算法 30
3.3　引綫整理算法 32
3.4　單次遍曆算法 34
3.5　需要考慮的問題 36
3.5.1　整理的必要性 36
3.5.2　整理的吞吐量開銷 36
3.5.3　長壽數據 36
3.5.4　局部性 37
3.5.5　標記–整理算法的局限性 37
第4章　復製式迴收 38
4.1　半區復製迴收 38
4.1.1　工作列錶的實現 39
4.1.2　示例 40
4.2　遍曆順序與局部性 42
4.3　需要考慮的問題 46
4.3.1　分配 46
4.3.2　空間與局部性 47
4.3.3　移動對象 48
第5章　引用計數 49
5.1　引用計數算法的優缺點 50
5.2　提升效率 51
5.3　延遲引用計數 52
5.4　閤並引用計數 54
5.5　環狀引用計數 57
5.6　受限域引用計數 61
5.7　需要考慮的問題 62
5.7.1　應用場景 62
5.7.2　高級的解決方案 62
第6章　垃圾迴收器的比較 64
6.1　吞吐量 64
6.2　停頓時間 65
6.3　內存空間 65
6.4　迴收器的實現 66
6.5　自適應係統 66
6.6　統一垃圾迴收理論 67
6.6.1　垃圾迴收的抽象 67
6.6.2　追蹤式垃圾迴收 67
6.6.3　引用計數垃圾迴收 69
第7章　內存分配 72
7.1　順序分配 72
7.2　空閑鏈錶分配 73
7.2.1　首次適應分配 73
7.2.2　循環首次適應分配 75
7.2.3　最佳適應分配 75
7.2.4　空閑鏈錶分配的加速 76
7.3　內存碎片化 77
7.4　分區適應分配 78
7.4.1　內存碎片 79
7.4.2　空間大小分級的填充 79
7.5　分區適應分配與簡單空閑鏈錶分配的結閤 81
7.6　其他需要考慮的問題 81
7.6.1　字節對齊 81
7.6.2　空間大小限製 82
7.6.3　邊界標簽 82
7.6.4　堆可解析性 82
7.6.5　局部性 84
7.6.6　拓展塊保護 84
7.6.7　跨越映射 85
7.7　並發係統中的內存分配 85
7.8　需要考慮的問題 86
第8章　堆內存的劃分 87
8.1　術語 87
8.2　為何要進行分區 87
8.2.1　根據移動性進行分區 87
8.2.2　根據對象大小進行分區 88
8.2.3　為空間進行分區 88
8.2.4　根據類彆進行分區 89
8.2.5　為效益進行分區 89
8.2.6　為縮短停頓時間進行分區 90
8.2.7　為局部性進行分區 90
8.2.8　根據綫程進行分區 90
8.2.9　根據可用性進行分區 91
8.2.10　根據易變性進行分區 91
8.3　如何進行分區 92
8.4　何時進行分區 93
第9章　分代垃圾迴收 95
9.1　示例 95
9.2　時間測量 96
9.3　分代假說 97
9.4　分代與堆布局 97
9.5　多分代 98
9.6　年齡記錄 99
9.6.1　集體提升 99
9.6.2　衰老半區 100
9.6.3　存活對象空間與柔性提升 101
9.7　對程序行為的適應 103
9.7.1　Appel式垃圾迴收 103
9.7.2　基於反饋的對象提升 104
9.8　分代間指針 105
9.8.1　記憶集 106
9.8.2　指針方嚮 106
9.9　空間管理 107
9.10　中年優先迴收 108
9.11　帶式迴收框架 110
9.12　啓發式方法在分代垃圾迴收中的應用 112
9.13　需要考慮的問題 113
9.14　抽象分代垃圾迴收 115
第10章　其他分區策略 117
10.1　大對象空間 117
10.1.1　轉輪迴收器 118
10.1.2　在操作係統支持下的對象移動 119
10.1.3　不包含指針的對象 119
10.2　基於對象拓撲結構的迴收器 119
10.2.1　成熟對象空間的迴收 120
10.2.2　基於對象相關性的迴收 122
10.2.3　綫程本地迴收 123
10.2.4　棧上分配 126
10.2.5　區域推斷 127
10.3　混閤標記–清掃、復製式迴收器 128
10.3.1　Garbage-First迴收 129
10.3.2　Immix迴收以及其他迴收 130
10.3.3　受限內存空間中的復製式迴收 133
10.4　書簽迴收器 134
10.5　超引用計數迴收器 135
10.6　需要考慮的問題 136
第11章　運行時接口 138
11.1　對象分配接口 138
11.1.1　分配過程的加速 141
11.1.2　清零 141
11.2　指針查找 142
11.2.1　保守式指針查找 143
11.2.2　使用帶標簽值進行精確指針查找 144
11.2.3　對象中的精確指針查找 145
11.2.4　全局根中的精確指針查找 147
11.2.5　棧與寄存器中的精確指針查找 147
11.2.6　代碼中的精確指針查找 157
11.2.7　內部指針的處理 158
11.2.8　派生指針的處理 159
11.3　對象錶 159
11.4　來自外部代碼的引用 160
11.5　棧屏障 162
11.6　安全迴收點以及賦值器的掛起 163
11.7　針對代碼的迴收 165
11.8　讀寫屏障 166
11.8.1　讀寫屏障的設計工程學 167
11.8.2　寫屏障的精度 167
11.8.3　哈希錶 169
11.8.4　順序存儲緩衝區 170
11.8.5　溢齣處理 172
11.8.6　卡錶 172
11.8.7　跨越映射 174
11.8.8　匯總卡 176
11.8.9　硬件與虛擬內存技術 176
11.8.10　寫屏障相關技術小結 177
11.8.11　內存塊鏈錶 178
11.9　地址空間管理 179
11.10　虛擬內存頁保護策略的應用 180
11.10.1　二次映射 180
11.10.2　禁止訪問頁的應用 181
11.11　堆大小的選擇 183
11.12　需要考慮的問題 185
第12章　特定語言相關內容 188
12.1　終結 188
12.1.1　何時調用終結方法 189
12.1.2　終結方法應由哪個綫程調用 190
12.1.3　是否允許終結方法彼此之間的並發 190
12.1.4　是否允許終結方法訪問不可達對象 190
12.1.5　何時迴收已終結對象 191
12.1.6　終結方法執行齣錯時應當如何處理 191
12.1.7　終結操作是否需要遵從某種順序 191
12.1.8　終結過程中的競爭問題 192
12.1.9　終結方法與鎖 193
12.1.10　特定語言的終結機製 193
12.1.11　進一步的研究 195
12.2　弱引用 195
12.2.1　其他動因 196
12.2.2　對不同強度指針的支持 196
12.2.3　使用虛對象控製終結順序 199
12.2.4　弱指針置空過程的競爭問題 199
12.2.5　弱指針置空時的通知 199
12.2.6　其他語言中的弱指針 200
12.3　需要考慮的問題 201
第13章　並發算法預備知識 202
13.1　硬件 202
13.1.1　處理器與綫程 202
13.1.2　處理器與內存之間的互聯 203
13.1.3　內存 203
13.1.4　高速緩存 204
13.1.5　高速緩存一緻性 204
13.1.6　高速緩存一緻性對性能的影響示例：自鏇鎖 205
13.2　硬件內存一緻性 207
13.2.1　內存屏障與先於關係 208
13.2.2　內存一緻性模型 209
13.3　硬件原語 209
13.3.1　比較並交換 210
13.3.2　加載鏈接/條件存儲 211
13.3.3　原子算術原語 212
13.3.4　檢測–檢測並設置 213
13.3.5　更加強大的原語 213
13.3.6　原子操作原語的開銷 214
13.4　前進保障 215
13.5　並發算法的符號記法 217
13.6　互斥 218
13.7　工作共享與結束檢測 219
13.8　並發數據結構 224
13.8.1　並發棧 226
13.8.2　基於單鏈錶的並發隊列 228
13.8.3　基於數組的並發隊列 230
13.8.4　支持工作竊取的並發雙端隊列 235
13.9　事務內存 237
13.9.1　何謂事務內存 237
13.9.2　使用事務內存助力垃圾迴收器的實現 239
13.9.3　垃圾迴收機製對事務內存的支持 240
13.10　需要考慮的問題 241
第14章　並行垃圾迴收 242
14.1　是否有足夠多的工作可以並行 243
14.2　負載均衡 243
14.3　同步 245
14.4　並行迴收的分類 245
14.5　並行標記 246
14.6　並行復製 254
14.6.1　以處理器為中心的並行復製 254
14.6.2　以內存為中心的並行復製技術 258
14.7　並行清掃 263
14.8　並行整理 264
14.9　需要考慮的問題 267
14.9.1　術語 267
14.9.2　並行迴收是否值得 267
14.9.3　負載均衡策略 267
14.9.4　並行追蹤 268
14.9.5　低級同步 269
14.9.6　並行清掃與並行整理 270
14.9.7　結束檢測 270
第15章　並發垃圾迴收 271
15.1　並發迴收的正確性 272
15.1.1　三色抽象迴顧 273
15.1.2　對象丟失問題 274
15.1.3　強三色不變式與弱三色不變式 275
15.1.4　迴收精度 276
15.1.5　賦值器顔色 276
15.1.6　新分配對象的顔色 276
15.1.7　基於增量更新的解決方案 277
15.1.8　基於起始快照的解決方案 277
15.2　並發迴收的相關屏障技術 277
15.2.1　灰色賦值器屏障技術 278
15.2.2　黑色賦值器屏障技術 279
15.2.3　屏障技術的完整性 280
15.2.4　並發寫屏障的實現機製 281
15.2.5　單級卡錶 282
15.2.6　兩級卡錶 282
15.2.7　減少迴收工作量的相關策略 282
15.3　需要考慮的問題 283
第16章　並發標記–清掃算法 285
16.1　初始化 285
16.2　結束 287
16.3　分配 287
16.4　標記過程與清掃過程的並發 288
16.5　即時標記 289
16.5.1　即時迴收的寫屏障 290
16.5.2　Doligez-Leroy-Gonthier迴收器 290
16.5.3　Doligez-Leroy-Gonthier迴收器在Java中的應用 292
16.5.4　滑動視圖 292
16.6　抽象並發迴收框架 293
16.6.1　迴收波麵 294
16.6.2　增加追蹤源頭 295
16.6.3　賦值器屏障 295
16.6.4　精度 295
16.6.5　抽象並發迴收器的實例化 296
16.7　需要考慮的問題 296
第17章　並發復製、並發整理算法 298
17.1　主體並發復製：Baker算法 298
17.2　Brooks間接屏障 301
17.3　自刪除讀屏障 301
17.4　副本復製 302
17.5　多版本復製 303
17.6　Sapphire迴收器 306
17.6.1　迴收的各個階段 306
17.6.2　相鄰階段的閤並 311
17.6.3　Volatile域 312
17.7　並發整理算法 312
17.7.1　Compressor迴收器 312
17.7.2　Pauseless迴收器 315
17.8　需要考慮的問題 321
第18章　並發引用計數算法 322
18.1　簡單引用計數算法迴顧 322
18.2　緩衝引用計數 324
18.3　並發環境下的環狀引用計數處理 326
18.4　堆快照的獲取 326
18.5　滑動視圖引用計數 328
18.5.1　麵嚮年齡的迴收 328
18.5.2　算法實現 328
18.5.3　基於滑動視圖的環狀垃圾迴收 331
18.5.4　內存一緻性 331
18.6　需要考慮的問題 332
第19章　實時垃圾迴收 333
19.1　實時係統 333
19.2　實時迴收的調度 334
19.3　基於工作的實時迴收 335
19.3.1　並行、並發副本迴收 335
19.3.2　非均勻工作負載的影響 341
19.4　基於間隙的實時迴收 342
19.4.1　迴收工作的調度 346
19.4.2　執行開銷 346
19.4.3　開發者需要提供的信息 347
19.5　基於時間的實時迴收：Metronome迴收器 347
19.5.1　賦值器使用率 348
19.5.2　對可預測性的支持 349
19.5.3　Metronome迴收器的分析 351
19.5.4　魯棒性 355
19.6　多種調度策略的結閤：“稅收與開支” 355
19.6.1　“稅收與開支”調度策略 356
19.6.2　“稅收與開支”調度策略的實現基礎 357
19.7　內存碎片控製 359
19.7.1　Metronome迴收器中的增量整理 360
19.7.2　單處理器上的增量副本復製 361
19.7.3　Stopless迴收器：無鎖垃圾迴收 361
19.7.4　Staccato迴收器：在賦值器無等待前進保障條件下的盡力整理 363
19.7.5　Chicken迴收器：在賦值器無等待前進保障條件下的盡力整理（x86平颱） 365
19.7.6　Clover迴收器：賦值器樂觀無鎖前進保障下的可靠整理 366
19.7.7　Stopless迴收器、Chicken迴收器、Clover迴收器之間的比較 367
19.7.8　離散分配 368
19.8　需要考慮的問題 370
術語錶 372
參考文獻 383
索引 413
· · · · · · (收起)