本文已收录至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
一起交流学习,期待与你共同进步!文章来源地址https://www.toymoban.com/news/detail-666200.html
到了这里,关于昨晚做梦面试官问我三色标记算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!