深入理解 JVM 垃圾回收算法 - 标记清理算法

标记-清理(mark-sweep)、标记-复制(mark-copy)、标记-整理(mark-compact) 是 JVM 最常用的三种基本垃圾回收策略。大多数的垃圾回收器都会以不同的方式对这些基本回收策略进行组合，比如在新生代使用标记-复制算法，而在老年代使用标记-整理算法。



接下来的几篇文章会对这几种基本的垃圾回收算法做详细的介绍。

什么是标记-清理算法

标记-清理算法是实现 Tracing GC 语义最直接也最简单的算法。使用标记-清理算法的回收器在回收过程中分为两个阶段：

• 追踪(Trace)阶段：回收器从 GC Roots(寄存器、栈、全局变量) 开始遍历对象图，并标记所遇到的每个对象；

• 清理(Sweep)阶段：回收器检查堆中的每一个对象，并将所有未被标记的对象当作垃圾进行回收。



标记-清理算法是一种间接回收算法，它并非直接检测垃圾本身，而是先确定所有存活对象，然后反过来判断其他对象都是垃圾。



在开始具体的算法内容之前，先明确几个基本概念：

• Mutator：应用的执行者，可以简单的理解为“应用程序”，GC就是在 Mutator 的内部工作。Mutator 主要进行两种操作：创建对象和更新对象间的引用关系。与此同时，也会为用户做些额外的工作，比如数值计算、浏览网页等，在很多地方也被简单地称为赋值器；

• Collector：垃圾回收器，有时候也被直接称为回收器；

• Allocator：分配器，当 Mutator 需要创建新对象时，就会向 Allocator 申请一个大小合适的空间，Allocator 就会在堆中的可用空间中寻找满足要求的空间，返回给 Mutator。



我们可以用一句话来简单描述这三者是如何协同工作的：当 Mutator 需要创建对象时，就会向 Allocator 申请空间，如果没有足够的内存空间，则唤起 Collector，等待 Collector 完成相关工作后，再次尝试分配内存，如果仍没有足够内存，则说明堆内存耗尽整个流程可以用下面的代码来描述。



New() {
    // 赋值器尝试分配内存
    object = allocate();
    // 如果没有足够内存空间，分配内存失败
    if (object == null) {
        // 唤起回收器，执行垃圾回收
        collect();
        // 再次尝试分配内存
        object = allocate();
        // 如果还是分配失败，则说明堆内存耗尽，抛出错误
        if (object == null) {
            throw Out of memeory error;
        }
    }
    return object;
}



如果使用标记-清理算法的垃圾回收器，其垃圾回收过程可用如下代码来描述。



// 回收器执行垃圾回收
Collect() {
    // 从 GC Roots 开始标记
    markFromGCRoots();
    // 清理
    sweep(heapStart, heapEnd);
}



所有实现 Tracing GC 语义的垃圾回收器，它的第一个步骤就是枚举 GC Roots，然后从根节点开始标记，并把标记后的根节点加入一个工作列表 ( work list )，接着从工作列表中拿出根节点，对其所引用的对象进行标记，直到工作列表变空为止。



markFromGCRoots() {
    // 初始化一个空的工作列表
    workList = initWorkList();  
    // 遍历所有GC Roots
    for (root in Roots) {
        // 如果根节点未被标记，标记后把它扔到工作列表workList
        if (root != null && !isMarked(root)) {
            setMarked(root);
            workList.push(root);
            // 以此根节点为起点，遍历对象图
            // 如果遇到未被标记的节点就进行标记
            mark();
        }
    }
}
initWorkList() {
    return new Stack();
}
mark() {
    while (isNotEmpty(workList)) {
        // workList里面都是已经标记过的节点
        ref = workList.pop();
        // 获取ref引用的所有节点
        for (child in ref.getAllRefNodes()) {
            if (child != null && !isMarked(child)) {
                setMarked(child);
                workList.add(child);
            }
        }
    }
}



当使用栈来实现工作列表时，Collector 将以深度优先算法遍历对象图。如果熟悉算法的同学应该一眼就能看出，这段代码是使用非递归的方式来实现深度优先遍历，使用递归的方式可能会更直观一点：



