GC 三色标记算法（Go & Java版本）-Toy模板网

这篇具有很好参考价值的文章主要介绍了GC 三色标记算法（Go & Java版本）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、前言

GC全称Garbage Collection，目前主流的垃圾回收算法有两类，分别是追踪式垃圾回收算法（Tracing garbage collection）和引用计数法（ Reference counting ）。

而三色标记法是属于追踪式垃圾回收算法的一种。追踪式算法的核心思想是判断一个对象是否可达，因为一旦这个对象不可达就可以立刻被 GC 回收了。

那如何判断一个对象是否可达呢？

在go推出三色标记法之前，Go 所使用的gc算法叫Mark-And-Sweep（标记清除）。这个算法就是严格按照追踪式算法的思路来实现的。

1.1 GC的发展

GC 三色标记算法（Go & Java版本）
上面是几个比较重要的版本.左图是根据 twitter 工程师的数据绘制的(堆比较大), 从 1.4 的百 ms 级别的停顿到 1.8 以后的小于 1ms.右图是我对线上服务(Go 1.11 编译)测试的一个结果, 是一个批量拉取数据的服务, 大概 3000qps, 服务中发起的 rpc 调用大概在 2w/s. 可以看到大部分情况下 GC 停顿小于 1ms, 偶尔超过一点点.

整体来说 golang gc 用起来是很舒心的, 几乎不用你关心.

1.2 标记清除算法

标记清除（Mark-Sweep）算法是最常见的垃圾收集算法，标记清除收集器是跟踪式垃圾收集器，其执行过程可以分成标记（Mark）和清除（Sweep）两个阶段：

标记阶段 — 从根对象出发查找并标记堆中所有存活的对象；
清除阶段 — 遍历堆中的全部对象，回收未被标记的垃圾对象并将回收的内存加入空闲链表；

如下图所示，内存空间中包含多个对象，我们从根对象出发依次遍历对象的子对象并将从根节点可达的对象都标记成存活状态，即 A、C 和 D 三个对象，剩余的 B、E 和 F 三个对象因为从根节点不可达，所以会被当做垃圾：
GC 三色标记算法（Go & Java版本）
标记阶段结束后会进入清除阶段，在该阶段中收集器会依次遍历堆中的所有对象，释放其中没有被标记的 B、E 和 F 三个对象并将新的空闲内存空间以链表的结构串联起来，方便内存分配器的使用。 GC 三色标记算法（Go & Java版本）
这里介绍的是最传统的标记清除算法，垃圾收集器从垃圾收集的根对象出发，递归遍历这些对象指向的子对象并将所有可达的对象标记成存活；标记阶段结束后，垃圾收集器会依次遍历堆中的对象并清除其中的垃圾，整个过程需要标记对象的存活状态，用户程序在垃圾收集的过程中也不能执行，我们需要用到更复杂的机制（三色标记法）来解决 STW 的问题。

1.3 垃圾收集的执行周期

CMS 收集器是基于标记-清除算法实现的，它的运作过程相对于前面几种收集器来说要更复杂一些，整个过程分为四个步骤，包括：

1）初始标记（CMS initial mark）暂停所有的其他线程（STW）。记录下 GC ROOT 直接引用对象，速度很快。

2）并发标记（CMS concurrent mark）并发标记阶段就是从 GC ROOT 行的直接关联对象开始遍历整个对象的过程，这个过程耗时比较长但是不需要停顿用户线程，可以与垃圾收集器一起并发运行。因此用户程序继续运行，可能会导致已经标记过的对象状态发生变化。

3）重新标记（CMS remark）重新标记阶段就是为了修正并发标记期间，因为用户程序继续运行而导致标记产生变动，的那一部分对象的标记记录。这个阶段的停顿时间一般比初始标记阶段的时间稍长，远远比并发标记阶段时间短。主要是用到三色标记里的增量更新算法

4）并发清除（CMS concurrent sweep）开启用户线程，同时 GC 线程开始对未标记的区域做清扫，这个阶段如果有新增对象会被标记为黑色不做任何处理（见下面三色标记算法详解）。

