GC算法笔记（一）标记-清除算法

发表于 | 分类于

在介绍JVM中提供的垃圾收集器之前，我觉得有必要先补充一下关于垃圾回收（以下简称 GC）的理论知识 —— 垃圾回收算法（以下简称 GC 算法）。

GC 算法的基本类型并不多，概括起来大概就以下三种：

  • 标记-清除算法 (Mark-Sweep) - 由 John McCarthy 1960 年在论文 Recursive functions of symbolic expressions and their computation by machine 中提出的标记-清除算法。
  • 引用计数法 (Reference Counting) - 由 George E. Collins 1960 年在论文 A method for overlapping and erasure of lists 提出的引用计数法。
  • 复制算法 (Copying) - 由 Marwin L.Minsky 1963 年在论文 A Lisp garbage collector algorithm using serial secondary storage 中提出的复制算法。

在这之后还出现了各种各样的 GC 算法，但究其根本都可以归纳为以上三种算法的组合和应用。

GC 算法的评价标准

聊算法总免不了要进行一番性能比较，既然要比较，就需要一些能够度量的标准。
以下列举了一些常见度量：

  • 吞吐量 (Throughput) - 在一段较长的时间内， 非 GC 运行时间所占总运行时间的百分比。
  • GC 开销 (Garbage collection overhead) - 与吞吐量相反，即 GC 时间占总时间的百分比。
  • 暂停时间 (Pause time) - 在整个程序执行过程中程序为了进行 GC 而停下来的时间。关于暂停时间的度量包括最大暂停时间、平均暂停时间和暂停时间的分布等。
  • 收集频率 (Frequency of collectoin)
  • 堆利用效率 - 不同的算法会引入不等的空间开销：
    • per-object 空间开销，比如引用计数法要求每个对象多加一块保存引用计数的空间，或者还有的算法需要标记位。
    • per-heap 空间开销，比如复制算法只能利用一半的堆空间。
    • 额外的数据结构，比如跟踪式 GC 算法 (Tracing Garbarge Collection) 可能需要使用栈来跟踪遍历，或者要使用单独的bitmap来保存标记等。
  • 可扩展性和可移植性 (Scalability and Portability) - 随着硬件（多核、并行能力）的提升和扩展、内存空间的扩展，GC 算法是否能有效利用硬件。

在选择 GC 算法时，要考虑到程序的应用场景，举几个例子：

  • 交互式 (interactive) 应用可能要求 GC 暂停时间要短，这样对用户操作才更友好。
  • 非交互式 (non-interactive) 应用，比如运行在后台的程序，对整个 GC 运行的时间的要求所占权重就更高。
  • 实时 (real-time) 应用则可能对 GC 暂停时间和 GC 总时间的占比上限都更低。
  • 运行在有限内存空间上的嵌入式应用可能对堆使用效率要求更高。
  • …

在进入本文的正题之前，还有一个问题要解决：哪些对象是需要回收的呢？
这就涉及到一个判定方法 —— 可达性分析。

可达性分析