markFromGCRoots() {
  for (root in Roots) {
    mark(root);
  }
}
mark(obj) {
    if(!isMarked(obj)) {
      setMarked(obj);
        for (child : obj.getAllRefNodes()) {
            mark(child);
        }
    }
}



整个流程结束后，Collector 就完成了对每个可达对象的访问与标记，任何没有打上标记的对象都是垃圾。



接下拉进入清理阶段，Collector 通常会在堆中进行线性扫描，即从堆底开始释放未标记对象，同时还需要清空已标记对象的标志位，以方便下次回收，其大致的流程可用如下代码描述。



sweep(heapStart, heapEnd) {
  object = heapStart;
    // 线性扫描所有堆空间
    // 如果对象已被标记则释放其标记位
    // 如果对象未被标记则释放其内存空间
    while (object < heapEnd) {
      if (isMarked(object)) {
          unsetMarked(object);
        } else {
          free(object);
        }
        object = object.next();
    }
}



标记-清理算法的优点是算法简单，实现容易，从上面的代码也可以看出来。而缺点也很明显：

• 内存碎片化：堆内存中容易出现大量碎片，不仅会导致内存利用率低，还会严重影响内存的分配速度，毕竟碎片越多，找到合适大小内存就越慢；

• GC效率低：由于 Collector 在清除阶段会遍历所有堆进行垃圾回收，堆越大，清除阶段花费的时间就会越长，因此 GC 时间与堆空间大小成正比；

• STW：标记-清理算法的基本假设是对象间的引用关系不会在标记阶段发生变化，也就是说执行标记操作时，需要暂停所有可能修改对象引用关系的线程。

如何改进标记-清理算法

三色标记法可以解决 Mutator 与 Collector(主要是标记阶段) 不能并发执行的问题，这一并发 GC 算法会在后面独立成文分析，这里主要说说解决其他两个问题的优化手段。

Bitmap marking

简单实现标记-清理算法时，对于每个可达对象，一般都会使用一个标记位(mark bit)来描述该对象是否已经被标记过。如果将标记位保存在对象头部通常会带来一些额外的复杂度，因为对象头部通常会存放一些 Mutator 的共享数据，例如锁或哈希值，那么当标记线程与 Mutator 并发执行时，就可能会产生冲突。所以为了确保安全，标记位通常会占用头部中一个额外的bit，以便与 Mutator 的共享数据区分，当然也可以使用原子操作来设置头部中的标记位。



在对象头存储标记位有一个很大的缺陷是不能发挥写时复制技术的优点，从而导致内存的浪费。



写时复制技术(copy-on-write) 简单来说就是类 Unix 系统调用 fork() 函数复制进程时，出于效率考虑，大部分内存空间都不会被复制，而是与父进程共享内存空间。只有当某个进程需要写入数据时，才会把父进程的内容复制一份给子进程，更多详细内容可自行搜索。



使用标记-清理算法时，即使没修改对象内容，GC也会设置所有活动对象的标志位，这样就会频繁发生本不应该发生的复制，也就相当于写时复制技术根本就没起作用。



而使用位图标记 (Bitmap marking) 则可以避免这个问题。位图标记使用一个独立的位图表格来维护标记位，从而与对象本身的管理区分开来。



其实现关键是位图表格中的每个位都要与堆中对象地址相对应，这就需要对象在内存中布局需要进行对齐。比如在 HotSpot 中，对象的起始地址必须是8字节的整数倍，也就是对象大小必须是8的整数倍，当实例数据部分大小不满足8的整数倍时，需要通过占位符来填充。



因为只有对象对齐后，扫描位图时，才能通过偏移量来计算出对应的内存地址，就如下图所示，一个位图表格关联一个堆，已知堆的起始地址和对象按多少字节对齐，就可以通过位图表格来查找到关联对象的首地址。



比如一个大小为 65536 字节的堆，所有对象以16字节对齐，那么堆内存中就有4096个地址可以作为对象的起始地址，与之对应需要4096个bit即大小为512字节的位图。



而位图表格的实现，则可以有多种方式，像哈希表和树形结构，甚至是数组都是OK的。



综上所述，位图标记相对于对象头标记位主要有两个优势：