三色标记法是传统 Mark-Sweep 的一个改进，它是一个并发的 GC 算法。on-the-fly

二、什么是三色标记法

为了解决原始标记清除算法带来的长时间 STW，多数现代的追踪式垃圾收集器都会实现三色标记算法的变种以缩短 STW 的时间。
主流的垃圾收集器基本上都是基于可达性分析算法来判定对象是否存活的。根据对象是否被垃圾收集器扫描过而用白、灰、黑三种颜色来标记对象的状态的一种方法。而其中

白色对象 —表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始阶段，所有的对象都是白色的，若在分析结束之后对象仍然为白色，则表示这些对象为不可达对象，对这些对象进行回收。
黑色对象 —表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经被扫描过。黑色表示这个对象扫描之后依然存活，是可达性对象，如果有其他对象引用指向了黑色对象，无须重新扫描，黑色对象不可能不经过灰色对象直接指向某个白色对象。
灰色对象 — 表示对象已经被垃圾收集器访问过，但是这个对象至少存在一个引用（属性）还没有被扫描过。

三、三色标记的过程

从我们main方法的根对象（JVM中称为GC Root）开始沿着他们的对象向下查找，用黑灰白的规则，标记出所有跟GC Root相连接的对象（不递归），扫描一遍结束后一般需要进行一次短暂的STW(Stop The World)。

只需找出灰色对象并顺着继续往下标记（且因为大部分的标记工作已经在第一次并发的时候发生了，所以灰色对象数量会很少，标记时间也会短很多）, 此时程序继续执行，GC线程扫描所有的内存，找出扫描之后依旧被标记为白色的对象（垃圾）并清除。
GC 三色标记算法（Go & Java版本）
go 采用的是并发三色标记清除法. 图展示的是一个简单的原理.有几个问题可以思考一下:

并发情况下, 会不会漏标记对象?
对象的三色状态存放在哪?
如何根据一个对象来找到它引用的对象?

3.1 标记的原理

整个进程空间里申请每个对象占据的内存可以视为一个图，初始状态下每个内存对象都是白色标记。

第一轮：先stop the world，将扫描任务作为多个并发的goroutine立即入队给调度器，进而被CPU处理，第一轮先扫描所有可达的内存对象，标记为灰色放入队列。

第二轮：可以恢复start the world，将第一步队列中引用的对象置为灰色加入队列，一个对象引用的所有对象都置灰并加入队列后，这个对象才能置为黑色并从队列之中取出。循环往复，最后队列为空时，整个图剩下的白色内存空间即不可到达的对象，即没有被引用的对象；

第三轮：再次stop the world，将第二轮过程中新增对象申请的内存进行标记（灰色），这里使用了writebarrier（写屏障）去记录这些内存的身份；

这个算法可以实现 on-the-fly（即时），也就是在程序执行的同时进行收集，并不需要暂停整个程序。
GC 三色标记算法（Go & Java版本）

3.2 标记的步骤

（1）首先创建三个集合：白、灰、黑。
GC 三色标记算法（Go & Java版本）
（2）将所有对象放入白色集合中。

（3）然后从根节点开始遍历所有对象（注意这里并不递归遍历），把遍历到的对象从白色集合放入灰色集合。因为root set 指向了A、F，所以从根结点开始遍历的是A、F，所以是把A、F放到灰色集合中。
GC 三色标记算法（Go & Java版本）
（4）之后遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合，我们可以发现这个A指向了B，C，D所以也就是把BCD放到灰色中，把A放到黑色中，而F没有指任何的对象，所以直接放到黑色中。
GC 三色标记算法（Go & Java版本）
（5）重复 4 直到灰色中无任何对象，因为D指向了A所以D也放到了黑色中，而B和C能放到黑色集合中的道理和F一样，已经没有了可指向的对象了。

（6）通过write-barrier检测对象有无变化，重复以上操作，由于这个EGH并没有和RootSet有直接或是间接的关系，所以就会被清除。
GC 三色标记算法（Go & Java版本）
（7）收集所有白色对象（垃圾）

