三分钟了解JVM的垃圾回收和三色标记

今天，我争取用三分钟，说清楚JVM中的垃圾回收和三色标记，倒计时，开始。

---

什么是垃圾

垃圾的定义

垃圾，在我们日常生活中，就是使用过后不再需要的东西。并且随着时间的推移，你产生的垃圾会越来越多。怎么清理垃圾，何时清理垃圾，就显得尤为重要，毕竟你也不希望你的家里充满了垃圾吧？

而在计算机的世界里也是一样，不管我给你一块128m，256m，还是4g，8g，16g的内存，它都是一个有限的空间，就像我们的房子，70平，80平，100平就这么大。我们的程序在运行中也会产生垃圾，计算机中有无数的内存对象，每一块逻辑，每一个行为，都有可能产生新的对象，当这些对象不再使用的时候，就变成了垃圾。这些垃圾，如果不及时合理的清理，计算机的内存一样会被吃满，导致最终无法再正常运行。

寻找垃圾

那么，计算机是怎么找垃圾的呢？
一般来说，有两种算法能找出哪些内存对象是垃圾——引用计数法和可达性分析法

引用计数法

想象一下，你爸妈买了一个玩具回家，这个玩具，你要玩，你哥哥要玩，你妹妹要玩，你们三个人都要玩，如果把这个玩具对比计算机中的内存对象，那么这个对象的引用计数就是3。
假如有一天，你妹妹买了别的玩具，不再跟你们一块玩你们的玩具，这个时候，这个玩具的引用计数就是2。
又过了几天，你哥哥要上学去了，他也不再玩玩具了，这个玩具的引用计数就是1。
最后，你长大了，对玩具也没兴趣了，这个玩具的引用计数就变成了0。
这个时候，它就成了垃圾，是一个可以被扔掉，被清理掉的垃圾。

当然了，引用计数法有什么问题吗？有的！
男生小时候玩过四驱车吧，假如有一天，你妈妈跟你说，来，我们收拾一下，把你不用的四驱车零件扔了。
她拿起了一个轮圈问你，这个有用吗，你说这个轮圈要套在轮毂上。于是她又拿起了你的轮毂问，这个有用吗，你说这个轮毂要装在轮圈里。
你妈啪的一巴掌就呼过来了，说，你的四驱车不是都有轮胎吗，这俩多出来的你还要它干嘛？

这个问题就显而易见了，对于轮圈来说，轮毂要用它，那么它的引用计数就是1，而对于轮毂来说，轮圈要用它，那么它的引用计数也是1。但是，这兄弟俩都是多出来的零件，所有的四驱车都有轮胎了，这俩多出来的零件谁也不需要了。对这俩的整体来说，它俩都是垃圾。

当然了，对于我们人来说，我们肯定轻而易举就能知道，我不管你俩都用谁，你俩现在都是垃圾，都得扔掉。而对于计算机来说，就很困难了，在引用计数法里，计算机只看你身上的引用计数是不是0，只要不是0，我就不认为你是垃圾，就不能清理你。这样一来，这种垃圾就会越堆越多。这就是常说的引用计数法中的循环引用的问题，不止是两个对象相互引用，甚至会有三个四个对象循环引用。

可达性分析法

相比于引用计数法，可达性分析法就更能精确的找出谁是垃圾，谁不是垃圾了。可达性分析法可以用一句话就概括了
顺着根对象，找出所有有引用的对象，不在根对象的引用范围内的，都是垃圾

我们还是以四驱车为例。假如我们有四辆车，有一天，你妈妈又说了，把你这四辆车用不到的零件都扔了。

这次，她不一个一个问你有没有用了，她顺着你的四驱车的车架子一个一个找零件，这个轮圈归车A，这个轴承归车B，那个马达归车C， 那个电池归车D，就这样，你妈妈就从ABCD四辆车找齐了所有他们用到的零件。