可达性分析 (Reachability Analysis) 是现在主流商用程序语言 (Java、C#等）的实现中用于判断对象是否存活的一种算法。
它的基本思想就是通过一组被称为 “GC Root” 的对象作为起始点，从这些节点开始遍历，所经过的路径被称为 “引用链”，当一个对象没有存在于任何一个 “GC Root” 的引用链上时，就证明此对象是不可达的。这些不可达的对象就是要回收的对象。

举个例子，如下图所示，对象 object 6、object 7、object 8 都是GC Roots 不可达的，所以它们会被判定为可回收对象。
reachability analysis example

那么哪些对象属于 “GC Root” 呢？通常包括如下几类：

  • 寄存器中的数据 (registers)
  • 栈中的数据 (stack)
  • 全局静态数据 (global static data)

一切就绪，我们终于可以揭开标记-清楚算法的神秘面纱了~

标记-清除算法

顾名思义，标记-清除 (Mark-Sweep) 算法分为两个阶段：

  • 标记阶段 - 先标记出所有需要回收的对象
  • 清除阶段 - 统一回收所有被标记的对象

标记阶段

标记阶段的主要工作就是利用可达性分析将需要回收的对象标记出来。
伪码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
mark_phase () {
    // 挨个遍历所有的 GC Roots
    for (r: roots) {
        mark(r)
    }
}

mark (obj) {
    if (obj.mark == FALSE) {
        obj.mark = TRUE
        // 遍历子节点
        for (child: obj.children) {
            mark(child)
        }
    }
}

  • 考虑到深度优先遍历比广度优先遍历内存使用量要小一些，在标记阶段常用深度优先遍历
  • 标记阶段会标记所有的活动对象，由此可知，标记时间与活动对象的总数成正比

清除阶段

在清除阶段，GC会遍历整个堆，回收未被标记的对象（即垃圾们）。
伪码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
sweep_phase () {
    cursor = $heap_start; // $heap_start表示堆首地址
    while (cursor < $head_end) {
        if (cursor.mark == TRUE) {
            cursor.mark = FALSE // 重置标记状态，准备下一次的 GC
        } else {
            // 将当前对象空间释放，连接到空闲链表头部
            cursor.next = $free_list
            $free_list = cursor
        }
        cursor += cursor.size // 跳过当前对象所占空间，指向下一个对象
    }
}

  • 在清除阶段，GC 会遍历整个堆，也就是说，清除时间与堆大小成正比

我们可以通过一张图来看看堆中的空间在垃圾回收前后状态的变化：
mark-sweep memory

不难看出，经过多轮空间分配和垃圾回收后，堆从一整片完整的空间被划分为了很多不连续的碎片。空闲链表中的每个节点就都指向这样一个大小不一的分块。

合并

如果在清除垃圾时发现前后两个分块是连续的，则可以考虑把小分块连在一起形成一个大分块。
这种连接连续分块的操作就叫做合并。

合并在清除阶段进行，后续我们将看到的 Mark-Sweep-Compact 算法其实可以看作是对合并的进一步优化。

空间分配策略

空间被回收后的分配策略又应该是怎样的呢？

有三种分配策略可供选择：

  • First-Fit - 选择找到的首个大于等于所需要空间大小的分块。
  • Best-Fit - 选择找到的大于等于所需要空间的最小分块。
  • Worst-Fit - 找到空闲链表中最大的分块，将其分割为申请的大小和剩余的大小。目的是将分割后的分块最大化，但这样做很容易产生大量的小分块，不推荐使用。

优缺点

优点很显然，实现简单。
什么，就这一条？
大道至简，这还不够优秀吗？

缺点

缺点那可得好好说说了。

碎片化 ragmentation)

上文也提到了，标记-清除算法在使用过程中会产生逐步被细化的分块。

  • 如果碎片化严重，即使堆中分块的总大小够用，也会因为每个分块太小而不能执行分配。

  • 一般在将数据从内存读取到缓存中时，考虑到“访问的局部性”效应，会将其附近的数据读取到缓存中。如果能把具有引用关系的对象安排在邻近位置则能提高在缓存中读取到想利用的数据的概率。而碎片化很可能导致对象相隔太远，降低高速缓存命中率。

    「Note」 程序在运行时可能表现出良好的时间局部性或空间局部性，而高速缓存可以利用这样的局部性提升程序的性能。

    • 时间局部性 (temporal locality) - 一旦程序访问了某个内存地址，则很可能在不久之后再次访问该地址，因此值得将它的值缓存。
    • 空间局部性 (space locality) - 一旦程序访问了某个内存地址，则很可能在不久之后访问该地址附近的数据。
      现代硬件可以从两方面利用程序的局部性，一方面，高速缓存与更低级别内存之间不会进行单个字节的数据传输，而是以固定字节数的最小传输单元，通常为 32 - 128 字节；另一方面，处理器可能会使用硬件预取 (prefetch) 技术，例如探测有规律的内存访问操作，从而提前读取数据流。

分配速度受限

由于分块不是连续的，每次分配都必须遍历空闲链表，找到足够大的分块。最坏的情况下，每次进行分配都会要遍历整个空闲链表。

与写时复制技术不兼容

写时复制技术 (Copy-on-write) 是指在复制进程时（比如执行fork()函数)只是装作复制了内存空间，实际上是将内存空间共享了。如果只是从内存空间上读数据，访问共享内存并没有问题。但是如果要进行写入操作，就不能直接重写共享内存，而需要复制自己私有空间的数据，对这个私有空间进行重写，复制后只访问这个私有空间而不再访问共享内存。也就是说，这么技术是在写入时才进行复制，因而被称为写时复制技术。

正因为这种特性，标记-清除算法每次进行标记时都要对对象执行写入操作，从而触发写时复制，这样会导致频繁发生本不应该的发生的复制。

优化

针对上文指出的缺点，我们可以针对性的采取一些优化措施。

多个空闲链表

