对三色标记法的理解

前言

最近在回看 JVM 的相关概念，看到了三色标记法的使用，所以就记录一下。

三色标记法是什么

在可达性分析的过程中，对象有且只有三种状态：完全没被扫描，对象被扫描但子对象还没完全被扫描，对象与其子对象都被扫描了。

而这三种状态即为三种颜色

白色：完全没被扫描。对象与子对象确定被回收。
灰色：对象被扫描但子对象还没完全被扫描。根对象确定存活，子对象可能被回收。
黑色：对象与其子对象都被扫描了。对象与子对象确定存活。

出现的原因

三色标记法是对堆上的对象进行归类，简化可达性分析中的重复扫描的工作量。

作用阶段

作用阶段包括初始标记与并发标记。

初始标记主要是确定 GC Root ，并把根节点标为灰色。初始标记需要暂停用户线程。

并发标记主要是根据 GC Root 往下扫描子对象，将子对象从白色扭转为黑色/灰色。并发标记过程标记线程与用户线程并行。

可能出现的问题

在进行回收前，对象有且只会存在两个颜色：黑色以及白色。
但由于扫描所有对象耗时久，所以扫描只能与用户线程并发，并发过程中会发生对象图关系的改变，会出现两个问题

1. 黑色对象变成了白色对象，最终应该被回收但未被回收，俗称浮动垃圾，下一次回收也行。
2. 白色对象变成了黑色对象，最终不应被回收却被回收了，会导致程序异常。

问题的原因

白色对象变成黑色对象的原因，需要同时满足下面两个：

1. 黑色根对象增加了对上述白色对象的引用。
2. 灰色根对象删除对白色子对象引用。

最后的结果是：白色对象实际上是黑色对象，但回收程序仍认为是白色对象。

问题的解决

针对上述的变动，解决办法有两个：

1. 增量更新：记录黑色根对象对白色对象的新增调用，并且以黑色根对象为根重新扫描这部分的引用。
2. 原始快照：记录灰色根对象删除对白色子对象的删除，并且重新扫描整个对象图。

	增量更新	原始快照
优点	扫描范围小，最终标记过程停顿时间短	不会产生浮动垃圾，根据对象图重新扫描
缺点	产生新的浮动垃圾。仅记录新增引用，未记录删除引用	最终标记时间长。扫描了整个对象图
适用范围	老年代。老年代对象引用变化少，上述缺点出现概率低	基于 Region 实现的垃圾收集器

最后的叨叨

为什么会有并发标记与最终标记两阶段

我觉得主要是为了尽可能缩短 STW 的时间。

两阶段更像是二八原则的具象化。80%对象关系不会变化，20%对象关系会变化（实际上更少）。

针对不会变化的部分，并发标记能减少业务感知的时间。针对变化的部分，则记录下来再 STW 确定最终引用关系。

本文首发于cartoon的博客

转载请注明出处:https://cartoonyu.github.io