昨晚做梦面试官问我三色标记算法

这篇具有很好参考价值的文章主要介绍了昨晚做梦面试官问我三色标记算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本文已收录至GitHub,推荐阅读 👉 Java随想录

微信公众号:Java随想录

原创不易,注重版权。转载请注明原作者和原文链接

目录
  • 三色标记算法
  • 增量更新
  • 原始快照

某天,爪哇星球上,一个普通的房间,正在举行一场秘密的面试:

面试官:我们先从JVM基础开始问,了解三色标记算法吗?

我:额......不了解。

面试官:出去的时候记得把门带上。


现在Java面试真的已经是越来越卷了,直接上来问原理给你直接干懵。

上篇我们讲了记忆集,这篇来聊聊「三色标记算法」,也是Java面试的常客。聊好了会让面试官觉得你这小伙子有点东西。

三色标记算法

既然叫三色标记算法,首先我们要搞明白是哪三色,三色是:黑色,白色,灰色。

把可达性分析遍历对象图过程中遇到的对象,按照「是否访问过」这个条件标记成以下三种颜色:

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

《深入理解Java虚拟机》书中关于这块图画的很好,一目了然,直接上原图:

从上面这段话中,我们提炼一下关键要点:

  • 初始阶段,GC Root是黑色的,所有的对象都是白色的,若在分析结束的阶段,仍然是白色的对象,即代表不可达。

  • 如果有其他对象引用指向了黑色对象,无须重新扫描一遍。

  • 黑色对象不可能直接指向某个白色对象。

让我来给大伙稍微解释一下第二点和第三点。

我上面画了一个示意图,第一幅和第二幅画的是对的,第三幅画的是错的。

先分析第二点,如果有其他对象引用指向了黑色对象,那么这个对象只能为灰色或者黑色,自然无须再重新扫描一遍。

然后再说第三点,黑色对象不可能直接指向某个白色对象。

我们从上面可知黑色对象的定义是:「对象的所有引用都已经扫描过」,而白色对象是:「对象尚未被垃圾收集器访问过」。

那么问题来了,如果黑色对象直接指向某个白色对象,那么他就跟黑色对象的定义矛盾了。

因为白色对象还没被访问过,怎么能算所有引用都扫描过了呢,所以他就不可能是黑色。

上面这个很重要,把这个理解透彻之后,我们看看三色标记算法存在的一些问题:

由于一些垃圾回收器存在垃圾回收线程和用户线程并发的情况(例如CMS的并发阶段),那么三色标记会有两个问题:

  • 一种是把原本消亡的对象错误标记为存活,这不是好事,但其实是可以容忍的,只不过产生了一点逃过本次收集的浮动垃圾而已,下次收集清理掉就好,问题不大。
  • 另一种是把原本存活的对象错误标记为已消亡,这就是非常致命的后果了,程序肯定会因此发生错误。

第一点无伤大雅,所以我们解决问题的重心放到第二点上。

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

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

其实一句话说白了就是:「跟灰色对象断开连接,跟黑色对象建立连接」。

因此,我们要解决并发扫描时的对象消失问题,只需破坏这两个条件中的任意一个即可。

由此分别产生了两种解决方案:「增量更新(Incremental Update)」和「原始快照(Snapshot At The Beginning,SATB)」。

这两个解决方案各破坏一个条件。

增量更新

增量更新要破坏的是第一个条件。

当黑色对象插入新的指向白色对象的引用关系时,就将这个新插入的引用记录下来,等并发扫描结束之后,再将这些记录过的引用关系中的黑色对象为根,重新扫描一次。

这可以简化理解为,黑色对象一旦新插入了指向白色对象的引用之后,它就变回灰色对象了。

这其实有点像之前讲过类似OopMap的思想,本质也是维护了个映射关系,扫描结束的时候把这个映射关系再重新扫描一遍,不用全局扫描。

如图,将这个新插入的引用关系记录下来,扫描结束之后,将记录过的引用关系中的黑色对象1为根,重新扫描一次,就OK了。

原始快照

原始快照要破坏的是第二个条件。

当灰色对象要删除指向白色对象的引用关系时,就将这个要删除的引用记录下来,在并发扫描结束之后,再将这些记录过的引用关系中的灰色对象为根,重新扫描一次。

这也可以简化理解为,无论引用关系删除与否,都会按照刚刚开始扫描那一刻的「对象图快照」来进行搜索,故名「原始快照」。

如图,将这个删除的引用关系记录下来,扫描结束之后,将记录过的引用关系中的灰色对象2为根,重新扫描一次,就OK了。

那么有个问题,增量更新和原始快照都需要记录引用关系,那这个记录的时间点发生在什么时刻呢?

不知道大家还是否记得之前说过的「写屏障」,是的没错。

无论是增量更新还是原始快照,虚拟机的记录操作都是通过写屏障实现的。

写屏障,我们之前讲记忆集与卡表的时候介绍过的,可以理解为Spring中的AOP,目前为止卡表状态的维护,增量更新,原始快照都是基于写屏障。

另外,课外拓展一下,CMS使用的是增量更新,G1使用的是原始快照。