所以我们可以看出这里的情况，只要是和root set根集合直接相关的对象或是间接相关的对象都不会被清楚。只有不相关的才会被回收。

四、标记存在的问题—多标和漏标

垃圾收集器在并发标记的过程中，执行标记期间应用线程还在并行运行，对象间的引用关系时刻发生变化，垃圾收集器在标记过程中就容易发生多标和漏标（其实多标和漏标我们统称为误标）。

三色标记示例

public class TriColorMarking {

    public static void main(String[] args) {
        A a = new A();
        //开始做并发标记
        D d = a.b.d;   // 1.读
        a.b.d = null;  // 2.写
        a.d = d;       // 3.写
    }
}

class A {
    B b = new B();
    D d = null;
}

class B {
    C c = new C();
    D d = new D();
}

class C {
}

class D {
}

例子的一个简单说明：

在 new A() 的时候会创建引用关系 A -> B ，B-> C , B -> D;
当我们做并发标记的时候，垃圾收集器访问过 A、B、C、D 最终都标记为黑色。但是这个时候程序执行了一个 a.b.d = null 就标识 D 其实是没有引用，理论上 D 对象可以被回收。这种情况就产生了 “浮动垃圾”。
当我们发现了 D 没有引用，标记为白色，但是在标记完成过后发现 a.d = d 。又新增了对象引用如果将 d 回收掉程序就会报错肯定是不行的。这是一个典型的 “多标” 场景。

下面我们会通过并发标记的过程中出现的漏标和多标场景进行分析。

4.1 漏标

在并发标记过程中，将原本消亡的对象标记为存活对象，这就是漏标。就会产生浮动垃圾，需要等到下次 GC 的时候清理。

产生过程：程序删除了全部从灰色对象到该白色对象的直接或者间接引用。
GC 三色标记算法（Go & Java版本）
其实浮动垃圾是可以接受的只会影响垃圾收集器的效率，或者说是收集的比率。

4.2 多标

在并发标记过程中，将原本存活的对象标记为需要回收的对象。

产生过程：程序插入一条或者多条从黑色对象到白色对象的新引用。
GC 三色标记算法（Go & Java版本）
这种情况是不可以接受的，如果正在被使用的程序对象被 JVM 回收，会导致程序运行错误，是不可以接受的会导致严重 BUG。

五、解决漏标和多标的方案

解决漏标和多标分别有两种解决方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning, STAB）。

增量更新（Incremental Update）：在并发标记过程中，当黑色对象插入了新的指向白色引用关系时，就将这个插入引用记录下来，并发标记结束后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。简化理解, 黑色对象一旦新插入了指向白色对象的引用之后，它就变成灰色对象。
原始快照（Snapshot At The Beginning, STAB）：这并发标记过程中，当灰色对象要删除白色对象的引用关系时，就将这个需要删除的记录下来，在并发扫描结束后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次，这样就能扫描到白色对象，将白色的对象直接标记为黑色（目的就是为了让这种对象在本轮 GC 清理中能够存活下来，待下一轮 GC 的时候重新扫描，这个对象也可能成为浮动垃圾）总之，无论是引用关系记录插入还是删除，虚拟机的记录操作都是通过写屏障来实现的。

5.1 写屏障（Write Barrier）

GC 三色标记算法（Go & Java版本）
GC 最基本的就是正确性: 不漏标记对象, 如果程序还在用的对象都被清除了, 那程序就错误了. 有一点浮动垃圾是允许的.

在并发情况下, 如果没有一些措施来保障, 那可能会有什么问题呢?

看上面代码和图示, 第 2 步标记完 A 对象, A 又没有引用对象, 那 A 变成黑色对象. 在第 3 步的时候, muator(程序)运行, 把对象 C 从 B 转到了 A, 第 4 步, GC 继续标记, 扫描 B, 此时 B 没有引用对象, 变成了黑色对象. 我们会发现 C 对象被漏标记了.

