【原创】面试官问我G1回收器怎么知道你是什么时候的垃圾（）【原创】面试官问我G1回收器怎

这是why技术的第36篇原创文章

上面的图片是我上周末在家拍的。以后的文章里面我的第一张配图都用自己随手拍下的照片吧。分享生活，分享技术，哈哈。
阳台上的花开了，成都的春天快来了，疫情也应该快要过去了吧。
最近在看《霍乱时期的爱情》，不知道为什么和《大话西游》联系了起来，所以你可以看到玻璃上的倒影，是我在看《大话西游》。
谁都曾经有过大闹天宫的梦想，爱上层楼的忧愁，但是早晚有一天，你也会像他转身之后一样，走在路上，像一条狗。
好了，说回文章

文章图片

让你看看“浮动垃圾” 传奇小说网 www.xs86.com 上《面试官:你说你熟悉jvm?那你讲一下并发的可达性分析》这篇文章主要聊了 jvm 的可达性分析算法。
借助“三色标记”大法分析了垃圾回收线程扫描的过程中，用户线程同时执行修改引用关系的操作时，可能会出现的“对象消失”问题，以及其对应的两种解决方案
增量更新和原始快照。
在文章中我写道：对象关系图的变化会导致出现两种情况一是“浮动垃圾”，二是“对象消失”。大概率的情况下面试官更加关心第二种情况，因为第二种情况会给程序带来异常。接下来我就做动图分析了“对象消失”的情况
但是我是万万没想到呀，读者更关心的是“浮动垃圾”。有的读者就来问我，浮动垃圾是怎么产生的，你倒是给个图啊。

文章图片

像我这样的又暖又有料的硬核原创作者，你说你要，那我肯定是要给你的。
下面就给你补上“浮动垃圾”的动图：

文章图片

当并发标记完成后，对象图就变成了下面这个样子：
你看出来了吧。对象7，8，4，11，10都是浮动垃圾。因为他们被标记成了黑色，所以逃过了本次垃圾回收。

文章图片

什么？你问我为什么黑色就不回收了？你个假粉丝，建议你先去读一读上周的文章。

文章图片

G1垃圾回收时新对象怎么处理？有的读者就提出了另外的很有探讨性的问题：
why哥你好，你《面试官:你说你熟悉jvm?那你讲一下并发的可达性分析》这篇文章主要解决了在并发标记阶段，GC线程和用户线程并发执行时，用户线程修改了对象引用关系，导致“对象消失”的问题。G1是采用原始快照加写前屏障的方式解决这个问题的。
但是我还有另外的一个问题：用户线程执行时不仅修改了对象引用关系，还新分配了新对象，我觉得这个情况是非常常见的，G1是如何找到并处理这些对象的呢？
换句话说，就是文章标题啦：G1收集器是怎么知道这些对象是什么时候应该进行垃圾标记的？
这是一个好问题，一看就是用心读了文章并带有自己的思考。很不错。
这位读者的问题属于第一个问题的连环炮，让我突然有了一种掉进了面试官布好的天罗地网里面的感觉。
面试官先故意漏出破绽，让你聊“对象消失”、“三色标记”、“增量更新”。然后等你得意洋洋的时候，突然抛出第二个问题：刚刚对象消失的问题回答的不错，那如果并发标记的时候用户线程分配了新对象，G1是怎么处理的呢？

文章图片

说实话，我觉得只要你简历上没有写精通jvm，面试一般问到这种程度的我觉得是真的到了探讨的地步了。答的上来加分，答不上来也不扣分。
遥想2016年，我刚毕业，只身闯北京的时候，一连面试了9家公司，没有一家公司聊到 jvm （当然我当时面的是初级开发）。现在不一样了，不知道什么时候 jvm 从进阶面试题，变成了初级面试题。面试阶段如果没有问 jvm ，就感觉不是一次完整的面试。
我觉得就这几年面试题的变化，其实也就是反映了一个现象：想入行的人越来越多，导致入行的门槛越来越高。
不是jvm的地位变了，而是门槛越来越高了。

好了，瞎逼逼完了，接下来我们聊聊G1。
初识Garbage First(G1) 我不知道你是怎么知道G1的，但是我是从周志明大大的《深入理解Java虚拟机(第2版)》这本书里面第一次知道G1收集器的。
我记得当时读到G1的时候感觉这就是天书啊。
因为作者在介绍G1之前介绍了很多其他的收集器，我先给你看一下目录，带你回顾回顾：

