【JVM精通之路】垃圾回收-三色标记算法

首先预期你已经基本了解垃圾回收的相关知识，包括新生代垃圾回收器，老年代垃圾回收器，以及他们的算法，可达性分析等等。

---

先想象一个场景

最开始黑色节点是GC-Roots的根节点，这些对象有这样的特点因此被选为垃圾回收的根节点。

虚拟机栈(栈桢中的本地变量表)中的引用的对象 
方法区中的类静态属性引用的对象 
方法区中的常量引用的对象 
本地方法栈中JNI的引用的对象

记不住没事~你只需要知道，这些对象都有长生不老的特点，它一直存在，所以从它开始遍历查找，才知道哪些对象没有人使用，可以被回收。

那么最开始堆里的对象默认都是白色的。

现在要开始垃圾回收了。

如果是你你怎么设计，嗯，我们因为有这张图从三维看二维开天眼立马知道哪些对象是活着的。

但是程序不知道，它需要遍历。这里需要注意一个其他博客都没有提到的点，这里是GC-Roots引用了右边的对象，而不是右边的对象引用了GC-Roots。

你可以这么思考，因为是Roots依赖了右边的某些对象，又因为Roots是持久存在的，那么右边某些对象也必须存在。所以是Roots引用了某些对象，所以这些对象必须存活。很多博客在这里没有说清楚引用关系。

如果是右边对象依赖了GC-Roots，那么右边的对象存在与否和Roots有什么关系？

因为人引用了空气，他需要空气，所以必须空气存在。

1.定义

黑色：一直存在不需要清理的对象，它用到的对象都确定需要存活。下一次不扫描黑色对象。

灰色：一直存在不需要清理的对象，它用到的其他对象还没确定是否存活。下一次从它开始扫描。

白色：扫描完毕后，还是白色的对象，就清理掉。

颜色的标记 记录在每个对象的头部信息的Markword中！

CMS有四步，初始标记（STW），并发标记，重复标记（STW），并发清除四步。

1.开始遍历

第一次遍历：

第二次遍历：

 第三次扫描：

 第四次扫描：

 第五次扫描：

 第六次扫描

 

 第七次扫描：

 然后这时候把所有白色对象清理掉。

以上的图的过程都是发生在并发标记中。先不考虑重复标记。

2.思考

2.1 三色标记解决了什么问题

思考一下，你现在幻身为一个线程，你只知道堆里有一堆对象，你并不知道他们是什么颜色，你现在只知道根节点在堆内存的哪个地址下。老板叫你去清理堆内存的废物对象。而且你随时可能会被CPU抽掉灵魂。（线程被阻塞）

你：我特么不能每次醒过来都从根节点去遍历吧。不行我得有个记事本，（线程可以访问标记记录集合）记住哪些我标记了的。这样下次直接从已经标记的对象开始遍历。

那这时候只需要黑白二色标记就够了。

但是有几个问题：

1.黑色太多了。我需要从很多黑色对象开始找，费时，麻烦！

2.我在把对象18由白色变黑的过程中，如果对象7把对象18抛弃了。那我是不是多标了。让本来应该死亡清除的对象18没有被清除。

3.现在堆内存中全都黑了，我要清理垃圾了。正要清理的时候，对象7突然引用了对象17，这时候就会出现漏标的问题。

如何解决呢？

思考...

---

问题1，那么能不能有个中间态。把还需要往下扫描的对象变成灰色，把不需要继续往下扫描的对象变成黑色。这时候往回看上文的扫描图，可以看见灰色节点的集合是非常少的，因此每次我只需要从较少的节点开始扫描

好了我手里有两个笔记本了。一个灰色笔记本，一个黑色笔记本。

解决了扫描对象过多的问题的同时也能解决STW的时间。

重新想起CMS有四步过程，初始标记（STW），并发标记，重复标记（STW），并发清除四步。

因为重新标记阶段也只需要从灰色节点开始扫描了。因为黑色是确定是活的，就算重新标记之后死掉了，也最多变成浮动垃圾，因为重新标记阶段是STW的，所以也不会有引用的变化。

并且只有并发标记的过程才会有引用的变化。

---

问题2，本来应该清除的对象没有被清除，这问题不大，当成浮动垃圾下一次垃圾回收再扫描一次就行了。多标本质造成浮动垃圾的问题。问题不大。

问题3，漏标怎么办，不能错杀啊。没有被标记的对象是要被杀掉的。不能被错杀。那么我必须stop the world了！STW。

只有停止所有用户线程才能避免我在标记对象的过程中，有对象复活了但是没被我标记，被活埋了！这个很重要。并不是因为三色标记才能避免漏标问题。三色标记只是为了减少STW的时间，以及减少遍历树的时间。

很多博客这里压根没讲清楚因果关系。只告诉你三色标记和标记清除算法里，有初始标记，并发标记，重复标记，怎么变色，多标，漏标问题。但是没把问题和解决方案对应起来。

我们都知道CMS有四步，初始标记（STW），并发标记，重复标记（STW），并发清除四步。

我不能从GC-Roots开始遍历的时候就STW一直到并发清除吧。STW这么长那么CMS的意义就不存在了。那么考虑哪些步骤可以与用户线程并发执行。

初始标记：将直接与GC-Roots的对象变灰，这部分速度很快，且不能出错，可以STW，性价比高。

并发标记：需要将对所有灰色节点遍历树结构，比较耗时，这部分肯定不能STW。

重复标记：这部分是最后扫尾工作，肯定不能让用户线程来参一脚，必须STW。并且修复并发标记时的错误标记，把并发标记漏标的白色变灰。

这里很多博客也没说清楚是什么错误。那么我们研究一下：并发标记只会让白变灰，或让灰变黑。

因为到重复标记时，堆内存只有黑白色了。

那么修复错误：

让白变灰：因为并发标记没有遍历到的对象一直白色，并发标记到重复标记开始之前如果有黑色对象引用到了白色对象。那么重复标记需要将白变灰。同时它是STW，这时变灰正好解决漏标。

为什么没有让黑变灰：正常来说并发标记标记为黑色后，但是之后黑色对象如果没有被任何对象引用了。需要将它变灰。但是重复标记只是扫尾工作，它是STW的，并且需要解决漏标问题。如果此时又让黑变灰，那么是否又考虑让灰变白。但是这两步完全可以放到下一轮垃圾回收的并发标记中去做，因为并发标记不STW，同时也能扫描到灰色对象。这里也是CMS单次回收不能很好解决浮动垃圾的问题，他可以解决，但是没必要。

之后并发清除可以清除白色对象了。

总结：

也就是三色标记法，可以区分标记的过程中的粒度，从而让垃圾回收器根据不同的标记阶段，更好的做出不一样的行为，并且对不同的行为采用不一样的STW规则，从而减少STW时间，增加用户线程运行时间。黑色就是需要活着的对象，灰色就是还需要往下遍历的对象，白色就是需要清除的对象。三个颜色也是标明了对象处于的扫描阶段。