一.資料圖片

二.資料簡(jiǎn)介

在自動(dòng)內(nèi)存管理領(lǐng)域，Richard Jones于1996年出版的《Garbage Collection：Algorithms for Automatic Dynamic Memory Management》可謂是一部里程碑式的作品。接近20年過去了，垃圾回收技術(shù)得到了非常大的發(fā)展，因此有必要將該領(lǐng)域當(dāng)前最先進(jìn)的技術(shù)呈現(xiàn)給讀者。本書匯集了自動(dòng)內(nèi)存管理研究者和開發(fā)者們?cè)谶^去50年間的豐富經(jīng)驗(yàn)，在本書中，作者在一個(gè)統(tǒng)一的易于接受的框架內(nèi)比較了當(dāng)下最重要的回收策略以及最先進(jìn)的回收技術(shù)。

本書從近年來硬件與軟件的發(fā)展給垃圾回收所帶來的新挑戰(zhàn)出發(fā)，探討了這些挑戰(zhàn)給高性能垃圾回收器的設(shè)計(jì)者與實(shí)現(xiàn)者所帶來的影響。在簡(jiǎn)單的傳統(tǒng)回收算法之外，本書還涵蓋了并行垃圾回收、增量式垃圾回收、并發(fā)垃圾回收以及實(shí)時(shí)垃圾回收。書中配備了豐富的偽代碼與插圖，以描述各種算法與概念。

本書特色

為1996年《Garbage Collection：Algorithms for Automatic Dynamic Memory Management》一書提供了完整的、最新的、權(quán)威的續(xù)作。

全面講解并行垃圾回收算法、并發(fā)垃圾回收算法以及實(shí)時(shí)垃圾回收算法。

深入剖析某些垃圾回收領(lǐng)域的棘手問題，包括與運(yùn)行時(shí)系統(tǒng)的接口。

提供在線數(shù)據(jù)庫(kù)支持，包含超過2500條垃圾回收相關(guān)文獻(xiàn)。

三.作者簡(jiǎn)介

理查德·瓊斯（Richard Jones）

坎特伯雷-肯特大學(xué)計(jì)算機(jī)學(xué)院教授。1998年聯(lián)合創(chuàng)立了國(guó)際存儲(chǔ)管理研討會(huì)，并擔(dān)任*屆會(huì)議主席。他發(fā)表了多篇關(guān)于垃圾回收技術(shù)、堆可視化技術(shù)、電子出版技術(shù)相關(guān)的論文，多次擔(dān)任主要國(guó)際會(huì)議計(jì)劃委員會(huì)的常務(wù)委員，同時(shí)還是《Software Practice and Experience》雜志的編輯委員會(huì)成員。因在動(dòng)態(tài)存儲(chǔ)管理領(lǐng)域的研究和學(xué)術(shù)成績(jī)，他于2005年被聘任為格拉斯哥大學(xué)名譽(yù)研究員，2006年被計(jì)算機(jī)協(xié)會(huì)評(píng)為杰出科學(xué)家。

安東尼·霍思金（Antony Hosking）

普渡大學(xué)西拉法葉分校計(jì)算機(jī)學(xué)院副教授。他的主要研究方向是編程語(yǔ)言的設(shè)計(jì)與實(shí)現(xiàn)，特別是數(shù)據(jù)庫(kù)與持久化編程語(yǔ)言、面向?qū)ο髷?shù)據(jù)庫(kù)系統(tǒng)、動(dòng)態(tài)存儲(chǔ)管理、編譯器優(yōu)化以及編程語(yǔ)言和應(yīng)用的架構(gòu)支持。

艾略特·莫斯（Eliot Moss）

馬薩諸塞大學(xué)阿默斯特分校計(jì)算機(jī)科學(xué)學(xué)院教授。他的主要研究方向?yàn)榫幊陶Z(yǔ)言及其實(shí)現(xiàn)，而且早在1978年就構(gòu)建出垃圾回收器。除了自動(dòng)存儲(chǔ)管理領(lǐng)域之外，他在持久編程語(yǔ)言、虛擬機(jī)實(shí)現(xiàn)、事務(wù)性編程與事務(wù)內(nèi)存方面也擁有較高的知名度。他曾與IBM研究員一起推動(dòng)Jikes RVM Java虛擬機(jī)的學(xué)術(shù)研究許可，并*終促使其成為開源項(xiàng)目。

四.資料目錄

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

本文鏈接：http://fangxuan.com.cn/algorithm/352.html