Javaer 面试必背系列!超高频八股之三色标记法-编程思维

可达性分析可以分成两个阶段

  1. 根节点枚举
  2. 从根节点开始遍历对象图

前文提到过,在可达性分析中,第一阶段 ”根节点枚举“ 是必须 STW 的,不然如果分析过程中用户进程还在运行,就可能会导致根节点集合的对象引用关系不断变化,这样可达性分析结果的准确性显然也就无法保证了;而第二阶段 ”从根节点开始遍历对象图“,如果不进行 STW 的话,会导致一些问题,由于第二阶段时间比较长,长时间的 STW 很影响性能,所以大佬们设计了一些解决方案,从而使得这个第二阶段可以不用 STW,大幅减少时间

上篇文章已经介绍过第一阶段 “根节点枚举”,本篇就来分析第二阶段 ”从根节点开始遍历对象图“~

老规矩,背诵版在文末

前言

事实上,GC Roots 相比起整个 Java 堆中全部的对象毕竟还算是极少数,且在各种优化技巧(比如 OopMap)的加持下,它带来的停顿已经是非常短暂且相对固定的了,也就是说,“根节点枚举” 阶段的停顿时间不会随着堆容量的增长而增加

当我们枚举完了所有的 GC Roots,就得进入第二阶段继续往下遍历对象图了,这一步骤同样需要 STW,并且停顿时间与 Java 堆容量直接成正比例关系:堆越大,存储的对象越多,对象图结构越复杂,要标记更多对象而产生的停顿时间自然就更长,这是理所当然的事情

也就是说,“从根节点开始遍历对象图” 阶段的停顿时间随着堆容量的增长而增加

要知道包含“标记”阶段(也就是可达性分析)是所有追踪式垃圾收集算法的共同特征,如果这个阶段会随着堆变大而等比例增加停顿时间,其影响就会波及几乎所有的垃圾收集器。如果能够减少这部分停顿时间的话,那收益也将会是巨大的

想降低 STW 时间甚至是避免 STW,我们就要先搞清楚为什么必须在一个能保障一致性的快照上才能进行对象图的遍历

为了能解释清楚这个问题,大佬们引入了三色标记法(Tri-color Marking)这个工具

需要注意的是,三色标记法只是辅助我们分析的工具,并不是某个垃圾收集器具体使用的算法!!!!!更不是降低 STW 时间 or 消除 STW 的方法,具体解决方法下面还会介绍

在这里,三色标记法可以帮助我们搞清楚在可达性分析的第二阶段(也就是遍历对象图),如果用户线程和垃圾收集线程同时进行,会出现什么问题

辅助分析的工具:三色标记法

所谓三色标记法,就是把遍历对象图过程中遇到的对象,按照 “是否访问过” 这个条件标记成以下三种颜色:

  • 白色:表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段,所有的对象都是白色的,若在分析结束的阶段,仍然是白色的对象,即代表不可达(可达性分析到不了的对象,就是死亡对象,需要被回收)

  • 黑色:表示对象已经被垃圾收集器访问过,且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过,它是安全存活的,如果有其他对象引用指向了黑色对象,无须重新扫描一遍。黑色对象不可能直接(不经过灰色对象)指向某个白色对象。

  • 灰色:表示对象已经被垃圾收集器访问过,但这个对象上至少存在一个引用还没有被扫描过

    灰色可能不好理解,这里举个例子:A(GC roots) → B → C,如果 B 已经被扫描过,但是 B 的引用 C 还没有被扫描过,那么 B 就是灰色的,C 由于还没有被扫描,所以是白色的

所以对象图遍历的过程,其实就是由灰色从黑向白推进的过程,灰色是黑和白的分界线。

下面我们就用三色标记法来分析下,如果在对象图遍历这个阶段用户线程与收集器并发工作会出现什么问题

问题 1:浮动垃圾

