25-【扩展补充】JVM 三色标记增量更新原始快照

2024-01-14 12:22:52

1 基本算法

要找出存活对象，根据可达性分析，从GC Roots开始进行遍历访问，可达的则为存活对象：

最终结果：A/D/E/F/G 可达

我们把遍历对象图过程中遇到的对象，按“是否访问过”这个条件标记成以下三种颜色：

白色：尚未访问过。
黑色：本对象已访问过，而且本对象引用到的其他对象也全部访问过了。
灰色：本对象已访问过，但是本对象引用到的其他对象尚未全部访问完。全部访问后，会转换为黑色。

三色标记遍历过程

假设现在有白、灰、黑三个集合（表示当前对象的颜色），其遍历访问过程为：

初始时，所有对象都在【白色集合】中；
将GC Roots 直接引用到的对象挪到【灰色集合】中；
从灰色集合中获取对象：
3.1. 将本对象引用到的其他对象全部挪到【灰色集合】中；
3.2. 将本对象挪到【黑色集合】里面。
重复步骤3，直至【灰色集合】为空时结束。
结束后，仍在【白色集合】的对象即为GC Roots 不可达，可以进行回收。

注：如果标记结束后对象仍为白色，意味着已经“找不到”该对象在哪了，不可能会再被重新引用。

当Stop The World （以下简称 STW）时，对象间的引用是不会发生变化的，可以轻松完成标记。
而当需要支持并发标记时，即标记期间应用线程还在继续跑，对象间的引用可能发生变化，多标和漏标的情况就有可能发生。

浮动垃圾(多标)：将原本应该被清除的对象，误标记为存活对象。后果是垃圾回收不彻底，不过影响不大，可以在下个周期被回收；
对象消失(漏标)：将原本应该存活的对象，误标记为需要清理的对象。后果很严重，影响程序运行，是不可容忍的。

能不能在并发标记期间，将用户线程对引用关系的修改都保存起来？并发标记完成后，再将这些保存的修改过程，重新进行标记和调整？能，CMS 就是这么干的。它将并发标记期间引用发生变化的对象都暂存起来，并发标记完成后，再重新对这些暂存的对象重新进行一次标记。虽然重新标记的过程是需要 STW 的，但是重新标记的对象数量远远小于并发标记阶段的对象数量，因此停顿时间也是短暂且相对固定的，因此这个方法可行！

2 多标-浮动垃圾

假设已经遍历到E（变为灰色了），此时应用执行了 objD.fieldE = null ：

D > E 的引用断开

此刻之后，对象E/F/G是“应该”被回收的。然而因为E已经变为灰色了，其仍会被当作存活对象继续遍历下去。最终的结果是：这部分对象仍会被标记为存活，即本轮GC不会回收这部分内存。

这部分本应该回收但是没有回收到的内存，被称之为“浮动垃圾”。浮动垃圾并不会影响应用程序的正确性，只是需要等到下一轮垃圾回收中才被清除。

另外，针对并发标记开始后的新对象，通常的做法是直接全部当成黑色，本轮不会进行清除。这部分对象期间可能会变为垃圾，这也算是浮动垃圾的一部分。

3 漏标-读写屏障

假设GC线程已经遍历到E（变为灰色了），此时应用线程先执行了：s

var G = objE.fieldG; 
objE.fieldG = null;  // 灰色E 断开引用 白色G 
objD.fieldG = G;  // 黑色D 引用 白色G

E > G 断开，D引用 G

此时切回GC线程继续跑，因为E已经没有对G的引用了，所以不会将G放到灰色集合；尽管因为D重新引用了G，但因为D已经是黑色了，不会再重新做遍历处理。
最终导致的结果是：G会一直停留在白色集合中，最后被当作垃圾进行清除。这直接影响到了应用程序的正确性，是不可接受的。

漏标必须要同时满足以下两个条件：

赋值器插入了一条或者多条从黑色对象到白色对象的新引用；
赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。

这两个条件必须全部满足，才会出现对象消失的问题。那么我们只需要对上面条件进行破坏，破坏其中的任意一个，都可以防止对象消失问题的产生。这样就产生了两种解决方案：

增量更新：Incremental Update。
原始快照：Snapshot At The Beginning，SATB。

增量更新破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用时，就将这个新加入的引用记录下来，待并发标记完成后，重新对这种新增的引用记录进行扫描；原始快照破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，也是将这个记录下来，并发标记完成后，对该记录进行重新扫描。

HotSpot 虚拟机中，不管是新增还是删除，这种记录的操作都是通过写屏障实现的。我们可以将写屏障理解为 JVM 对引用修改操作的一层 AOP，注意它与内存屏障是两个不同的东西。

增量更新与原始快照在 HotSpot 中都有实际应用，其中增量更新用在 CMS 中，原始快照用在了 G1、Shenandoah 等回收器中。

增量更新

增量更新破坏的是第一个条件，在新增一条引用时，将该记录保存。实际的实现中，通常是将引用相关的节点进行重新标记。考虑下图中的例子：

上面就是一次引用关系修改导致的对象消失问题。增量更新进行的处理，就是将由 A 到 C 的这条新增的引用关系进行保存。首先看下 Dijkstra 等人提出的方式：

write_barrier(obj, field, newobj) {
    if (newobj.mark == FALSE) {
        newobj.mark = TRUE;
        push(newobj, $mark_stack);
    }
    *field = newobj;
}

如果新引用的对象 newobj 没有被标记，那么就将其标记后堆到标记栈里。换句话说，如果 newobj 是白色对象，就把它涂成灰色。这样操作后的结果如下图所示：

此时 C 被涂成了灰色，它将在后续被重新扫描，阻止了对象消失。

Steele 提出了一种更严厉的方法，它相比 Dijkstra 的方法，可以减少错误标记的对象数量。

write_barrier(obj, field, newobj) {
    if($gc_phase == GC_MARK && obj.mark == TRUE && newobj.mark == FALSE) {
        obj.mark = FALSE;
        push(obj, $mark_stack);
    }
    *field = newobj;
}

如果在标记过程中发出引用的对象是黑色对象，且新的引用的目标对象为灰色或白色，那么我们就把发出引用的对象涂成灰色。这样操作后的结果如下图：

此时 A 由原来的黑色变成了灰色，将在后续被重新扫描。

原始快照

原始快照破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，并发扫描结束后，在将这些记录重新扫描一次。

write_barrier(obj, field, newobj) {
    oldobj = *field;
    if(gc_phase == GC_MARK && oldobj.mark == FALSE) {
        oldobj.mark = TRUE;
        push(oldobj, $mark_stack);
    }
    *field = newobj;
}

当 GC 进入到标记阶段且 oldobj 没被标记时，则标记 oldobj，并将其记录。也就是说，在标记阶段中如果指针更新前引用的 oldobj 是白色对象，就将其涂成灰色。

上图依旧是对象消失的例子。a 到 b 中，产生了一条由 A 到 C 的引用关系，这里并没有像增量更新那样将 A 或者 C 标为灰色，相反原始快照中允许出现从黑色指向白色的引用。而在从 b 到 c 中，删除了由 B 到 C 的引用关系。这时候就需要进行处理，将 C 涂为灰色。

以上内容摘自：https://www.cnblogs.com/hongdada/p/14578950.html

码农公寓

1 基本算法

2 多标-浮动垃圾

3 漏标-读写屏障

增量更新

原始快照

相关文章