垃圾收集

图书标准信息

• 作者 琼斯、谢之易 著
• 出版社 人民邮电出版社
• 出版时间 2004-04
• 版次 1
• ISBN 9787115120700
• 定价 45.00元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 341页
• 字数 541千字
• 原版书名 Garbage Collection: Algorithms for Automatic Dynamic Memory Management

【内容简介】

　　书围绕着动态内存自动回收的话题，介绍了垃圾收集机制，详细分析了各种算法和相关技术。
　　本书共12章。第1章首先介绍计算机存储器管理的演化和自动内存回收的需求，并引入了本书所使用的术语和记法。第2章介绍了3种“经典”的垃圾收集技术：引用计数（referencecounting）、标记－清扫（mark-sweep）和节点复制（copying）。随后的4章更详细地讨论了上述这些垃圾收集方式和标记－缩并（mark-compact）收集。第7章和第8章分别介绍了在现代垃圾收集实现中具有重要地位的分代式（generational）垃圾收集和渐进式（incremental）垃圾收集。第9章和第10章扩展了垃圾收集的领域，讨论了如何让垃圾收集能够在无法得到来自语言编译器的支持的环境（分别是C和C++）中运行。第11章讨论了一个相对较新的研究领域--垃圾收集和硬件数据cache的相互作用。第12章简要地考察了用于分布式系统的垃圾收集。
　　本书适合对动态内存管理感兴趣的读者阅读，可供专业的研究人员参考。

【目录】

第1章简介1
1.1内存分配的历史2
1.1.1静态分配2
1.1.2栈分配3
1.1.3堆分配3
1.2状态、存活性和指针可到达性4
1.3显式堆分配5
1.3.1一个简单的例子5
1.3.2垃圾5
1.3.3悬挂引用6
1.3.4共享6
1.3.5失败6
1.4为什么需要垃圾收集7
1.4.1语言的需求7
1.4.2问题的需求7
1.4.3软件工程的课题8
1.4.4没有银弹9
1.5垃圾收集的开销有多大11
1.6垃圾收集算法比较11
1.7记法15
1.7.1堆15
1.7.2指针和子女15
1.7.3伪代码16
1.8引文注记16

第2章经典算法18
2.1引用计数算法18
2.1.1算法18
2.1.2一个例子20
2.1.3引用计数算法的优势和弱点21
2.1.4环形数据结构22
2.2标记－清扫算法23
2.2.1算法23
2.2.2标记－清扫算法的优势和弱点25
2.3节点复制算法26
2.3.1算法27
2.3.2一个例子28
2.3.3节点复制算法的优势和弱点30
2.4比较标记－清扫技术和节点复制技术31
2.5需要考虑的问题32
2.6引文注记36

第3章引用计数38
3.1非递归的释放38
3.1.1算法38
3.1.2延迟释放的优点和代价39
3.2延迟引用计数39
3.2.1Deutsch-Bobrow算法40
3.2.2一个例子41
3.2.3ZCT溢出43
3.2.4延迟引用计数的效率43
3.3计数域大小受限的引用计数44
3.3.1“粘住的”计数值44
3.3.2追踪式收集恢复计数值44
3.3.3仅有一位的计数值45
3.3.4恢复独享信息46
3.3.5“Oughttobetwo”缓冲区47
3.4硬件引用计数48
3.5环形引用计数49
3.5.1函数式程序设计语言49
3.5.2Bobrow的技术50
3.5.3弱指针算法51
3.5.4部分标记－清扫算法54
3.6需要考虑的问题60
3.7引文注记63

第4章标记－清扫垃圾收集66
4.1与引用计数技术的比较66
4.2使用标记栈67
4.2.1显式地使用栈来实现递归67
4.2.2最小化栈的深度68
4.2.3栈溢出70
4.3指针反转72
4.3.1Deutsch-Schorr-Waite算法73
4.3.2可变大小节点的指针反转75
4.3.3指针反转的开销75
4.4位图标记76
4.5延迟清扫78
4.5.1Hughes的延迟清扫算法78
4.5.2Boehm-Demers-Weiser清扫器79
4.5.3Zorn的延迟清扫器81
4.6需要考虑的问题82
4.7引文注记84

第5章标记－缩并垃圾收集86
5.1碎片现象86
5.2缩并的方式87
5.3“双指针”算法89
5.3.1算法90
5.3.2对“双指针”算法的分析91
5.3.3可变大小的单元91
5.4Lisp2算法92
5.5基于表的方法93
5.5.1算法93
5.5.2间断表94
5.5.3更新指针95
5.6穿线方法95
5.6.1穿线指针95
5.6.2Jonkers的缩并算法96
5.6.3前向指针97
5.6.4后向指针98
5.7需要考虑的问题99
5.8引文注记101

第6章节点复制垃圾收集103
6.1Cheney的节点复制收集器104
6.1.1三色抽象104
6.1.2算法105
6.1.3一个例子106
6.2廉价地分配109
6.3多区域收集110
6.3.1静态区域111
6.3.2大型对象区域111
6.3.3渐进的递增缩并垃圾收集111
6.4垃圾收集器的效率113
6.5局部性问题114
6.6重组策略115
6.6.1深度优先节点复制与广度优先节点复制116
6.6.2不需要栈的递归式节点复制收集117
6.6.3近似于深度优先的节点复制119
6.6.4层次分解120
6.6.5哈希表121
6.7需要考虑的问题122
6.8引文注记124

