如何实现GC

垃圾收集器的具体实现

❝  

这部分的内容，笔者点到为止，觉得看的不爽的欢迎进群一起讨论。因为不确定的东西我不能写出来误导别人，要做一个讲笔德的作者。

❞  

我站在周老师的肩上高歌 ”HotSpot 是这么实现的垃圾收集器！“

根节点枚举

通过上一篇的内容我们知道了一些可以固定作为 GC Roots 的内容，他们包括静态变量、常量、方法运行时上下文。我们也知道了可达性分析算法 （这里如果不清楚的请参考笔者前两篇文章内容，>" data-itemshowtype="0" tab="innerlink" data-linktype="2">这里放个传送门>>） 。不过运行时这么多引用，全部都扫描一遍这啥虚拟机也受不了啊，GC 2秒钟，扫描8小时啊。

所以就有了第一阶段的根结点枚举，这一步就是直接扫描与 GC Roots 直接相关的那部分内容。这一步的操作需要 “Stop The World”（Stop The World 就是用来形容在安全点用户线程暂停的这种状态的一个叫法，关于安全点接下来就会提到）。

可达性分析时，并不会全部的挨个扫描执行上下文和全局引用。在 HotSpot 中，有一个叫做 OopMap 的数据结构，专门存放着引用信息，这个普通对象指针是在类加载和即时编译时分别将全局引用和执行上下文「特定」的相关位置记录下来的。（这地方与后面的内容有关，记一下）

❝  

OopMap（ Ordinary Object Pointer）  点到为止，这部分内容可以根据代码的编译结果看到，感兴趣的可以研究研究。图片来自《深入理解 Java 虚拟机》3.4.1 代码清单 3-3

❞  

安全点

通过上面我们知道 GC 要做的事是通过 OopMap 找出来那些被引用的对象，而这个 OopMap 里面存了两种数据，一部分是全局引用，这好说，类加载的时候怼上，不会变了。那执行上下文怎么办？那一个个方法的调用，一个个栈帧，栈帧里又那么多变量 （这部分内容在前面已经学过了，如果不清楚可以回到前面文章复习，>" data-itemshowtype="0" tab="innerlink" data-linktype="2">再次召唤传送门>>） 。如果把全部的字节码指令全部都存下来那不疯了？所以 hotspot 没疯，它只存了一些特定的位置把这个信息记到 OopMap 中。在程序执行过程中会有多个这样的特定位置，这些特定的位置就被称为 「安全点」 。

在安全点才能 GC

有了安全点我们就应该知道了，GC 不是任何时候都能做的。必须要等到程序到达安全点之后才能做。为啥应该不难理解吧，两个安全点之间如果你执行了 GC ，是不是会导致一部分执行上下文相关的引用你不知道，因为 OopMap 里面只存了最近一个安全点内的指令内容。

安全点在哪

明白了这个必须等到安全点才能 GC 之后，又有新的问题了，（ GC 做一次真是太难了）你说这个安全点，你放多少个合适，间隔又要多少才合理，放远了吧，半天半天不能做一次 GC ，放近了吧倒是随时想做就能做，但是你要知道这个安全点也是一条指令啊，那插入那么多额外的指令到程序中你觉得合适吗？而且这玩应也要存储啊不是 OopMap 了解一下。于是 hotspot 的开发者就研究。最后来有了一个比较银杏的解决办法。

因为一般指令执行的时间很短，所以这个解决办法就是，在一些长时间执行的部分给它怼一个安全点，防止程序长时间执行我没办法 GC ，根据长时间执行的特征，有些地方就显而易见的被选出来祭天了，它们是 方法调用 、循环回边处 、异常跳转

怎么到达安全点

现在我们知道了 GC 需要通过 OopMap 找到 GC Roots 中的相关引用，又知道了要在安全点的时候暂停的时候开始找这些引用，但又有问题了，我知道 GC 要在线程执行到安全点的时候暂停，可怎么才能让每一个线程到达最近的安全点上，并且暂停呢？

两种办法，虚拟机强行等你到安全点，还有一种就全凭自觉。

什么叫虚拟机强行等你到安全点呢，他还有个名字叫 「Preemptive Suspension」，就是 先发制人（抢先式中断） 。虚拟机直接中断用户线程，然后看你到没到安全点，没到继续跑，然后在中断。再看再跑再看再跑，直到全部线程都到达安全点，over 任务完成。

