垃圾回收的算法与实现 PDF 文档

Question

本书分为 算法篇 和 实现篇 两大部分。算法篇介绍了标记 - 清除算法、引用计数法、复制算法、标记 - 压缩算法、保守式 GC、分代垃圾回收、增量式垃圾回收、RC Immix 算法等几种重要的算法；实现篇介绍了垃圾回收在 Python、DalvikVM、Rubinius、V8 等几种语言处理程序中的具体实现。本书适合各领域程序员阅读。

计算机的进步，特别是硬件的发展之快总是让我们感到惊讶。在这波不断向前涌动的洪流中，技术领域的浮沉也愈发激烈。本书涉及的垃圾回收（Garbage Collection，GC）与其说是理论，其实更偏向技术层面，然而它却有着令人吃惊的漫长历史。GC 在计算机发展的激流中没有浮起，也没有沉下。直到 1995 年 Java 发布，因为其内藏 GC，人们才开始意识到 GC的作用。

追溯 Lisp 语言的秘史我们会发现，GC 这种让已经无法利用的内存实现自动再利用（可能称为“内存资源回收”更恰当）的技术，是于 Lisp 的设计开始约 1 年后，也就是 1959 年的夏天首次出现的。实现 GC 的是一个叫 D. Edwards 的人。至今已经经过了 50 多年的漫长岁月。

这期间人们进行了海量的研究和开发，与其相关的论文也堆积如山。这么说来，我也写过几篇关于 GC 的论文。然而让我吃惊的是，这么久以来竟然没有一本关于 GC 的教科书 或 专业书籍。英语界曾于 1996 年首次针对 GC 出版了一本 Garbage Collection（Richard E. Jones、Rafael D. Lins 著），这是 37 年来在 GC 领域的一次破天荒的壮举，本书也将其作为了参考文献。然而在日本，本书可以说是第一本用日语写的 GC 专业图书，可谓五十年磨一剑，在此也对年轻有为的二位作者致以深深的敬意。

如果看看某本教科书中的一节或者读读几篇论文就能明白 GC 是什么东西，那么或许就不需要这本书了，但 GC 并没有那么简单。在学习或工作中不得不使用 GC 的人，首先就必须看两三篇有名的论文，之后还要去研究那些可能与其有关的原著。也就是说，从某种意义上而言，最后还是需要自己去想很多东西。

