性能文章>一文带你弄懂 JVM 三色标记算法!>

一文带你弄懂 JVM 三色标记算法!原创

203202

大家好,我是树哥。

最近和一个朋友聊天,他问了我 JVM 的三色标记算法。我脑袋一愣发现竟然完全不知道!于是我带着疑问去网上看了几天的资料,终于搞清楚啥事三色标记算法,它是用来干嘛的,以及它和 CMS 回收器和 G1 回收器的关系了。今天,就让树哥带着大家一起盘一盘它!
image1.png

根可达算法

我们要进行垃圾回收,就需要弄明白哪些对象是需要回收的,哪些对象是不需要回收的。针对这个问题,其实业界已经有几种常见的解决方法了。
第一种是计数法,就是每个对象都有一个计数器,被引用了加一,移除引用减一。但这种方法比较麻烦,而且也会有循环依赖的问题,因此并不被广泛使用。第二种是根可达算法,即以 GCRoots 为基础去扫描整个引用链,从而找到所有的可达对象,那剩下的其他对象就是不可达的垃圾对象了。
现在被广泛使用的是第二种算法,即根可达算法。

那怎么去实现根可达算法呢?

最简单的一种实现方案是:从 GCRoots 节点开始,使用「标记 - 清除」算法去实现。

这种实现方案分为两个阶段,分别是:标记阶段、清除阶段。在标记阶段,它从 GCRoots 节点开始扫描整个引用链,找到所有可达的对象。在清除阶段,扫描整个引用链的不可达对象,然后将垃圾对象清除掉。整个算法实现过程如下图所示。
image2.jpeg

但这种方式有一个很大的缺点:整个过程必须「Stop the World」。这就导致整个应用程序必须停止,不能做任何改变,这是非常不友好的。 CMS 回收器出现之前的所有回收器,都是用这种方式实现的,因此 GC 停顿时间都比轿长。

三色标记算法

为了解决上面「标记 - 清除」算法的问题,于是就出现了「三色标记算法」!

三色标记算法指的是将所有对象分为白色、黑色和灰色三种类型。黑色表示从 GCRoots 开始,已扫描过它全部引用的对象,灰色指的是扫描过对象本身,还没完全扫描过它全部引用的对象,白色指的是还没扫描过的对象。
image3.jpeg

但仅仅将对象划分成三个颜色还不够,真正关键的是:实现根可达算法的时候,将整个过程拆分成了初始标记、并发标记、重新标记、并发清除四个阶段。

初始标记阶段,指的是标记 GCRoots 直接引用的节点,将它们标记为灰色,这个阶段需要 「Stop the World」。

并发标记阶段,指的是从灰色节点开始,去扫描整个引用链,然后将它们标记为黑色,这个阶段不需要「Stop the World」。

重新标记阶段,指的是去校正并发标记阶段的错误,这个阶段需要「Stop the World」。

并发清除,指的是将已经确定为垃圾的对象清除掉,这个阶段不需要「Stop the World」。

对比一下「四阶段拆分」和「一段式」的实现方式,我们可以看出:通过将最耗时的引用链扫描剥离出来作为并发标记阶段,将其与用户线程并发执行,从而极大地降低了 GC 停顿时间。 但 GC 线程与用户线程并发执行,会带来新的问题:对象引用关系可能会发生变化,有可能发生多标和漏标问题。

多标与漏标问题

多标问题指的是原本应该回收的对象,被多余地标记为黑色存活对象,从而导致该垃圾对象没有被回收。 多标问题会出现,是因为在并发标记阶段,有可能之前已经被标记为存活的对象,其引用被删除,从而变成了不可达对象。例如下图中,假设我们现在遍历到了节点 E,此时应用执行了 objD.fieldE = null;。那么此刻之后,对象 E、F、G 应该是被回收的。但因为节点 E 已经是灰色的,那么 E、F、G 节点都会被标记为存活的黑色状态,并不会被回收。
image4.jpeg
多标问题会导致内存产生浮动垃圾,但好在其可以再下次 GC 的时候被回收,因此问题还不算很严重。

漏标问题指的是原本应该被标记为存活的对象,被遗漏标记为黑色,从而导致该垃圾对象被错误回收。 例如下图中,假设我们现在遍历到了节点 E,此时应用执行如下代码。这时候因为 E 对象没有引用了 G 对象,因此扫描 E 对象的时候并不会将 G 对象标记为黑色存活状态。但由于用户线程的 D 对象引用了 G 对象,这时候 G 对象应该是存活的,应该标记为黑色。但由于 D 对象已经被扫描过了,不会再次扫描,因此 G 对象就被漏标了。

var G = objE.fieldG; 
objE.fieldG = null;  // 灰色E 断开引用 白色G 
objD.fieldG = G;  // 黑色D 引用 白色G

image5.jpeg
漏标问题就非常严重了,其会导致存活对象被回收,会严重影响程序功能。
那么我们的垃圾回收器是怎么解决这个问题的呢?

答案是:增加一个「重新标记」阶段。无论是在 CMS 回收器还是 G1 回收器,它们都在并发标记阶段之后,新增了一个「重新标记」阶段来校正「并发标记」阶段出现的问题。 只是对于 CMS 回收器和 G1 回收器来说,它们解决的原理不同罢了。

漏标解决方案