所谓浮动垃圾,就是由于垃圾收集和用户线程是并行的,这个对象实际已经死亡了,已经没有其他人引用它了,但是被垃圾收集器错误地标记成了存活对象

举个例子,a 引用了 b,此时 b 被扫描为可达,但是用户线程随后又执行了 a.b = null,这个时候其实 b 已经是死亡的垃圾对象了,但是由于黑色对象不会被重新扫描,所以在垃圾收集里 b 依然作为存活对象被标记成黑色,因此就成了浮动垃圾。如下图所示:

浮动垃圾当然不是一件好事,但其实是可以容忍的,因为这只不过产生了一点逃过本次收集的浮动垃圾而已,反正还会有下一次垃圾收集,到时候就会被标记为垃圾被清理掉了

问题 2:对象消失

对象消失和浮动垃圾恰恰相反,对象消失是把原本存活的对象错误标记为已消亡,这就是非常致命的后果了,程序肯定会因此发生错误,下面表演示了这样的致命错误具体是如何产生的

如上图所示,b -> c 的引用被切断,但同时用户线程建立了一个新的从 a -> c 的引用,由于已经遍历到了 b,不可能再回去遍历 a(黑色对象不会被重新扫描),再遍历 c,所以这个 c 实际是存活的对象,但由于没有被垃圾收集器扫描到,被错误地标记成了白色。

总结下对象消失问题的两个条件:

  1. 插入了一条或多条从黑色对象到白色对象的新引用
  2. 删除了全部从灰色对象到该白色对象的直接或间接引用

Wilson 于 1994 年在理论上证明了,当且仅当以上两个条件同时满足时,才会产生 “对象消失” 的问题,即原本应该是黑色的对象被误标为白色

遍历对象图不需要 STW 的解决方案

如上所述,如果遍历对象图的过程不 STW 的话,第一个浮动垃圾的问题很好处理,但是第二个对象消失问题就很棘手了。

但是呢,遍历对象图的过程又实在太长,设计 JVM 的大佬们不得不想出一些办法来解决对象消失问题,使得在遍历对象图的过程中不用进行 STW(也就是用户线程和对象线程可以同时工作),从而提升可达性分析的效率

上面总结了对象消失问题的两个条件,所以说,如果我们想要解决并发扫描时的对象消失问题,只需破坏这两个条件的任意一个即可。由此分别产生了两种解决方案:

  1. 增量更新(Incremental Update):增量更新破坏的是第一个条件,当黑色对象插入新的指向白色对象的引用关系时(就是上图中的 a -> c 引用关系),就将这个新插入的引用记录下来,等并发扫描结束之后,再将这些记录过的引用关系中的黑色对象(a)为根,重新扫描一次。这可以简化理解为,黑色对象一旦新插入了指向白色对象的引用之后,它就变回灰色对象了
  2. 原始快照(Snapshot At The Beginning,SATB):原始快照要破坏的是第二个条件,当灰色对象要删除指向白色对象的引用关系时(上图中的 b -> c 引用关系),就将这个要删除的引用记录下来,在并发扫描结束之后,再将这些记录过的引用关系中的灰色对象(b)为根,重新扫描一次。这也可以简化理解为,无论引用关系删除与否,都会按照刚刚开始扫描那一刻的对象图快照来进行搜索

在 HotSpot 虚拟机中,增量更新和原始快照这两种解决方案都有实际应用,CMS 是基于增量更新来做并发标记的,G1、Shenandoah 则是用原始快照来实现


最后放上这道题的背诵版:

🥸 面试官:讲一讲三色标记法?

😎 小牛肉:在可达性分析中,第一阶段 ”根节点枚举“ 是必须 STW 的,不然如果分析过程中用户进程还在运行,就可能会导致根节点集合的对象引用关系不断变化,这样可达性分析结果的准确性显然也就无法保证了。不过 GC Roots 相比起整个 Java 堆中全部的对象算是极少数,且在各种优化技巧(比如 OopMap)的加持下,它带来的停顿已经是非常短暂且相对固定的了,也就是说,“根节点枚举” 阶段的停顿时间不会随着堆容量的增长而增加。