这时候，她再回头看，诶？这个轮圈和轮毂，是不是多出来的？你说是。于是这俩，就成了垃圾。
再一看，这个马达，那个电池，通通没有用，全都是垃圾。

怎么清理垃圾

找到了垃圾，那么我们怎么清理垃圾呢？垃圾回收算法有很多，这里简单说说常见的几种垃圾回收算法，以下算法均是基于可行性分析法寻找垃圾的

就拿我们小时候玩的游戏王卡片举例吧，假如在你的房间整整齐齐的摆放一堆的卡片，你的小伙伴又不断的送你新的卡片，这是你需要看看，把哪些卡片扔掉，哪些卡片留下

标记-清除

标记清除就很简单暴力。你就直接从你的卡片堆里找哪些不要的卡片，找到了，就扔掉。
扔完之后，你可能会发现，整整齐齐排列的卡片中，这里缺一块，那里缺一块，很难看。

如果这个时候，你有五张黑暗大法师的卡片（男生都懂得吧，五张卡片可以合成一个黑暗大法师），你想把它们放一块，你就只能往最后面放，而不能插入到中间。（内存空间碎片化）

标记-复制

你把你的房间分成两片区域，新来的卡片，你先把它扔在区域A，你看着差不多快堆满的时候，想要清理一些不要的，你就会先把区域A里要用的卡片，一个一个拿出来，挨个整齐的摆放在区域B，完事之后，你再把区域A剩下的卡片全部扔掉。
这时候又不断的来了一些新的卡片，你把他们继续扔在区域B，你看着差不多快堆满的时候，再把区域B要用的卡片一个一个拿出来，挨个整齐的摆放在区域A，完事之后，再把区域B剩下的卡片全部扔掉。如此往复。

这样一来，你的这个房间的卡片中，不会有一个一个的洞，所有的卡片也都能整齐摆放。当然了，你很快就会发现，这样问题也很明显，就是我能装1000张卡片的房间，现在最多只能装500张了，另一半要用来清理垃圾。（内存空间利用率减半）

标记-整理

你把房间里的卡片，一个一个的整理，把有用的排前面，没用的扔后面，最后再把没用的扔掉。这样最后你也可以得到一个整齐摆放的干净的房间，但是你会发现，要清理一次不用的卡片，会花费你很多时间。

分代收集

这个算法其实没有什么新鲜的东西，它只是在房间的规划上更复杂了。它把房间分成了初始区（Eden），活跃A区（Survivor0），活跃B区（Survivor1）和老年区（Old）。

简单来说，新来的卡片，你都会把它扔在初始区，你会不断对初始区和两个活跃区进行扫描，看哪些卡片是不要的。

首先你会看初始区和活跃A区，把要用的卡片都一个一个放到活跃B区，然后再把初始区和活跃A区剩下的卡片都扔掉。这个过程其实就是上面说到的标记复制算法，不同的是，我把卡片整理扔过去之后，需要在卡片的上面记个数。
好，再来一次扫描，你会看初始区和活跃B区，把要用的卡片都扔到活跃A区，然后把初始区和活跃B区剩下的卡片都扔掉，然后你再把这些卡片的计数加一。(YoungGC)

就这样反反复复的折腾，直到有一次你再整理的时候，你发现有一堆卡片，它身上的计数都是达到15次了，也就是你整理了15次，它都是有用的，那么你毫不犹豫的把它们扔到了老年区，处于这个区域的卡片，扫描的频率就会很低了，因为你知道，这些你都是要常用的。（升代）

又过了很久很久，你发现你的老年区的卡片堆到百分之七八十了，你觉得把老年区也一块扫描了吧，于是你来了一次大清理，把老年区不要的卡片也都扔掉，这个期间，你告诉你的小伙伴（用户线程），你等一会给我卡片，等我清理完了（标记清除算法），你再给我。（Full GC）