由于空间的不连续性，每次都有可能要遍历整个链表来找到合适大小的分块。针对这一情况，我们可以按照分块大小创建多个空闲链表。比如创建一个分块大小全是 2 个字长的空闲链表，一个分块大小全是 3 个字长的空闲链表，…，一个分块大小全是 N 个字长的空闲链表。

问题是，创建多少个空闲链表才好呢？总不能无止尽的建下去吧。

一般来说，很少会申请非常大的分块，所以我们可以设定一个上限，如果分块大小大于等于这个大小，就都交给一个空闲链表处理。反正这种情况是极少数，效率低一点对整体的影响不大。

BiBOP

发生碎片化的原因之一就是堆上散布着大小各异的对象。而BiBOP (Big Bag of Pages) 的意思就是把堆分割成固定大小的块，每一块的大小可以不同，但一个特定大小的块只能配置同样大小的对象。
这样做的目的原本是为了消除碎片化，但效果并不一定好。比如如果在全部用于 2 个字长的块中只有一个两个活动对象，其实大多数的 2 个字长的分块仍然是分散且未能利用的碎片。

位图标记

前面提到的标记是直接作用在对象上，另一种标记方式则是将对象的标志位单独拎出来，与对象分开管理。通常我们称这组标志位的集合为位图表格 (bitmap table)。利用这个表进行标记的行为就被称为位图标记。
位图表格的实现方式有很多，数组、散列表、树形结构等都行，只要能保证每一位能与堆中的对象一一对应即可。一般来说，堆中的 1 个字会分配到 1 个位。

位图标记比直接在对象上标记实现复杂，但这样做有两个好处：

  • 与写时复制技术兼容 - 使用位图标记就不需要对堆上的对象执行写入操作了，可以避免多余的对象复制。虽然对位图表的重写还是会触发对位图的复制，但位图表非常小，所以代价不那么大。
  • 清除操作更高效 - 利用位图表格的清除操作把对象的标志位集中到一起，可以快速重置标志位。

「Note」如果有多个堆，一般会为每个堆准备一个位图表格。

延迟清除

上文有提到清除操作花费的时间与堆的大小成正比，处理的堆越大，清除需要的时间就越长。

但是不是清除阶段的开销就时整个标记-清除过程的主要部分呢？这可不一定。这是因为标记阶段追踪指针过程中的内存访问模式是不可预测的，而清除阶段的可预测性要高得多，同时清除一个对象的开销也比追踪的开销小得多。因此，优化清除阶段高速缓存行为的一种方案是使用对象预取。

除此之外，我们还可以考虑进一步降低清除阶段的暂停时间。分析可知，对象及其标记位具备两个特征：

  • 一旦某个对象成为垃圾，它将一直是垃圾，不能再被赋值器访问或复活；
  • 赋值器永远不会访问对象的标记位。

由此，我们可以在赋值器工作的同时启动多个清除线程并发工作。

当然啦，还有更简单的方案，那就是 —— 延迟清除 (Lazy Sweep) 。

延迟清除是针对缩减清除操作所用时间的优化。主要改进就是在标记结束后，不一定立马进行清除操作，而是延迟到下一次为新对象分配空间时，将寻找可用空间加清除垃圾的任务放到分配空间的过程中。

延迟清除采用一个全局变量来记录上一次清理后返回的分块结束的位置：

  1. 当要申请新空间时，先检当前这个对象的标志位，如果被标记了则检查下一个；
  2. 如果没被标记，则检查当前这个分块的大小够不够用，如果够用就直接返回分块并停止清除；
  3. 如果不够，就继续找下一个
  4. 如果没找到，就申请空间失败

延迟清除不是一下遍历整个堆，而是只在分配时执行必要的遍历，从而缩短了清除操作导致的暂停时间。

「Note」延迟清除的效果是不均衡的。

  • 如果可回收对象是连续的一片空间，形成了邻接状态，那么延迟清除能很快获得合适的分块
  • 如果延迟清除的指针进入了大批活动对象所处的范围，则很可能一直查询失败，直到遍历完所有的活动对象才找到合适的空闲分块

很久以前看 Node 的时候也有概括过标记-清除算法，不过没有这么详细。
别看标记-清除的缺点不少，但它的主要思想真的是GC算法最最基本的始祖。那关于标记-清除算法的笔记到这里就差不多啦。

7/21 17:26
熬夜加失眠使我现在脑子不太清醒，有点晕乎乎的，今天先这样吧。先去回个血，回见～

参考资料

  • 垃圾回收的算法与实现
  • 垃圾回收算法手册：自动内存管理的艺术
  • 深入理解 Java 虚拟机（第二版）