浅谈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

vlambda博客
学习文章列表