第1章简介 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.4共享 6
1.3.5 失败 6
1.3.3悬挂引用 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.1引用计数算法 18
2.1.1算法 18
第2章经典算法 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
35.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.4Lisp 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.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 NewJersey收集器 136
7.3.4 自适应提升 137
7.4.1每个分代一个半区 140
7.4.2创建空间 140
7.4分代组织和年龄记录 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.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.5用const和volatile修饰的指针 236
10.6.6智能指针的“泄漏” 236
10.6.4某些指针无法“智能化” 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.3 内存访问的模式 254
11.3.1标记—清扫技术使用标记位图和延迟清扫 254
11.2.4特殊的cache指令 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.3与分布式垃圾收集有关的课题 272
12.3.1分类原则 272
12.2.3分布式共享存储器之上的垃圾收集 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.6 Vestal的算法 278
12.4.5 Augusteijn的算法 278
12.4.7 Schelvis-Bledoeg算法 278
12.4.4 Liskov-Ladin算法 278
12.4.8 Emerald收集器 279
12.4.9 IK收集器 280
12.5分布式节点复制 280
12.6.1Lermen-Maurer协议 281
12.6.2间接引用计数 281
12.6分布式引用计数 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.1 Halstead算法 285
12.7.2标记算法 285
12.7对actor进行垃圾收集 285
12.7.3逻辑上集中式的收集器 286
12.8引文注记 286
术语表 288
参考文献 298
索引 331
算法列表 339
6.6重组策略 1105