文章图片

可以看到，3.5.1节到3.5.6节介绍的收集器工作的时候， Java 堆的内存布局是按照新生代，老年代进行整体的区域划分的。
但是到了G1收集器， Java 堆的内存布局就有点"妖艳贱货"了。然后就有点越来越看不懂了，当时的场景就像下面这样：

它虽然还是保留的有新生代和老年代的概念，但是新生代和老年代之前再也不是区域上的隔离了。它将整个 Java 堆划分为多个大小相等的独立区域，叫做 Region 。而新生代和老年代就是由一个个 Region 动态组成的区域，它们可以是不连续的区间。
每一个 Region 都可以根据需要，扮演新生代的 Eden 空间，Survivor 空间，或者老年代空间。除此之外它还有一类特殊的区域叫做 Humongous，专门用来存储大对象。
上面说的是啥意思呢？其实用图片看起来就非常直观了：
比如对于 CMS，使用的堆内存结构如下：

文章图片

可以看到上面的图片中不论是年轻代、老年代都是逻辑上连续的空间（但是不要求物理上的连续）。
而G1的堆内存被划分为多个大小相等的 Region ，但是 Region 的总个数在 2048 个左右，默认是 2048 。对于一个 Region 来说，是逻辑连续的一段空间，其大小的取值范围是 1MB 到 32MB 之间。
结构如下：

文章图片

上面的E、S和没有写字母的蓝色方块（可以理解为old）没啥说的。
但是可以看到H是以往的垃圾收集器中没有的概念，它代表 Humongous，这表示这些 Region 存储的是巨型对象（humongous object，H-obj），当新建对象大小超过 Region 大小一半时，直接在新的一个或多个连续 Region 中分配，并标记为H。

说实话上面的这概念已经“烂大街”了，任何一篇写G1都会聊到，包括本文也是。

没办法啊，朋友们，这是引子，必须得先聊几句。就像斗地主，你第一手牌能直接出王炸吗？不能啊，你不得先来一个对三，循序渐进啊。

下面我送你一个小彩蛋吧。

注意到我上面说的几个数据了吗，2048个左右，1MB到32MB，这些数据是哪里来的呢，我说你就信了吗？
很多文章聊到G1的时候都只是说堆内存被划分为多个大小相等的 Region ， Region 大小的取值范围为 1MB 到 32MB ，但是并没有提到 2048 这回事，我来给你寻根问祖一下：

文章图片

我找到的第一个数据来源于上面的这篇论文，即文末的资料4：

The goal is to have around 2048 regions for the total heap.

这篇论文的作者是Monica Beckwith，你可以去搜一下，她（是的，我没打错，是个妹子）担任过Oracle G1 垃圾收集器性能团队 Leader，权威吧。
第二个数据来源当然是源码了，更权威吧：

http://hg.openjdk.java.net/jdk/jdk/file/fa2f93f99dbc/src/hotspot/share/gc/g1/heapRegionBounds.hpp

文章图片

知道这个2048重要吗？我觉得不重要。
但是知道了就更牛逼呀！当妹子聊到2048的时候她只知道这是一个游戏，你要告诉她这个数字也是G1的Region的默认个数。
事了拂衣去,深藏功与名。

文章图片

G1的工作步骤这一部分，也是耳熟能详的部分，但是忍一忍，马上就要到你高呼：卧槽，牛逼的部分了。
众所周知，一般我们说G1的收集过程分为下面这四个步骤（下面四个步骤的描述来自于《深入理解Java虚拟机(第3版)》）：

说实在的，下面的描述确实看的让人很懵逼的。面试的过程中问到这一部分的时候，我相信大多数朋友都是硬背下来的。

所以，本文的目的就是为了让你理解下面这几个阶段的具体过程。

这么说吧，如果看完这篇文章你还是没搞懂上面这几个阶段的话，那你再读一遍。

再读一遍，还是没懂的话，那我这篇文章就算写失败了。

