浅谈JVM GC三色标记算法

浅谈JVM GC三色标记算法

“同学，可以讲一下JVM的GC三色标记算法吗？”
“额……这个……这是啥……不了解”

这几天逛脉脉，有的网友提到面试的时候面试官问到了JVM GC的三色标记算法，好吧，看来Java面试真的已经是卷的飞起来，都开始问这种问题了……

那么今天，我们就来简单聊聊JVM的GC三色标记算法。

三色标记算法

三色标记法是一种垃圾回收法，它可以让JVM不发生或仅短时间发生STW(Stop The World)，从而达到清除JVM内存垃圾的目的。

三色标记可以简洁地描述回收过程中对象状态的变化，包括是否已经被标记，是否在工作列表中等。

三色标记是描述追踪式回收器的一种十分有用的方法，利用它可以推演回收器的正确性，这恰恰是回收器必须保证的。

三色标记算法模型中，将对象划分为三大类：

• 白色：未被垃圾回收器扫描过的对象，任意对象在初始状态下均为白色；
• 黑色：已经被垃圾回收器扫描过的对象，确认对象存活，当回收器完成该对象的扫描并找到其全部子节点之后，将其标记为黑色；
• 灰色：正在被回收器处理的对象，当回收器初次扫描到某一对象的时候将其着色为灰色。

目前主要采用三色标记法的回收器有CMS GC与G1。

工作过程

常见的垃圾回收器均采用了标记-清除算法，即通过GC ROOT为起点发起查找，寻找存活的对象，在这个过程中，对象的颜色变化如下图所示：

上图表示了一个基本对象图以及其标记栈（即工作列表的具体实现）在标记过程中某个阶段的状态。
标记栈中的所有对象都会再次得到访问，因此它们是灰色的，所有已经标记但不再标记栈中的对象都是黑色的，其他对象均为白色的。
但是，一旦mark方法完成对图的遍历，标记栈将变为空（即没有灰色对象），则只有对象C依然会是白色（垃圾），其他对象都将得到标记（黑色）。
上述算法中存在一个重要的不变式：在标记过程完成后，对象图中将不可能存储从黑色对象指向白色对象的引用，因此在标记过程中，所有白色可达对象都只能是从灰色对象可达的。

存在的问题

浮动垃圾：并发标记的过程中，若一个已经被标记成黑色或者灰色的对象，突然变成了垃圾，此时，此对象不是白色的不会被清除，重新标记也不能从GC Root中去找到，所以成为了浮动垃圾，这种情况对系统的影响不大，留给下一次GC进行处理即可。

对象漏标问题（需要的对象被回收）：并发标记的过程中，一个业务线程将一个未被扫描过的白色对象断开引用成为垃圾（删除引用），同时黑色对象引用了该对象（增加引用）（这两部可以不分先后顺序）；
因为黑色对象的含义为其属性都已经被标记过了，重新标记也不会从黑色对象中去找，导致该对象被程序所需要，却又要被GC回收，此问题会导致系统出现问题。
为了应对这个问题，而CMS与G1，两种回收器在使用三色标记法时，都采取了一些措施来应对，CMS对增加引用环节进行处理（Increment Update），G1则对删除引用环节进行处理(SATB)。

关于CMS的Increment Update与G1的SATB，本篇我就不进行过多的讨论，推荐JVM大神R大对于这两个知识点的详细解答：
https://hllvm-group.iteye.com/group/topic/44381?page=2

结语

好啦，就此我们就简单了解了JVM GC的三色标记法，如果再遇见面试官问你类似的问题，你可以好好秀他一脸咯。