垃圾收集

第1章 简介

1. 1 内存分配的历史

1. 1. 1 静态分配

1. 1. 2 栈分配

1. 1. 3 堆分配

1. 2 状态. 存活性和指针可到达性

1. 3 显式堆分配

1. 3. 1 一个简单的例子

1. 3. 2 垃圾

1. 3. 3 悬挂引用

1. 3. 4 共享

1. 3. 5 失败

1. 4 为什么需要垃圾收集

1. 4. 1 语言的需求

1. 4. 2 问题的需求

1. 4. 3 软件工程的课题

1. 4. 4 没有银弹

1. 5 垃圾收集的开销有多大

1. 6 垃圾收集算法比较

1. 7 记法

1. 7. 1 堆

1. 7. 2 指针和子女

1. 7. 3 伪代码

1. 8 引文注记

第2章 经典算法

2. 1 引用计数算法

2. 1. 1 算法

2. 1. 2 一个例子

2. 1. 3 引用计数算法的优势和弱点

2. 1. 4 环形数据结构

2. 2 标记一清扫算法

2. 2. 1 算法

2. 2. 2 标记—清扫算法的优势和弱点

2. 3 节点复制算法

2. 3. 1 算法

2. 3. 2 一个例子

2. 3. 3 节点复制算法的优势和弱点

2. 4 比较标记—清扫技术和节点复制技术

2. 5 需要考虑的问题

2. 6 引文注记

第3章 引用计数

3. 1 非递归的释放

3. 1. 1 算法

3. 1. 2 延迟释放的优点和代价

3. 2 延迟引用计数

3. 2. 1 Deutsch-Bobrow算法

3. 2. 2 一个例子

3. 2. 3 ZCT溢出

3. 2. 4 延迟引用计数的效率

3. 3 计数域大小受限的引用计数

3. 3. 1 “粘住的”计数值

3. 3. 2 追踪式收集恢复计数值

3. 3. 3 仅有一位的计数值

3. 3. 4 恢复独享信息

3. 3. 5 “Ought to be two”缓冲区

3. 4 硬件引用计数

3. 5 环形引用计数

3. 5. 1 函数式程序设计语言

3. 5. 2 Bobrow的技术

3. 5. 3 弱指针算法

3. 5. 4 部分标记—清扫算法

3. 6 需要考虑的问题

3. 7 引文注记

第4章 标记—清扫垃圾收集

4. 1 与引用计数技术的比较

4. 2 使用标记栈

4. 2. 1 显式地使用栈来实现递归

4. 2. 2 最小化栈的深度

4. 2. 3 栈溢出

4. 3 指针反转

4. 3. 1 Deutsch-Schorr-Waite算法

4. 3. 2 可变大小节点的指针反转

4. 3. 3 指针反转的开销

4. 4 位图标记

4. 5 延迟清扫

4. 5. 1 Hughes的延迟清扫算法

4. 5. 2 Boehm-Demers-Weiser清扫器

4. 5. 3 Zorn的延迟清扫器

4. 6 需要考虑的问题

4. 7 引文注记

第5章 标记—缩并垃圾收集

5. 1 碎片现象

5. 2 缩并的方式

5. 3 “双指针”算法

5. 3. 1 算法

5. 3. 2 对“双指针”算法的分析

5. 3. 3 可变大小的单元

5. 4 Lisp 2 算法

5. 5 基于表的方法

5. 5. 1 算法

5. 5. 2 间断表

5. 5. 3 更新指针

5. 6 穿线方法

5. 6. 1 穿线指针

5. 6. 2 Jonkers的缩并算法

5. 6. 3 前向指针

5. 6. 4 后向指针

5. 7 需要考虑的问题

5. 8 引文注记

第6章 节点复制垃圾收集

6. 1 Cheney的节点复制收集器

6. 1. 1 三色抽象

6. 1. 2 算法

6. 1. 3 一个例子

6. 2 廉价地分配

6. 3 多区域收集

6. 3. 1 静态区域

6. 3. 2 大型对象区域

6. 3. 3 渐进的递增缩并垃圾收集

6. 4 垃圾收集器的效率

6. 5 局部性问题

6. 6 重组策略

6. 6. 1 深度优先节点复制与广度优先节点复制

6. 6. 2 不需要栈的递归式节点复制收集

6. 6. 3 近似于深度优先的节点复制

6. 6. 4 层次分解

6. 6. 5 哈希表

6. 7 需要考虑的问题

6. 8 引文注记

第7章 分代式垃圾收集

7. 1 分代假设

7. 2 分代式垃圾收集

7. 2. 1 一个简单例子

7. 2. 2 中断时间

7. 2. 3 次级收集的根集合

7. 2. 4 性能

7. 3 提升策略

7. 3. 1 多个分代

7. 3. 2 提升的闽值

7. 3. 3 Standard ML of New Jersey收集器

7. 3. 4 自适应提升

7. 4 分代组织和年龄记录

7. 4. 1 每个分代一个半区

7. 4. 2 创建空间

7. 4. 3 记录年龄

7. 4. 4 大型对象区域

7. 5 分代间指针

7. 5. 1 写拦截器

7. 5. 2 入口表

7. 5. 3 记忆集

7. 5. 4 顺序保存缓冲区

7. 5. 5 硬件支持的页面标记

7. 5. 6 虚存系统支持的页面标记

7. 5. 7 卡片标记