如何解决这个问题? go 使用了写屏障, 这里的写屏障是指由编译器生成的一小段代码. 在 gc 时对指针操作前执行的一小段代码, 和 CPU 中维护内存一致性的写屏障不太一样哈.所以有了写屏障后, 第 3 步, A.obj=C 时, 会把 C 加入写屏障 buf. 最终还是会被扫描的.
GC 三色标记算法（Go & Java版本）
这里感受一下写屏障具体生成的代码. 我们可以看到在写入指针 slot 时, 对写屏障是否开启做了判断, 如果开启了, 会跳转到写屏障函数, 执行加入写屏障 buf 的逻辑. 1.8 中写屏障由 Dijkstra 写屏障改成了混合式写屏障, 使得 GC 停顿达到了 1ms 以下.

JVM 通过写屏障（Write Barrier）来维护卡表，卡表是记忆集的实现。记忆集是用来缩小 GC Root 的扫描范围，我们在 GC 的时候只需要去过滤卡表变脏（Dirty）的元素，找到具体一块卡页内存块，放入 GC Root 中一块扫描。这是大概的一个流程，后续会讲到，先有一个印象。再回到写屏障，下面是一个对象赋值操作：

/**
* @param field 某对象的成员变量，如 a.b.d 
* @param new_value 新值，如 null
*/
void oop_field_store(oop* field, oop new_value) { 
    *field = new_value; // 赋值操作
}

写屏障可以看做是虚拟机执行对象字段赋值的一个拦截，类比 Spring AOP 的切面思想。

void oop_field_store(oop* field, oop new_value) {  
    pre_write_barrier(field);          // 写前屏障
    *field = new_value; 
    post_write_barrier(field, value);  // 写后屏障
}

5.1.1 写屏障之STAB

当对象B的成员变量的引用发生变化时，比如引用消失（a.b.d = null），我们可以利用写屏障，将B原来成员变量的引用对象D记录下来：

void pre_write_barrier(oop* field) {
    oop old_value = *field;    // 获取旧值
    remark_set.add(old_value); // 记录原来的引用对象
}

5.1.2 写屏障之增量更新

当对象A的成员变量的引用发生变化时，比如新增引用（a.d = d），我们可以利用写屏障，将A新的成员变量引用对象D记录下来。

void post_write_barrier(oop* field, oop new_value) {  
    remark_set.add(new_value);  // 记录新引用的对象
}

5.2 读屏障（Load Barrier）

oop oop_field_load(oop* field) {
    pre_load_barrier(field); // 读屏障-读取前操作
    return *field;
}

读屏障是直接针对第一步：D d = a.b.d，当读取成员变量时，一律记录下来：

void pre_load_barrier(oop* field) {  
    oop old_value = *field;
    remark_set.add(old_value); // 记录读取到的对象
}

5.3 记忆集和卡表（Remembered Set And Card Table）

垃圾收集器在新生代建立了记忆集（Remembered Set）的数据结构，用来避免把整个老年代的 GC root 扫描一遍。事实上并不只是新生代、老年代之间才有跨代引用的问题，所有涉及部分区域收集（Partial GC）行为的垃圾收集器，典型的如G1、 ZGC 和 Shenandoah 收集器，都会面临相同的问题。记忆集是一种记录非收集区域指向收集区域的指针集合抽象的数据结构。

Hotspot 中使用一种叫做 “卡表” （Card Table）的方式来实现记忆集，也是目前最常用的一种方式。卡表和记忆集的关系，可以类比 Java 语言中 HashMap 和 Map 之间的关系。卡表是一个字节数组实现：CARD_TABLE[]，每个元素都对应着一个标识的内存区域一块特定大小的内存块，称为“卡页”。Hotsport 卡页的大小是 2^9 也就是 512 字节。
GC 三色标记算法（Go & Java版本）
一个卡页中可以包含多个对象，只要卡页内一个或者多个对象的字段存在跨代引用，其对应的卡表的元素标识就变成了1，表示该元素变脏，否则为 0。GC 时，只需要筛选卡表中变脏的元素加入到 GCRoot 中。