当我们枚举完了所有的 GC Roots,就得进入第二阶段继续往下遍历对象图了,这一步骤同样需要 STW,并且停顿时间与 Java 堆容量直接成正比例关系,三色标记法就是帮助我们搞清楚在这个阶段如果用户线程和垃圾收集线程同时进行,会出现什么问题,的这么一个工具方法

所谓三色标记法,就是把遍历对象图过程中遇到的对象,按照 “是否访问过” 这个条件标记成以下三种颜色:

  • 白色:表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段,所有的对象都是白色的,若在分析结束的阶段,仍然是白色的对象,即代表不可达(可达性分析到不了的对象,就是死亡对象,需要被回收)
  • 黑色:表示对象已经被垃圾收集器访问过,且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过,它是安全存活的,如果有其他对象引用指向了黑色对象,无须重新扫描一遍。黑色对象不可能直接(不经过灰色对象)指向某个白色对象。
  • 灰色:表示对象已经被垃圾收集器访问过,但这个对象上至少存在一个引用还没有被扫描过

所以对象图遍历的过程,其实就是由灰色从黑向白推进的过程,灰色是黑和白的分界线。

在 “对象图遍历” 这个阶段用户线程与收集器并发工作会出现两个问题:

1)浮动垃圾:所谓浮动垃圾,就是由于垃圾收集和用户线程是并行的,这个对象实际已经死亡了,已经没有其他人引用它了,但是被垃圾收集器错误地标记成了存活对象。

举个例子,a 引用了 b,此时 b 被扫描为可达,但是用户线程随后又执行了 a.b = null,这个时候其实 b 已经是死亡的垃圾对象了,但是由于黑色对象不会被重新扫描,所以在垃圾收集里 b 依然作为存活对象被标记成黑色,因此就成了浮动垃圾

浮动垃圾不是一件好事,但其实是可以容忍的,因为这只不过产生了一点逃过本次收集的浮动垃圾而已,反正还会有下一次垃圾收集,到时候就会被标记为垃圾被清理掉了

2)对象消失:对象消失和浮动垃圾恰恰相反,对象消失是把原本存活的对象错误标记为已消亡(原本应该是黑色的对象被误标为白色),产生对象消失问题需要满足两个条件:

  • 插入了一条或多条从黑色对象到白色对象的新引用
  • 删除了全部从灰色对象到该白色对象的直接或间接引用

对象消失是一个很致命的问题,程序肯定会因此发生错误,所以 “对象图遍历” 这个阶段最好是进行 STW 的,但是这个阶段的时间又很长,所以我们需要想出一些办法来解决对象消失问题,使得在遍历对象图的过程中不用进行 STW(也就是用户线程和对象线程可以同时工作),从而提升可达性分析的效率

上面总结了对象消失问题的两个条件,所以说,如果我们想要解决并发扫描时的对象消失问题,只需破坏这两个条件的任意一个即可。由此分别产生了两种解决方案:

  1. 增量更新(Incremental Update):增量更新破坏的是第一个条件,当黑色对象插入新的指向白色对象的引用关系时(就是上图中的 a -> c 引用关系),就将这个新插入的引用记录下来,等并发扫描结束之后,再将这些记录过的引用关系中的黑色对象(a)为根,重新扫描一次。这可以简化理解为,黑色对象一旦新插入了指向白色对象的引用之后,它就变回灰色对象了。
  2. 原始快照(Snapshot At The Beginning,SATB):原始快照要破坏的是第二个条件,当灰色对象要删除指向白色对象的引用关系时(上图中的 b -> c 引用关系),就将这个要删除的引用记录下来,在并发扫描结束之后,再将这些记录过的引用关系中的灰色对象(b)为根,重新扫描一次。这也可以简化理解为,无论引用关系删除与否,都会按照刚刚开始扫描那一刻的对象图快照来进行搜索。