第7章分代式垃圾收集126
7.1分代假设126
7.2分代式垃圾收集129
7.2.1一个简单例子129
7.2.2中断时间131
7.2.3次级收集的根集合132
7.2.4性能133
7.3提升策略134
7.3.1多个分代134
7.3.2提升的阈值135
7.3.3StandardMLofNewJersey收集器136
7.3.4自适应提升137
7.4分代组织和年龄记录140
7.4.1每个分代一个半区140
7.4.2创建空间140
7.4.3记录年龄141
7.4.4大型对象区域144
7.5分代间指针145
7.5.1写拦截器145
7.5.2入口表146
7.5.3记忆集147
7.5.4顺序保存缓冲区148
7.5.5硬件支持的页面标记149
7.5.6虚存系统支持的页面标记150
7.5.7卡片标记151
7.5.8记忆集还是卡片153
7.6非节点复制的分代式垃圾收集154
7.7调度垃圾收集155
7.7.1关键对象156
7.7.2成熟对象空间157
7.8需要考虑的问题159
7.9引文注记160

第8章渐进式和并发垃圾收集162
8.1同步163
8.2拦截器方案165
8.3标记－清扫收集器167
8.3.1写拦截器167
8.3.2新单元171
8.3.3初始化和终止173
8.3.4虚存技术176
8.4并发引用计数177
8.5Baker的算法180
8.5.1算法181
8.5.2Baker算法的延迟的界限182
8.5.3Baker的算法的局限182
8.5.4Baker算法的变种183
8.5.5动态重组184
8.6Appel-Ellis-Li收集器186
8.6.1各种改进188
8.6.2大型对象188
8.6.3分代189
8.6.4性能189
8.7应变复制收集器190
8.7.1Nettle的应变复制收集器190
8.7.2Huelsbergen和Larus的收集器191
8.7.3Doligez-Leroy-Gonthier收集器192
8.8Baker的工作环收集器194
8.9对实时垃圾收集的硬件支持196
8.10需要考虑的问题197
8.11引文注记199

第9章C语言的垃圾收集202
9.1根不确定收集的一个分类203
9.2保守式垃圾收集205
9.2.1分配205
9.2.2寻找根和指针206
9.2.3内部指针209
9.2.4保守式垃圾收集的问题209
9.2.5识别错误211
9.2.6效率212
9.2.7渐进式、分代式垃圾收集214
9.3准复制式收集215
9.3.1堆的布局215
9.3.2分配216
9.3.3垃圾收集216
9.3.4分代式垃圾收集218
9.3.5无法精确识别的数据结构218
9.3.6准复制式收集的效率219
9.4优化的编译器是“魔鬼”220
9.5需要考虑的问题223
9.6引文注记224

第10章C++语言的垃圾收集226
10.1用于面向对象语言的垃圾收集227
10.2对C++垃圾收集器的需求228
10.3在编译器中还是在库中230
10.4保守式垃圾收集230
10.5准复制式收集器231
10.6智能指针234
10.6.1在没有智能指针类层次的情况下进行转换234
10.6.2多重继承235
10.6.3不正确的转换235
10.6.4某些指针无法“智能化”236
10.6.5用const和volatile修饰的指针236
10.6.6智能指针的“泄漏”236
10.6.7智能指针和引用计数237
10.6.8一个简单的引用计数指针238
10.6.9用于灵活的垃圾收集的智能指针238
10.6.10用于追踪式垃圾收集的智能指针240
10.7为支持垃圾收集而修改C++241
10.8Ellis和Detlefs的建议242
10.9终结机制243
10.10需要考虑的问题245
10.11引文注记246

第11章垃圾收集与cache248
11.1现代处理器体系结构248
11.2cache的体系结构250
11.2.1cache容量250
11.2.2放置策略251
11.2.3写策略252
11.2.4特殊的cache指令254
11.3内存访问的模式254
11.3.1标记－清扫技术，使用标记位图和延迟清扫254
11.3.2节点复制垃圾收集255
11.3.3渐进式垃圾收集256
11.3.4避免读取256
11.4改进cache性能的标准方法257
11.4.1cache的容量257
11.4.2块大小260
11.4.3相联度260
11.4.4特殊指令262
11.4.5预取262
11.5失误率和总体cache性能263
11.6专用硬件265
11.7需要考虑的问题265
11.8引文注记266

第12章分布式垃圾收集268
12.1需求269
12.2虚拟共享存储器270
12.2.1共享虚拟存储器模型271
12.2.2共享数据对象模型271
12.2.3分布式共享存储器之上的垃圾收集272
12.3与分布式垃圾收集有关的课题272
12.3.1分类原则272
12.3.2同步274
12.3.3鲁棒性274
12.4分布式标记－清扫275
12.4.1Hudak和Keller275
12.4.2Ali的算法277
12.4.3Hughes的算法277
12.4.4Liskov-Ladin算法278
12.4.5Augusteijn的算法278
12.4.6Vestal的算法278
12.4.7Schelvis-Bledoeg算法278
12.4.8Emerald收集器279
12.4.9IK收集器280
12.5分布式节点复制280
12.6分布式引用计数281
12.6.1Lermen-Maurer协议281
12.6.2间接引用计数281
12.6.3Mancini-Shrivastava算法282
12.6.4SPG协议282
12.6.5“Garbagecollectingtheworld”283
12.6.6网络对象283
12.6.7带权引用计数284
12.6.8世代引用计数284
12.7对actor进行垃圾收集285
12.7.1Halstead算法285
12.7.2标记算法285
12.7.3逻辑上集中式的收集器286
12.8引文注记286
参考文献298
术语表288
索引331
算法列表339