垃圾收集PDF电子书下载

第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