正如前面所说,三色标记算法会造成漏标和多标问题。但多标问题相对不是那么严重,而漏标问题才是最严重的。我们经过分析可以知道,漏标问题要发生需要满足如下两个充要条件:

  1. 有至少一个黑色对象在自己被标记之后指向了这个白色对象
  2. 所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用

只有当上面两个条件都满足,三色标记算法才会发生漏标的问题。换言之,如果我们破坏任何一个条件,这个白色对象就不会被漏标。这其实就产生了两种方式,分别是:增量更新、原始快照。CMS 回收器使用的增量更新方案,G1 采用的是原始快照方案。

CMS 解决方案

CMS 回收器采用的是增量更新方案,即破坏第一个条件:「有至少一个黑色对象在自己被标记之后指向了这个白色对象」。

既然有黑色对象在自己标记后,又重新指向了白色对象。那么我就把这个黑色对象的引用记录下来,在后续「重新标记」阶段再以这个黑色对象为跟,对其引用进行重新扫描。通过这种方式,被黑色对象引用的白色对象就会变成灰色,从而变为存活状态。

这种方式有个缺点,就是会重新扫描新增的这部分黑色对象,会浪费多一些时间。但是这段时间相对于并发标记整个链路的扫描,还是小巫见大巫,毕竟真正发生引用变化的黑色对象是比较少的。

G1 解决方案

G1 回收器采用的是原始快照的方案,即破坏第二个条件:「所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用」。

既然灰色对象在扫描完成后删除了对白色对象的引用,那么我是否能在灰色对象取消引用之前,先将灰色对象引用的白色对象记录下来。随后在「重新标记」阶段再以白色对象为根,对它的引用进行扫描,从而避免了漏标的问题。通过这种方式,原本漏标的对象就会被重新扫描变成灰色,从而变为存活状态。

这种方式有个缺点,就是会产生浮动垃圾。 因为当用户线程取消引用的时候,有可能是真的取消引用,对应的对象是真的要回收掉的。这时候我们通过这种方式,就会把本该回收的对象又复活了,从而导致出现浮动垃圾。但相对于本该存活的对象被回收,这个代码还是可以接受的,毕竟在下次 GC 的时候就可以回收了。

对于 CMS 和 G1 这两种处理方案哪种更好,很多资料说的是 G1 这种解决方案更好。 原因是其觉得 G1 这种方式产生了一些浮动垃圾,但节省了一些时间。但我对比了一下发现:CMS 和 G1 都需要重新对某些元素进行引用链扫描。从这点看来,好像差别不大。有弄懂的朋友可以评论区留言讨论讨论。

总结

看完了整篇文章,我们试图来回答一些问题。
三色标记算法是什么? 三色标记算法是根可达算法的一种实现方案,其目的是为了找出所有可达对象。

为什么要有三色标记算法? 因为传统的「标记 - 清除」算法效率太低,于是采用三色标记算法通过将对象分成白色、黑色、灰色,以及将整个过程拆分成「初始标记、并发标记、重新标记、并发清除」4 个过程,从而降低 GC 停顿时间。

三色标记算法有什么缺陷? 三色标记算法会产生多标和漏标问题,其中漏标问题最严重。漏标问题会导致本该存活的对象被回收,从而导致严重的程序问题。

漏标有什么解决方案? 漏标有两种解决方案,分别是:增量更新和原始快照方式。CMS 回收器采用了增量更新方式,G1 回收器采用了原始快照方式。

漏标哪种解决方案最好? 江湖传闻 G1 回收器的原始快照方式效率高,但没有确切的理论证明,且听且珍惜。

参考资料
非常好!权威资料!VIP!!Tracing garbage collection - Wikipedia
VIP!VIP!讲清楚了!三色标记的漏标问题及两种解决方案_小幻_159 的博客 - CSDN 博客_三色标记漏标
三色标记法:多标与漏标 - 爱代码爱编程
三色标记!!!12. 垃圾收集底层算法 – 三色标记详解 - 腾讯云开发者社区 - 腾讯云
三色标记!!!GC 中的 三色标记法_骚人贵的博客 - CSDN 博客_gc 三色标记
三色标记法:多标与漏标_朱四龙的博客 - CSDN 博客_三色标记漏标

点赞收藏
树哥聊编程
请先登录,感受更多精彩内容
快去登录吧,你将获得
  • 浏览更多精彩评论
  • 和开发者讨论交流,共同进步

为你推荐

【全网首发】一次想不到的 Bootstrap 类加载器带来的 Native 内存泄露分析

【全网首发】一次想不到的 Bootstrap 类加载器带来的 Native 内存泄露分析

记一次线上RPC超时故障排查及后续GC调优思路

记一次线上RPC超时故障排查及后续GC调优思路

解读JVM级别本地缓存Caffeine青出于蓝的要诀 —— 缘何会更强、如何去上手

解读JVM级别本地缓存Caffeine青出于蓝的要诀 —— 缘何会更强、如何去上手

【全网首发】一次疑似 JVM Native 内存泄露的问题分析

【全网首发】一次疑似 JVM Native 内存泄露的问题分析

解读JVM级别本地缓存Caffeine青出于蓝的要诀2 —— 弄清楚Caffeine的同步、异步回源方式

解读JVM级别本地缓存Caffeine青出于蓝的要诀2 —— 弄清楚Caffeine的同步、异步回源方式

【全网首发】从源码角度分析一次诡异的类被加载问题

【全网首发】从源码角度分析一次诡异的类被加载问题

2
0