初始标记(Initial Marking)：这阶段仅仅只是标记GC Roots能直接关联到的对象并修改TAMS(Next Top at Mark Start)的值，让下一阶段用户程序并发运行时，能在正确的可用的Region中创建新对象，这阶段需要停顿线程，但是耗时很短。
而且是借用进行Minor GC的时候同步完成的，所以G1收集器在这个阶段实际并没有额外的停顿。
并发标记(Concurrent Marking)：从GC Roots开始对堆的对象进行可达性分析，递归扫描整个堆里的对象图，找出存活的对象，这阶段耗时较长，但是可以与用户程序并发执行。
当对象图扫描完成以后，还要重新处理SATB记录下的在并发时有引用变动的对象。
最终标记(Final Marking)：对用户线程做另一个短暂的暂停，用于处理并发阶段结束后仍遗留下来的最后那少量的 SATB 记录。
筛选回收(Live Data Counting and Evacuation)：负责更新 Region 的统计数据，对各个 Region 的回收价值和成本进行排序，根据用户所期望的停顿时间来制定回收计划。
可以自由选择任意多个 Region 构成回收集，然后把决定回收的那一部分 Region 的存活对象复制到空的 Region 中，再清理掉整个旧 Region 的全部空间。
这里的操作涉及存活对象的移动，是必须暂停用户线程，由多条收集器线程并行完成的。
上面虽然有4个阶段，但是从上帝视角，我们可以把它分为两大部分，或者说从整个算法的角度，我们可以切分为两大部分：
1.Global Concurrent Marking：全局并发标记。
2.Evacuation Pauses：该阶段是负责把一部分Region里的活对象拷贝到空Region里面去，然后回收原本的Region空间。
为什么我敢这样去划分呢？
一部分原因来自这篇论文中：

文章图片

《Garbage-First Garbage Collection》这篇论文是 sun 实验室在 2004 年发布的第一篇关于 G1 的论文。够权威吧？
该论文中，2.3小节就是介绍 Evacuation Pauses ，2.5小节就是介绍 Concurrent Marking ，下面是部分内容截图：

文章图片

另一部分原因是 R大也这样说的(见文末参考资料)。
接下来，要回答读者提出的问题，我们就需要了解全局并发标记阶段。
全局并发标记这一节就是回答这个问题：用户线程执行的时候不仅修改了对象引用关系，还新分配了新对象，G1 是如何找到并处理这些对象的呢？
要回答这个问题，就涉及到 TAMS 了。前面我引用的书里说：

初始标记（Initial Marking）：这阶段仅仅只是标记 GC Roots 能直接关联到的对象并修改 TAMS（Next Top at Mark Start）的值，让下一阶段用户程序并发运行时，能在正确的可用的 Region 中创建新对象。

这句话，每个字都能看懂，连在一起读，也品出点儿味道，但是总感觉似懂非懂的样子。
什么是 TAMS？什么是正确可用的 Region？新对象是创建在 Region 中的哪个位置的？
我们先从论文入手，我捡关键点给你说：

文章图片

1.有两个 bitmap。

2.一个叫 previous，一个叫 next。

3.previous bitmap 是 concurrent marking 阶段完成后的最后一个 bitmap。（有点绕，后面会解释）。

4.next bitmap 是当前将要或正在进行的 concurrent marking 的结果。

5.当标记完成后，两个 bitmap 会交换角色。

文章图片

1.标记周期的第一个阶段就是清理 next bitmap。

2.然后，初始标记阶段 Stop The World（后面简称STW），目的是标记 GC Roots 能直接关联到的对象。该阶段借助 Minor GC 完成，没有额外的停顿。

3.每个 Region 包含两个 TAMS。

4.一个对应前一轮标记，一个对应下一次标记。

从论文中我们可以知道，G1的Concurrent Marking 用了两个 marking bitmap。
一个 previous Bitmap 记录的是上一轮 Concurrent Marking 后的对象标记状态，因为上一轮已经完成，所以这个bitmap的信息可以直接使用。
一个 next Bitmap 记录的是当前这一轮 Concurrent Marking 的结果。这个bitmap是当前将要或正在进行的 Concurrent Marking 的结果，尚未完成，所以还不能使用。
我们可以假设一次并发标记变成后的 Bitmap（previous Bitmap）大概长这样:

文章图片

白色地址之间是可以回收的对象，灰色地址之间是不可以回收的对象。
除了两个 bitmap 外，还有两个 TAMS（top at mark start）。每个 Region 都有两个 TAMS，分别是 previous TAMS 和 next TAMS。
bitmap 和 TAMS 可以用下面的图片来表示：