又过了很久很久，你发现不管你整理初始区和两个活跃区，还是老年区，你的卡片都是有用的，这个时候，你很难过的告诉你的小伙伴，你的卡堆满了，再送也装不下了（OOM）。

一边产生垃圾一边清理垃圾

我们每次在整理垃圾的时候，都需要用户线程暂停，也就是一个很酷的单词（STW——Stop The World），因为内存对象的引用关系是在不断变化的，不暂停用户线程，很难正确的进行垃圾回收，像原来的Serial和Serial Old，PS（Parallel Scavenge）和PO（Parallel Old），其实都是需要STW来回收垃圾的。

很显然，这对响应要求高的程序是不能接受的，不能因为你在清理垃圾，我就什么都不能干了吧？于是，三色标记算法诞生了。

三色标记

别看它名字叫三色标记，听起来挺高大上，实际上它就是把对象分成了三个不同的状态，扫描标记垃圾的时候，会根据它的状态来扫描。
三色分为黑白灰三个颜色，当然，叫什么颜色无所谓，你要叫它红绿蓝，或青橙紫，都没问题，它代表的就是三种状态。

• 白色：还没有被扫描到的对象。这样对象，会被从头扫描。
• 黑色：自己和自己的所有引用都被扫描完了的对象。这样的对象，不会再被扫描。
• 灰色：自己和自己的所有引用中，一部分被扫描了，但还没扫描完。这样的对象，还需要继续扫描。

在并发标记的情况下，由于多线程在CPU时间片的分配是不确定的，很可能垃圾回收线程扫描到一半，CPU就切换到用户线程了，所以用三色标记法，可以记录下当前扫描的情况，以便于下次切回来的时候继续扫描。

三色标记的Bug

其实只要涉及到并发了，难免就会产生一些令人头疼的Bug。
假如班级组织春游，老师（垃圾回收器）把班里的同学（内存对象）分成了ABC三个小组，每个小组有一个小组长。
出发之前，老师开始点名，把A组的同学全部点完了，开始点B组，B组同学刚点完一半，老师想去上厕所，这时候老师跟三个组长分别说了一句话

跟A组的组长说，一会回来提醒我一下你们组点完了（黑色）
跟B组的组长说，一会回来提醒我，你们组点了一半，点到了谁谁谁（灰色）
跟C组的组长说，一会回来提醒我，你们组还没开始点（白色）

于是当前的三色标记状态如下：

多标

即已经标记完的对象，有一个引用消失了

在老师上厕所的时候，A组有一位同学X（已经点完名的那组），家里有点事，他的爸爸妈妈来学校把他接走了。
过了几分钟，老师回来了，老师继续点名，点完了B组，点完了C组。好，大家一块出发了。

X同学呢，就已经回家了，但是老师还不知道，名单上依然有这么一个人（如果集体买雪糕或者集体买门票的话，就会始终多出来一个），因为他所在的A组点名已经点完了，所以等老师再回来的时候，也不会再点他的名字了，所以直到最后大家出发，老师也没有发现少了一个人。

这就是三色标记算法产生的浮动垃圾。这部分的垃圾对程序的正确并不会产生什么影响，并且在老师下次点名的时候（下一次垃圾标记），就能把X同学（浮动垃圾）从名单上划掉

漏标

还是上面的情形，老师还是去上厕所了，这时候，B组有一位Y同学和他们组的一个同学产生矛盾了，一怒之下离开了B组（与B的小组长断开引用），并加入了A组（与A的小组长建立引用）。
过了几分钟，老师回来了，老师继续点名…由于Y同学离开了B组，所以老师点B名单的时候，不会点到Y，而老师已经点过了A组的名单，因此也不会再回去点A组的同学了。这样的话，Y同学就变得多余了（变成垃圾了），春游时老师买门票的时候，就不会给Y同学买门票。

这个bug，可比浮动垃圾的bug严重多了，这会直接导致程序出现bug，大家开发中引用的好好的对象，突然就null了，还一脸懵逼。