相比虚拟机怼我到安全点，我还不如自觉点  **Voluntary Suspension  ** 主动式中断 。虚拟机会发出一个安全点集合信号，所有线程轮询这个集合信号，一旦信号为真时，当前线程会在最近的一个安全点到达时挂起。

人生苦短，我选自觉。现在大部分虚拟机都是选的自觉方式来到达安全点。毕竟先发制人太不讲武德了。

❝  

点到为止内容，就是线程的这个轮询操作的实现。因为需要频繁执行，且高效。HotSpot 只使用了一条汇编指令实现了这个操作。

test %eax,0x160100 当需要暂停用户线程时， 虚拟机把0x160100的内存页设置为不可读， 那线程执行到test指令时就会产生一个自陷异常信号， 然后在预先注册的异常处理器中挂起线程实现等待。

❞  

安全区域

这部分可以算是安全点的扩展，因为程序执行过程中，不能保证线程全部都在运行状态，或等待或阻塞等等，所以就有了安全区域的概念，这部分区域内容标志着在这个区域中，对象的引用关系不会发生改变。不会影响 GC 正常进行，当用户线程执行到安全区域后会标志自己现在在安全区域， GC 不要管我，等到用户线程从安全区域出来的时候要和 GC 打招呼，“GC 你完事了吗？我要出来了” 如果这个时候没有 GC 动作，那你就可以出来了，如果这个时候在 根结点枚举 阶段，或在收集过程需要用户线程暂停的阶段，那么用户线程就需要等待，知道 GC 结束才能从安全区域出来。

记忆集（Remembered Set）

上面的 GC 过程，在只有新生代内存被使用，老年代没有使用的时候还是没问题的，但是一旦出现之前文章提到过的跨代引用问题，就需要考虑了，跨代引用是指老年代中存在引用新生代对象的指针。为了解决对象跨代引用所带来的问题，垃圾收集器在新生代中建立了名为记忆集（Remembered Set）的数据结构，一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。这个在后面不光用在了这种只有新生代和老年代的收集器中，后面的区域收集器也会用到。

❝  

区域收集器指的是 G1 ，ZGC 还有 Shenandoah收集器这种。

❞  

卡表（Card Table）

有了记忆集的概念之后，就考虑怎么保存含有跨代引用的信息，可以将有跨代引用的对象全部保存下来，但是这样做太占内存，而且维护起来也不方便。于是有一种较好的记录方案，就是按区域划分内存，将有跨代引用的那部分内存区域记录下来，这种实现方式称为 “卡表”。

HotSpot 将整个堆划分为一个个大小为 512 字节的卡页，维护成一个卡表，每个卡表的大小默认为 1 个字节用来存储每张卡的一个标识位0或者1。这个标识位代表对应的卡「是否可能存有指向新生代对象的引用」。如果可能存在，那么这张卡就是 「脏卡」。在 GC 的时候，只需要筛选脏卡对应内存区域中的对象就好了，不需要扫描全部的对象。

❝  

注意不要搞混记忆集与卡表的概念，一个是定义的数据结构，另一个是具体的实现方法。

❞  

写屏障

知道了用卡表来解决跨代或跨内存区域的问题，当某个卡页可能存在跨代引用时就会变脏，那这个变脏的过程是怎么样的呢？又是怎么实现的呢？

正常情况下，卡表变脏的时机是当前区域中的对象中，引用了其他区域的对象，此时更新这张表为脏表。如果解释执行，一条条执行下去可以，虚拟机可以根据变量赋值的指令来判断，进行相应的操作，但是在即时编译过程中，这个就需要一些对应的机器指令操作了。在HotSpot虚拟机里是通过写屏障（Write Barrier）技术来维护卡表状态的。「与 volatile 的重排序屏障指令不同！！！」

这个写屏障的具体实现分为两个，一个叫做写前屏障，一个叫做写后屏障。他们的操作类似 AOP ，他们可以在一个变量赋值操作前后做出一个通知。在 hotspot 中大多使用了写后屏障。这样就可以在变量赋值操作之后，将其对应的卡表更新为脏表。

虚共享