文章图片

首先我们可以看到 bottom 和 top 之间是一个 Region 已使用的部分。Top 到 end 之前是一个 Region 未使用的部分。
另外可以看到上面我留了四个问号，接下我们的目的就是填补这些问号。当这些问号被填上之后，所有的问题都会迎刃而解。
两个 Bitmap 和两个 TAMS 是怎么工作的呢？
接下来按照：

初始标记（Initial Marking）

并发标记（Concurrent Marking）

最终标记（final marking，也叫Remark）

清理阶段（Cleanup）

这四个阶段作图说明
初始标记（Initial Marking）

文章图片

从图片可以看到初始标记阶段 nextBitmap 是清空状态，没有标记任何存活的对象。
接着我们再次回到书中的描述里，我给你逐字描述清楚：

初始标记（Initial Marking）：这阶段仅仅只是标记 GC Roots 能直接关联到的对象并修改 TAMS（Next Top at Mark Start）的值，让下一阶段用户程序并发运行时，能在正确的可用的 Region 中创建新对象。

GC Roots 能直接关联到的对象：就是一个 Region 已经使用过的部分，所以在 Bottom 与 top 之间。
修改 TAMS 的值：就是让此时的 prevTAMS 指向 Bottom ，也就是一个 Region 内存地址起始值。让此时的 nextTAMS 指向 Top。Top 实际上就是一个 Region 未分配区域和已分配区域的分界点。
**正确的可用的 Region **：对一个 Region 来说，当上面的 nextBitmap 为空、4个指针都准备就绪后，这个 Region 在下一阶段用户程序并发运行时，就是一个正确的 Region。
下一阶段用户程序并发运行时，在正确的可用的 Region 中创建新对象是什么意思呢？
下一阶段用户程序并发运行时指的就是并发标记阶段。
并发标记（Concurrent Marking）先看前面引用的书中描述：

并发标记（Concurrent Marking）：从 GC Roots 开始对堆的对象进行可达性分析，递归扫描整个堆里的对象图，找出存活的对象，这阶段耗时较长，但是可以与用户程序并发执行。当对象图扫描完成以后，还要重新处理 SATB 记录下的在并发时有引用变动的对象。

再看动图：

文章图片

从 GC Roots 开始对堆的对象进行可达性分析，递归扫描整个堆里的对象图，找出存活的对象：
意思就是说在并发标记阶段， GC 线程工作在 prevTAMS 和 NextTAMS 之间，对堆里的对象进行可达性分析（回想一下“三色标记”），标记完成后， NextBitmap 就有对应有值了（里面放的是地址值），黑色对应的是存活对象，白色对应的垃圾对象。
这样就找出存活对象了。
但是书中并没有提及用户线程分配对象的情况。所以读者提出的问题，在书中也找不到明确的答案。
答案就是： NextTAMS 与 Top 之间的对象，就是本次并发标记阶段用户线程新分配的对象，它们是隐式存活的。
为什么这么说？你去品一品论文里面我框起来的这句话。

文章图片

但是面试官想要的是这一句话的答案吗？不是的。
你听到这个问题后，你先微微一皱眉，做出沉思状，然后轻轻说说一句：这个问题问的很好，我先组织一下语言。（先舔他一波）

文章图片

然后你按照阶段把图画出来，指着给他讲 TAMS 和 Bitmap 是怎么工作的。
另外，关于 NextTAMS 与 Top 为什么是重叠的，也得补充说明一下：并发标记的前一个阶段是初始标记。由于初始标记是 STW 的，所以从动图中我们可以看到：并发标记开始，即初始标记结束的时候， NextTAMS 与 Top 是重叠的。
随着并发标记过程的进行， NextBitmap 被填充上了值。而 NextTAMS 与 Top 之间的区域越来越大，这就是用户线程在并发标记阶段分配的新对象。
同时通过下面的图我们可以看到， GC 线程的工作区间和用户线程的工作区间是有重叠的（用工作区间这个概念去理解其中的一些细节不一定正确，但是可以这样抽象的认为，方便理解）。

文章图片

