垃圾收集

    书围绕着动态内存自动回收的话题，介绍了垃圾收集机制，详细分析了各种算法和相关技术。 本书共12章。第1章首先介绍计算机存储器管理的演化和自动内存回收的需求，并引入了本书所使用的术语和记法。第2章介绍了3种“经典”的垃圾收集技术：引用计数（reference counting）、标记－清扫（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.1 Deutsch-Bobrow算法 40
3.2.2 一个例子 41
3.2.3 ZCT溢出 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 “Ought to be two”缓冲区 47
3.4 硬件引用计数 48
3.5 环形引用计数 49
3.5.1 函数式程序设计语言 49
3.5.2 Bobrow的技术 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.1 Deutsch-Schorr-Waite算法 73
4.3.2 可变大小节点的指针反转 75
4.3.3 指针反转的开销 75
4.4 位图标记 76
4.5 延迟清扫 78
4.5.1 Hughes的延迟清扫算法 78
4.5.2 Boehm-Demers-Weiser清扫器 79
4.5.3 Zorn的延迟清扫器 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.4 Lisp 2算法 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.2 Jonkers的缩并算法 96
5.6.3 前向指针 97
5.6.4 后向指针 98
5.7 需要考虑的问题 99
5.8 引文注记 101
第6章 节点复制垃圾收集 103
6.1 Cheney的节点复制收集器 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.3 Standard ML of New Jersey收集器 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.5 Baker的算法 180
8.5.1 算法 181
8.5.2 Baker算法的延迟的界限 182
8.5.3 Baker的算法的局限 182
8.5.4 Baker算法的变种 183
8.5.5 动态重组 184
8.6 Appel-Ellis-Li收集器 186
8.6.1 各种改进 188
8.6.2 大型对象 188
8.6.3 分代 189
8.6.4 性能 189
8.7 应变复制收集器 190
8.7.1 Nettle的应变复制收集器 190
8.7.2 Huelsbergen和Larus的收集器 191
8.7.3 Doligez-Leroy-Gonthier收集器 192
8.8 Baker的工作环收集器 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.8 Ellis和Detlefs的建议 242
10.9 终结机制 243
10.10 需要考虑的问题 245
10.11 引文注记 246
第11章 垃圾收集与cache 248
11.1 现代处理器体系结构 248
11.2 cache的体系结构 250
11.2.1 cache容量 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.1 cache的容量 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.1 Hudak和Keller 275
12.4.2 Ali的算法 277
12.4.3 Hughes的算法 277
12.4.4 Liskov-Ladin算法 278
12.4.5 Augusteijn的算法 278
12.4.6 Vestal的算法 278
12.4.7 Schelvis-Bledoeg算法 278
12.4.8 Emerald收集器 279
12.4.9 IK收集器 280
12.5 分布式节点复制 280
12.6 分布式引用计数 281
12.6.1 Lermen-Maurer协议 281
12.6.2 间接引用计数 281
12.6.3 Mancini-Shrivastava算法 282
12.6.4 SPG协议 282
12.6.5 “Garbage collecting the world” 283
12.6.6 网络对象 283
12.6.7 带权引用计数 284
12.6.8 世代引用计数 284
12.7 对actor进行垃圾收集 285
12.7.1 Halstead算法 285
12.7.2 标记算法 285
12.7.3 逻辑上集中式的收集器 286
12.8 引文注记 286
参考文献 298
术语表 288
索引 331
算法列表 339