本篇文章就到这了,本篇篇幅可能有点短,不过能把事情说清楚就行。之后开始讲垃圾回收器,大家一起期待下吧。

用心写文章,大伙要是有收获,希望点个赞激励一下,thank you。


感谢阅读,如果本篇文章有任何错误和建议,欢迎给我留言指正。

老铁们,关注我的微信公众号「Java 随想录」,专注分享Java技术干货,文章持续更新,可以关注公众号第一时间阅读。

一起交流学习,期待与你共同进步!文章来源地址https://www.toymoban.com/news/detail-666200.html

到了这里,关于昨晚做梦面试官问我三色标记算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 一个资深测试工程师面试一来就问我这些题目

    德玛作为一个已经工作有10年经验的测试工程师,其间也辗转了几个大的互联网公司,虽然确实缺少了一些稳定性,但同时也积累了一些面试的经验,不才分享一些给大家。那么主要是针对测试工程师的一些总结,对于其他的工种,我可能会在别的文章中去总结一些面试技巧

    2024年02月09日
    浏览(48)
  • 【面试】面试官问的几率较大的网络安全面试题

    攻击者在HTTP请求中注入恶意的SQL代码,服务器使用参数构建数据库SQL命令时,恶意SQL被一起构造,并在数据库中执行。 用户登录,输入用户名 lianggzone,密码 ‘ or ‘1’=’1 ,如果此时使用参数构造的方式,就会出现 select * from user where name = ‘lianggzone’ and password = ‘’ or

    2024年02月01日
    浏览(48)
  • 大厂面试题-JVM中的三色标记法是什么?

    目录 问题分析 问题答案 三色标记法是 Java 虚拟机 (JVM)中垃圾回收算法的一种,主要用来标记内存中存活和 需要回收的对象。 它的好处是,可以让 JVM 不发生或仅短 时间发生STW(Stop The World),从而达到清 除 JVM 内 存垃圾的目的 , JVM中的「CMS、G1垃圾回收器」都用到了三色标

    2024年02月07日
    浏览(38)
  • 面试官问:kafka为什么如此之快?

    天下武功,唯快不破。同样的,kafka在消息队列领域,也是非常快的,这里的块指的是kafka在单位时间搬运的数据量大小,也就是吞吐量,下图是搬运网上的一个性能测试结果,在同步发送场景下,单机Kafka的吞吐量高达17.3w/s,不愧是高吞吐量消息中间件的行业老大。 那究竟

    2024年02月07日
    浏览(41)
  • JVM 三色标记算法

    我们要进行垃圾回收,就需要弄明白哪些对象是需要回收的,哪些对象是不需要回收的。针对这个问题,其实业界已经有几种常见的解决方法了。 第一种是计数法 ,就是每个对象都有一个计数器,被引用了加一,移除引用减一。但这种方法比较麻烦,而且也会有循环依赖的

    2024年02月12日
    浏览(36)
  • 关于三色标记算法

    三色标记算法是一种用于垃圾收集得算法,主要用于解决在并发垃圾收集中可能出现得对象引用更新问题。在JVM中,这种算法主要应用于CMS(ConcurrentMarkSweep)收集器和G1(Garbage-first)收集器。 三色标记算法将对象分为三种颜色: 白色:表示对象尚未被垃圾收集器访问过,如

    2024年02月20日
    浏览(25)
  • 造轮子系列】面试官问:你能手写Vuex吗(一)?

    前后端面试题库 (面试必备) 推荐:★★★★★ 地址:前端面试题库  web前端面试题库 VS java后端面试题库大全 Vuex 是 Vue.js 的状态管理模式,它主要解决了组件之间共享状态时的问题。在本文中,我们将实现一个简单的状态管理器,来帮助我们更好地理解 Vuex 的实现原理

    2024年02月03日
    浏览(39)
  • 面试官问 : ArrayList 不是线程安全的,为什么 ?(看完这篇,以后反问面试官)

    金三银四 ? 也许,但是。 近日,又收到金三银四一线作战小队成员反馈的战况 : 我不管你从哪里看的面经,但是我不允许你看到我这篇文章之后,还不清楚这个面试问题。 本篇内容预告:   ArrayList 是线程不安全的, 为什么 ? ① 结合代码去探一探所谓的不安全  ② 我们

    2024年02月02日
    浏览(59)
  • 【137期】面试官问:RocketMQ 与 Kafka 对比,谈谈两者的差异?(1)

    先自我介绍一下,小编浙江大学毕业,去过华为、字节跳动等大厂,目前阿里P7 深知大多数程序员,想要提升技能,往往是自己摸索成长,但自己不成体系的自学效果低效又漫长,而且极易碰到天花板技术停滞不前! 因此收集整理了一份《2024年最新Java开发全套学习资料》,

    2024年04月27日
    浏览(33)
  • GC 三色标记算法(Go & Java版本)

    GC全称Garbage Collection,目前主流的垃圾回收算法有两类,分别是追踪式垃圾回收算法(Tracing garbage collection)和引用计数法( Reference counting )。 而三色标记法是属于追踪式垃圾回收算法的一种。追踪式算法的核心思想是判断一个对象是否可达,因为一旦这个对象不可达就可以

    2024年02月05日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包