各种并发的垃圾回收器的算法，其实最主要需要解决的，就是这个bug

CMS的漏标解决方案

CMS全称是Concurrent Mark Sweep，即并发标记清除，它主要分四个阶段——初始标记（扫描根节点，STW，但很快），并发标记，重新标记（STW，停顿最长），并发清除，它的诞生其实就是开辟一条并发垃圾回收的道路，起着承上启下的作用，CMS就不过多展开了，这里主要说说它对于并发标记的漏标的处理方式——Increament Update增量更新。
其实理解起来非常简单，就是当一个黑色的对象下面，产生了一个新的引用的时候，这个黑色的对象就变灰（写屏障）。

还拿上面的例子举例，当Y同学要从B组跑到A组的时候，A组已经是点完名的了，但是当老师回来的时候，A组的组长报告老师说，我们组还有一个Y同学没有点名，这时候，老师就能把这个Y同学点上了。

这样一来，漏标问题看似就解决了。看似解决了，看似解决了。

没错，这里面还有相当隐蔽的一个bug。
还是上面的例子，B组点了一半， 老师还是去上厕所了，这时候，C组还没点名呢，C组有一个Z同学，跑B组来了，并且坐在已经点完名的那片同学当中，这时候老师回来了，接着点名，点完B组还没点的同学和C组的同学，但是Z同学点不到名了，因为他藏在了B组已经点完的那部分当中，这种情况下，Z同学就不会被点上名。

这个比喻稍有不恰当的地方：灰色对象中，假如有已经扫描完的引用A和未扫描的引用B，垃圾回收线程暂停的时候，引用A指向了一个白色对象，这时候垃圾回收线程恢复的时候，不会再扫描A了，因为A已经扫描过了，这时候，A依然会被漏标。

那CMS对于这样的情况怎么解决的呢？嗯，就是STW，重新扫描一遍（重新标记）。大家都别活了，从头屡！
虽然说CMS的诞生就是为了解决STW的问题，但是STW时间最长的也是它。

G1的漏标解决方案

G1，即Garbage first，是jdk1.8以后的主流垃圾回收器，后面有时间，可以再详细讲讲G1的垃圾回收机制（基本上可以淘汰掉CMS了），这里还是以漏标问题解决为主。G1对于漏标问题的解决方案是SATB（Snapshot At Begining），即原始快照。当灰色对象指向一个白色对象的引用消失时，我们会把这个引用记录在GC堆栈中。三色标记+SATB其实就是G1核心算法中的一部分了。

还是以上面的例子来说，老师上厕所去了，B组同学Y还是跑到了A组，同时，这位同学在黑板上写，B组的Y。等老师回来的时候，老师看到了就会问Y，你现在到哪组了啊，Y说我到A组了，那么老师就会记上Y的名字（标灰）。

这样的解决方法，其实就可以比较完美的解决了漏标问题，虽然也有产生浮动垃圾的bug，但是至少既能保证程序的正确性，又能保证垃圾回收的效率。

关于G1，其实还有很多不同于CMS的优化算法，有时间再研究研究，写一篇G1的分析

---

看到这里，不知道大家有没有计时，有没有三分钟内看完，如果没有的话，那我下次再节省一点篇幅，争取用最简单语言，最形象的比喻，描述最晦涩的技术点。

对于JVM的垃圾定义，垃圾回收，以及三色标记，网上其实能搜到的文章教程一大堆，但是我发现很少有人能把它们和实际生活作比喻。所以我想，或许我可以尝试用自己的理解，根据实际情况，用形象的比喻来表达晦涩难懂的技术细节。用白话文表达出来，既能把复杂的东西简单化，对自己来说也能把核心点理解的更透彻。

如果每一个晦涩的知识点，都能通过形象的比喻，用三分钟把它描述清楚，那么相信大家理解起来也会非常容易，看技术文章也能像看故事一样。