在 HotSpot 虚拟机中,增量更新和原始快照这两种解决方案都有实际应用,CMS 是基于增量更新来做并发标记的,G1、Shenandoah 则是用原始快照来实现


小伙伴们大家好呀,我是小牛肉,公众号【飞天小牛肉】定期推送大厂面试题,提供背诵版 + 详细版,知其然而知其所以然,让八股文变得有价值!)

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/cswiki/p/16377334.html

这个Spring Security登录插件牛啊,验证码、小程序、OAuth2都能快速接入-编程思维

上次我们把验证码登录、小程序登录优雅地集成到了Spring Security,很多同学大呼过瘾,相比较一些传统玩法高级了很多。胖哥就赶紧抓住机会举一反三,把几个非标准的OAuth2也接入了进来,主要是微信、企业微信,做到应接尽接。 只需要通过下面几行简单的代码就可以完成集成: @Bean Delegat

判断一个点是否在指定的直角三角形内-编程思维

《Java 语言程序设计与数据结构》(基础篇)练习题 3.27 题目: 假设一个平面上有一个直角三角形,如下图所示。直角点在(0,0)处,其他两个点分别在(200,0)和(0,100)处。编写程序,提示用户输入一个点的 x 坐标和 y 坐标,然后判断这个点是否在该三角形内。下面是运行示例: Enter a poi

Lambda表达式(匿名内部类)中外部局部变量的使用探讨-编程思维

一.前言 JAVA8引入的stream流在日常开发中使用非常频繁,配合着Lambda表达式一起使用让原本冗长的代码瞬间变得清爽干练了许多,不过在使用之中也出现了些许问题,例如下情况,在lambda表达式中使用了外部变量,并且想要修改它 可以看到编译器直接编译报错,并且提示lambda表达中的使用的变量需要是final

超详细干货!Docker+PXC+Haproxy搭建高可用强一致性的MySQL集群-编程思维

前言 干货又来了,全程无废话,可先看目录了解。 MySQL搭建集群最常见的是binlog方式,但还有一种方式是强一致性的,能保证集群节点的数据一定能够同步成功,这种方式就是pxc,本篇就使用图文方式一步步展示具体的搭建步骤及最终效果。 搭建 本次搭建集群环境以5节点MySQL为例 1、安装pxc镜像 拉取px

浅谈大数据广告下个人隐私保护,开发者视角的广告原理-编程思维

本文已收录于 Github CodeClass 和 Gitee CodeClass 致力于打造高质量编程学习课堂,内含百篇原创技术文章,千本计算机开源电子书,谷歌、阿里大神开源 LeetCode 题解,各类编程学习资源,欢迎 star ,一起学习! 大家好,我是柠檬哥。 最近有在了解广告归因相关的内容,发现挺有意思

【大厂面试必备系列】滑动窗口协议-编程思维

引言 想象一下这个场景:主机 A 一直向主机 B 发送数据,不考虑主机 B 的接收能力,则可能导致主机 B 的接收缓冲区满了而无法再接收数据,从而导致大量的数据丢包,引发重传机制。而在重传的过程中,若主机 B 的接收缓冲区情况仍未好转,则会将大量的时间浪费在重传数据上,降低传送数据的效率。 所以引入了流量控制机制,主机

如何选择合适的自动化测试工具?_陈琦聊测试-编程思维

自动化测试是高质量软件交付领域中最重要的实践之一。在今天的敏捷开发方法中,几乎任一软件开发过程都需要在开发阶段的某个时候进行自动化测试,以加速回归测试的工作。自动化测试工具可以帮助测试人员以及整个团队专注于自动化工具无法处理的各自任务,但困难的部分就是选择自动化工具。事实上,测试人员最常见的问题就是,如何选择适宜的自动