目录
序章
算法篇
1 学习 GC 之前
1.1 对象/ 头/ 域
1.1.1 头
1.1.2 域
1.2 指针
1.3 mutator
1.4 堆
1.5 活动对象 / 非活动对象
1.6 分配
1.7 分块
1.8 根
1.9 评价标准
1.9.1 吞吐量
1.9.2 最大暂停时间
1.9.3 堆使用效率
1.9.4 访问的局部性
2 GC 标记-清除算法
2.1 什么是 GC 标记- 清除算法
2.1.1 标记阶段
2.1.2 清除阶段
2.1.3 分配
2.1.4 合并
2.2 优点
2.2.1 实现简单
2.2.2 与保守式 GC 算法兼容
2.3 缺点
2.3.1 碎片化
2.3.2 分配速度
2.3.3 与写时复制技术不兼容
2.4 多个空闲链表
2.5 BiBOP 法
2.6 位图标记
2.6.1 优点
2.6.1.1 与写时复制技术兼容
2.6.1.2 清除操作更高效
2.6.2 要注意的地方
2.7 延迟清除法
2.7.1 new_obj() 函数
2.7.2 lazy_sweep() 函数
2.7.3 有延迟清除法就够了吗
3 引用计数法
3.1 引用计数的算法
3.1.1 计数器值的增减
3.1.2 new_obj() 函数
3.1.3 update_ptr() 函数
3.2 优点
3.2.1 可即刻回收垃圾
3.2.2 最大暂停时间短
3.2.3 没有必要沿指针查找
3.3 缺点
3.3.1 计数器值的增减处理繁重
3.3.2 计数器需要占用很多位
3.3.3 实现烦琐复杂
3.3.4 循环引用无法回收
3.4 延迟引用计数法
3.4.1 什么是延迟引用计数法
3.4.2 dec_ref_cnt() 函数
3.4.3 new_obj() 函数
3.4.4 scan_zct() 函数
3.4.5 优点
3.4.6 缺点
3.5 Sticky 引用计数法
3.5.1 什么是 Sticky 引用计数法
3.5.2 什么都不做
3.5.3 使用 GC 标记- 清除算法进行管理
3.61 位引用计数法
3.6.1 什么是 1 位引用计数法
3.6.2 copy_ptr() 函数
3.6.3 delete_ptr() 函数
3.6.4 优点
3.6.5 缺点
3.7 部分标记- 清除算法
3.7.1 什么是部分标记- 清除算法
3.7.2 前提
3.7.3 dec_ref_cnt() 函数
3.7.4 new_obj() 函数
3.7.5 scan_hatch_queue() 函数
3.7.6 paint_gray() 函数
3.7.7 scan_gray() 函数
3.7.8 collect_white() 函数
3.7.9 限定搜索对象
3.7.10 paint_gray() 函数的要点
3.7.11 部分标记- 清除算法的局限性
4 GC 复制算法
4.1 什么是 GC 复制算法
4.1.1 copy() 函数
4.1.2 new_obj() 函数
4.1.3 执行过程
4.2 优点
4.2.1 优秀的吞吐量
4.2.2 可实现高速分配
4.2.3 不会发生碎片化
4.2.4 与缓存兼容
4.3 缺点
4.3.1 堆使用效率低下
4.3.2 不兼容保守式 GC 算法
4.3.3 递归调用函数
4.4 Cheney 的 GC 复制算法
4.4.1 copy() 函
4.4.2 执行过程
4.4.3 被隐藏的队列
4.4.4 优点
4.4.5 缺点
4.5 近似深度优先搜索方法
4.5.1 Cheney 的 GC 复制算法（复习）
4.5.2 前提
4.5.3 执行过程
4.5.4 执行结果
4.6 多空间复制算法
4.6.1 multi_space_copying() 函数
4.6.2 mark_or_copy() 函数
4.6.3 copy() 函数
4.6.4 执行过程
4.6.5 优点
4.6.6 缺点
5 GC 标记-压缩算法
5.1 什么是 GC 标记- 压缩算法
5.1.1 Lisp2 算法的对象
5.1.2 概要
5.1.3 步骤 1— 设定 forwarding 指针
5.1.4 步骤 2— 更新指针
5.1.5 步骤 3— 移动对象
5.2 优点
可有效利用堆
5.3 缺点
压缩花费计算成本
5.4 Two-Finger 算法
5.4.1 前提
5.4.2 概要
5.4.3 步骤 1—移动对象
5.4.4 步骤 2—更新指针
5.4.5 优点
5.4.6 缺点
5.5 表格算法
5.5.1 概要
5.5.2 步骤 1（前半部分）—移动对象
5.5.3 步骤 1（后半部分）—构筑间隙表格
5.5.4 步骤 2—更新指针
5.5.5 优点
5.5.6 缺点
5.6 ImmixGC 算法
5.6.1 概要
5.6.2 堆的构成
5.6.3 对象的分类
5.6.4 分配
5.6.5 分配时的标记操作
5.6.6 步骤 1—选定备用 From 块
5.6.7 步骤 2—搜索阶段
5.6.8 步骤 3—清除阶段
5.6.9 优点
5.6.10 缺点
6 保守式 GC
6.1 什么是保守式 GC
6.1.1 不明确的根
6.1.2 指针和非指针的识别
6.1.3 貌似指针的非指针
6.1.4 不明确的数据结构
6.2 优点
语言处理程序不依赖于 GC
6.3 缺点
6.3.1 识别指针和非指针需要付出成本
6.3.2 错误识别指针会压迫堆
6.3.3 能够使用的 GC 算法有限
6.4 准确式 GC
6.4.1 正确的根
6.4.2 打标签
6.4.3 不把寄存器和栈等当作根
6.4.4 优点
6.4.5 缺点
6.5 间接引用
6.5.1 经由句柄引用对象
6.5.2 优点
6.5.3 缺点
6.6 MostlyCopyingGC
6.6.1 概要
6.6.2 堆结构
6.6.3 分配
6.6.4 new_obj() 函数
6.6.5 add_pages() 函数
6.6.6 GC 执行过程
6.6.7 mostly_copying() 函数
6.6.8 promote_page() 函数
6.6.9 page_scan() 函数
6.6.10 copy() 函数
6.6.11 优点和缺点
6.7 黑名单
6.7.1 指针的错误识别带来的害处
6.7.2 黑名单
6.7.3 面向黑名单内的地址的分配
6.7.4 优点和缺点
7 分代垃圾回收
7.1 什么是分代垃圾回收
7.1.1 对象的年龄
7.1.2 新生代对象和老年代对象
7.2 Ungar 的分代垃圾回收
7.2.1 堆的结构
7.2.2 记录集
7.2.3 写入屏障
7.2.4 对象的结构
7.2.5 分配
7.2.6 新生代 GC
7.2.7 老年代 GC
7.3 优点
吞吐量得到改善
7.4 缺点
在部分程序中会起到反作用
7.5 记录各代之间的引用的方法
7.5.1 卡片标记
7.5.2 页面标记
7.6 多代垃圾回收
7.7 列车垃圾回收
7.7.1 堆的结构
7.7.2 新生代 GC
7.7.3 老年代 GC
7.7.4 写入屏障
7.7.5 优点
7.7.6 缺点
8 增量式垃圾回收
8.1 什么是增量式垃圾回收
8.1.1 三色标记算法
8.1.2 GC 标记- 清除算法的分割
8.1.3 根查找阶段
8.1.4 标记阶段
8.1.5 写入屏障
8.1.6 清除阶段
8.1.7 分配
8.2 优点和缺点
8.2.1 缩短最大暂停时间
8.2.2 降低了吞吐量
8.3 Steele 的算法
8.3.1 mark() 函数
8.3.2 写入屏障
8.4 汤浅的算法
8.4.1 标记阶段
8.4.2 从黑色对象指向白色对象的指针
8.4.3 写入屏障
8.4.4 分配
8.5 比较各个写入屏障
9 RC Immix 算法
9.1 目的
9.2 合并型引用计数法
9.2.1 伪代码
9.2.2 优点和缺点
9.3 合并型引用计数法和 Immix 的融合
9.3.1 新对象
9.3.2 被动的碎片整理
9.3.3 积极的碎片整理
9.4 优点和缺点
9.4.1 优点
9.4.2 缺点
实现篇
10 Python 的垃圾回收
10.1 本章前言
10.1.1 Python 是什么
10.1.2 Python 的源代码
10.1.3 Python 的垃圾回收算法
10.2 对象管理
10.3 Python 的内存分配器
10.4 第 0 层 通用的基础分配器
10.5 第 1 层 Python 低级内存分配器
10.5.1 内存结构
10.5.2 arena
10.5.3 pool
10.5.4 new_arena()
10.5.5 usable_arenas 和 unused_arena_objects
10.5.6 第 1 层总结
10.6 第 2 层 Python 对象分配器
10.6.1 block
10.6.2 usedpools
10.6.3 复杂的 usedpools
10.6.4 block 的状态管理
10.6.5 PyObject_Malloc()
10.6.6 （A）从 usedpools 中取出 pool
10.6.7 （B）返回 pool 内的 block
10.6.8 （C）调用 new_arena()
10.6.9 （D）初始化使用完毕的 pool
10.6.10 （E）初始化 pool 并返回 block
10.6.11 （F）初始化空 pool
10.6.12 PyObject_Free()
10.6.13 （A）把作为释放对象的 block 连接到 freeblock
10.6.14 （B）将 pool 返回 arena
10.6.15 （C）释放 arena
10.6.16 （D）移动到 usable_arenas 的开头
10.6.17 （E）对 usable_arenas 进行排序
10.6.18 （F）插入 pool
10.6.19 arena 和 pool 的释放策略
10.6.20 从 block 搜索 pool 的技巧
10.7 第 3 层 对象特有的分配器
10.8 引用计数法
10.8.1 增量
10.8.2 Q：计数器不会出现溢出吗？
10.8.3 减量操作
10.8.4 终结器
10.8.5 插入计数处理
10.9 引用的所有权
10.9.1 传递引用的所有权（返回值）
10.9.2 出借引用的所有权（返回值）
10.9.3 占据引用的所有权（参数）
10.9.4 出借引用的所有权（参数）
10.9.5 使用引用计数法会留下 BUG 吗
10.10 如何应对有循环引用的垃圾对象
10.10.1 循环引用垃圾回收的算法
10.10.2 容器对象
10.10.3 生成容器对象
10.10.4 追踪容器对象
10.10.5 结束追踪容器对象
10.10.6 分代容器对象链表
10.10.7 何时执行循环引用垃圾回收
10.10.8 循环引用垃圾回收
10.10.9 gc_list_merge()
10.10.10 update_refs()
10.10.11 subtract_refs()
10.10.12 move_unreachable()
10.10.13 move_finalizers()
10.10.14 move_finalizer_reachable()
10.10.15 delete_garbage()
10.10.16 handle_finalizers()
10.10.17 循环引用中终结器的问题
10.10.18 不需要写入屏障吗
10.11 性能调整的建议
10.11.1 gc.set_debug()
10.11.2 gc.collect()
10.11.3 gc.disable()
11 DalvikVM 的垃圾回收
11.1 本章前言
11.1.1 什么是 Android
11.1.2 Android 架构
11.1.3 DalvikVM 的特征
11.1.4 Android 是多任务的
11.1.5 bionic
11.1.6 ashmem
11.1.7 dlmalloc
11.2 重新学习 mmap
11.2.1 什么是 mmap
11.2.2 活用分配
11.2.3 请求页面调度
11.2.4 共享映射与私有映射
11.2.5 写时复制技术
11.3 DalvikVM 的源代码
11.3.1 获取源代码
11.3.2 源代码结构
11.4 DalvikVM 的 GC 算法
11.5 对象管理
11.5.1 对象的种类
11.5.2 对象结构
11.5.3 DalvikVM 的内存结构
11.5.4 dvmHeapSourceStartup()
11.5.5 addNewHeap()
11.5.6 对象位图
11.5.7 dvmHeapBitmaplnit()
11.5.8 分配到 DalvikVM 的 VM Heap 空间
11.5.9 标记到对象位图
11.5.10 分配实例
11.6 标记阶段
11.6.1 启动 GC 的时机
11.6.2 标记的顺序
11.6.3 保守的根
11.6.4 DalvikVM 是寄存器机器
11.6.5 VM 的调用栈
11.6.6 初始标记
11.6.7 位图的标记
11.6.8 区别非指针和指向对象的指针
11.6.9 搜索对象
11.6.10 dvmHeapScanMarkedObjects()
11.6.11 dvmHeapBitmapXorWalk()
11.6.12 scanBitmapCallback()
11.6.13 scanObject()
11.6.14 processMarkStack()
11.7 清除阶段
11.7.1 在清除之前
11.7.2 开始清除
11.7.3 dvmHeapSweepUnmarkedObjects()
11.7.4 dvmHeapBitmapXorWalk()
11.7.5 sweepBitmapCallback()
11.7.6 dvmHeapSourceFree()
11.8 Q&A
11.8.1 终结器是什么？
11.8.2 为什么要准备两个位图？
11.8.3 碎片化的问题是？
11.8.4 为什么要采用位图标记？
12 Rubinius 的垃圾回收
12.1 本章前言
12.1.1 什么是 Rubinius
12.1.2 获取源代码
12.1.3 源代码结构
12.2 Rubinius 的 GC 算法
12.3 对象管理
12.3.1 对象的结构
12.3.2 用于 GC 复制算法的内存空间
12.3.3 对象的分配器
12.3.4 GC 复制算法的分配器
12.4 走向准确式 GC 之路
12.4.1 根
12.4.2 CRuby 是保守式 GC
12.4.3 CRuby 的 C 语言扩展库
12.4.4 C 语言扩展库（准确式 GC 篇）
12.4.5 Rubinius 的解决方法
12.4.6 Hello Hello World
12.4.7 Rubinius 的处理器管理
12.4.8 与 GC 的关系
12.4.9 Rubinius 和 C 语言扩展库的交换
12.4.10 我们能实际运用 Rubinius 的 Ruby C-API 吗
12.4.11 FFI
12.4.12 内嵌对象和指针的区别
12.5 GC 复制算法
12.5.1 整体流程
12.5.2 collect()
12.5.3 (1) 搜索从记录集引用的对象
12.5.4 写入屏障
12.5.5 (2) 复制从根引用的对象
12.5.6 saw_object()
12.5.7 (3) 搜索复制完毕的对象
12.5.8 copy_unscanned()
12.5.9 scan_object()
12.5.10 (4) 垃圾对象的后处理
12.6 Q&A
12.6.1 该在何时启动各个 GC 算法呢?
12.6.2 为什么把执行 GC 复制算法的类叫作 BakerGC?
12.6.3 为什么是准确式 GC?
12.6.4 不解释一下如何实现 ImmixGC 吗?
12.6.5 为什么要把老年代对象存储在记录集里呢?
13 V8 的垃圾回收
13.1 本章前言
13.1.1 什么是 Google Chrome
13.1.2 什么是 V8
13.1.3 获取源代码
13.1.4 源代码结构
13.2 V8 的 GC 算法
13.3 对象管理
13.3.1 持有不同分配器的两种类
13.3.2 Malloced 类
13.3.3 Object 类
13.3.4 其他特殊的类
13.3.5 VM Heap
13.3.6 老年代指针空间的结构
13.3.7 对象分配器
13.4 通往准确式 GC 之路（V8 篇）
13.4.1 HandleScope
13.4.2 HandleScope 的有效范围
13.4.3 HandleScope 的切换
13.4.4 打标签
13.4.5 控制对象内的域
13.4.6 与型相对应的访问器
13.4.7 域的位置和准确式 GC
13.5 GC 标记- 压缩算法
13.5.1 GC 算法
13.5.2 启动 GC 的时机
13.5.3 GC 概要
13.6 标记阶段
13.6.1 标记阶段的概要
13.6.2 生成标记栈
13.6.3 标记根
13.6.4 标记对象
13.6.5 标记子对象
13.6.6 采用了标记栈的深度优先标记
13.6.7 标记栈的溢出
13.6.8 对象的标志位
13.7 压缩阶段
13.7.1 压缩阶段概要
13.7.2 (1) 设定 forwarding 指针
13.7.3 目标空间地址信息
13.7.4 map 地址信息
13.7.5 EncodeForwardingAddresses()
13.7.6 EncodeForwardingAddressesInRange()
13.7.7 EncodeForwardingAddressInPagedSpace()
13.7.8 (2) 更新指针
13.7.9 UpdatingVisitor
13.7.10 GetForwardingAddressInOldSpace()
13.7.11 (3) 移动对象
13.7.12 (4) 更新记录集
13.7.13 记录集的结构
13.7.14 RebuildRSets(
13.7.15 UpdateRSetVisitor
13.7.16 SetRSet()
13.8 Q&A
13.8.1 听说 V8 是在 Android 平台上运行的，是这样吗？
13.8.2 终结器是什么？
附录
附录 A 简单语言入门：Python 篇
附录 B 简单语言入门：Java 篇
附录 C 简单语言入门：Ruby 篇
附录 D 简单语言入门：JavaScript 篇
后记
参考文献

下载地址：https://www.wenjiangs.com/wp-content/uploads/2023/10/uyNqGxw1wiF2dN3Y.zip