• 清除操作更高效，以往的清除操作都必须遍历整个堆，把非活动对象连接到空闲链表，同时取消活动对象的标志位。利用了位图表格的清除操作则把所有对象的标志位集合到一处，所以可以快速消去标志位；

• 在类 Unix 系统中，在 fork() 进程时有利于利用写时复制技术提升内存利用率和性能。

Lazy sweeping

在标记-清理算法中，标记过程的时间复杂度是O(L)，L为堆中存活对象的数量；清理过程的时间复杂度是O(H)，H为堆空间大小，由于H>L，所以我们很容易误认为清理阶段的开销是整个标记-清理开销的主要部分，但实际情况并未如此。



标记阶段对象追踪过程中的内存访问模式是不可预测，而清理过程的可预测性要高得多，就比如上面提到的位图标记法，在清理时，甚至都不需要去遍历堆空间。同时，清理一个对象的开销也比追踪一个的开销小得多。



但我们仍然可以通过降低清理阶段的耗时来降低整个标记-清理的耗时。



对象标记存在以下两个特征：

• 一旦某个对象称为垃圾，就不可能再被访问或者复活

• Mutator 永远不会访问对象的标记位



基于这两个特征，清理操作完全可以与 Mutator 同时工作，甚至是使用多个清理线程与 Mutator 并发工作。但更为简单的方案是使用懒惰清理法。



它把清理操作放到 allocate(内存分配) 过程中，并且只在没有足够空间时才会去真正的进行回收，其算法实现如下所示：



// 整个垃圾回收只有标记阶段，而没有清理阶段
// reclaimList 为待回收内存块链表
Collect(){
    markFromRoots();
    // 这里以 block 为单位管理更高效
    for(block in Blocks){ 
        // 内存块中是否存在已标记过对象
        if (!isMarked(block)) {
            // 如果内存块中没有被标记过的对象，说明要么是未分配内存，要么全是垃圾
            // 将内存块归还给分配器
            add(blockAllocator, block);
        } else {
            // 将内存块添加到懒惰清扫队列
            add(reclaimList, block);
        }
    }
}            
// 分配
allocate(size) {
    // 尝试分配 size 大小的内存空间
    result = remove(size);
    // 如果没有足够可用空间
    if (result = null) {
        // 仅执行少量清理工作
        lazySweep(size);
        // 再次尝试分配
        result = remove(size);
    }
    // 如果还是分配失败，则需要调用 collect
    return result;
}    
lazySweep(size){
    while(block == null) {
        // 从可回收的懒惰队列里拿出 size 大小的内存块
        // 这里需要分配一个size大小的block
        // 可见block需要按大小分组管理的
        block = nextBlock(reclaimList, size)  
        if (block != null){
            // 清理内存块
            sweep(start(block), end(block))
            if (spaceFound(block)){
                return
            }
        }
    }
    // 获取一个新内存块
    // 如果获取失败，则需要执行垃圾回收
    allocSlow(size);
}    
// 获取一个空闲内存块
allocSlow(size){
    // 从块分配器中获取内存块
    block = allocateBlock(size);
    if block != null {
        // 新内存块通常需要通过设置元数据的方式进行初始化
        // 比如构建空闲链表或创建标记位图
        init(block);
    }
    return block;
}



在这种算法中，分配器通常只会在一个内存块中分配相同大小的对象，每种空间大小分级都会对应一个或多个用于分配的内存块，以及一个待回收内存块链表。



因为懒惰清除法不是一下子遍历整个堆，它只在分配时执行必要的遍历，所以可以压缩因清除操作而导致的mutator的暂停时间。除此之外，它还有以下优点：

• 更好的内存利用率，被回收的内存块会尽快地重新使用

• GC复杂度由 O(H) + O(L) 变成了 O(H)



深入理解JVM系列的第11篇，完整目录请移步：深入理解JVM系列文章目录

封面图：Ramón Salinero

参考资料

为什么“GC标记-清除算法”与“写时复制技术(copy-on-write)”不兼容？

Mark-Sweep 详析及其优化

垃圾回收算法手册：自动内存管理的艺术

垃圾回收的算法与实现