而重叠的部分，就是可能产生“对象消失”的部分。对G1来说，就是原始快照（STAB）加写前屏障（Pre-Wirte Barrier）工作的部分。
所以这就是书里为什么说：当 GC 线程扫描完对象图后，还需要重新处理 STAB 记录下的在并发时有引用变动的对象。
最终标记（Remark）书中是这样的写的：

最终标记（Final Marking）：对用户线程做另一个短暂的暂停，用于处理并发阶段结束后仍遗留下来的最后那少量的 SATB 记录。

最终标记阶段，由于是 STW 的，所以该阶段对应的图是并发标记阶段完成后的图，如下：

文章图片

处理并发阶段结束后仍遗留下来的最后那少量的 SATB 记录是什么意思呢？
你想，并发标记阶段， GC 线程完成对象图的扫描之后，还会去处理 SATB 记录下的在并发时有引用变动的对象。
在处理 SATB 记录的数据的时候，由于用户线程可能还是在继续修改对象图，继续在产生 SATB 数据，所以还是会有一小部分的 SATB 数据，所以才需要一个短暂的暂停。
清理阶段（Cleanup）书里写的是筛选回收阶段。其实就包含了清理阶段和回收阶段。这里我们只讨论清理阶段，不讨论回收。
在这个阶段， NextBitmap 和 PrevBitmap 会交换位置：

文章图片

所以，我们的图就变成了下面的样子：

文章图片

可以看到，NextBitmap 和 PrevBitmap 交换了位置，NextTAMS 和 PrevTAMS 交换了位置。
而 Region 中， Bitmap 白色部分对应的已使用内存变成了浅灰色。它仅仅是标记了出来，并没有进行清扫操作。
需要注意的是：清理阶段不拷贝任何对象
引用R大的回答来描述这个阶段：

清点和重置标记状态。这个阶段有点像 mark-sweep 中的 sweep 阶段，不过不是在堆上 sweep 实际对象，而是在 marking bitmap 里统计每个 Region 被标记为活的对象有多少。这个阶段如果发现完全没有活对象的 Region 就会将其整体回收到可分配 Region 列表中。

好了，到这里我们就能把前面的那张图给填上了：

文章图片

然后再看一下论文中的这张图片，你就会发现，我上面的过程都是基于这张图片去分析的，图中展示了两个循环， A-B-C ， D-E-F 。其中 E、F 过程就是 B、C 过程的重复：

文章图片

我让上面的图片动起来，请细细品。请注意各个阶段 PrevTAMS 、 NextTAMS 指针的交换、 PrevBitmap 和 NextBitmap 位置的交换：

文章图片

如果一次看不懂，就再看一次。看的时候结合上面的长图和动图一起分析，效果更佳。

文章图片

参考资料：
1.https://max.book118.com/html/2018/0815/7043143036001143.shtm
2.https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/G1GettingStarted/index.html
3.https://www.oracle.com/technetwork/java/javase/tech/g1-intro-jsp-135488.html
4.https://www.infoq.com/articles/G1-One-Garbage-Collector-To-Rule-Them-All/
5.https://hllvm-group.iteye.com/group/topic/44381
6.《深入理解Java虚拟机(第三版)》
最后说一句（求关注）本文是对《面试官:你说你熟悉jvm?那你讲一下并发的可达性分析》这篇文章的补充说明。如果你没看过，我建议你去看看。
我觉得有些知识点仅仅靠文章和图片是很难说清楚的，所以我费劲的做了动图。
为了做这篇文章和上篇文章中的几张动图，加起来我截了 80 多张图。你知道我为了把每张图截的一个像素都不差，我有多努力吗？
截的我眼球布满了血丝，眼睛都快瞎了，你不关注一波？
我四级半的英语水平，为了文章的正确性，强行啃英文论文，你不感动吗？

文章图片

点个关注呀，别白嫖我啊，大哥。写文章很辛苦的，需要来点正反馈。
才疏学浅，难免会有纰漏，如果你发现了错误的地方，还请你留言给我指出来，我对其加以修改。
感谢您的阅读，我坚持原创，十分欢迎并感谢您的关注。
我是why技术，一个不是大佬，但是喜欢分享，又暖又有料的四川好男人。
以上。
欢迎关注公众号【why技术】,坚持输出原创。分享技术、品味生活，愿你我共同进步。
【【原创】面试官问我G1回收器怎么知道你是什么时候的垃圾（）】