C/C++教程

三色标记算法原理详述及CMS和G1如何解决其并发标记问题

本文主要是介绍三色标记算法原理详述及CMS和G1如何解决其并发标记问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

三色标记算法是CMS和G1在并发标记阶段都普遍采用的一种trace算法

首先,为什么要对对象进行标记?

因为tracing的过程中你必须对已经遍历过、正在遍历、还没有遍历到的对象进行区分,如果不进行区分的话,那你tracing有什么意义呢?每次某个垃圾回收线程重新获得了cpu的时间分片,回来之后发现自己根本啥都不记得了,遍历过哪些对象(是否是垃圾)已经全忘了,只能从头重新tracing... 这是一个非常严重的问题!!!

 

因此为了有效的对是否遍历过的对象的状态进行区分,便有了这个三色标记的算法,其思想很简单,那就是将我刚刚提到的对象的三种状态用不同的颜色进行标记,如果这个对象及对象的引用对象全部都tracing完了,那么这时候我就可以将对象标记为黑色,而如果对象本身已经遍历过了,但是对象所引用的那些孩子对象还没有遍历过,这时候我可以将对象标记为灰色,如果对象完全没有遍历过(对象本身 + 对象的引用孩子),那么此时我就可以将对象标记为白色,这样一来,即使发生了线程切换,因为在对象头(hotspot)里面存在着对象的颜色标记,仍然看可以从上次遍历过的地方继续遍历,tracing就可以了

 

这个过程感觉有点类似于层序遍历算法BFS,每次我tracing一层,然后如果孩子不为空的话,将孩子都入队列,然后将本身标记为灰色,之后就不断的从队列中取孩子,如果孩子全部都遍历完了,那么这时候就可以将原来的父节点,置为黑色,以后便可以不再找这个黑色父节点的麻烦了!

 

 

 刚刚我解释的过程如果用一张图来表示的话,大概就是这样,三种颜色代表着tracing的三种 不同的状态!

 

但是我们知道,不论是CMS还是G1的垃圾回收的过程中,并发标记都是和用户线程一起进行的,这会带来什么问题呢?

你一边遍历tracing,但是发现对象间的引用关系还在不断的发生变化,这个过程是不是有点太扯了,让垃圾收集器很难做啊!(真的太难了T T)

具体说的话会带来哪些问题呢? 一共分为两种case:

1.部分对象会存在遍历不到的问题

 

 

 

 如上图所示,B本来有个引用属性,是引用了对象D B.d = D,但是随着用户线程的继续进行,却B到D的这个引用关系却消失了, B.d = null 这时候势必会没有办法遍历到D这个对象了,我们仔细思考一下,对于D本身而言,没有任何GC Roots对象可以遍历到它,它本身就是一个垃圾对象,如果遍历过程遍历不到的话,它也会变成一个浮动垃圾,所以对于JVM来说的话从结果上看没什么问题,D对象变成了浮动垃圾,计算这次GC干不掉它,下次GC也一定可以把它给干掉。

(顺便插一句,这也就是为什么CMS不会真的等到堆空间快满了的时候再去执行垃圾清理的过程,因为随着用户线程不断变化引用关系,势必会有浮动垃圾产生,这时候如果用户线程不断产生大量的对象到堆,浮动垃圾本次又无法清理,会导致堆空间立马打满,JVM只能产生STW来清理堆空间,对于用户而言,就会看到程序假死)

 

2.产生last object remove的问题(很严重)

转变为 -> 

 也就是原来B到D的引用消失了,但是D并没有变成垃圾,而是被A重新引用上了这样一个过程

可是对于虚拟机而言,这个过程是存在问题的,因为A已经变成了黑色,从三色标记算法的约定角度出发,是不会再去重新遍历A的,而B会继续遍历,但是因为引用关系的改变,D也不会通过B再trace到了,这样的话,D对于通过三色标记算法的trace而言是一个垃圾对象,会被垃圾回收器进行回收!

可是D因为存在着A到它的引用关系,它并不是一个垃圾,如果此时垃圾回收器清理了D,那么导致的问题就是程序执行到A并取其d属性的时候就会发生空指针异常的问题!

 

上面就是三色标记算法,及其可能产生的两个问题的总结

 

接下来补充一个知识点,那就是CMS和G1在进行并发标记的过程中,是如何解决上述我提到的last object remove的问题的呢?

 

对于CMS而言,它的解决方案非常的直觉,那就是利用write barrier当发生了类似于A->D这种重新引用的情况时,如果发现主动引用的对象此时已经是黑色了,那么这时候我就会重新将其变为灰色,这样子就会重新发起对A对象的再trace的过程,理论上变不会漏掉其新增的属性对象了;

但是这个过程仍然存在bug,看图

 

 如上图中文字标记的过程所示,m1线程将属性1已经trace完了,然后m2的用户线程此时将新的白色对象D指向了已经标记完的属性1,然后m3线程此时将对象A标记为灰色

这个重新标记成灰色的过程其实没啥用不知道大家发现了没有,因为对于m1线程而言,其看A本身就是还是灰色的,2属性还没标记呢,然后m3线程因为发生了1属性的重新指向,所以再次将A的颜色变为灰色,

根本就没啥区别,当m1重新获得执行权限的时候,它会继续遍历2属性,当2属性也trace完了之后,就把A对象标记为黑色了,问题还是没有得到解决!

所以,最终CMS采用的终极解决方案那就是再重新标记的过程中,对于这种可能存在问题的对象,再执行一遍从头trace的过程,这个过程是需要STW的!

 

 

那G1是怎么解决这个问题的呢?

G1不会从变更和改动入手去解决这个问题,而是追根溯源,采用了一种叫做SATB的方式来解决,所谓的SATB,就是snatshop at the begining的缩写,看翻译我们大概也能够知道这种思路,那就是如果B对D的引用发生了变化的话,我们会将这条消失的引用关系链记录到一个队列里,当我们都trace完成之后,会从队列中将这部分消失的关系,重新取出来,在继续进行补充遍历过程,这样子便不会再发生刚刚说过的last object remove的问题啦!

 

PS:本文所用配图来自mashibing老师的ppt中,如果侵权立马删除,才疏学浅,知识理解能力有限,如有错误,欢迎批评指正!

这篇关于三色标记算法原理详述及CMS和G1如何解决其并发标记问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!