写屏障带来了一个问题，这个问题是由 CPU 引起的，现在的 CPU 缓存中都是有一个个缓冲行保存的数据，在多核处理器的情况下，可能存在多个线程共享一个缓冲行的情况，比如一个缓冲行的大小是 32 kb，那么一张存有 64 张卡页的卡表（64 * 512字节）就有可能在同一个缓冲行上面。为了解决多个线程同时更新同一个缓冲行浪费的性能开销。hotspot 在更新卡表状态时，加入了一个当前卡表是否为脏表的判断，如果是脏表就不再进行更新操作。

❝  

在JDK 7之后，HotSpot虚拟机增加了一个新的参数-XX：+UseCondCardMark，用来决定是否开启卡表更新的条件判断。开启会增加一次额外判断的开销，但能够避免伪共享问题，两者各有性能损耗，是否打开要根据应用实际运行情况来进行测试权衡。

❞  

并发的可达性分析

上面已经对整个垃圾回收过程涉及的细节过了一遍，接下来就要看看其中的重头戏，可达性分析算法了，也就是上面一直说的扫描扫描的内个。

我们知道可达性分析算法是需要暂停用户线程才能够使用，就是需要 Stop The World ，根结点枚举这一步的暂停时间虽然很短，但是还是要暂停的，同时这个暂停的时候会随着系统的对象的增长而增长，成正比关系。

三色标记

可达性分析算法的描述目前都是采用三色标记来辅助理解的。

❝  

希望这块的内容能够和之前的 finalize 方法联系起来，还记得之前文章中我们提到的自己救自己一次的那个地方吗，待会可以倒过去看一看，这可以帮助你加深这块的理解，当然也只有我才会给你说这么细的提醒

❞  

• 白色：死亡的颜色，即没有引用的对象。只会发生在 GC 开始标记工作之前（还没开始标记，大家都是白色），和 GC 工作之后（标记完了，就你是白色）
• 黑色：GC 已经开始工作到过这里，而且确认这个节点存活，其存在有效的引用，即这个对象的引用也全都扫描过。被黑色节点引用的对象一定可以活下来。可达性分析算法对已经是黑色的节点，不会在进行扫描（重要，后面理解三色标记的问题会用到）
• 灰色：GC 已经开始工作到过这里，但这个对象上至少还有一个引用没有扫描。

并发标记的问题

❝  

周老师《深入理解 Java 虚拟机》（第三版）3.4.6插图

此例子中的图片引用了Aleksey Shipilev在DEVOXX 2017上的主题演讲：《Shenandoah GC Part I：The Garbage Collector That Could》。

❞  

 

上图最后两个情况说明了在并发阶段的标记问题。因为并发标记是指 GC 的工作线程与用户线程并发执行，所以就会出现一边标记一边改变对象引用的情况。

并发标记会出现两类问题，一类是漏标，一类是误标。漏标是指某个应该为白色的对象没有被标记成白色，这种问题一般不会有太大影响。最多浪费一部分内存在下一次 GC 时将其再次标记回收。而另一类问题就是误标。这两个问题在上图的最后两个里面可以体现出来。

误标的危害是很严重的，如果一个正在引用的对象，被误标记成了白色。那么 GC 结束之后这个对象被清除，可能直接导致系统崩溃。

这个问题的出现原因有被证实过，当且仅当满足以下两点时才会出现误标的情况

1. 赋值器插入一条以上由黑色节点指向白色节点的引用
2. 赋值器删除了灰色节点直接或间接到达白色节点的全部引用

通过这两个情况，我们也不难理解误标的产生，因为黑色节点的规则是不会在扫描，而灰色则是会再进行扫描。所以对应的解决办法也比较清晰，只需要不要让以上两个条件同时满足即可。HotSpot 针对以上两点分别使用了「增量更新」和「原始快照」两种解决方案。

增量更新的意思是指，如果一个引用关系是从黑色节点指向白色节点，那么就需要在并发标记结束对这些个黑色节点作为根节点，重新进行扫描，即黑色节点发生新的引用关系后，其会变成灰色节点。（CMS 收集器中的重新标记使用的这种方案）

原始快照指的是，如果一个灰色节点删除了指向白色节点的引用，那么需要将这个删除的引用记录下来，在并发标记结束对这个记录的引用关系中灰色节点作为根结点重新扫描。无论这个对象是否删除了，都会重新再扫描一次。（G1 的最终标记使用的这种方案）