7. 5. 8 记忆集还是卡片

7. 6 非节点复制的分代式垃圾收集

7. 7 调度垃圾收集

7. 7. 1 关键对象

7. 7. 2 成熟对象空间

7. 8 需要考虑的问题

7. 9 1 文注记

第8章 渐进式和并发垃圾收集

8. 1 同步

8. 2 拦截器方案

8. 3 标记—清扫收集器

8. 3. 1 写拦截器

8. 3. 2 新单元

8. 3. 3 初始化和终止

8. 3. 4 虚存技术

8. 4 并发引用计数

8. 5 Baker的算法

8. 5. 1 算法

8. 5. 2 Baker算法的延迟的界限

8. 5. 3 Baker的算法的局限

8. 5. 4 Baker算法的变种

8. 5. 5 动态重组

8. 6 Appel-Ellis-Li收集器

8. 6. 1 各种改进

8. 6. 2 大型对象

8. 6. 3 分代

8. 6. 4 性能

8. 7 应变复制收集器

8. 7. 1 Nettle的应变复制收集器

8. 7. 2 Huelsbergen和Larus的收集器

8. 7. 3 Doligez-Leroy-Gonthier收集器

8. 8 Baker的工作环收集器

8. 9 对实时垃圾收集的硬件支持

8. 10 需要考虑的问题

8. 11 引文注记

第9章 C语言的垃圾收集

9. 1 根不确定收集的一个分类

9. 2 保守式垃圾收集

9. 2. 1 分配

9. 2. 2 寻找根和指针

9. 2. 3 内部指针

9. 2. 4 保守式垃圾收集的问题

9. 2. 5 识别错误

9. 2. 6 效率

9. 2. 7 渐进式. 分代式垃圾收集

9. 3 准复制式收集

9. 3. 1 堆的布局

9. 3. 2 分配

9. 3. 3 垃圾收集

9. 3. 4 分代式垃圾收集

9. 3. 5 无法精确识别的数据结构

9. 3. 6 准复制式收集的效率

9. 4 优化的编译器是“魔鬼”

9. 5 需要考虑的问题

9. 6 引文注记

第10章 C++语言的垃圾收集

10. 1 用于面向对象语言的垃圾收集

10. 2 对C++垃圾收集器的需求

10. 3 在编译器中还是在库中

10. 4 保守式垃圾收集

10. 5 准复制式收集器

10. 6 智能指针

10. 6. 1 在没有智能指针类层次的情况下进行转换

10. 6. 2 多重继承

10. 6. 3 不正确的转换

10. 6. 4 某些指针无法“智能化”

10. 6. 5 用const和volatile修饰的指针

10. 6. 6 智能指针的“泄漏”

10. 6. 7 智能指针和引用计数

10. 6. 8 一个简单的引用计数指针

10. 6. 9 用于灵活的垃圾收集的智能指针

10. 6. 10 用于追踪式垃圾收集的智能指针

10. 7 为支持垃圾收集而修改C++

10. 8 Ellis和Deters的建议

10. 9 终结机制

10. 10 需要考虑的问题

10. 11 引文注记

第11章 垃圾收集与cache

11. 1 现代处理器体系结构

11. 2 cache的体系结构

11. 2. 1 cache容量

11. 2. 2 放置策略

11. 2. 3 写策略

11. 2. 4 特殊的cache指令

11. 3 内存访问的模式

11. 3. 1 标记 —清扫技术, 使用标记位图和延迟清扫

11. 3. 2 节点复制垃圾收集

11. 3. 3 渐进式垃圾收集

11. 3. 4 避免读取

11. 4 改进cache性能的标准方法

11. 4. 1 cache的容量

11. 4. 2 块大小

11. 4. 3 相联度

11. 4. 4 特殊指令

11. 4. 5 预取

11. 5 失误率和总体cache性能

11. 6 专用硬件

11. 7 需要考虑的问题

11. 8 引文注记

第12章 分布式垃圾收集

12. 1 需求

12. 2 虚拟共享存储器

12. 2. 1 共享虚拟存储器模型

12. 2. 2 共享数据对象模型

12. 2. 3 分布式共享存储器之上的垃圾收集

12. 3 与分布式垃圾收集有关的课题

12. 3. 1 分类原则

12. 3. 2 同步

12. 3. 3 鲁棒性

12. 4 分布式标记—清扫

12. 4. 1 Hudak和Keller

12. 4. 2 Ali的算法

12. 4. 3 Hughes的算法

12. 4. 4 Liskov-Ladin算法

12. 4. 5 Augusteijn的算法

12. 4. 6 Vestal的算法

12. 4. 7 Schelvis-Bledoeg算法

12. 4. 8 Emerald收集器

12. 4. 9 IK收集器

12. 5 分布式节点复制

12. 6 分布式引用计数

12. 6. 1 Lermen-Maurer协议

12. 6. 2 间接引用计数

12. 6. 3 Mancini-Shrivastava算活

12. 6. 4 SPG协议

12. 6. 5 “Garbage collecting the world”

12. 6. 6 网络对象

12. 6. 7 带权引用计数

12. 6. 8 世代引用计数

12. 7 对actor进行垃圾收集

12. 7. 1 Halstead算法

12. 7. 2 标记算法

12. 7. 3 逻辑上集中式的收集器

12. 8 引文注记

术语表

参考文献

索引

算法列表