书名：垃圾回收的算法与实现

    作者：[日] 中村成洋 相川光(著) 竹内郁雄(审校)

    译者：丁灵

    ISBN：978-7-115-42747-2

    本书由北京图灵文化发展有限公司发行数字版。版权所有，侵权必

    究。

    您购买的图灵电子书仅供您个人使用，未经授权，不得以任何方式复制

    和传播本书内容。

    我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

    如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐

    号等维权措施，并可能追究法律责任。

    图灵社区会员 云江月光石(flyingsky005@gmail.com) 专享 尊重版权版权声明

    审校者前言

    前言

    谢辞

    本书评论

    序章

    GC的定义

    垃圾的回收

    GC 要做两件事

    GC的好处

    没有 GC 的世界

    有 GC 的世界

    GC的历史

    GC 是一门古老的技术

    GC 是一门古老的技术

    引用计数法

    GC 复制算法

    50 年来，GC 的根本都没有改变

    未知的第四种算法

    为什么我们现在要学 GC

    GC—— 存在即合理

    多种多样的处理程序的实现

    留意内存空间的用法

    不会过时的技术

    更何况，GC 很有趣

    读者对象

    本书中的符号

    图中的箭头伪代码

    命名规则

    空指针和真假值

    函数

    缩进

    指针

    域

    for 循环

    栈与队列

    特殊的函数

    算法篇

    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.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.6 1 位引用计数法

    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 优点

    语言处理程序不依赖于 GC6.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.2 合并型引用计数法和 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 usedpools10.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 QA

    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 QA

    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 EncodeForwardingAddressesInRange13.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 QA

    13.8.1 听说 V8 是在 Android 平台上运行的，是这样吗？

    13.8.2 终结器是什么？

    附录

    附录 A 简单语言入门：Python 篇

    内置数据类型

    数值型

    序列型

    类

    附录 B 简单语言入门：Java 篇

    基本数据类型和引用类型

    数组

    类

    附录 C 简单语言入门：Ruby 篇

    全都是对象

    类

    附录 D 简单语言入门：JavaScript 篇

    基本数据类型和引用类型对象

    后记

    参考文献

    论文

    图书版权声明

    Garbage Collection-Algorithms and Implementations

    Copyright ? 2010 NARIHIRO NAKAMURA , HIKARI AIKAWA , IKUO

    TAKEUCHI

    All rights reserved.

    Chinese ( in simplified characters only ) translation rights arranged with

    NARIHIRO NAKAMURA , HIKARI AIKAWA , IKUO TAKEUCHI .

    Japan

    through CREEK RIVER Co., Ltd. and CREEK RIVER SHANGHAI

    Co., Ltd.

    本书中文简体字版由 NARIHIRO NAKAMURA , HIKARI AIKAWA ,IKUO TAKEUCHI 授权人民邮电出版社独家出版。未经出版者书面许

    可，不得以任何方式复制或抄袭本书内容。

    版权所有，侵权必究。审校者前言

    计算机的进步，特别是硬件的发展之快总是让我们感到惊讶。在这波不

    断向前涌动的洪流中，技术领域的浮沉也愈发激烈。本书涉及的垃圾回

    收(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 的人，首先就必须看两三篇有名的论文，之后还要

    去研究那些可能与其有关的原著。也就是说，从某种意义上而言，最后

    还是需要自己去想很多东西。

    尽管如此，还是有许多真心喜欢编程的人士，他们之中有一大群叫作

    GCLover 的人。因为 GC 基本上没有什么教科书，所以这群人之间似乎

    有着一种地下组织般的团队意识。总而言之，对他们来说，GC 是个非

    常有意思、充满乐趣的程序。你读过本书后就会明白，GC 算法会根据

    自动内存回收所需的环境(机器、语言、应用等)的不同而不同。到具

    体的程序层面，GC 则为程序员提供了一个最佳的游乐场所，令其尽情地发挥编程技巧，大展身手。事实上我也属于长年乐在其中的一份子。

    GC 这东西很麻烦，但却是必需的。它就像一个幕后英雄，默默地做着

    贡献，用户并不会期待它变得显眼。但因为它进行的是幕后工作，所以

    编程老手们或许会为之心动。

    如上所述，因为 Java 的出现，人们开始普遍认识到 GC 的可贵，自此多

    数的脚本语言都具备了 GC。看到这种情形，我这个跟 GC 拉拉扯扯了

    近 40 年的人真是感慨万千。虽然没有什么切实的根据，但是我一直认

    为，具备 GC 的语言要比不具备 GC 的同等语言生产效率高百分之三

    十。

    既然话说到这里了，我就再介绍一下我的个人看法吧。实际上，GC 相

    当于虚拟内存。一般的虚拟内存技术是在较小的物理内存的基础上，利

    用辅助存储创造一片看上去很大的“虚拟”地址空间。也就是说，GC 是

    扩大内存空间的技术，因此我称其为空间性虚拟存储。这样一来，GC

    就成了永久提供一次性存储空间的时间轴方向的时间性虚拟存储。神奇

    的是，比起称为“垃圾回收”，把 GC 称为“虚拟内存”令人感觉其重要了

    许多。当初人们根据计算机体系结构开发了许多关于空间性虚拟存储的

    支持，所以大部分的计算机都标配了空间性虚拟存储。只要硬件支持，GC 性能就能稳步提升，然而现实情况是几乎没有支持 GC 的硬件，这

    不能不令人感到遗憾。

    要说本书与涵盖面较广的 Garbage Collection 有什么不同，那就是本书

    涉及的面不那么广，但“算法篇”中对 GC 的基础内容进行了详实的讲

    解。另外，“实现篇”是本书的一大特色，其中解读了实际的 GC 代码。

    总体而言，本书作为一本教科书有着教育和现实意义。我作为本书审校

    者，全方位检查、琢磨了书中的内容，担保这是一本通俗易懂的书。我

    深信，本书作为一本 GC 专业图书，能让读者了解到 GC 是何物，体味

    到它的有趣之处以及它的重要性。

    如果能让更多读者了解到 GC 的重要性，那么由硬件和 OS 支持 GC 的

    真的时间性虚拟存储总有一天会实现吧。这就是我发自肺腑想说的话。

    开拓新技术的原石正在滚滚前进哦!

    东京大学情报理工学系研究科教授 竹内郁雄2010 年 2 月

    注意

    1. 本书是作者个人的研究成果。

    2. 本书内容已经过严格的审查和勘误，如发现内容缺失、错误等，请以

    书面形式联络出版方。

    3. 关于运用本书内容所造成的任何结果，作译者及出版社不承担与上述

    两项无关的责任，敬请谅解。

    4. 未经出版方书面许可，不得擅自盗印本书内容。

    关于商标

    本书中省略了 ?、?、? 等符号，敬请谅解。

    关于本书中涉及的程序名称、系统名称及 CPU 名称等，书中一律

    使用其最常用的称呼。

    一般情况下，本书中使用的程序名称、系统名称及 CPU 名称等为

    各公司的商标或注册商标。前言

    净是拿比自己弱的人当对手，不可能有意思。

    没有人能一看到谜题就瞬间解出答案。

    读到一半就知道犯人的推理小说真是无聊透顶。

    将自身能力发挥至极限去解开问题，这时才能把知识变成自己的东

    西。

    ——青木峰郎《Ruby 源代码完全解读》

    原书名为『Ruby ソースコード完全解説』(Ruby Hacking Guide)，目前尚无中文版。—译

    者注

    本书中涉及以下两个主题。

    1. GC 的算法(算法篇)

    2. GC 的实现(实现篇)

    在“算法篇”中，我们从众多的 GC 算法中严格挑选了一些重要的算法来

    介绍，包括传统算法和基本算法，以及稍微难一些的算法。“算法篇”最

    大的目的是让你了解 GC 独特的思维方式和各算法的特性。

    在“实现篇”中，你需要逐步阅读我们选择的语言处理程序的 GC 算法。

    因为我们在“算法篇”中扎实地学习了理论，所以需要在“实现篇”中检验

    一下能把理论运用到什么程度。

    特地设计“实现篇”还有一个目的，就是想让你亲身感受“理论和实现的

    不同”。要成功实现，不仅要使用 GC 算法，还要在细节上下很多功

    夫，以与硬件环境和语言功能相协调。通过学习更有实践性意义的知

    识，希望能进一步加你对 GC 的理解。

    此外，随着深入阅读 GC，你会有另一种惊喜，即加深了对语言处理程

    1

    1序的认识。语言处理程序是由数万行代码群构成的巨大程序。在阅读这

    样巨大的程序时，如果没有一个明确的目标，那么就很难继续往下读。

    这就好比挖坑，如果往深处挖，坑的直径就会自然而然地扩大。同理，如果我们去深入理解某一点，那么也就会逐渐理解其整体。“实现篇”就

    是在持续挖掘 GC 这个深坑。我们深信，这项工作有助于加深我们对语

    言处理程序的整体理解。

    中村成洋、相川光

    2010 年 1 月谢辞

    来自二位笔者的谢辞

    首先要感谢本书中参考的论文和图书的作者，以及本书中引用的源代码

    的编写者。

    感谢以下阅读本书原稿，给出众多评论的人士：

    齐藤 tadashi、中川真宏、三浦英树、k.inaba、mokehehe(按五十音和字

    母顺序排列)。

    上述人士也在“本书评论”中有所赠言。

    感谢来自东京大学(2010 年 2 月)的本书审校者竹内郁雄教授。竹内

    教授痛快地接下了本书审校的工作，还给予了我们很多意见。感谢

    Ruby 的设计者松本行弘先生为本书所做的推荐。此外，还要感谢秀和

    SYSTEM 株式会社第二出版编辑部的各位，特别是本书的编辑 K。

    来自中村成洋的谢辞

    感谢在笔者写作第 12 章时，通过邮件列表热心回答笔者问题的 Evan

    Phoenix。

    感谢在我小时候给我买了昂贵的 PC 的妈妈。感谢喜欢新事物但已故去

    的爸爸。感谢同爸爸一样喜欢新事物的哥哥。感谢与我一起成长的伙伴

    们。

    来自相川光的谢辞

    在此向京都大学的汤浅太一老师致以谢意，是您令我邂逅了 GC。

    在此对东京大学的本位田真一教授和本位田研究室的各位致以诚挚的感

    谢。感谢各位在本书执笔期间给予的全面支持。

    从心底感谢远在滋贺县、一直温柔守护我的爸爸妈妈以及妹妹。本书评论

    在这里，我们请阅读过本书原稿的人士发表了一下他们对本书的看法，如下所示(姓名按五十音顺序和字母顺序排列，敬称略去)。

    齐藤 Tadashi

    我是个门外汉，所以刚开始还挺担心自己能不能理解呢!不过书中的讲

    解十分细致，作者把每个知识点都掰开嚼碎了，让我非常享受这个学习

    过程。非常期待中村和相川两位老师的下一部作品。

    中川真宏

    大都都管我叫 D 语言传教士，我每天都在想着怎么改变一下 D 语言。

    就在这时，我遇见了这本书。这本书肯定能教会每个人创建自己的

    GC。大家也不妨试试做出自己的 GC，享受精彩的编程生活吧!

    三浦英树

    我是一名喜欢 Lisp 和 Ruby 的水管工，喜欢写语言处理程序，在学生时

    代就写过 GC 标记 - 清除算法和 GC 复制算法。不过太迟了，非常遗憾

    当年没有出现这本书，没能知道其中介绍的各种各样的技巧!通过本书

    我学到了非常多的东西!

    k.inaba

    我喜欢 Code Golf 和编程竞赛，是一个代码玩家。关于 GC，我只知道

    一些基本理论，于是就战战兢兢地凭着对 GC 的一点了解阅读了本书原

    稿。然后我发现，通过基本算法知识的积累，慢慢就能理解一般语言处

    理程序中使用的具有一定规模的 GC 源代码了。体会到这一点的时候别

    提有多开心了!

    代码高尔夫，计算机编程竞赛的一种，参加者要尽可能用最短的源代码描述给出的算法。—

    译者注

    mokehehe

    1

    1刚开始我半信半疑地试着用了下 GC，然后就交到了女朋友!我已经没

    法想象没有 GC 的日子了!我要把这份喜悦分享给大家!序章

    在序章中，我们将对什么是 GC、GC 的历史、学习 GC 的目的进行简

    要说明。此外还将说明阅读本书时的注意事项。GC的定义

    GC 是 Garbage Collection 的简称，中文称为“垃圾回收”。

    垃圾的回收

    Garbage Collection 的 Garbage，也就是“垃圾”，具体指的是什么呢？

    在现实世界中，说到垃圾，指的就是那些不读的书、不穿的衣服等。这

    种情况下的“垃圾”指的是“自己不用的东西”。

    在 GC 中，“垃圾”的定义也是如此。GC 把程序不用的内存空间视为垃

    圾。关于“垃圾”的详细介绍，我们会在 1.5 节进行阐述。

    GC 要做两件事

    GC 要做的有两件事。

    1. 找到内存空间里的垃圾

    2. 回收垃圾，让程序员能再次利用这部分空间

    满足这两项功能的程序就是 GC。GC的好处

    GC 到底会给程序员带来怎样的好处呢？

    没有 GC 的世界

    在没有 GC 的世界里，程序员必须自己手动进行内存管理，必须清楚地

    确保必要的内存空间，释放不要的内存空间。

    程序员在手动进行内存管理时，申请内存尚不存在什么问题，但在释放

    不要的内存空间时，就必须一个不漏地释放。这非常地麻烦。

    如果忘记释放内存空间，该内存空间就会发生内存泄露 ，即无法被使

    用，但它又会持续存在下去。如果将发生内存泄露的程序放着不管，总

    有一刻内存会被占满，甚至还可能导致系统崩溃。

    内存泄露：内存空间在使用完毕后未释放。

    另外，在释放内存空间时，如果忘记初始化指向释放对象的内存空间的

    指针，这个指针就会一直指向释放完毕的内存空间。因为这个指针没有

    指向有效的内存空间，处于一种悬挂的状态，所以我们称其为“悬垂指

    针”(dangling pointer)。如果在程序中错误地引用了悬垂指针，就会产

    生无法预期的 BUG。此外，悬垂指针也会导致严重的安全漏洞 。

    2009 年 IE67 的零日漏洞曾轰动一时。——译者注

    更有甚者，还可能会出现错误释放了使用中的内存空间的情况。一旦错

    误释放了使用中的内存空间，下一次程序使用此空间时就会发生故障。

    大多数情况下会发生段错误，运气不好的话还可能引发恶性 BUG。

    上述这样与内存相关的 BUG，其共通之处在于“难以确定 BUG 的原

    因”。我们都知道，与内存相关的 BUG 的潜在场所和 BUG 出现的场所

    在位置上(或者是时间上)不一致，所以很难确定 BUG 的原因。

    有 GC 的世界

    1

    1

    2

    2为了省去上述手动内存管理的麻烦，人们钻研开发出了 GC。如果把内

    存管理交给计算机，程序员就不用去想着释放内存了。

    在手动内存管理中，程序员要判断哪些是不用的内存空间(垃圾)，留

    意内存空间的寿命。但只要有 GC 在，这一切都可以交给 GC 来做。

    有了 GC，程序员就不用再去担心因为忘了释放内存等而导致 BUG，从

    而大大减轻了负担。也不用再去头疼费事的内存管理。GC 能让程序员

    告别恼人的内存管理，把精力集中在更本质的编程工作上。GC的历史

    GC 是一门古老的技术

    据笔者所知，GC 因为 Java 的发布而一举成名，所以很多人可能会认为

    GC 是最近才有的技术。不过 GC 有着非常久远的历史，最初的 GC 算

    法是 John McCarthy 在 1960 年发布的。

    GC 是一门古老的技术

    John McCarthy 身为 Lisp 之父和人工智能之父，是一名非常有名的黑

    客，事实上他同时也是 GC 之父(多么伟大的黑客啊)。

    1960 年，McCarthy 在其论文

    [1]

    中首次发布了 GC 算法。

    当然，当时还没有 Garbage Collection 这个词。证据就在这篇论文的脚

    注之中，如下所示。

    我们把这个功能称为Garbage Collection。

    但是我们没有在这篇论文中用到这个名称。

    要是我想用，恐怕咬文嚼字研究所的女士们都会过来阻拦我吧。

    给人感觉很青涩呢。

    在这篇论文中发布的算法，就是现在我们所说的 GC 标记 - 清除算法。

    引用计数法

    1960 年，George E. Collins 在论文

    [6]

    中发布了叫作引用计数的 GC 算

    法。

    当时 Collins 可能没有注意到，引用计数法有个缺点，就是它不能回

    收“循环引用” 。Harold McBeth

    [26]

    在 1963 年指出了这个缺点。 3

    3循环引用：两个及两个以上对象循环互相引用。详细内容请参考第 3 章。

    GC 复制算法

    1963 年，也有“人工智能之父”之称的 Marvin L. Minsky 在论文

    [7]

    中发

    布了复制算法。

    GC 复制算法把内存分成了两部分，这篇论文中将第二部分称为磁带存

    储空间。不得不说带有浓烈的时代色彩。

    50 年来，GC 的根本都没有改变

    从 50 年前 GC 算法首次发布以来，众多研究者对其进行了各种各样的

    研究，因此许多 GC 算法也得以发布。

    但事实上，这些算法只不过是把前文中提到的三种算法进行组合或应

    用。也可以这么说，1963 年 GC 复制算法诞生时，GC 的根本性内容就

    已经完成了。

    未知的第四种算法

    现在为世人所知的 GC 算法，不过是从之前介绍的三种基本算法中衍生

    出来的产物。

    本书中除了细致介绍这些基本的 GC 算法，还会介绍应用到它们的 GC

    算法。把这些算法全看完后，请跟笔者一起，就 GC 的课题进行思考。

    也许发现全新的第四种基本算法的人，就是你。

    3为什么我们现在要学 GC

    为什么我们现在有必要学习 GC 的原理？有以下几个原因。

    GC—— 存在即合理

    现在我们使用的多数编程语言都搭载有 GC。以下是几个具体的例子。

    Lisp

    Java

    Ruby

    Python

    Perl

    Haskell

    大家有没有使用过其中的某种编程语言呢？如果使用过，当时应该也在

    不知不觉中获得了 GC 带来的好处。

    对编程语言来说，GC 就是一个无名英雄，默默地做着贡献。打个比

    方，天鹅在水面优雅地游动时，实际上脚蹼却在水下拼命地划着水。

    GC 也是如此。在由编程语言构造的美丽的源代码这片水下，GC 在拼

    命地将垃圾回收再利用。

    如上所述，GC 是语言处理程序中非常重要的一部分，相当于树荫。应

    该有很多人感觉“GC 帮忙回收垃圾是理所当然”的吧？

    GC 基本上是高负载处理，需要花费一定的时间。打个比方，当编写像

    动作游戏这样追求即时性的程序时，就必须尽量压低 GC 导致的最大暂

    停时间。如果因为 GC 导致玩家频繁卡顿，相信谁都会想摔手柄。碰到

    这种应用，我们就需要选择最大暂停时间较短的 GC 算法了。

    再打个比方，对音乐和动画这样类似于编码应用的程序来说，GC 的最大暂停时间就不那么重要了。更为重要的是，我们必须选择一个整体处

    理时间更短的算法。

    笔者深信，事先知道“这个 GC 算法有这样的特征，所以它适合这个应

    用”对程序员来说很有价值。

    如果我们不理所当然地去利用 GC，而是去了解其内部情况，自己来评

    价 GC 算法，那么自身的编程水平就一定会得到提高吧。

    多种多样的处理程序的实现

    近年来，随着编程语言的发展，燃起了一股发布语言处理程序的势头，这些语言处理程序都搭载有不同的 GC 算法。作为语言处理程序的关键

    功能，很多人将采用了优秀的 GC 算法作为一大卖点。

    GC 性能在语言处理程序的性能评价中也是一大要素。为了正确评价

    GC 的性能，对 GC 算法的理解是不可或缺的。

    留意内存空间的用法

    应该有不少人是通过使用搭载 GC 的编程语言来学习编程的吧。本书的

    作者之一中村也是如此，他最初接触的编程语言是 Java。

    可以说在用 Java 语言编写程序时完全不用留意内存空间的用法。当然

    这也是多亏了 GC，这是好事，但太不留心也会招致麻烦。

    例如，有时会出现无意中把内存空间挥霍一空的情况。比如在循环中生

    成一些没用的对象等。

    这是因为没有把握好编程语言背后的内存管理的概念。

    本书中以具体的编程语言为例，来说明编程语言中所使用的内存空间的

    结构，以及 GC 的运行。通过阅读本书，我们就能在编程中留意内存空

    间的用法了。

    不会过时的技术

    GC 自 1960 年发布以来，一直在吸引着顶尖工程师们的目光。笔者确信，只要计算机构造不发生根本性的改变，GC 就是一门不会过时的技

    术。对程序员来说，比起学习日新月异的最新技术，学习 GC 这样的古

    典技术不是更幸福吗？

    更何况，GC 很有趣

    说实话，其实笔者自己学习 GC 的时候，并没有想过上述这些略复杂的

    事情。现在回过头觉得学了 GC 真好，也只是因为它具备前面那些优点

    而已。

    为什么当初要学 GC 呢？对笔者而言，之所以会学习 GC 的算法和实

    现，纯粹是觉得有趣。

    笔者小时候就喜欢拆点什么东西，看看里面是怎样的。电视机、收音

    机、红白机什么的都拆了个遍。平时也喜欢研究那些看似理所当然地在

    运转的机器，看看它们的内部如何。笔者至今都还记得看到其内部时的

    快感，以及了解其构造时的感动。

    或许学习 GC 也差不多是这样。对笔者来说，研究 GC 这种理所当然存

    在的东西，看看它的内部，这是一件非常刺激的事。

    本书中饱含了笔者在看到 GC 的内部时生出的“感动”。读完本书后，相

    信你心中的疑问——“为什么要学 GC ？”也一定会转化成感动，发自内

    心地认为“GC 真有趣!”。读者对象

    本书由两部分构成。

    1. 算法篇

    2. 实现篇

    在“算法篇”中，我们没有必要去详细了解特定的编程语言，你只要能用

    任何一种语言编程，就能往下读“算法篇”。

    阅读“实现篇”需要具备 C 和 C++ 的知识。只要会用 C 的函数指针、C++ 的模板，阅读“实现篇”就没有什么障碍。关于 GC 算法的知识，读

    完本书的“算法篇”就相当够用了。

    另一方面，对于“实现篇”中涉及的各种编程语言，最好有一定程度的了

    解，那样阅读起来会比较轻松。关于本书涉及的编程语言，在本书

    的“附录”部分中略有介绍。本书中的符号

    图中的箭头

    本书的插图中会出现各种各样的箭头。关于本书中主要使用的箭头，请

    参考图 1。

    图 1 箭头的样式

    箭头 (a) 表示引用关系，用于从根到对象的引用等。

    箭头 (b) 表示赋值操作和转移操作，用于给变量赋值、复制对象、转移

    对象等。

    箭头 (c) 表示处理流程，用于流程图和函数调用等。

    箭头 (d) 表示时间的经过。

    箭头 (e) 表示继承关系，主要会在“实现篇”的类图中出现。伪代码

    为了帮助读者理解 GC 算法，本书采用伪代码进行解说。关于用到的伪

    代码，本书后文中会对其表示法进行说明。

    本书用到的伪代码，其基本语法跟一般编程语言很像。因此读者可以直

    观地理解本书中出现的众多伪代码。

    命名规则

    变量以及函数都用小写字母表示(例：obj)。常量都用大写字母表示

    (例：COPIED)。另外，本书采用下划线连接两个及两个以上的单词

    (例：free_list、update_ptr、HEAP_SIZE)。

    空指针和真假值

    设真值为 TRUE，假值为 FALSE。拥有真假值的变量 var 的否定为!var。

    除此之外，本书用 NULL 表示没有指向任何地址的指针。

    函数

    本书采用与一般编程语言相同的描述方法来定义函数。例如，我们将以

    arg1、arg2 为参数的函数 func 定义如下。

    1 func(arg1, arg2){

    2 ...

    3 }

    当我们以整数 100 和 200 为实参调用该函数时，即为

    func(100,200)。

    缩进

    我们将缩进也算作语法的一部分。例如像下面这样，用缩进表示 if 语

    句的作用域。1 if(test == TRUE)

    2 a = 1

    3 b = 2

    4 c = 3

    5 d = 4

    在上面的例子中，只有当 test 为真的时候，才会执行第 2 行到第 4

    行。第 5 行与 test 的值没有关系，所以一定会被执行。此外，我们把

    缩进长度设为两个空格。

    指针

    在 GC 算法中，指针是不可或缺的。我们用星号()访问指针所引用

    的内存空间。例如我们把指针 ptr 指向的对象表示为 ptr。

    域

    我们可以用 obj.field 访问对象 obj 的域 field。例如，我们要想在

    对象 girl 的各个域 name、age、job 中分别代入值，可按如下书写。

    1 girl.name = Hanako

    2 girl.age = 30

    3 girl.job = lawyer

    for 循环

    我们在给整数增量的时候使用 for 循环。例如用变量 sum 求 1 到 10 的

    和时，代码如下所示。

    1 sum = 0

    2 for(i : 1..10)

    3 sum += i

    for 循环也用来访问数组元素。例如，想把函数 do_something 应用

    在数组 array 中包含的所有元素中时，我们可以用 for(变量：集合)

    的形式来按顺序访问全部元素。1 for(obj : array)

    2 do_something(obj)

    当然，也可以像下面这样把 index 作为下标(整数 N 是数组 array 的

    长度)。和 C 语言等编程语言一样，数组的下标都从 0 开始。

    1 for(index : 0..(N-1))

    2 do_something(array[index])

    栈与队列

    GC 中经常用到栈和队列等数据结构。栈是一种将后进入的数据先取出

    的数据结构，即 FILO(First-In Last-Out)。与其相反，队列是将先进

    入的数据先取出的数据结构，即 FIFO(First-In First-Out)。

    我们分别用 push 函数和 pop 函数将数据压栈(push)和出栈

    (pop)。用 push(stack, obj) 向栈 stack 中压入对象 obj。用

    pop(stack) 从 stack 中取出数据，并将此数据作为返回值。另外，我

    们用 is_full(stack) 检查 stack 是否为满，用 is_empty(stack) 检

    查 stack 是否为空，并返回真假值。

    另一方面，我们用 enqueue 函数和 dequeue 函数来向队列内添加

    (enqueue)以及取出(dequeue)数据，用 enqueue(queue, data) 来

    向队列 queue 中添加数据 data，用 dequeue(queue) 来从 queue 取出

    并返回数据。

    特殊的函数

    除了以上介绍的函数之外，我们还有两个在伪代码中出现的特殊函数。

    首先是 copy_data 函数，它是复制内存区域的函数。我们用

    copy_data(ptr1, ptr2, size) 把 size 个字节的数据从指针 ptr2

    指向的内存区域复制到 ptr1 指向的内存区域。这个函数跟 C 语言中的

    memcpy 函数用法相同。

    swap 函数是替换两个变量值的函数。我们用 swap(var1, var2) 来替换变量 var1 和变量 var2 的值。算法篇1 学习 GC 之前

    本章中将为各位说明 GC 中的基本概念。1.1 对象 头 域

    对象这个词，在不同的使用场合其意思各不相同。比如，在面向对象编

    程中，它指“具有属性和行为的事物”，然而在 GC 的世界中，对象表示

    的是“通过应用程序利用的数据的集合”。

    对象配置在内存空间里。GC 根据情况将配置好的对象进行移动或销毁

    操作。因此，对象是 GC 的基本单位。本书中的所有“对象”都表示这个

    含义。

    一般来说，对象由头(header)和域(field)构成。我们下面将对其逐

    一说明。

    1.1.1 头

    我们将对象中保存对象本身信息的部分称为“头”。头主要含有以下信

    息。

    对象的大小

    对象的种类

    如果不清楚对象的大小和种类，就会发生问题，例如无法判别内存中存

    储的对象的边界。因此头对 GC 来说非常重要。

    此外，头中事先存有运行 GC 所需的信息。然而根据 GC 算法的不同，信息也不同。

    比如将在第 2 章中介绍的 GC 标记 - 清除算法，就是在对象的头部中设

    置 1 个 flag(标志位)来记录对象是否已标记，从而管理各个对象。

    因为任何 GC 算法中都会用到对象大小和种类的信息，所以本书就不专

    门在图中将其标记出来了。另一方面，我们会将标志位等算法特有的信

    息作为对象的一部分明确写出。

    1.1.2 域我们把对象使用者在对象中可访问的部分称为“域”。可以将其想成 C 语

    言中结构体的成员，这样就很简单了吧。对象使用者会引用或替换对象

    的域值。另一方面，对象使用者基本上无法直接更改头的信息。

    域中的数据类型大致分为以下 2 种。

    指针

    非指针

    指针是指向内存空间中某块区域的值。用 C 语言和 C++ 语言编程过的

    读者对它应该很熟悉了吧。即使是像 Java 这样语言使用者没有明确用

    到指针的编程语言，语言处理程序内部也用到了指针。关于指针，我们

    在 1.2 节中再详细介绍。

    非指针指的是在编程中直接使用值本身。数值、字符以及真假值都是非

    指针。

    在对象内部，头之后存在 1 个及 1 个以上的域。在“算法篇”中，对象、头以及域的关系如图 1.1 所示。

    图 1.1 对象、头以及域

    为了更简单地向大家说明，我们事先把“算法篇”中域的大小全设成 1 个

    字 。

    字是计算机进行数据处理和运算的单位。字由若干字节构成，字的位数叫作字长，不同档次

    的机器有不同的字长。例如一台 8 位机的字长为 8 位，一台 16 位机的字长为 16 位。

    1

    1此外在伪代码中，可以用 obj.field1、obj.field2 …… 来从头按顺

    序访问对象 obj 的 各个域。1.2 指针

    通过 GC，对象会被销毁或保留。这时候起到关键作用的就是指针。因

    为 GC 是根据对象的指针指向去搜寻其他对象的。另一方面，GC 对非

    指针不进行任何操作。

    在这里有两点需要我们注意。

    首先，要注意语言处理程序是否能判别指针和非指针。要判别指针和非

    指针需要花费一定的功夫，关于这一点我们会在第 6 章详细说明。除第

    6 章之外，在“算法篇”的各个章节中，我们都以 GC 可判别对象各域中

    的值是指针还是非指针为前提进行解说。

    另一点是指针要指向对象的哪个部分。指针如果指向对象首地址以外的

    部分，GC 就会变得非常复杂。在大多数语言处理程序中，指针都默认

    指向对象的首地址。因为存在这个制约条件，不仅是 GC，就连语言处

    理程序的其他各种处理都变得简单了。因此我们在“算法篇”中也以此条

    件为前提。

    在“算法篇”中，对象和指针的关系如图 1.2 所示。图 1.2 对象和指针

    在此我们把图 1.2 中的 B 和 C 称为 A 的子对象。对某个对象的子对象

    进行某项处理是 GC 的基本操作。在“算法篇”的伪代码部分，我们用

    children(obj) 获取指向对象 obj 的子对象的指针数组。使用这个

    children 函数，我们可以把遍历子对象的操作写得简单一些。打个

    比方，我们假设执行了以下代码来处理图 1.2 的情况。

    1 for(child : children(A))

    2 func(child)

    此时，对象 B、C 依次作为实参调用 func 函数。1.3 mutator

    mutator 是 Edsger Dijkstra

    [15]

    琢磨出来的词，有“改变某物”的意思。说

    到要改变什么，那就是 GC 对象间的引用关系。不过光这么说可能大家

    还是不能理解，其实用一句话概括的话，它的实体就是“应用程序”。这

    样说就容易理解了吧。GC 就是在这个 mutator 内部精神饱满地工作

    着。

    mutator 实际进行的操作有以下 2 种。

    生成对象

    更新指针

    mutator 在进行这些操作时，会同时为应用程序的用户进行一些处理

    (数值计算、浏览网页、编辑文章等)。随着这些处理的逐步推进，对

    象间的引用关系也会“改变”。伴随这些变化会产生垃圾，而负责回收这

    些垃圾的机制就是 GC。1.4 堆

    堆指的是用于动态(也就是执行程序时)存放对象的内存空间。当

    mutator 申请存放对象时，所需的内存空间就会从这个堆中被分配给

    mutator。

    GC 是管理堆中已分配对象的机制。在开始执行 mutator 前，GC 要分配

    用于堆的内存空间。一旦开始执行 mutator，程序就会按照 mutator 的要

    求在堆中存放对象。等到堆被对象占满后，GC 就会启动，从而分配可

    用空间。如果不能分配足够的可用空间，一般情况下我们就要扩大堆。

    然而，为了让读者能更容易理解，在“算 法篇”中 我们把堆的大小固定

    为常量 HEAP_SIZE，不会进行扩大。此外，我们把 heap_start 定为

    指向堆首地址的指针，把 heap_end 定为指向堆末尾下一个地址的指

    针。也就是说，heap_end 等于 heap_start + HEAP_SIZE。

    此外，本书中将如图所示的堆的左侧设为内存的低地址，右侧设为高地

    址。

    HEAP_SIZE、heap_start 和 heap_end 的关系如图 1.3 所示。

    图 1.3 堆1.5 活动对象 非活动对象

    我们将分配到内存空间中的对象中那些能通过 mutator 引用的对象称

    为“活动对象”。反过来，把分配到堆中那些不能通过程序引用的对象称

    为“非活动对象”。也就是说，不能通过程序引用的对象已经没有人搭理

    了，所以死掉了。死掉的对象(即非活动对象)我们就称为“垃圾”。

    这里需要大家注意的是：死了的对象不可能活过来。因为就算 mutator

    想要重新引用(复活)已经死掉的对象，我们也没法通过 mutator 找到

    它了。

    因此，GC 会保留活动对象，销毁非活动对象。当销毁非活动对象时，其原本占据的内存空间会得到解放，供下一个要分配的新对象使用。

    图 1.4 活动对象和非活动对象1.6 分配

    分配(allocation)指的是在内存空间中分配对象。当 mutator 需要新对

    象时，就会向分配器(allocator)申请一个大小合适的空间。分配器则

    在堆的可用空间中找寻满足要求的空间，返回给 mutator。

    像 Java 和 Ruby 这些配备了 GC 的编程语言在生成实例时，会在内部进

    行分配。另一方面，因为 C 语言和 C++ 没有配备 GC，所以程序员要使

    用 malloc 函数和 new 运算符等进行手动分配。

    然而，当堆被所有活动对象占满时，就算运行 GC 也无法分配可用空

    间。这时候我们有以下两种选择。

    1. 销毁至今为止的所有计算结果，输出错误信息

    2. 扩大堆，分配可用空间

    之前在 1.4 节中也讲过，为了让本书的“算法篇”更易懂，这里我们选择

    第 1 个选项。我们将在伪代码中用 allocation_fail 函数进行第 1

    项的处理。

    不过，在现实的执行环境中选择第 2 项会更贴合实际。因为我们必须尽

    可能地避免因内存不足造成的程序停止。在内存空间大小没有特殊限制

    的情况下，应该扩大堆。1.7 分块

    分块(chunk)在 GC 的世界里指的是为利用对象而事先准备出来的空

    间。

    初始状态下，堆被一个大的分块所占据。

    然后，程序会根据 mutator 的要求把这个分块分割成合适的大小，作为

    (活动)对象使用。活动对象不久后会转化为垃圾被回收。此时，这部

    分被回收的内存空间再次成为分块，为下次被利用做准备。也就是说，内存里的各个区块都重复着分块→活动对象→垃圾(非活动对象)→分

    块→ …… 这样的过程。1.8 根

    根(root)这个词的意思是“根基”“根底”。在 GC 的世界里，根是指向

    对象的指针的“起点”部分。

    这些都是能通过 mutator 直接引用的空间。举个例子，请看下面的伪代

    码。

    1 obj = Object.new

    2 obj.field1 = Object.new

    在这里 obj 是全局变量。首先，我们在第 1 行分配一个对象(对象

    A)，然后把 obj 代入指向这个对象的指针。在第 2 行我们也分配一

    个对象(对象 B)，然后把 obj.field1 代入指向这个对象的指针。

    在执行完第 2 行后，全局变量空间及堆如图 1.5 所示。

    图 1.5 全局变量空间及堆的示意图

    在这里我们可以使用 obj 直接从伪代码中引用对象 A，也就是说 A 是活动对象。此外，因为可以通过 obj 经由对象 A 引用对象 B，所以对

    象 B 也是活动对象。因此 GC 必须保护这些对象。

    GC 把上述这样可以直接或间接从全局变量空间中引用的对象视为活动

    对象。

    与全局变量空间相同，我们也可以通过 mutator 直接引用调用栈(call

    stack)和寄存器。也就是说，调用栈、寄存器以及全局变量空间都是

    根。

    但在这里我们必须注意一点，那就是 GC 在一般情况下无法严谨地判断

    寄存器和调用栈中的值是指针还是非指针。关于这一点会在第 6 章详细

    说明。为了判断根中的指针，我们需要下点功夫。

    在这里介绍怎么去判断未免太费口舌。所以在“算法篇”，我们先暂

    定“GC 可以严谨判断根中的指针和非指针”。这跟 1.2 节的前提相同。

    在“算法篇”中，根如图 1.6 所示。

    图 1.6 根和堆里的对象此外，我们将伪代码中有根的指针数组表示为 roots。也就是说，像

    下面这样编写，就能依次把所有由根引用的对象作为 func 函数的参

    数。

    1 for(r : roots)

    2 func(r)1.9 评价标准

    评价 GC 算法的性能时，我们采用以下 4 个标准。

    吞吐量

    最大暂停时间

    堆使用效率

    访问的局部性

    下面我们逐一进行说明。

    1.9.1 吞吐量

    从一般意义上来讲，吞吐量(throughput)指的是“在单位时间内的处理

    能力”，这点在 GC 的世界中也不例外。

    请参照图 1.7 的示例。

    图 1.7 mutator 和 GC 的执行示意图

    在 mutator 整个执行过程中，GC 一共启动了 3 次，我们把花费的时间

    分别设为 A、B、C。也就是说，GC 总共花费的时间为(A + B +

    C)。另一方面，我们前面提到过，以 GC 为对象的堆大小是

    HEAP_SIZE。也就是说，在大小为 HEAP_SIZE 的堆进行内存管理，要花费的时长为(A + B + C)。因此，这种情况下 GC 的吞吐量为

    HEAP_SIZE (A + B + C)。

    当然，人们通常都喜欢吞吐量高的 GC 算法。然而判断各算法吞吐量的

    好坏时不能一概而论。

    打个比方，众所周知 GC 复制算法和 GC 标记 - 清除算法相比，活动对

    象越少吞吐量越高。这是因为 GC 复制算法只检查活动对象，而 GC 标

    记 - 清除算法则会检查所有的活动和非活动对象。

    然而，随着活动对象的增多，各 GC 算法表现出的吞吐量也会相应地变

    化。极端情况下，甚至会出现 GC 标记 - 清除算法比 GC 复制算法表现

    的吞吐量更高的情况。

    也就是说，即便是同一 GC 算法，其吞吐量也是受 mutator 的动作左右

    的。评价 GC 算法的吞吐量时，有必要把 mutator 的动作也考虑在内。

    1.9.2 最大暂停时间

    本书“算法篇”中介绍的所有 GC 算法，都会在 GC 执行过程中令 mutator

    暂停执行。最大暂停时间指的是“因执行 GC 而暂停执行 mutator 的最长

    时间”。这么说可能比较难理解，请再看一遍图 1.7。最大暂停时间是 A

    ～C 的最大值，也就是 B。

    那么，我们在何种情况下需要重视此种指标呢？

    典型例子是两足步行的机器人。如果在其步行过程中启动 GC，我们对

    机器人的控制就会暂时中断，直到 GC 执行完毕方可重启。也就是说，在这期间机器人完全不能运作。很显然，机器人会摔倒。

    再举个例子，Web 浏览器会如何呢？如果在浏览 Web 网页的时候发生

    GC，浏览器就会看似卡住，带给用户心理负担。像 Web 浏览器这样的

    GUI 应用，大多数都是以人机交互为前提的，所以我们不希望执行过程

    中长时间受到 GC 的影响。

    这种情况下就需要缩短最大暂停时间。然而不管尝试哪种 GC 算法，我

    们都会发现较大的吞吐量和较短的最大暂停时间不可兼得。所以应根据

    执行的应用所重视的指标的不同，来分别采用不同的 GC 算法。1.9.3 堆使用效率

    根据 GC 算法的差异，堆使用效率也大相径庭。左右堆使用效率的因素

    有两个。

    一个是头的大小，另一个是堆的用法。

    首先是头的大小。在堆中堆放的信息越多，GC 的效率也就越高，吞吐

    量也就随之得到改善。但毋庸置疑，头越小越好。因此为了执行 GC，需要把在头中堆放的信息控制在最小限度。

    其次，根据堆的用法，堆使用效率也会出现巨大的差异。举个例子，GC 复制算法中将堆二等分，每次只使用一半，交替进行，因此总是只

    能利用堆的一半。相对而言，GC 标记 - 清除算法和引用计数法就能利

    用整个堆。

    撇开这个不说，因为 GC 是自动内存管理功能，所以过量占用堆就成了

    本末倒置。与吞吐量和最大暂停时间一样，堆使用效率也是 GC 算法的

    重要评价指标之一。

    然而，堆使用效率和吞吐量，以及最大暂停时间不可兼得。简单地说就

    是：可用的堆越大，GC 运行越快；相反，越想有效地利用有限的堆，GC 花费的时间就越长。

    1.9.4 访问的局部性

    PC 上有 4 种存储器，分别是寄存器、缓存、内存、辅助存储器。它们

    之间有着如图 1.8 所示的层级关系。图 1.8 存储器的层级构造

    众所周知，越是可实现高速存取的存储器容量就越小。毫无疑问，我们

    都希望尽可能地利用较高速的存储器，但由于高速的存储器容量小，因

    此通常不可能把所有要利用的数据都放在寄存器和缓存里。一般我们会

    把所有的数据都放在内存里，当 CPU 访问数据时，仅把要使用的数据

    从内存读取到缓存。与此同时，我们还将它附近的所有数据都读取到缓

    存中，从而压缩读取数据所需要的时间。

    另一方面，具有引用关系的对象之间通常很可能存在连续访问的情况。

    这在多数程序中都很常见，称为“访问的局部性”。考虑到访问的局部

    性，把具有引用关系的对象安排在堆中较近的位置，就能提高在缓存中

    读取到想利用的数据的概率，令 mutator 高速运行。想深入了解访问的

    局部性的读者，请参考《计算机组成与设计：硬件、软件接口》[29]。

    有些 GC 算法会根据引用关系重排对象，例如在第 4 章中提到的 GC 复

    制算法等。2 GC 标记-清除算法

    世界上首个值得纪念的 GC 算法是 GC 标记 - 清除算法(Mark Sweep

    GC)[1]。自其问世以来，一直到半个世纪后的今天，它依然是各种处

    理程序所用的伟大的算法。2.1 什么是 GC 标记- 清除算法

    就如它的字面意思一样，GC 标记 - 清除算法由标记阶段和清除阶段构

    成。标记阶段是把所有活动对象都做上标记的阶段。清除阶段是把那些

    没有标记的对象，也就是非活动对象回收的阶段。通过这两个阶段，就

    可以令不能利用的内存空间重新得到利用。首先，标记 - 清除算法的伪

    代码如代码清单 2.1 所示。

    代码清单 2.1：mark_sweep 函数

    1 mark_sweep{

    2 mark_phase

    3 sweep_phase

    4 }

    确实分成了标记阶段和清除阶段。接下来我们就对各个阶段进行说明。

    在之后的说明中，我们都以对图 2.1 中的堆执行 GC 为前提。

    图 2.1 执行 GC 前堆的状态2.1.1 标记阶段

    我们用 mark_phase 函数来进行标记阶段的处理。

    代码清单 2.2：mark_phase 函数

    1 mark_phase{

    2 for(r : roots)

    3 mark(r)

    4 }

    非常简单明了吧。在标记阶段中，collector 会为堆里的所有活动对象打

    上标记。为此，我们首先要标记通过根直接引用的对象。这里的“对

    象”就是我们在 1.8 节中讲到的“确实活动着的对象”。首先我们标记这样

    的对象，然后递归地标记通过指针数组能访问到的对象。这样就能把所

    有活动对象都标记上了。

    第 3 行出现的 mark 函数的定义如代码清单 2.3 所示。

    代码清单 2.3：mark 函数

    1 mark(obj){

    2 if(obj.mark == FALSE)

    3 obj.mark = TRUE

    4 for(child : children(obj))

    5 mark(child)

    6 }

    在第 2 行中，检查作为实参传递的 obj 是否已被标记。在引用中包含了

    循环等的情况下，即使对已被标记的对象，有时程序也会调用 mark

    函数。出现类似这种情况的时候，我们就要避免重复进行标记处理。

    如果标记未完成，则程序会在对象的头部进行置位操作。这个位要分配

    在对象的头之中，并且能用 obj.mark 访问。意思是若 obj.mark 为

    真，则表示对象已标记；若 obj.mark 为假，则对象没有被标记。图 2.2 设置标志位的处理

    标记完所有活动对象后，标记阶段就结束了。标记阶段结束时的堆如图

    2.3 所示。

    图 2.3 标记阶段结束后的堆状态

    在标记阶段中，程序会标记所有活动对象。毫无疑问，标记所花费的时

    间是与“活动对象的总数”成正比的。

    以上是关于标记阶段的说明。用一句话概括，标记阶段就是“遍历对象

    并标记”的处理过程。这个“遍历对象”的处理过程在 GC 中是一个非常

    重要的概念，在之后还会多次出现，请务必记牢。

    专栏深度优先搜索与广度优先搜索

    我们在搜索对象并进行标记时使用的是深度优先搜索(depth -first

    search)。这是尽可能从深度上搜索树形结构的方法。

    图 2.4 深度优先搜索

    另一方面，还有广度优先搜索(breadth-first search)方法。这是尽

    可能从广度上搜索树形结构的方法。图 2.5 广度优先搜索

    顺便说一下，图 2.4 和图 2.5 中各对象旁边的号码表示搜索顺序。

    GC 会搜索所有对象。不管使用什么搜索方法，搜索相关的步骤数

    (调查的对象数量)都不会有差别。

    另一方面，比较一下内存使用量(已存储的对象数量)就可以知

    道，深度优先搜索比广度优先搜索更能压低内存使用量。因此我们

    在标记阶段经常用到深度优先搜索。

    2.1.2 清除阶段

    在清除阶段中，collector 会遍历整个堆，回收没有打上标记的对象(即

    垃圾)，使其能再次得到利用。

    代码清单 2.4：sweep_phase 函数

    1 sweep_phase{

    2 sweeping = heap_start

    3 while(sweeping < heap_end)

    4 if(sweeping.mark == TRUE)

    5 sweeping.mark = FALSE

    6 else 7 sweeping.next = free_list

    8 free_list = sweeping

    9 sweeping += sweeping.size

    10 }

    在此出现了叫作 size 的域，这是存储对象大小(字节数)的域。跟

    mark 域一样，我们事先在各对象的头中定义它们。

    在清除阶段，我们使用变量 sweeping 遍历堆，具体来说就是从堆首地

    址 heap_start 开始，按顺序一个个遍历对象的标志位。

    设置了标志位，就说明这个对象是活动对象。活动对象必然是不能回收

    的。在第 5 行我们取消标志位，准备下一次的 GC。

    我们必须把非活动对象回收再利用。回收对象就是把对象作为分块，连

    接到被称为“空闲链表”的单向链表。在之后进行分配时只要遍历这个空

    闲链表，就可以找到分块了。

    我们在 sweep_phase 函数的第 7 行、第 8 行进行这项操作。

    在第 7 行新出现了叫作 next 的域。我们只在生成空闲链表以及从这个

    空闲链表中取出分块时才会使用到它。没有必要为各个对象特别准备

    域，从对象已有的域之中分出来一个就够了。在本章中，next 表示对

    象(或者分块)最初的域，即 field1。也就是说，给 field1 这个域

    起个别名叫 next。这跟 C 语言中的联合体(union)的概念相同。

    这里要注意的是在第 7 行重写 sweeping 的域这一步。读者可能会有疑

    问：“GC 重写了对象的域也没事吗？”因为我们知道这个对象已经死

    了，所以事实上没有任何问题。图 2.6 清除阶段结束后的堆状态

    在清除阶段，程序会遍历所有堆，进行垃圾回收。也就是说，所花费时

    间与堆大小成正比。堆越大，清除阶段所花费的时间就会越长。

    以上是对标记阶段以及清除阶段的大体说明。不过还有几件事情必须事

    先说一下。

    2.1.3 分配

    接下来为大家讲解分配的相关内容。这里的分配是指将回收的垃圾进行

    再利用。那么，分配是怎样进行的呢？也就是说，当 mutator 申请分块

    时，怎样才能把大小合适的分块分配给 mutator 呢？

    如前文所述，我们在清除阶段已经把垃圾对象连接到空闲链表了。搜索

    空闲链表并寻找大小合适的分块，这项操作就叫作分配。执行分配的函

    数 new_obj 如代码清单 2.5 所示。

    代码清单 2.5：new_obj 函数

    1 new_obj(size){

    2 chunk = pickup_chunk(size, free_list)

    3 if(chunk != NULL)4 return chunk

    5 else

    6 allocation_fail

    7 }

    第 2 行的 pickup_chunk 函数用于遍历 free_list，寻找大于等于

    size 的分块。它不光会返回和 size 大小相同的分块，还会返回比

    size 大的分块。如果它找到和 size 大小相同的分块，则会直接返回该

    分块；如果它找到比 size 大的分块，则会将其分割成 size 大小的分

    块和去掉 size 后剩余大小的分块，并把剩余的分块返回空闲链表。

    如果此函数没有找到合适的分块，则会返回 NULL。返回 NULL 时分配是

    不会进行的。为了处理这种情况，我们在代码清单 2.5 中调用了之前在

    1.6 节提到的 allocation_fail 函数。

    专栏

    First - fit、Best - fit、Worst - fit 的不同

    之前我们讲的分配策略叫作 First - fit。因为在 pickup_chunk 函

    数中，最初发现大于等于 size 的分块时就会立即返回该分块。

    然而，分配策略不止这些。还有遍历空闲链表，返回大于等于

    size 的最小分块，这种策略叫作 Best - fit。

    还有一种策略叫作 Worst - fit，即找出空闲链表中最大的分块，将

    其分割成 mutator 申请的大小和分割后剩余的大小，目的是将分割

    后剩余的分块最大化。但因为 Worst - fit 很容易生成大量小的分

    块，所以不推荐大家使用此方法。

    除去 Worst - fit，剩下的还有 Best - fit 和 First - fit 这两种。当我们

    使用单纯的空闲链表时，考虑到分配所需的时间，选择使用 First -

    fit 更为明智。

    2.1.4 合并

    前文中已经提过，根据分配策略的不同可能会产生大量的小分块。但如

    果它们是连续的，我们就能把所有的小分块连在一起形成一个大分块。这种“连接连续分块”的操作就叫作合并(coalescing)，合并是在清除阶

    段进行的。

    执行合并的函数 sweep_phase 如代码清单 2.6 所示。

    代码清单 2.6：执行合并的 sweep_phase 函数

    1 sweep_phase{

    2 sweeping = heap_start

    3 while(sweeping < heap_end)

    4 if(sweeping.mark == TRUE)

    5 sweeping.mark = FALSE

    6 else

    7 if(sweeping == free_list + free_list.size)

    8 free_list.size += sweeping.size

    9 else

    10 sweeping.next = free_list

    11 free_list = sweeping

    12 sweeping += sweeping.size

    13 }

    代码清单 2.6 的 sweep_phase 函数只有第 7 行、第 8 行与代码清单

    2.4 不同。第 7 行用于调查这次发现的分块和上次发现的分块是否连

    续，如果发现分块连续，则在第 8 行将邻接的 2 个分块合并，整理成 1

    个分块。2.2 优点

    2.2.1 实现简单

    说到 GC 标记 - 清除算法的优点，那当然要数算法简单，实现容易了。

    打个比方，接下来我们将在第 3 章中提到引用计数法，在引用计数法中

    就很难切实管理计数器的增减，实现也很困难。

    另外，如果算法实现简单，那么它与其他算法的组合也就相应地简单。

    在第 3 章和第 4 章中，我们会为大家介绍把 GC 标记 - 清除算法与其他

    GC 算法相结合的方法。

    2.2.2 与保守式 GC 算法兼容

    在第 6 章中介绍的保守式 GC 算法中，对象是不能被移动的。因此保守

    式 GC 算法跟把对象从现在的场所复制到其他场所的 GC 复制算法(第

    4 章)与标记 - 压缩算法(第 5 章)不兼容。

    而 GC 标记 - 清除算法因为不会移动对象，所以非常适合搭配保守式

    GC 算法。事实上，在很多采用保守式 GC 算法的处理程序中也用到了

    GC 标记 - 清除算法。2.3 缺点

    2.3.1 碎片化

    在 GC 标记 - 清除算法的使用过程中会逐渐产生被细化的分块，不久后

    就会导致无数的小分块散布在堆的各处。我们称这种状况为碎片化

    (fragmentation)。众所周知，Windows 的文件系统也会产生这种现

    象。

    图 2.7 碎片化

    如果发生碎片化，那么即使堆中分块的总大小够用，也会因为一个个的

    分块都太小而不能执行分配。

    此外，如果发生碎片化，就会增加 mutator 的执行负担。如 1.9.4 节中所

    述，把具有引用关系的对象安排在堆中较远的位置，就会增加访问所需

    的时间。

    因为分块在堆中的分布情况取决于 mutator 的运行情况，所以只要使用

    GC 标记 - 清除算法，就会或多或少地产生碎片化。

    为了避免碎片化，可以采用将在第 4 章以及第 5 章中介绍的“压缩”，以及在本章介绍的“BiBOP 法”。

    2.3.2 分配速度

    GC 标记 - 清除算法中分块不是连续的，因此每次分配都必须遍历空闲

    链表，找到足够大的分块。最糟的情况就是每次进行分配都得把空闲链

    表遍历到最后。

    另一方面，因为在 GC 复制算法和 GC 标记 - 压缩算法中，分块是作为

    一个连续的内存空间存在的，所以没必要遍历空闲链表，分配就能非常

    高速地进行，而且还能在堆允许范围内分配很大的对象。

    本章在后面叙述的多个空闲链表(multiple free-list)和 BiBOP 法都是为

    了能在 GC 标记 - 清除算法中高速进行分配而想出的方法。

    2.3.3 与写时复制技术不兼容

    写时复制技术(copy-on-write)是在 Linux 等众多 UNIX 操作系统的虚

    拟存储中用到的高速化方法。打个比方，在 Linux 中复制进程，也就是

    使用 fork 函数时，大部分内存空间都不会被复制。只是复制进程，就复制了所有内存空间的话也太说不过去了吧。因此，写时复制技术只

    是装作已经复制了内存空间，实际上是将内存空间共享了。

    在各个进程中访问数据时，能够访问共享内存就没什么问题了。

    然而，当我们对共享内存空间进行写入时，不能直接重写共享内存。因

    为从其他程序访问时，会发生数据不一致的情况。在重写时，要复制自

    己私有空间的数据，对这个私有空间进行重写。复制后只访问这个私有

    空间，不访问共享内存。像这样，因为这门技术是“在写入时进行复

    制”的，所以才被称为写时复制技术。

    这样的话，GC 标记 - 清除算法就会存在一个问题 —— 与写时复制技术

    不兼容。即使没重写对象，GC 也会设置所有活动对象的标志位，这样

    就会频繁发生本不应该发生的复制，压迫到内存空间。

    为了处理这个问题，我们采用位图标记(bitmap marking)的方法。关

    于这个方法，将在 2.6 节中介绍。2.4 多个空闲链表

    之前我们讲的标记 - 清除算法中只用到了一个空闲链表，在这个空闲链

    表中，对大的分块和小的分块进行同样的处理。但是这样一来，每次分

    配的时候都要遍历一次空闲链表来寻找合适大小的分块，这样非常浪费

    时间。

    因此，我们有一种方法，就是利用分块大小不同的空闲链表，即创建只

    连接大分块的空闲链表和只连接小分块的空闲链表。这样一来，只要按

    照 mutator 所申请的分块大小选择空闲链表，就能在短时间内找到符合

    条件的分块了。

    下面来具体看一下这个方法。

    图 2.8 只利用一个空闲链表的情况

    当只利用一个空闲链表时，需要遍历多次空闲链表才能分配 3 个字的分

    块。那么，利用多个空闲链表时会如何呢？图 2.9 利用多个空闲链表的情况

    这次数组的各个元素都位于空闲链表的前面，第 1 个元素是由 2 个字的

    分块连接的空闲链表的开头，第 2 个元素是由 3 个字的分块连接的空闲

    链表的开头。因此，例如在分配 3 个字的分块时，只要查询用于 3 个字

    的空闲链表就够了。比起只利用一个空闲链表来说，此方法大幅节约了

    分配所需要的时间。

    不过请稍等，这里有一处需要我们留意。那就是到底制造多少个空闲链

    表才好呢？用于 2 个字的空闲链表、用于 3 个字的、用于 500 个字的…… 照这样下去，我们就得准备无数个空闲链表了。

    一般情况下，mutator 很少会申请非常大的分块。为了应对这种极少出

    现的情况而大量制造空闲链表，会使得空闲链表的数组过于巨大，结果

    压迫到内存空间。

    因此，我们通常会给分块大小设定一个上限，分块如果大于等于这个大

    小，就全部采用一个空闲链表处理。有人可能会想：“这样一来，最后

    不还是没能有效率地搜索大的分块吗？”然而，因为这种分配非常大的

    分块的情况是极为罕见的，所以效率低一点也不是什么大问题。比这更

    为重要的是怎么去更快地搜索 mutator 频繁申请分配的小分块，把关注

    的重点移到这上面来才是更精明的做法。打个比方，如果设定分块大小上限为 100 个字，那么准备用于 2 个字、3 个字、……、100 个字，以

    及大于等于 101 个字的总共 100 个空闲链表就可以了。

    利用多个空闲链表时，我们需要修正 new_obj 函数以及

    sweep_phase 函数。修正后的 new_obj 函数以及

    sweep_phase 函数分别如代码清单 2.7、代码清单 2.8 所示。

    代码清单 2.7：利用多个空闲链表的 new_obj 函数

    1 new_obj(size){

    2 index = size (WORD_LENGTH BYTE_LENGTH)

    3 if(index <= 100)

    4 if(free_list[index] != NULL)

    5 chunk = free_list[index]

    6 free_list[index] = free_list[index].next

    7 return chunk

    8 else

    9 chunk = pickup_chunk(size, free_list[101])

    10 if(chunk != NULL)

    11 return chunk

    12

    13 allocation_fail

    14 }

    代码清单 2.8：利用多个空闲链表的 sweep_phase 函数

    1 sweep_phase{

    2 for(i : 2..101)

    3 free_list[i] = NULL

    4

    5 sweeping = heap_start

    6

    7 while(sweeping < heap_end)

    8 if(sweeping.mark == TRUE)

    9 sweeping.mark = FALSE

    10 else

    11 index = size (WORD_LENGTH BYTE_LENGTH )

    12 if(index <= 100)

    13 sweeping.next = free_list[index]

    14 free_list[index] = sweeping

    15 else

    16 sweeping.next = free_list[101]

    17 free_list[101] = sweeping18 sweeping += sweeping.size

    19 }2.5 BiBOP 法

    本节中要向大家介绍的是 BiBOP 法。BiBOP 是 Big Bag Of Pages 的缩

    写。这么说可能比较难懂，用一句话概括就是“将大小相近的对象整理

    成固定大小的块进行管理的做法”。

    我们来详细说明一下。前面已经跟大家讲过，GC 标记 - 清除算法中会

    发生碎片化。碎片化的原因之一就是堆上杂乱散布着大小各异的对象。

    对此，我们可以用这个方法：把堆分割成固定大小的块，让每个块只能

    配置同样大小的对象。这就是 BiBOP 法。

    仅看文字说明可能还是比较难懂，请看下图。

    图 2.10 BiBOP 法的示意图

    如图 2.10 所示，3 个字的对象被整合分配到左数第 1 个和第 3 个块，2个字的对象被整合分配到左数第 2 个块。像这样配置对象，就会提高内

    存的使用效率。因为每个块中只能配置同样大小的对象，所以不可能出

    现大小不均的分块。

    但是，使用 BiBOP 法并不能完全消除碎片化。比方说在全部用于 2 个

    字的块中，只有 1 到 2 个活动对象，这种情况下就不能算是有效利用了

    堆。

    BiBOP 法原本是为了消除碎片化，提高堆使用效率而采用的方法。但像

    上面这样，在多个块中分散残留着同样大小的对象，反而会降低堆使用

    效率。2.6 位图标记

    在单纯的 GC 标记 - 清除算法中，用于标记的位是被分配到各个对象的

    头中的。也就是说，算法是把对象和头一并处理的。然而之前在 2.3.3

    节中也提过，这跟写时复制技术不兼容。

    对此我们有个方法，那就是只收集各个对象的标志位并表格化，不跟对

    象一起管理。在标记的时候，不在对象的头里置位，而是在这个表格中

    的特定场所置位。像这样集合了用于标记的位的表格称为“位图表

    格”(bitmap table)，利用这个表格进行标记的行为称为“位图标记”。

    位图表格的实现方法有多种，例如散列表和树形结构等。为了简单起

    见，这里我们采用整数型数组。位图标记的情况如图 2.11 所示。

    图 2.11 位图标记

    在位图标记中重要的是，位图表格中位的位置要和堆里的各个对象切实

    对应。一般来说，堆中的 1 个字会分配到 1 个位，我们在本书中也是这

    么规定的。位图标记中的 mark 函数如代码清单 2.9 所示。

    代码清单 2.9：位图标记中的 mark 函数

    1 mark(obj){

    2 obj_num = (obj - heap_start) WORD_LENGTH

    3 index = obj_num WORD_LENGTH

    4 offset = obj_num % WORD_LENGTH

    5

    6 if((bitmap_tbl[index] (1 << offset)) == 0)

    7 bitmap_tbl[index] |= (1 << offset)

    8 for(child : children(obj))

    9 mark(child)

    10 }

    在这里，WORD_LENGTH 是个常量，表示的是各机器中 1 个字的位宽

    (例如 32 位机器的 WORD_LENGTH 就是 32)。obj_num 指的是从位图

    表格前面数起，obj 的标志位在第几个。例如图 2.11 中的 E，它的

    obj_num 值就是 8。然而请大家注意，图 2.12 中位的排列顺序和图 2.11

    是相反的。因此，E 的标志位是从 bitmap_table[0] 的右边起第 9 个

    位。图 2.12 对象E 的标志位位置

    我们用 obj_num 除以 WORD_LENGTH 得到的商 index 以及余数 offset

    来分别表示位图表格的行编号和列编号。第 6 行和第 7 行中用到了位运

    算，看上去有些复杂，实际上只是干了件非常简单的事情。

    和在对象的头中直接置标志位的方法相比，该方法稍微有些复杂，但是

    这样做有两个好处。

    2.6.1 优点

    2.6.1.1 与写时复制技术兼容

    以往的标记操作都是直接对对象设置标志位，这会产生无谓的复制。

    然而，使用位图标记是不会对对象设置标志位的，所以也不会发生无谓

    的复制。当然，因为对位图表格进行了重写，所以在此处会发生复制。

    不过，因为位图表格非常小，所以即使被复制也不会有什么大的影响。

    此外，以上问题只发生在写时复制技术的运行环境(Linux 等)中，以

    及频繁执行 fork 函数的应用程序中。也就是说，它对于一般的程序

    来说完全不是问题。

    因此引发问题的情况极为少见，本书第 11 章中会举例为大家详细说

    明。

    2.6.1.2 清除操作更高效

    不仅在标记阶段，在清除阶段也可以得到好处。以往的清除操作都必须

    遍历整个堆，把非活动对象连接到空闲链表，同时取消活动对象的标志

    位。

    利用了位图表格的清除操作则把所有对象的标志位集合到一处，所以可

    以快速消去标志位。

    位图标记中的清除操作如代码清单 2.10 所示。

    代码清单 2.10：位图标记的sweep_phase 函数 1 sweep_phase{

    2 sweeping = heap_start

    3 index = 0

    4 offset = 0

    5

    6 while(sweeping < heap_end)

    7 if(bitmap_tbl[index] (1 << offset) == 0)

    8 sweeping.next = free_list

    9 free_list = sweeping

    10 index += (offset + sweeping.size) WORD_LENGTH

    11 offset = (offset + sweeping.size) % WORD_LENGTH

    12 sweeping += sweeping.size

    13

    14 for(i : 0..(HEAP_SIZE WORD_LENGTH - 1))

    15 bitmap_tbl[i] = 0

    16 }

    与一般的清除阶段相同，我们用 sweeping 指针遍历整个堆。不过，这

    里使用了 index 和 offset 两个变量，在遍历堆的同时也遍历位图表

    格。

    第 6 行到第 12 行是从堆的开头开始遍历。第 7 行是调查遍历过程中与

    对象对应的标志位。当对象没有设置标志位时，程序会在第 8 行和第 9

    行将此对象连接到空闲链表。当对象已经设立了标志位时，程序就不会

    在此进行消除位的操作，而是放到之后一并进行。

    第 10 行、第 11 行是遍历位图表格，第 12 行是遍历堆。

    第 14 行、第 15 行是把所有在位图表格中设置的位取消。因为能够一并

    消除标志位，所以能够有效地取消位。

    2.6.2 要注意的地方

    在进行位图标记的过程中，有件事情我们必须注意，那就是对象地址和

    位图表格的对应。就像之前和大家说明的那样，想通过对象的地址求与

    其对应的标志位的位置，是要进行位运算的。然而在堆有多个，对象地

    址不连续的情况下，我们无法用单纯的位运算求出标志位的位置。因

    此，在堆为多个的情况下，一般会为每个堆都准备一个位图表格。2.7 延迟清除法

    在 2.1.3 节的末尾我们曾经提到过，清除操作所花费的时间是与堆大小

    成正比的。也就是说，处理的堆越大，GC 标记 - 清除算法所花费的时

    间就越长，结果就会妨碍到 mutator 的处理。

    延迟清除法(Lazy Sweep)是缩减因清除操作而导致的 mutator 最大暂

    停时间的方法。在标记操作结束后，不一并进行清除操作，而是如其字

    面意思一样让它“延迟”，通过“延迟”来防止 mutator 长时间暂停。那

    么，延迟清除操作意味着什么呢？

    本书之后会为大家介绍 R. John M. Hughes 开发的延迟清除法

    [12]。

    2.7.1 new_obj 函数

    延迟清除法中的 new_obj 函数的定义如代码清单 2.11 所示。

    代码清单 2.11：延迟清除法中的new_obj 函数

    1 new_obj(size){

    2 chunk = lazy_sweep(size)

    3 if(chunk != NULL)

    4 return chunk

    5

    6 mark_phase

    7

    8 chunk = lazy_sweep(size)

    9 if(chunk != NULL)

    10 return chunk

    11

    12 allocation_fail

    13 }

    在分配时直接调用 lazy_sweep 函数，进行清除操作。如果它能用清

    除操作来分配分块，就会返回分块；如果不能分配分块，就会执行标记

    操作。当 lazy_sweep 函数返回 NULL 时，也就是没有找到分块时，会调用 mark_phase 函数进行一遍标记操作，再调用 lazy_sweep

    函数来分配分块。在这里没能分配分块也就意味着堆上没有分块，mutator 也就不能再进行下一步处理了。

    2.7.2 lazy_sweep 函数

    那么我们来看一下 lazy_sweep 函数吧。

    代码清单 2.12：lazy_sweep 函数

    1 lazy_sweep(size){

    2 while(sweeping < heap_end)

    3 if(sweeping.mark == TRUE)

    4 sweeping.mark = FALSE

    5 else if(sweeping.size >= size)

    6 chunk = sweeping

    7 sweeping += sweeping.size

    8 return chunk

    9 sweeping += sweeping.size

    10

    11 sweeping = heap_start

    12 return NULL

    13 }

    lazy_sweep 函数会一直遍历堆，直到找到大于等于所申请大小的分

    块为止。在找到合适分块时会将其返回。但是在这里 sweeping 变量

    是全局变量。也就是说，遍历的开始位置位于上一次清除操作中发现的

    分块的右边。

    当 lazy_sweep 函数遍历到堆最后都没有找到分块时，会返回

    NULL。

    因为延迟清除法不是一下遍历整个堆，它只在分配时执行必要的遍历，所以可以压缩因清除操作而导致的 mutator 的暂停时间。这就是“延

    迟”清除操作的意思。

    2.7.3 有延迟清除法就够了吗

    我们已经知道，通过延迟清除法可以缩减 mutator 的暂停时间，不过这

    是真的吗？稍微想想看就会明白，延迟清除的效果是不均衡的。打个比

    方，假设刚标记完的堆的情况如图 2.13 所示。图 2.13 堆里垃圾分布不均的情况

    也就是说，垃圾变成了垃圾堆，活动对象变成了活动对象堆，它们形成

    了一种邻接的状态。在这种情况下，程序在清除垃圾较多的部分时能马

    上获得分块，所以能减少 mutator 的暂停时间。然而一旦程序开始清除

    活动对象周围，就怎么也无法获得分块了，这样就增加了 mutator 的暂

    停时间。

    结果，如果一下子清除的堆大小不一定，那么 mutator 的暂停时间就会

    增大。关于保持所清除的堆大小的方法我们将在第 8 章中详细为大家说

    明。

    虽然在这里没有特别提及，不过标记阶段导致的暂停时间和清除阶段导

    致的暂停时间一样，也是个问题。关于如何改善这个问题，我们也会在

    第 8 章中为大家解说。3 引用计数法

    GC 原本是一种“释放怎么都无法被引用的对象的机制”。那么人们自

    然而然地就会想到，可以让所有对象事先记录下“有多少程序引用自

    己”。让各对象知道自己的“人气指数”，从而让没有人气的对象自己消

    失，这就是引用计数法(Reference Counting)，它是 George E.

    Collins

    [6]

    于 1960 年钻研出来的。3.1 引用计数的算法

    引用计数法中引入了一个概念，那就是“计数器”。计数器表示的是对象

    的人气指数，也就是有多少程序引用了这个对象(被引用数)。计数器

    是无符号的整数，用于计数器的位数根据算法和实现而有所不同。引用

    计数法中的对象如图 3.1 所示。

    图 3.1 引用计数法中的对象

    那么，让我们来看看在引用计数法中是怎样进行内存管理的吧。

    3.1.1 计数器值的增减

    在 GC 标记 - 清除算法等其他 GC 算法中，没有分块时 mutator 会调用

    下面这样的函数，启动 GC 分配空闲的内存空间。

    代码清单 3.1：garbage_collect 函数

    1 garbage_collect{

    2 ....

    3 }

    然而在引用计数法中并没有 mutator 明确启动 GC 的语句。引用计数法

    与 mutator 的执行密切相关，它在 mutator 的处理过程中通过增减计数

    器的值来进行内存管理。在两种情况下计数器的值会发生增减，这涉及

    了 new_obj 函数和 update_ptr 函数。3.1.2 new_obj 函数

    代码清单 3.2：new_obj 函数

    1 new_obj(size){

    2 obj = pickup_chunk(size, free_list)

    3

    4 if(obj == NULL)

    5 allocation_fail

    6 else

    7 obj.ref_cnt = 1

    8 return obj

    9 }

    与 GC 标记 - 清除算法相同，mutator 在生成新对象的时候会调用

    new_obj 函数。

    在这里，pickup_chunk 函数的用法也大致与在 GC 标记 - 清除算法

    中的用法相同。不过这次当 pickup_chunk 函数返回 NULL 时，分配

    就失败了。关于这点我们也会在之后的 3.2.1 节中为大家说明。在引用

    计数法中，除了连接到空闲链表的对象，其他所有对象都是活动对象。

    也就是说，在 pickup_chunk 函数返回 NULL 那一刻，堆中就没有合

    适大小的分块了，分配就无法进行了。

    当通过 pickup_chunk 函数返回合适大小的对象时，在第 7 行把计数

    器的值定为 1。很明显，这里新生成了对象，且对象被某处引用了。另

    外，域 ref_cnt 代表对象 obj 的计数器。这点在本章之后也一样，请

    大家牢记。

    3.1.3 update_ptr 函数

    update_ptr 函数用于更新指针 ptr，使其指向对象 obj，同时进行

    计数器值的增减。

    代码清单 3.3：update_ptr 函数

    1 update_ptr(ptr, obj){

    2 inc_ref_cnt(obj)

    3 dec_ref_cnt(ptr)4 ptr = obj

    5 }

    虽然在 mutator 更新指针时程序会执行此函数，但事实上进行指针更新

    的只有第 4 行的 ptr = obj 部分，第 2 行和第 3 行是进行内存管理的

    代码。程序具体进行的是以下 2 项操作。

    1. 对指针 ptr 新引用的对象(obj)的计数器进行增量操作

    2. 对指针 ptr 之前引用的对象(ptr)的计数器进行减量操作

    首先我们要介绍的是执行计数器增量操作的 inc_ref_cnt 函数。

    代码清单 3.4：inc_ref_cnt 函数

    1 inc_ref_cnt(obj){

    2 obj.ref_cnt++

    3 }

    inc_ref_cnt 函数是一个简单的函数，它只对新引用的对象 obj 的

    计数器进行增量操作。下面我们再来看看进行计数器减量操作的

    dec_ref_cnt 函数。

    代码清单 3.5：dec_ref_cnt 函数

    1 dec_ref_cnt(obj){

    2 obj.ref_cnt--

    3 if(obj.ref_cnt == 0)

    4 for(child : children(obj))

    5 dec_ref_cnt(child)

    6 reclaim(obj)

    7 }

    首先对更新指针之前引用的对象 ptr 的计数器进行减量操作。减量操

    作后，计数器的值为 0 的对象变成了“垃圾”。因此，这个对象的指针会

    全部被删除。换言之，程序需要对 ptr 的子对象的计数器进行减量操

    作。在第 5 行递归调用 dec_ref_cnt 函数就是为了这个。然后，通过 reclaim 函数将 obj 连接到空闲链表。reclaim 函数会在本章

    中多次出现，请牢记。

    那么，看到这里大家会不会心生疑问呢？为什么要先调用

    inc_ref_cnt 函数，后调用 dec_ref_cnt 函数呢？从引用计数算

    法的角度来考虑，先调用 dec_ref_cnt 函数，后调用

    inc_ref_cnt 函数才合适吧。答案就是“为了处理 ptr 和 obj 是同

    一对象时的情况”。如果按照先 dec_ref_cnt 后 inc_ref_cnt 函

    数的顺序调用，ptr 和 obj 又是同一对象的话，执行

    dec_ref_cnt(ptr) 时 ptr 的计数器的值就有可能变为 0 而被回

    收。这样一来，下面再想执行 inc_ref_cnt(obj) 时 obj 早就被回收

    了，可能会引发重大的 BUG。因此我们要通过先对 obj 的计数器进行

    增量操作来回避这种 BUG。

    最后结合图片来看一下 update_ptr 函数执行时的情况。请看图

    3.2(a)。初始状态下从根引用 A 和 C，从 A 引用 B。A 持有唯一指向 B

    的指针，假设现在将该指针更新到了 C，请看图 3.2(b)。

    图 3.2 update_ptr 函数执行时的情况

    通过以上的更新，B 的计数器值变成了 0，因此 B 被回收了。且 B 连接

    上了空闲链表，能够再被利用了。又因为新形成了由 A 指向 C 的指

    针，所以 C 的计数器的值增量为 2。

    在变更数组元素等的时候会进行指针的更新。通过更新指针，可能会产

    生没有被任何程序引用的垃圾对象。引用计数法中会监督在更新指针的

    时候是否有产生垃圾，从而在产生垃圾时将其立刻回收。也就是说，这意味着在分配时没有分块的情况下，堆中所有的对象都为活动对象，这

    时没法新分配对象。另一方面，GC 标记 - 清除算法即使产生了垃圾也

    不会将其马上回收，只会在没有分块的时候将垃圾一并回收。像这样，可以说将内存管理和 mutator 同时运行正是引用计数法的一大特征。

    以上就是对引用计数的算法的说明。3.2 优点

    3.2.1 可即刻回收垃圾

    在引用计数法中，每个对象始终都知道自己的被引用数(就是计数器的

    值)。当被引用数的值为 0 时，对象马上就会把自己作为空闲空间连接

    到空闲链表。也就是说，各个对象在变成垃圾的同时就会立刻被回收。

    要说这有什么意义，那就是内存空间不会被垃圾占领。垃圾全部都已连

    接到空闲链表，能作为分块再被利用。

    另一方面，在其他的 GC 算法中，即使对象变成了垃圾，程序也无法立

    刻判别。只有当分块用尽后 GC 开始执行时，才能知道哪个对象是垃

    圾，哪个对象不是垃圾。也就是说，直到 GC 执行之前，都会有一部分

    内存空间被垃圾占用。

    3.2.2 最大暂停时间短

    在引用计数法中，只有当通过 mutator 更新指针时程序才会执行垃圾回

    收。也就是说，每次通过执行 mutator 生成垃圾时这部分垃圾都会被回

    收，因而大幅度地削减了 mutator 的最大暂停时间。

    就如我们在第 1 章中所说的那样，根据 mutator 的用途不同，最大暂停

    时间的长短会成为非常重要的因素。

    3.2.3 没有必要沿指针查找

    引用计数法和 GC 标记 - 清除算法不一样，没必要由根沿指针查找。当

    我们想减少沿指针查找的次数时，它就派上用场了。

    打个比方，在分布式环境中，如果要沿各个计算节点之间的指针进行查

    找，成本就会增大，因此需要极力控制沿指针查找的次数。

    所以，有一种做法是在各个计算节点内回收垃圾时使用 GC 标记 - 清除

    算法，在考虑到节点间的引用关系时则采用引用计数法。3.3 缺点

    3.3.1 计数器值的增减处理繁重

    虽然依据执行的 mutator 的动作不同而略有差距，我们不能一概而论，不过在大多数情况下指针都会频繁地更新。特别是有根的指针，会以近

    乎令人目眩的势头飞速地进行更新。这是因为根可以通过 mutator 直接

    被引用。在引用计数法中，每当指针更新时，计数器的值都会随之更

    新，因此值的增减处理必然会变得繁重。

    关于解决这个问题的方法，我们将在 3.4 节中为大家介绍。

    3.3.2 计数器需要占用很多位

    用于引用计数的计数器最大必须能数完堆中所有对象的引用数。打个比

    方，假如我们用的是 32 位机器，那么就有可能要让 2 的 32 次方个对象

    同时引用一个对象。考虑到这种情况，就有必要确保各对象的计数器有

    32 位大小。也就是说，对于所有对象，必须留有 32 位的空间。这就害

    得内存空间的使用效率大大降低了。打比方说，假如对象只有 2 个域，那么其计 数器就占了它整体的 13。

    3.3.3 实现烦琐复杂

    引用计数的算法本身很简单，但事实上实现起来却不容易。

    进行指针更新操作的 update_ptr 函数是在 mutator 这边调用的。打

    个比方，我们需要把以往写成 ptr=obj 的地方都重写成

    update_ptr(ptr,obj)。因为调用 update_ptr 函数的地方非常

    多，所以重写过程中很容易出现遗漏。如果漏掉了某处，内存管理就无

    法正确进行，就会产生 BUG。

    3.3.4 循环引用无法回收

    代码清单 3.6：循环垃圾的生成

    1 class Person{ 定义Person 类 2 string name

    3 Person lover

    4 }

    5

    6 taro = new Person( 太郎) 生成Person 类的实例太郎

    7 hanako = new Person( 花子) 生成Person 类的实例花子

    8 taro.lover = hanako 太郎喜欢花子

    9 hanako.lover = taro 花子喜欢太郎

    10 taro = null 将taro 转换为null

    11 hanako = null 将hanako 转换为null

    上述伪代码表示的是某对情侣。在执行这段伪代码后，对象的情况如图

    3.3 所示。

    图 3.3 循环引用对象

    像上述这样，因为两个对象互相引用，所以各对象的计数器的值都是

    1。但是这些对象组并没有被其他任何对象引用。因此想一并回收这两

    个对象都不行，只要它们的计数器值都是 1，就无法回收。像这样在两

    个及两个以上的对象互相循环引用形成对象组的情况下，即使这些对象

    组都成了垃圾，程序也无法将它们回收。

    我们说了很多引用计数法的缺点，像“处理繁重”“内存使用效率低

    下”等。那么引用计数法是不是一个“完全没法用”的算法呢？不，绝对

    不是。事实上，很多处理系统和应用都在使用引用计数法。

    要说为什么，那是因为引用计数法只要稍加改良，就会变得非常具有实

    用性了。之后我们将对如何改良引用计数法进行解说。3.4 延迟引用计数法

    3.4.1 什么是延迟引用计数法

    在讲引用计数法的缺点时，我们提到了其中一项是“计数器值的增减处

    理繁重”。下面就对改善此缺点的方法进行说明，即延迟引用计数法

    (Deferred Reference Counting)。这个方法是 L. Peter Deutsch 和 Daniel

    G. Bobrow

    [8]

    研究出来的。

    如 3.3.1 节中所述，计数器值增减处理繁重的原因之一是从根的引用变

    化频繁。

    因此，我们就让从根引用的指针的变化不反映在计数器上。打个比方，我们把重写全局变量指针的 update_ptr(ptr,obj) 改写成 ptr =

    obj。

    如上所述，这样一来即使频繁重写堆中对象的引用关系，对象的计数器

    值也不会有所变化，因而大大改善了“计数器值的增减处理繁重”这一缺

    点。

    然而，这样内存管理还是不能顺利进行。因为引用没有反映到计数器

    上，所以各个对象的计数器没有正确表示出对象本身的被引用数(即人

    气)。因此，有可能发生对象仍在活动，但却被错当成垃圾回收的情

    况。

    图 3.4 实际上仍在活动，但计数器值却为 0 的对象于是，我们在延迟引用计数法中使用 ZCT(Zero Count Table)。ZCT

    是一个表，它会事先记录下计数器值在 dec_ref_cnt 函数的作用下

    变为 0 的对象。ZCT 的示意图如图 3.5 所示。

    图 3.5 ZCT

    因为计数器值为 0 的对象不一定都是垃圾，所以暂时先将这些对象保

    留。由图 3.5 也能看出，我们必须修正 dec_ref_cnt 函数，使其适

    应延迟引用计数法。

    3.4.2 dec_ref_cnt 函数

    关于在延迟引用计数法中用到的 dec_ref_cnt 函数，其定义如代码

    清单 3.7 所示。

    代码清单 3.7：延迟引用计数法中的 dec_ref_cnt 函数

    1 dec_ref_cnt(obj){

    2 obj.ref_cnt--

    3 if(obj.ref_cnt == 0)

    4 if(is_full(zct) == TRUE)

    5 scan_zct

    6 push(zct, obj)

    7 }

    当 obj 的计数器值为 0(也就是说 obj 可能是垃圾)时，在第 6 行把

    obj 添加到 zct。不过，如果 zct 爆满，那么首先就要通过scan_zct 函数来减少 zct 中的对象(第 4 行、第 5 行)。

    3.4.3 new_obj 函数

    我们也要稍微修正一下 new_obj 函数。当无法分配大小合适的分块

    时，执行 scan_zct 函数。

    代码清单 3.8：延迟引用计数法中的 new_obj 函数

    1 new_obj(size){

    2 obj = pickup_chunk(size, free_list)

    3

    4 if(obj == NULL)

    5 scan_zct

    6 obj = pickup_chunk(size, free_list)

    7 if(obj == NULL)

    8 allocation_fail

    9

    10 obj.ref_cnt = 1

    11 return obj

    12 }

    如果第一次分配没有顺利进行，就意味着空闲链表中没有了大小合适的

    分块。此时程序要搜索一遍 zct，以再次分配分块。如果这样还不

    行，分配就失败了。

    分配顺利进行之后的流程通常与引用计数法完全一样。

    3.4.4 scan_zct 函数

    scan_zct 函数的伪代码如下所示。

    代码清单 3.9：scan_zct 函数

    1 scan_zct{

    2 for(r : roots)

    3 (r).ref_cnt++

    4

    5 for(obj : zct)

    6 if(obj.ref_cnt == 0) 7 remove(zct, obj)

    8 delete(obj)

    9

    10 for(r : roots)

    11 (r).ref_cnt--

    12 }

    在第 2 行和第 3 行，程序把所有通过根直接引用的对象的计数器都进行

    增量。这样才算把根引用反映到了计数器的值上。

    接下来调查所有与 zct 相连的对象，如果存在计数器值为 0 的对象，则将此对象从 zct 中删除，并执行以下 2 项操作。

    1. 对子对象的计数器进行减量操作

    2. 回收

    负责这 2 项操作的 delete 函数的定义如代码清单 3.10 所示。

    代码清单 3.10：delete 函数

    1 delete(obj){

    2 for(child : children(obj)

    3 (child).ref_cnt--

    4 if((child).ref_cnt == 0)

    5 delete(child)

    6

    7 reclaim(obj)

    8 }

    对 obj 的子对象的计数器进行减量操作，对计数器值变成 0 的对象执行

    delete 函数，最后回收 obj。

    最后把所有根引用的对象的计数器都进行减量操作。

    3.4.5 优点

    在延迟引用计数法中，程序延迟了根引用的计数，将垃圾一并回收。通

    过延迟，减轻了因根引用频繁发生变化而导致的计数器增减所带来的额外负担。

    3.4.6 缺点

    为了延迟计数器值的增减，垃圾不能马上得到回收，这样一来垃圾就会

    压迫堆，我们也就失去了引用计数法的一大优点 —— 可即刻回收垃

    圾。

    另外，scan_zct 函数导致最大暂停时间延长了。执行 scan_zct

    函数所花费的时间与 zct 的大小成正比。zct 越大，要搜索的对象就

    越多，妨碍 mutator 运作的时间也就越长。要想缩减因 scan_zct 函

    数而导致的暂停时间，就要缩小 zct。但是这样一来调用 scan_zct

    函数的频率就增加了，也压低了吞吐量。很明显这样就本末倒置了。3.5 Sticky 引用计数法

    3.5.1 什么是 Sticky 引用计数法

    在引用计数法中，我们有必要花功夫来研究一件事，那就是要为计数器

    设置多大的位宽。假设为了反映所有引用，计数器需要 1 个字(32 位

    机器就是 32 位)的空间。但是这样会大量消耗内存空间。打个比方，2

    个字的对象就要附加 1 个字的计数器。也就是说，计数器害得对象所占

    空间增大了 1.5 倍。

    图 3.6 对象拥有两个 1 个字的域以及一个 1 个字的计数器

    对此我们有个方法，那就是用来减少计数器位宽的“Sticky 引用计数

    法”。举个例子，我们假设用于计数器的位数为 5 位，那么这种计数器

    最多只能数到 2 的 5 次方减 1，也就是 31 个引用数。如果此对象被大

    于 31 个对象引用，那么计数器就会溢出。这跟车辆速度计的指针爆表

    是一个状况。

    针对计数器溢出(也就是爆表的对象)，需要暂停对计数器的管理。对

    付这种对象，我们主要有两种方法。

    3.5.2 什么都不做

    对于计数器溢出的对象，我们可以这样处理：不再增减计数器的值，就

    把它放着，什么也不做。不过这样一来，即使这个对象成了垃圾(即被

    引用数为 0)，也不能将其回收。也就是说，白白浪费了内存空间。

    然而事实上有很多研究表明，很多对象一生成马上就死了(详情请参考

    第 7 章)。也就是说，在很多情况下，计数器的值会在 0 到 1 的范围内变化，鲜少出现 5 位计数器溢出这样的情况。

    此外，因为计数器溢出的对象在执行中的程序里占有非常重要的地位，所以可想而知，其将来成为垃圾的可能性也很低。也就是说，不增减计

    数器的值，就把它那么放着也不会有什么大问题。

    考虑到以上事项，对于计数器溢出的对象，什么也不做也不失为一个可

    用的方法。

    3.5.3 使用 GC 标记 - 清除算法进行管理

    另一个方法是，在适当时机用 GC 标记 - 清除算法来充当引用计数法的

    后援。但是我们在这里用到的 GC 标记 - 清除算法和以往的有所不同。

    代码清单 3.11：作为备用的GC 标记 - 清除算法

    1 mark_sweep_for_counter_overflow{

    2 reset_all_ref_cnt

    3 mark_phase

    4 sweep_phase

    5 }

    首先，在第 2 行把所有对象的计数器值都设为 0。下面，我们进入标记

    阶段和清除阶段。

    代码清单 3.12：标记阶段

    1 mark_phase{

    2 for(r : roots)

    3 push(r, mark_stack)

    4

    5 while(is_empty(mark_stack) == FALSE)

    6 obj = pop(mark_stack)

    7 obj.ref_cnt++

    8 if(obj.ref_cnt == 1)

    9 for(child : children(obj))

    10 push(child, mark_stack)

    11 }在标记阶段，首先把由根直接引用的对象堆到标记栈里，然后按顺序从

    标记栈取出对象，对计数器进行增量操作。不过，这里必须只把各个对

    象及其子对象堆进标记栈一次。在第 8 行会检查各个对象是不是只堆进

    去了一次。一旦栈为空，则标记阶段结束。

    代码清单 3.13：清除阶段

    1 sweep_phase{

    2 sweeping = heap_top

    3 while(sweeping < heap_end)

    4 if(sweeping.ref_cnt == 0)

    5 reclaim(sweeping)

    6 sweeping += sweeping.size

    7 }

    在清除阶段，程序会搜索整个堆，回收计数器值仍为 0 的对象。

    我们在这里介绍的 GC 标记 - 清除算法和在第 2 章中介绍的 GC 标记 -

    清除算法主要有以下 3 点不同。

    1. 一开始就把所有对象的计数器值设为 0

    2. 不标记对象，而是对计数器进行增量操作

    3. 为了对计数器进行增量操作，算法对活动对象进行了不止一次的搜

    索

    像这样，只要把引用计数法和 GC 标记 - 清除算法结合起来，在计数器

    溢出后即使对象成了垃圾，程序还是能回收它。另外还有一个优点，那

    就是还能回收循环的垃圾。

    但是在进行标记处理之前，必须重置所有的对象和计数器。此外，因为

    在查找对象时没有设置标志位而是把计数器进行增量，所以需要多次

    (次数和被引用数一致)查找活动对象。考虑到这一点的话，显然在这

    里进行的标记处理比以往的 GC 标记 - 清除算法中的标记处理要花更多

    的时间。也就是说，吞吐量会相应缩小。3.6 1 位引用计数法

    3.6.1 什么是 1 位引用计数法

    1 位引用计数法(1bit Reference Counting)是 Sticky 引用计数法的一个

    极端例子。因为计数器只有 1 位大小，所以瞬间就会溢出，看上去几乎

    没什么意义。

    不过，据 Douglas W. Clark 和 C. Cordell Green

    [10]

    观察，“几乎没有对象

    是被共有的，所有对象都能被马上回收”。考虑到这一点，即使计数器

    只有 1 位，通过用 0 表示被引用数为 1，用 1 表示被引用数大于等于

    2，这样也能有效率地进行内存管理。使用 1 位计数器时各对象的处理

    方法如图 3.7 所示。

    图 3.7 使用 1 位计数器的对象的处理方法

    也就是说，我们用 1 位来表示某个对象的被引用数是 1 个还是多个。此

    外，引用计数法一般会让对象持有计数器，但 W. R. Stoye、T. J. W.

    Clarke、A. C. Norman

    [11]

    3 个人想出了 1 位引用计数法，以此来让指针

    持有计数器。本节中将介绍这个算法。不过因为是“1 位”引用计数法，所以与其叫它计数器，不如叫它“标签”(tag)更为妥当。设对象引用数

    为 1 时标签位为 0，引用数为复数时标签位为 1。我们分别称以上 2 种

    状态为 UNIQUE 和 MULTIPLE，处于 UNIQUE 状态下的指针为“UNIQUE

    指针”，处于 MULTIPLE 状态下的指针为“MULTIPLE 指针”。那么问题来了，我们要如何实现这个算法呢？其实，因为指针通常默认

    为 4 字节对齐，所以没法利用低 2 位。只要好好利用这个性质，就能确

    保拿出 1 位来用作内存管理。

    3.6.2 copy_ptr 函数

    基本上，1 位引用计数法也是在更新指针的时候进行内存管理的。不过

    它不像以往那样指定要引用的对象来更新指针，而是通过复制某个指针

    来更新指针。进行这项操作的就是 copy_ptr 函数。请看图 3.8。

    图 3.8 在 1 位引用计数法中复制指针

    这里更新了之前由 A 引用 D 的指针，让其引用 C。这也可以看成是把

    由 B 到 C 的指针复制到 A 了。通过这项操作，两个指向 C 的指针都变

    成了 MULTIPLE 指针。copy_ptr 函数的伪代码如代码清单 3.14 所

    示。

    代码清单 3.14：copy_ptr 函数

    1 copy_ptr(dest_ptr, src_ptr){

    2 delete_ptr(dest_ptr)

    3 dest_ptr = src_ptr

    4 set_multiple_tag(dest_ptr)

    5 if(tag(src_ptr) == UNIQUE)

    6 set_multiple_tag(src_ptr)

    7 }参数 dest_ptr 和 src_ptr 分别表示的是目的指针和被复制的原指

    针。打个比方，在图 3.8(a) 中，A 的指针就是目的指针，B 的指针就是

    被复制的原指针。

    在 copy_ptr 函数中，首先在第 2 行调用 delete_ptr 函数，尝试

    回收 dest_ptr 引用的对象。接下来，在第 3 行把 src_ptr 复制到

    dest_ptr。然后在第 4 行到第 6 行把指针 src_ptr 以及 dest_ptr 的

    标签更新为 MULTIPLE。

    第 5 行的 tag 函数返回实参(指针)的标签，返回 UNIQUE 或者

    MULTIPLE 的任意一个值。第 4 行和第 6 行的 set_multiple_tag

    函数则把实参(指针)变换成 MULTIPLE 指针。

    最后只要再把 mutator 这边的 update_ptr 函数调用全换成

    copy_ptr 函数，就能实现 1 位引用计数法。

    下面我们将对 delete_ptr 函数进行说明。

    3.6.3 delete_ptr 函数

    代码清单 3.15：1 位引用计数法的 delete_ptr 函数

    1 delete_ptr(ptr){

    2 if(tag(ptr) == UNIQUE)

    3 reclaim(ptr)

    4 }

    这个函数超级简单。只有当指针 ptr 的标签是 UNIQUE 时，它才会回收

    根据这个指针所引用的对象。因为当标签是 MULTIPLE 时，还可能存在

    其他引用这个对象的指针，所以它无法回收对象。

    3.6.4 优点

    1 位引用计数法的优点，是不容易出现高速缓存缺失。

    缓存作为一块存储空间，比内存的读取速度要快得多。如果要读取的数

    据就在缓存里的话，计算机就能进行高速处理；但如果需要的数据不在

    缓存里(即高速缓存缺失)的话，就需要读取内存，从内存中查找数据并将其读取到缓存里，这样一来就会浪费许多时间。

    也就是说，当某个对象 A 要引用在内存中离它很远的对象 B 时，以往

    的引用计数法会在增减计数器值的时候读取 B，从而导致高速缓存缺

    失，白白浪费大把时间。

    1 位引用计数法就不会这样，它不需要在更新计数器(或者说是标签)

    的时候读取要引用的对象。各位应该能看明白吧，在图 3.8 中完全没读

    取 C 和 D，指针的复制过程就完成了。

    此外，因为没必要给计数器留出多余的空间，所以节省了内存消耗量。

    这也不失为 1 位引用计数法的一个优点。

    3.6.5 缺点

    1 位引用计数法的缺点跟 Sticky 引用计数法的缺点基本一样。我们必须

    想个办法，看看怎么处理计数器溢出的对象。

    据 Clark 和 Green 的观测结果表明，很多对象的计数器值都不足 2。如

    果这个前提成立，那么把计数器溢出的对象放置不管也肯定没什么坏

    处。

    然而，我们没法保证 mutator 能一直顺利运行，很可能会出现很多对象

    计数器溢出的情况。

    上述情况下会生成大量计数器溢出的对象(也就是内存管理范围之外的

    对象)，这会给堆带来巨大负担。这样一来，我们就很难保证分块了。3.7 部分标记 - 清除算法

    3.7.1 什么是部分标记 - 清除算法

    之前已经讲过，引用计数法存在的一大问题就是不能回收循环的垃圾。

    这是引用计数法的一大特色，用 GC 标记 - 清除算法就不会有这种问

    题。那么我们自然会想到，只要跟之前使用延迟引用计数法时一样，利

    用 GC 标记 - 清除算法不就好了吗？也就是说，可以采用一般情况下执

    行引用计数法，在某个时刻启动 GC 标记 - 清除算法的方法。

    然而，这个方法可以说效率很低。利用 GC 标记 - 清除算法毕竟是单纯

    为了回收“有循环引用的垃圾”，而一般来说这种垃圾应该很少，单纯的

    GC 标记 - 清除算法又是以全部堆为对象的，所以会产生许多无用的搜

    索。

    对此，我们还有个方法，那就是只对“可能有循环引用的对象群”使用

    GC 标记 - 清除算法，对其他对象进行内存管理时使用引用计数法。像

    这样只对一部分对象群使用 GC 标记 - 清除算法的方法，叫作“部分标记

    - 清除算法”(Partial Mark Sweep)。不过它有个特点，执行一般的

    GC 标记 - 清除算法的目的是查找活动对象，而执行部分标记 - 清除算

    法的目的则是查找非活动对象。接下来我们就为大家介绍 Rafael D. Lins

    [9]

    于 1992 年研究出的部分标记 - 清除算法。

    3.7.2 前提

    在部分标记 - 清除算法中，对象会被涂成 4 种不同的颜色来进行管理。

    每个颜色的含义如下所示。

    1. 黑(BLACK)：绝对不是垃圾的对象(对象产生时的初始颜色)

    2. 白(WHITE)：绝对是垃圾的对象

    3. 灰(GRAY)：搜索完毕的对象

    4. 阴影(HATCH)：可能是循环垃圾的对象话虽这么说，事实上并没办法去给对象涂颜色，而是往头中分配 2 位空

    间，然后用 00～11 的值对应这 4 个颜色，以示区分。本书中用

    obj.color 来表示对象 obj 的颜色。obj.color 取

    BLACK、WHITE、GRAY、HATCH 中的任意一个值。

    为了解释算法，我们设一个堆，它里面的对象和引用关系如图 3.9 所

    示。

    图 3.9 初始状态

    有循环引用的对象群是 ABC 和 DE，其中 A 和 D 由根引用。此外，这

    里由 C 和 E 引用 F。所有对象的颜色都还是初始状态下的黑色。

    3.7.3 dec_ref_cnt 函数

    接下来，通过 mutator 删除由根到对象 A 的引用。这个引用是由

    update_ptr 函数产生的。跟以往的引用计数法一样，为了将对象 A

    的计数器减量，在 update_ptr 函数中调用 dec_ref_cnt 函数。

    不过在部分标记 - 清除算法中，dec_ref_cnt 函数和以往有少许不

    同。

    代码清单 3.16：部分标记- 清除算法中的 dec_ref_cnt 函数

    1 dec_ref_cnt(obj){

    2 obj.ref_cnt--

    3 if(obj.ref_cnt == 0)

    4 delete(obj)

    5 else if(obj.color != HATCH)6 obj.color = HATCH

    7 enqueue(obj, hatch_queue)

    8 }

    第 2 行到第 4 行的 dec_ref_cnt 函数和以往引用计数法中的没什么

    不同。不过，如果要删除的对象在队列中，那么这里使用的 delete

    函数也需要将该对象从队列中删除。

    我们该注意的是第 5 行之后。算法在对 obj 的计数器进行减量操作后，检查 obj 的颜色。当 obj 的颜色不是阴影的时候，算法会将其涂上阴

    影并追加到队列中。当 obj 的颜色是阴影的时候，obj 已经被追加到队

    列中了，所以程序什么都不做。

    dec_ref_cnt 函数执行之后的堆状态如图 3.10 所示。

    图 3.10 dec_ref_cnt 函数执行之后

    由根到 A 的引用被删除了，指向 A 的指针被追加到了队列

    (hatch_queue)之中。此外，A 被涂上了阴影。这个队列的存在是

    为了连接那些可能是循环引用的一部分的对象。被连接到队列的对象会

    被作为 GC 标记 - 清除算法的对象，使得循环引用的垃圾被回收。

    3.7.4 new_obj 函数

    在部分标记 - 清除算法中，我们不仅要修改 dec_ref_cnt 函数，也

    要修改 new_obj 函数。代码清单 3.17：部分标记- 清除算法中的 new_obj 函数

    1 new_obj(size){

    2 obj = pickup_chunk(size)

    3 if(obj != NULL)

    4 obj.color = BLACK

    5 obj.ref_cnt = 1

    6 return obj

    7 else if(is_empty(hatch_queue) == FALSE)

    8 scan_hatch_queue

    9 return new_obj(size)

    10 else

    11 allocation_fail

    12 }

    当可以分配时，对象就会被涂回黑色，执行这项操作的是第 3 行到第 6

    行。当分配无法顺利进行的时候，程序会调查队列是否为空。当队列不

    为空时，程序会通过 scan_hatch_queue 函数搜索队列，分配分

    块。scan_hatch_queue 函数执行完毕后，程序会递归地 调用

    new_obj 函数再次尝试分配。

    如果队列为空，则分配将会失败。

    3.7.5 scan_hatch_queue 函数

    scan_hatch_queue 函数在找到阴影对象前会一直从队列中取出对

    象。

    代码清单 3.18：scan_hatch_queue 函数

    1 scan_hatch_queue{

    2 obj = dequeue(hatch_queue)

    3 if(obj.color == HATCH)

    4 paint_gray(obj)

    5 scan_gray(obj)

    6 collect_white(obj)

    7 else if(is_empty(hatch_queue) == FALSE)

    8 scan_hatch_queue

    9 }如果取出的对象 obj 被涂上了阴影，程序就会将 obj 作为参数，依次

    调用 paint_gray 函数、scan_gray 函数和 collect_white 函

    数(第 4 行到第 6 行)，从而通过这些函数找出循环引用的垃圾，将其

    回收。关于各个函数我们会在之后按顺序解说。

    当 obj 没有被涂上阴影时，就意味着 obj 没有形成循环引用。此时程

    序对 obj 不会进行任何操作，而是再次调用 scan_hatch_queue 函

    数(第 8 行)。

    3.7.6 paint_gray 函数

    从 scan_hatch_queue 函数调用的 3 个函数中，首先调用的就是

    paint_gray 函数。它干的事情非常简单，只是查找对象进行计数器

    的减量操作而已。

    代码清单 3.19：paint_gray 函数

    1 paint_gray(obj){

    2 if(obj.color == (BLACK | HATCH))

    3 obj.color = GRAY

    4 for(child : children(obj))

    5 (child).ref_cnt--

    6 paint_gray(child)

    7 }

    程序会把黑色或者阴影对象涂成灰色，对子对象进行计数器减量操作，并调用 paint_gray 函数。把对象涂成灰色是为了防止程序重复搜

    索。在 scan_hatch_queue 函数中执 行 paint_gray 函数后，堆

    状态如图 3.11 所示。图 3.11 paint_gray 函数执行之后

    这里通过 paint_gray 函数按对象 A、B、C、F 的顺序进行了搜

    索。下面让我们来详细看一下，请看图 3.12。图 3.12 通过paint_gray 函数标记循环对象

    首先，在 (a) 中 A 被涂成了灰色。虽然程序对计数器执行了减量操作，但并不是对 A，而是对 B 的计数器进行了减量操作。下面在 (b) 中 B 也

    被涂成了灰色，不过这时程序并没有对 B 进行减量操作，而是对 C 进

    行了减量操作。在 (c) 中 C 被涂成灰色时，程序对 A 和 F 的计数器进行

    了减量操作。这样一来，A、B、C 的循环垃圾的计数器值都变成了 0。

    (d) 是 A、B、C、F 各个对象搜索结束后的样子。

    部分标记 - 清除算法的特征就是要涂色的对象和要进行计数器减量的对

    象不是同一对象，据此就可以很顺利地回收循环垃圾。关于这一点，我

    们将在 3.7.10 节中再为大家详细介绍。

    3.7.7 scan_gray 函数

    执行完 paint_gray 函数以后，下一个要执行的就是 scan_gray

    函数。它会搜索灰色对象，把计数器值为 0 的对象涂成白色。

    代码清单 3.20：scan_gray 函数

    1 scan_gray(obj){

    2 if(obj.color == GRAY)

    3 if(obj.ref_cnt > 0)

    4 paint_black(obj)

    5 else

    6 obj.color = WHITE

    7 for(child : children(obj))

    8 scan_gray(child)

    9 }

    打个比方，在图 3.11 这种情况下，程序会从对象 A 开始搜索，但是搜

    索的只有灰色对象。如果对象的计数器值为 0，程序就会把这个对象涂

    成白色，再查找这个对象的子对象。也就是说，A、B ......