为您推荐:
精华内容
最热下载
问答
  • 49KB ppcust 2020-05-27 17:31:38
  • 二、三色标记 在前文中提到了,在CMS的并发清理阶段才产生的垃圾,会被当做浮动垃圾,会留到下一次GC再清理。其实在并发标记阶段,由于用户线程在并发运行,也就可能导致引用关系改变,导致标记结果不准确,从而引发...

    本文是博主基于自己理解所写,可能与虚拟机具体实现有部分差异,三色标记是个基础算法,不同的产品落地也都可能有不同的实现

    一、三色标记算法

      在CMS垃圾收集器中提到了,在CMS的并发清理阶段才产生的垃圾对象,会被当做浮动垃圾,留到下一次GC再清理。其实在并发标记阶段,由于用户线程在并发运行,也可能会导致引用关系发生改变,导致标记结果不准确,从而引发更加严重的问题,这些发生变更的数据会在重新标记阶段被处理,那么会出现什么问题?又是如何处理的呢?
      CMS算法的基础是通过可达性分析找到存活的对象,然后给存活的对象打个标记,最终在清理的时候,如果一个对象没有任何标记,就表示这个对象不可达,需要被清理,标记算法就是使用的三色标记。并发标记阶段是从GC Root直接关联的对象开始枚举的过程。
      对于三色标记算法而言, 对象会根据是否被访问过(也就是是否在可达性分析过程中被检查过)被分为三个颜色:白色灰色黑色

    • 白色:这个对象还没有被访问过,在初始阶段,所有对象都是白色,所有都枚举完仍是白色的对象将会被当做垃圾对象被清理。
    • 灰色:这个对象已经被访问过,但是这个对象所直接引用的对象中,至少还有一个没有被访问到,表示这个对象正在枚举中。
    • 黑色:对象和它所直接引用的所有对象都被访问过。这里只要访问过就行,比如A只引用了B,B引用了C、D,那么只要A和B都被访问过,A就是黑色,即使B所引用的C或D还没有被访问到,此时B就是灰色。

      根据这些定义,我们可以得出:

    • 在可达性分析的初始阶段,所有对象都是白色,一旦访问了这个对象,那么就变成灰色,一旦这个对象所有直接引用的对象都访问过(或者没有引用其它对象),那么就变成黑色
    • 初始标记之后,GC Root节点变为黑色(GC Root不会是垃圾),GC Root直接引用的对象变为灰色
    • 正常情况下,一个对象如果是黑色,那么其直接引用的对象要么是黑色,要么是灰色,不可能是白色(如果出现了黑色对象直接引用白色对象的情况,就说明漏标了,就会导致对象误删,后面会介绍如何解决),这个特性也可以说是三色标记算法正确性保障的前提条件。

      算法大致的流程是(初始状态所有对象都是白色):

    1. 首先我们从GC Roots开始枚举,它们所有的直接引用变为灰色,自己变为黑色。可以想象有一个队列用于存储灰色对象,会把这些灰色对象放到这个队列中
    2. 然后从队列中取出一个灰色对象进行分析:将这个对象所有的直接引用变为灰色,放入队列中,然后这个对象变为黑色;如果取出的这个灰色对象没有直接引用,那么直接变成黑色
    3. 继续从队列中取出一个灰色对象进行分析,分析步骤和第二步相同,一直重复直到灰色队列为空
    4. 分析完成后仍然是白色的对象就是不可达的对象,可以作为垃圾被清理
    5. 最后重置标记状态

      前面的描述都比较抽象,这里以一个例子进行说明,假设现在有以下引用关系:
    在这里插入图片描述
      首先,所有GC Root的直接引用(A、B、E)变为灰色,放入队列中,GC Root变为黑色:
    在这里插入图片描述
      然后从队列中取出一个灰色对象进行分析,比如取出A对象,将它的直接引用C、D变为灰色,放入队列,A对象变为黑色:
    在这里插入图片描述
      继续从队列中取出一个灰色对象,比如取出B对象,将它的直接引用F变为灰色,放入队列,B对象变为黑色:
    在这里插入图片描述
      继续从队列中取出一个灰色对象E,但是E对象没有直接引用,变为黑色:
    在这里插入图片描述
      同理依次取出C、D、F对象,他们都没有直接引用,那么变成黑色(这里就不一个一个的画了):
    在这里插入图片描述
      到这里分析已经结束了,还剩一个G对象是白色,证明它是一个垃圾对象,不可访问,可以被清理掉。

    二、并发标记带来的问题

      如果整个标记过程是STW的,那么没有任何问题,但是并发标记的过程中,用户线程也在运行,那么对象引用关系就可能发生改变,进而导致两个问题出现。

    2.1 非垃圾变为了垃圾

      比如我们回到上述流程中的这个状态:
    在这里插入图片描述
      此时E对象已经被标记为黑色,表示不是垃圾,不会被清除。此时某个用户线程将GC Root2和E对象之间的关联断开了(比如 xx.e=null;):
    在这里插入图片描述
      后面的图就不用画了,很显然,E对象变为了垃圾对象,但是由于已经被标记为黑色,就不会被当做垃圾删除,姑且也可以称之为浮动垃圾

    2.2 垃圾变为了非垃圾

      如果上面提到的浮动垃圾你觉得没啥所谓,即使本次不清理,下一次GC也会被清理,而且并发清理阶段也会产生所谓的浮动垃圾,影响不大。但是如果一个垃圾变为了非垃圾,那么后果就会比较严重。比如我们回到上述流程中的这个状态:
    在这里插入图片描述
      标记的下一步操作是从队列中取出B对象进行分析,但是这个时候GC线程的时间片用完了,操作系统调度用户线程来运行,而用户线程先执行了这个操作:A.f = F;那么引用关系变成了:
    在这里插入图片描述
      接着执行:B.f=null;那么引用关系变成了:
    在这里插入图片描述
      好了,用户线程的事儿干完了,GC线程重新开始运行,按照之前的标记流程继续走:从队列中取出B对象,发现B对象没有直接引用,那么将B对象变为黑色:
    在这里插入图片描述
      接着继续分别从队列中取出E、C、D三个灰色对象,它们都没有直接引用,那么变为黑色对象:
    在这里插入图片描述
      到现在所有灰色对象分析完毕,你肯定已经发现问题了,出现了黑色对象直接引用白色对象的情况,而且虽然F是白色对象,但是它是垃圾吗?显然不是垃圾,如果F被当做垃圾清理掉了,那就GG~

    三、增量更新和原始快照(SATB)

      上面一共出现了两个问题,从结果上来看,可以这样描述:

    • 一个本应该是垃圾的对象被视为了非垃圾
    • 一个本应该不是垃圾的对象被视为了垃圾

      对于第一个问题,我们前文也提到了,即使不去处理它也无所谓,大不了等到下次GC再清理。最重要的是第二个问题,如果误清理了正在被使用的对象,那就是实打实的BUG了。那么如何解决这个问题呢?
      出现这个问题的主要原因是,一个对象从被B引用,变更为了被A引用。那么对于A来说就是多了一个直接引用,对于B来说就是少了一个直接引用。我们可以从这两个方面入手来解决这个问题,对应了也有两个方案,分别是增量更新(Incremental Update)原始快照(SATB,Snapshot At The Beginning)

    3.1 读写屏障

      在这讲述解决方案之前,要描述两个名词:读屏障写屏障。注意,这里的屏障和并发编程中的屏障是两码事儿。这里的屏障很简单,可以理解成就是在读写操作前后插入一段代码,用于记录一些信息、保存某些数据等,概念类似于AOP。

    3.2 增量更新

      增量更新是站在新增引用的对象(也就是例子中的A对象)的角度来解决问题。所谓增量更新,就是在赋值操作之前添加一个写屏障,在写屏障中记录新增的引用。比如,用户线程要执行:A.f = F;那么在写屏障中将新增的这个引用关系记录下来。标准的描述就是,当黑色对象新增一个白色对象的引用时,就通过写屏障将这个引用关系记录下来。然后在重新标记阶段,再以这些引用关系中的黑色对象为根,再扫描一次,以此保证不会漏标。
      在我们这个例子中,在并发标记阶段,A是一个黑色对象,F是一个白色对象,A引用了F,这个引用关系会被记录下来,然后通过这个记录在重新标记阶段再从A对象开始枚举一次,保证如果A还是保持着F的引用,那么F会被正确标记;如果A到F的引用在并发标记阶段又断开了,此次枚举也无法访问到它,活该被清除。
      要实现也很简单,在重新标记阶段直接把A对象(和其它有相同情况发生的对象)变为灰色,放入队列中,再来一次枚举过程。要注意,在重新标记阶段如果用户线程还是继续执行,那么这个GC永远可能也做不完了,所以重新标记需要STW,但是这个时间消耗不会太夸张。如果实在重新标记阶段耗时过长,那么可以尝试在重新标记之前做一次Minor GC,这个在CMS垃圾收集器中有介绍,这里就不赘述了。

    3.3 原始快照(SATB)

      原始快照是站在减少引用的对象(也就是例子中的B对象)的角度来解决问题。所谓原始快照,简单的讲,就是在赋值操作(这里是置空)执行之前添加一个写屏障,在写屏障中记录被置空的对象引用。比如,用户线程要执行:B.f=null;那么在写屏障中,首先会把B.f记录下来,然后再进行置空操作。记录下来的这个对象就可以称为原始快照。
      那么记录下来之后呢?很简单,之后直接把它变为黑色。意思就是默认认为它不是垃圾,不需要将其清理。当然,这样处理有两种情况,一种情况是,F的确不是垃圾,直到清理的那一刻,都仍然有至少一个引用链能访问到它,这没有什么问题;另一种情况就是F又变成了垃圾。在上述的例子中,就是A到F的引用链也断了,或者直接A都成垃圾了,那F对象就成了浮动垃圾。对于浮动垃圾,前面不止一次就提到了,直接不用理会,如果到下一次GC时它仍然是垃圾,自然会被清理掉。

    3.4 方案抉择

      从增量更新和原始快照的实现(理论上)就可以发现,原始快照相比于增量更新来说效率会更高,因为不用在重新标记阶段再去做枚举遍历,但是也就可能会导致有更多的浮动垃圾。G1使用的就是原始快照,CMS使用的是增量更新。
      既然原始快照可能会有更严重的浮动垃圾问题,那么为什么不使用增量更新呢?原因可能很简单,就是因为简单。想象一下,G1虽然也是基于年轻代和老年代的分代收集算法,但是年轻代和老年代被弱化为了逻辑上,其所管理的内存被划分为了很多region,对象跨代引用带来的问题在G1中要比传统的分代收集器更加突出,虽然有Remember Set方案缓解,但是相对来说在重新标记阶段进行再次遍历枚举的代价会大很多。最重要的是,重新标记(最终标记)阶段是会STW的,如果这个阶段花费太多的时间去做可达性分析,那么就违背了G1低延时的理念。当然这个是博主的猜测,如果读者朋友有更好的想法,欢迎提出。

    四、总结

      这里有一个需要注意的点,重新标记阶段会STW,以此保证标记结果的正确性(主要是漏标)。到现在你可能理解了,垃圾收集器中所描述的:并发清理阶段产生的垃圾会被当做浮动垃圾,只能留待下一次GC被清理。那么实际上是怎么回事呢?其实就很简单了,只要在并发清理阶段产生的对象,直接就认为是黑色对象,全部都不是垃圾。如果一个对象最终成了垃圾,那它就是浮动垃圾,如果没成垃圾,那么标记为黑色也没有什么问题。因为到了清理阶段,标记工作已经完成,没有办法再找到合适的方式去处理这个问题,不然一次GC可能永远也结束不了。
      话说回来,对于上面漏标的情况,你可能还有一个疑问:在并发标记过程中,除了引用关系发生变更的情况,如果用户线程直接创建了一个新对象,这个对象默认是白色,又直接和黑色对象关联,那又该当如何呢?也就是白色对象可能是从其他对象的引用链上”转移“过来的,也可能就是一个新对象。其实可以想象的到,对于新对象加入到黑色节点,我们无法使用原始快照,但是可以使用增量更新,或者直接简单处理,和并发清理阶段一样:在这期间创建的新对象都认为不是垃圾(比如标记为黑色),如果成了垃圾,那就是浮动垃圾,还是留待下一次GC处理。总之,标记的总体原则就是,“另可放过,不可杀错”。
      关于黑白灰三个颜色,是一个抽象的概念,虽然使用可达性分析的垃圾收集器基本都采取三色标记的思想,但在实现上可能也各不相同,像如何标识颜色、灰色队列如何实现等等。比如不止Java,在go的GC中也实现了三色标记算法。个人认为作为普通开发人员,理解思想就够了,如果要看具体的实现,就需要具体到实际的实现源码中去探寻。

    如有错误,感谢指出!

    展开全文
    huangzhilin2015 2021-03-28 16:14:13
  • 为什么会出现三色标记算法? 对于绝大部分垃圾收集器都是基于可达性分析算法来判断对象的存活状态;然后可达性分析算法理论上是一种基于一致性的快照中才能够进行分析,这就意味着需要进行STW(停顿用户线程进行垃圾...

    为什么会出现三色标记算法?

    对于绝大部分垃圾收集器都是基于可达性分析算法来判断对象的存活状态;然后可达性分析算法理论上是一种基于一致性的快照中才能够进行分析,这就意味着需要进行STW(停顿用户线程进行垃圾收集标记)。

    若堆中存储的对象很多,那么对于GC roots图结构越复杂,要标记更多的节点需要停顿更长时间,对于用户来说肯定是不友好,那么可通过削弱STW消耗的时间的话,那么收益也是系统级别的。三色标记算法是一种并发的可达性分析算法,可以削弱STW所耗费的时间。

    什么是三色标记算法?

    三色标记算法可以说是标记清除算法的一种升级版本,JVM在三色标记法中将所有对象(节点)划分为三类,分别用我们日常中的 三种颜色来表示每一类型的节点集合。其中三种颜色标记具体含义是什么呢?

    1、节点被标记成白色

    表示可达性分析初始阶段所有新创建的对象(节点)默认标记成白色状态,表示还没有被GC扫描过;如果可达性分析结束之后任是白色节点,则代表不可达,正常情况要被回收,异常情况看文章后面。

    2、节点被标记成灰色

    表示该节点至少还存在一个引用没有被扫描过,或者说是正在进行标记的节点,会被标记成灰色节点,也是一种中间状态最终会被标记成黑色或者停留在白色状态。

    3、节点被标记成黑色

    表示已经被GC扫描过的节点标记成黑色节点,此时黑色节点就是存活对象,不能被GC回收,黑色节点此时是安全的!

    如下图所示:可达性分析初始阶段,程序开始扫描一次Root Set,初始阶段被标记成白色节点,放入白色节点集合中。如下所示,有7个Node节点。
    在这里插入图片描述

    三色标记算法的流程

    1、初始阶段状态,都是白色节点状态,全部放入到白色节点集合中
    在这里插入图片描述
    2、然后从Root Set开始进行扫描,首先Node1Node5节点被扫描到,Node1Node5被标记成灰色节点如下图所示,从白色节点集合中挪到灰色节点集合中,对比第一步图示。

    注意:这里只遍历一次Root Set集合,不是递归遍历

    在这里插入图片描述

    3、然后GC会从灰色节点开始继续向下扫描,也就是从Node1Node5(被标记成灰色的节点)开始,然后扫描到Node2Node6会被标记成灰色,然后Node2Node6从白色节点集合挪到灰色节点,然后Node1Node5因为已经被扫描过了会被标记成黑色,然后从灰色节点集合挪到黑色节点集合中,如下图所示:对比第2步图示
    在这里插入图片描述
    4、继续从灰色节点Node2Node6开始往下遍历,因为Node2Node6已经被扫描过了,所以会被标记成黑色节点,从灰色节点挪到黑色节点集合中,Node3节点被标记成灰色节点,从白色节点集合中挪到灰色节点集合中,其实就是重复上述第2步骤。
    在这里插入图片描述
    4、继续从灰色节点Node3开始遍历,知道最终没有了灰色节点就不会再往下遍历了,因为Node3被遍历过了,所以会被标记成黑色节点,从灰色节点集合中挪到黑色节点集合中,最终只会剩下两种状态的节点(只有黑和白两种状态节点)

    黑色节点状态: 表示通过可达性分析算法最终存活下来的对象,该对象此时是安全的,不会被销毁

    白色节点状态: 表示通过即将被回收的垃圾对象
    在这里插入图片描述
    6、最终回收玩垃圾节点就会只剩下被标记成黑色状态的节点,表示存在对象引用!这就是整个三色标记算法标记过程。
    在这里插入图片描述

    三色标记法无STW(削弱STW、并发执行)带来的问题

    因为用户程序和标记是并发执行的,存在当扫描正在进行标记的时候,突然把新建了一个引用,引用了还没扫描过的白色节点,将还没来得及标记的对象赋值给了已经标记成黑色对象的节点了,此时存在两种情况:

    第一种:不删除灰色节点对白色节点的引用(p指针)

    被标记成黑色的节点突然新增一个对白色节点的引用,白色节点还未进行标记过,因为不删除灰色节点对白色节点的引用,所以这种情况不会出现什么问题,因为灰色节点还会往下继续查询标记白色节点。如下图所示:

    从灰色节点Node2开始继续向下正准备要对Node3进行标记时,突然由于并发原因,黑色节点Node5新增了一个对白色节点Node3的引用,q指针指向了Node3,此时p指针还有指向Node3的引用,所以Node3节点是会被扫描到并被标记成灰色,最终标记成黑色,不会被当成垃圾,这种情况可以不用考虑。
    在这里插入图片描述

    第二种:删除灰色节点对白色节点的引用(p指针)

    我们删除Node2Node3的引用(删除p指针),这样Node3节点就和Node2节点没有引用关系了,那么在可达性分析时,就标记不到Node3节点,默认还是白色状态的节点,那么就会被当成垃圾回收掉,但是此时Node3正在被黑色节点Node5引用着,如果Node3被当成垃圾回收掉了,问题就大了,Node3对象丢失了
    在这里插入图片描述

    总结:

    综合上述两种情况,三色标记法并发执行虽然可以削弱STW(可视为无STW,就是并发操作),但是由于并发操作的原因也随之而来产生了问题——对象丢失,其实就是满足了两个条件导致的对象丢失造,归结为两个条件:

    条件1: 白色节点被黑色节点引用(白色节点被挂在了黑色节点下,须知黑色节点是不会重新扫描的)

    条件2: 灰色节点和可达关系的白色对象之间的应用遭到了破坏(删除灰白引用)

    这两个条件其实也是三色标记算法种最不想要看到的局面,那么怎么避免解决这个问题呢?就得从这两个条件开始入手。

    三色标记算法弱STW问题解决方案

    强三色不变式(解决条件1)

    必须按照强制性要求三色标记,黑色节点不能引用白色状态的节点,黑色只能引用灰色节点。

    如图所示:Node1节点存在灰色节点的引用是允许的,但是存在白色节点的引用是不可以的,这是强三色硬性要求。
    在这里插入图片描述

    弱三色不变式(解决条件2)

    黑色节点可以引用白色节点,但是白色节点必须存在其他的灰色节点对他的引用(不能删除灰色节点对白色节点的引用),或者可达它的链路上有存在灰色节点也是可以的。如下图所示:

    第一种是不允许的,第二、三种是允许的, 因为白色节点Node2被灰色节点引用了,因为所有的灰色节点会遍历它下面所有的引用节点,所以Node2也会被标记成灰色,然后最终标记成黑色,存活下来,不会被当成垃圾回收掉。
    在这里插入图片描述

    强弱三色底层实现——写屏障

    在这里插入图片描述

    什么是写屏障?

    早在HotSpot虚拟机中就出现过通过写屏障技术维护卡表(保存跨代引用的指针)状态。写屏障广泛用于在低延迟垃圾收集器中(CMS等),可以看作是虚拟机层面对引用类型字段赋值这个动作的一个AOP切面。此屏障和我们的JUC中的内存屏障是有区分的。既然是AOP切面,那么必然是和我们Spring提供的AOP类似,也有写前屏障,写后屏障(类比于环绕通知)。这里展示更新卡表的写后屏障(后置通知)代码如下:

    void opp_field_store(oop* field, oop new_value){
    	// 引用字段赋值
    	*field = new_value;
    	// 写后屏障,在这里完成卡表更新操作
    	post_write_barrier(field, new_value);
    }
    

     

    屏障触发的时机

    在这里插入图片描述
    ▶注意:栈是不会启用屏障保护机制,堆上面才有屏障机制

    插入屏障(增量更新)

    1、所谓插入屏障就是在A节点新建引用B节点的时候,B节点强制被标记成灰色状态(B节点挂在了A节点的下游,B节点标记成灰色状态)

    2、插入屏障解决满足了强三色不变式,也就是新建的引用,不会再有黑色节点引用白色节点的情况发生了,因为插入屏障会强制让引用的对象标记成灰色状态,这样就严格遵守了三色标记法则

    演示插入屏障

    1、我们先截取某个状态下的扫描状态如图所示:然后以这个状态开始进行分析和理解什么是插入屏障;这里需要注意栈上没有屏障机制,堆中才会启用屏障机制。
    在这里插入图片描述

    2、在上述图扫描状态中,现在突然由于并发操作,外界想向Node1节点添加一个新的节点new_N1(栈),Node5节点添加一个新的节点new_N2(堆),如图所示:

    注意:我们分析都是以黑色节点引用白色节点为例子进行分析
    在这里插入图片描述

    2.1、因为Node5是在堆中,会触发开启屏障机制(强制把引用的节点标记成灰色状态),然后新建立的引用的节点new_N2会被标记成灰色节点,如图所示:对比上述图示
    在这里插入图片描述
    2.2、然后Node1节点新建的节点new_N1实在栈中的,所以不会触发屏障机制,需要等待在垃圾回收前重新扫描一遍栈中所有的白色节点,注意这里会先把所有栈中的节点重置成白色节点,然后重新扫描,而且还必须STW,然后有引用的白色节点自然而然会被标记成黑色节点,所以new_N1最终也会被标记成黑色节点

    注意扫描栈的标记是需要STW来保障数据的正确性,最终得到新建的两个节点都是存活节点,没有节点误判!
    在这里插入图片描述

    缺点:

    结束还需要重置所有栈中黑色节点成白色节点,然后STW(保证没有新进入的白色节点或者黑色节点的引用)来重新扫描,大约需要耗时10~100ms
     

    删除屏障(快照标记)

    就是把需要被删除的节点强制标记成灰色节点,因为灰色节点最终是可以继续遍历的。删除屏障其实是满足了弱三色不变式(保护了灰色到白色节点绝不会断开关系,怎么样都会有一个灰色节点存在)

    注意删除屏障栈,堆中都会启用!主要是借助STW来保存快照进行标记的。

    演示删除屏障

    1、我们也是通扫描的某个状态开始来演示分析什么是删除屏障,首先我们经过议论的扫描,Node1Node5标记成灰色状态,然后由于并发操作,删除了灰色节点Node1对白色节点Node2的引用,此时会触发删除屏障,强制要求Node2节点标记成灰色状态
    在这里插入图片描述
    2、如下图示:Node2被标记成了灰色状态的节点
    在这里插入图片描述然后最终标记成黑色节点,如果被标记成黑色的Node2节点没有被别人引用的话,其实就成为了浮动垃圾,这次可以逃过垃圾收集,第二次才会被收集!但是如果有引用的话,那么就不会被当成浮动垃圾进行回收(就比如Node5去引用Node2节点)!
    在这里插入图片描述

    缺点:

    回收率低,导致浮动垃圾的产生,只有等第二次垃圾回收才能被回收!

    对比确定如下图所示:
    在这里插入图片描述

    混合式写屏障(上述两种结合体)

    • GC开始会将栈上的节点全部标记为黑色(不在进行第二次重复扫描,无需STW)
    • GC期间,任何在栈上创建的新对象,均为黑色
    • 被删除的对象标记成灰色
    • 新添加的对象标记成灰色

    演示混合式屏障

    开始栈中的节点都会被标记成白色状态节点,如下图所示:有限扫描全部栈中的节点,将可达节点标记成黑色(Node4Node5非可达),这也是最原始的混合式屏障机制。
    在这里插入图片描述

    场景一:节点被一个堆节点删除引用,成为栈节点的下游

    在混合写屏障中,栈不开启屏障,因为全部被标记成黑色节点了,栈中黑色节点Node1,引用了堆中的白色节点Node7,然后Node6节点删除对应Node7的引用,这时会触发删除写屏障,强制将Node7标记成灰色的,然后加入到灰色标记集合中,这样栈中的黑色节点Node1就不会丢失对象Node7了,如下截图所示:
    在这里插入图片描述
    在这里插入图片描述

    场景二:节点被一个栈节点删除引用,成为另一个栈节点的下游

    在栈中新建一个节点Node8,因为是在栈上新生成的节点,在混合写屏障机制中,栈中的所有可达的节点被标记成黑色,所以Node8为黑色

    然后黑色节点Node8引用到了Node3节点,不会触发任何屏障机制,直接引用即可,而且Node2删除引用也没关系,Node3还是安全的,如下图所示:
    在这里插入图片描述

    场景三:节点被堆节点引用,成为另一个堆节点的下游

    在堆中新加入黑色节点Node8(以黑色节点考虑),然后引用堆的白色节点Node7,因为我么新加入引用,所以Node7节点标记成灰色,然后断开Node6的引用
    在这里插入图片描述
    在这里插入图片描述

    场景四:节点从栈中删除引用,然后成为堆节点的下游

    堆中节点Node6引用栈中的节点Node2,然后栈Node1删除对Node2引用,可以直接删除不用管,因为都是被标记成黑色的,然后堆中节点Node6删除对Node7的引用,会触发删除写屏障,从而Node7会强制标记成灰色。
    在这里插入图片描述在这里插入图片描述

    总结

    并发标记通过两个方法保证节点不丢失,增量更新(插入写屏障)原始快照(删除写屏障),实现这两种方法底层都是写屏障实现!其中CMS是基于增量更新来做并发标记的,G1Shenandoah 则是使用原始快照来实现标记!

     

    展开全文
    qq_35971258 2021-09-02 11:32:52
  • 文章目录CMS收集器CMS的缺点三色标记算法漏标错标原始快照和增量更新写屏障尾巴 CMS(Concurrent Mark Sweep)是一款里程碑式的垃圾收集器,为什么这么说呢?因为在它之前,GC线程和用户线程是无法同时工作的,即使...


    CMS(Concurrent Mark Sweep)是一款里程碑式的垃圾收集器,为什么这么说呢?因为在它之前,GC线程和用户线程是无法同时工作的,即使是Parallel Scavenge,也不过是GC时开启多个线程并行回收而已,GC的整个过程依然要暂停用户线程,即Stop The World。这带来的后果就是Java程序运行一段时间就会卡顿一会,降低应用的响应速度,这对于运行在服务端的程序是不能被接收的。

    GC时为什么要暂停用户线程?
    首先,如果不暂停用户线程,就意味着期间会不断有垃圾产生,永远也清理不干净。
    其次,用户线程的运行必然会导致对象的引用关系发生改变,这就会导致两种情况:漏标和错标。

    1. 漏标
      原本不是垃圾,但是GC的过程中,用户线程将其引用关系修改,导致GC Roots不可达,成为了垃圾。这种情况还好一点,无非就是产生了一些浮动垃圾,下次GC再清理就好了。
    2. 错标
      原本是垃圾,但是GC的过程中,用户线程将引用重新指向了它,这时如果GC一旦将其回收,将会导致程序运行错误。

    针对这些问题,CMS是如何解决的呢?它是如何做到GC线程和用户线程并发工作的呢???

    CMS收集器

    Concurrent Mark Sweep,从名字上就可以看出来,这是一款采用「标记清除」算法的垃圾收集器,它运行的示意图大概如下:
    在这里插入图片描述
    大概可分为四个主要步骤:
    在这里插入图片描述
    1、初始标记
    初始标记仅仅只是标记一下GC Roots能直接关联到的对象,速度很快。初始标记的过程是需要触发STW的,不过这个过程非常快,而且初试标记的耗时不会因为堆空间的变大而变慢,是可控的,因此可以忽略这个过程导致的短暂停顿。

    2、并发标记
    并发标记就是将初始标记的对象进行深度遍历,以这些对象为根,遍历整个对象图,这个过程耗时较长,而且标记的时间会随着堆空间的变大而变长。不过好在这个过程是不会触发STW的,用户线程仍然可以工作,程序依然可以响应,只是程序的性能会受到一点影响。因为GC线程会占用一定的CPU和系统资源,对处理器比较敏感。CMS默认开启的GC线程数是:(CPU核心数+3)/4,当CPU核心数超过4个时,GC线程会占用不到25%的CPU资源,如果CPU数不足4个,GC线程对程序的影响就会非常大,导致程序的性能大幅降低。

    3、重新标记
    由于并发标记时,用户线程仍在运行,这意味着并发标记期间,用户线程有可能改变了对象间的引用关系,可能会发生两种情况:一种是原本不能被回收的对象,现在可以被回收了,另一种是原本可以被回收的对象,现在不能被回收了。针对这两种情况,CMS需要暂停用户线程,进行一次重新标记。

    4、并发清理
    重新标记完成后,就可以并发清理了。这个过程耗时也比较长,且清理的开销会随着堆空间的变大而变大。不过好在这个过程也是不需要STW的,用户线程依然可以正常运行,程序不会卡顿,不过和并发标记一样,清理时GC线程依然要占用一定的CPU和系统资源,会导致程序的性能降低。

    CMS的缺点

    尽管CMS是一款里程碑式的垃圾收集器,开启了GC线程和用户线程同时工作的先河,但是不管是哪个JDK版本,CMS从来都不是默认的垃圾收集器,究其原因,还是因为CMS不太完美,存在一些缺点。
    在这里插入图片描述

    1、对处理器敏感
    并发标记、并发清理阶段,虽然CMS不会触发STW,但是标记和清理需要GC线程介入处理,GC线程会占用一定的CPU资源,进而导致程序的性能下降,程序响应速度变慢。CPU核心数多的话还稍微好一点,CPU资源紧张的情况下,GC线程对程序的性能影响非常大。

    2、浮动垃圾
    并发清理阶段,由于用户线程仍在运行,在此期间用户线程制造的垃圾就被称为“浮动垃圾”,浮动垃圾本次GC无法清理,只能留到下次GC时再清理。

    3、并发失败
    由于浮动垃圾的存在,因此CMS必须预留一部分空间来装载这些新产生的垃圾。CMS不能像Serial Old收集器那样,等到Old区填满了再来清理。在JDK5时,CMS会在老年代使用了68%的空间时激活,预留了32%的空间来装载浮动垃圾,这是一个比较偏保守的配置。如果实际引用中,老年代增长的不是太快,可以通过-XX:CMSInitiatingOccupancyFraction参数适当调高这个值。到了JDK6,触发的阈值就被提升至92%,只预留了8%的空间来装载浮动垃圾。
    如果CMS预留的内存无法容纳浮动垃圾,那么就会导致「并发失败」,这时JVM不得不触发预备方案,启用Serial Old收集器来回收Old区,这时停顿时间就变得更长了。

    4、内存碎片
    由于CMS采用的是「标记清除」算法,这就意味这清理完成后会在堆中产生大量的内存碎片。内存碎片过多会带来很多麻烦,其一就是很难为大对象分配内存。导致的后果就是:堆空间明明还有很多,但就是找不到一块连续的内存区域为大对象分配内存,而不得不触发一次Full GC,这样GC的停顿时间又会变得更长。
    针对这种情况,CMS提供了一种备选方案,通过-XX:CMSFullGCsBeforeCompaction参数设置,当CMS由于内存碎片导致触发了N次Full GC后,下次进入Full GC前先整理内存碎片,不过这个参数在JDK9被弃用了。


    三色标记算法

    介绍完CMS垃圾收集器后,我们有必要了解一下,为什么CMS的GC线程可以和用户线程一起工作。

    JVM判断对象是否可以被回收,绝大多数采用的都是「可达性分析」算法,关于这个算法,可以查看笔者以前的文章:大白话理解可达性分析算法

    从GC Roots开始遍历,可达的就是存活,不可达的就回收。

    CMS将对象标记为三种颜色:在这里插入图片描述
    标记的过程大致如下:

    1. 刚开始,所有的对象都是白色,没有被访问。
    2. 将GC Roots直接关联的对象置为灰色。
    3. 遍历灰色对象的所有引用,灰色对象本身置为黑色,引用置为灰色。
    4. 重复步骤3,直到没有灰色对象为止。
    5. 结束时,黑色对象存活,白色对象回收。

    这个过程正确执行的前提是没有其他线程改变对象间的引用关系,然而,并发标记的过程中,用户线程仍在运行,因此就会产生漏标和错标的情况。

    漏标

    假设GC已经在遍历对象B了,而此时用户线程执行了A.B=null的操作,切断了A到B的引用。
    在这里插入图片描述
    本来执行了A.B=null之后,B、D、E都可以被回收了,但是由于B已经变为灰色,它仍会被当做存活对象,继续遍历下去。
    最终的结果就是本轮GC不会回收B、D、E,留到下次GC时回收,也算是浮动垃圾的一部分。

    实际上,这个问题依然可以通过「写屏障」来解决,只要在A写B的时候加入写屏障,记录下B被切断的记录,重新标记时可以再把他们标为白色即可。

    错标

    假设GC线程已经遍历到B了,此时用户线程执行了以下操作:

    B.D=null;//B到D的引用被切断
    A.xx=D;//A到D的引用被建立
    

    在这里插入图片描述
    B到D的引用被切断,且A到D的引用被建立。
    此时GC线程继续工作,由于B不再引用D了,尽管A又引用了D,但是因为A已经标记为黑色,GC不会再遍历A了,所以D会被标记为白色,最后被当做垃圾回收。
    可以看到错标的结果比漏表严重的多,浮动垃圾可以下次GC清理,而把不该回收的对象回收掉,将会造成程序运行错误。

    错标只有在满足下面两种情况下才会发生:
    在这里插入图片描述

    只要打破任一条件,就可以解决错标的问题。

    原始快照和增量更新

    原始快照打破的是第一个条件:当灰色对象指向白色对象的引用被断开时,就将这条引用关系记录下来。当扫描结束后,再以这些灰色对象为根,重新扫描一次。相当于无论引用关系是否删除,都会按照刚开始扫描时那一瞬间的对象图快照来扫描。

    增量更新打破的是第二个条件:当黑色指向白色的引用被建立时,就将这个新的引用关系记录下来,等扫描结束后,再以这些记录中的黑色对象为根,重新扫描一次。相当于黑色对象一旦建立了指向白色对象的引用,就会变为灰色对象。

    写屏障

    这个写屏障指的可不是并发编程里的写屏障哦!这里的写屏障指的是属性赋值的前后加入一些处理,类似于AOP。

    CMS采用的方案就是:写屏障+增量更新来实现的,打破的是第二个条件。

    当黑色指向白色的引用被建立时,通过写屏障来记录引用关系,等扫描结束后,再以引用关系里的黑色对象为根重新扫描一次即可。

    伪代码大致如下:

    class A{
    	private D d;
    
    	public void setD(D d) {
    		writeBarrier(d);// 插入一条写屏障
    		this.d = d;
    	}
    
    	private void writeBarrier(D d){
    		// 将A -> D的引用关系记录下来,后续重新扫描
    	}
    }
    

    尾巴

    CMS为了让GC线程和用户线程一起工作,回收的算法和过程比以前旧的收集器要复杂很多。究其原因,就是因为GC标记对象的同时,用户线程还在修改对象的引用关系。因此CMS引入了三色算法,将对象标记为黑、灰、白三种颜色的对象,并通过「写屏障」技术将用户线程修改的引用关系记录下来,以便在「重新标记」阶段可以修正对象的引用。
    虽然CMS从来没有被JDK当做默认的垃圾收集器,存在很多的缺点,但是它开启了「GC并发收集」的先河,为后面的收集器提供了思路,光凭这一点,就依然值得记录下来。

    展开全文
    qq_32099833 2020-11-08 16:37:56
  • go语言的gc采用了三色标记法。 三色标记法将对象标记为黑、白、灰三种颜色,黑色对象为可达对象,应该保留,白色对象为不可达对象,应该被清除,灰色作为中间过度态。 下面以链表为例,介绍三色标记-清除法的过程。 ...

    go语言的gc采用了三色标记法。

    三色标记法将对象标记为黑、白、灰三种颜色,黑色对象为可达对象,应该保留,白色对象为不可达对象,应该被清除,灰色作为中间过度态。

    下面以链表为例,介绍三色标记-清除法的过程。

    1. 假设我们新建了三个结点A、B、C,其中,A和B是头结点,C是B的下一个节点,一般头结点都是可达的。由于GC周期还没开始,所以这三个对象都属于白色集合。
      在这里插入图片描述

    2. 接着我们新建节点D,并作为A的下一个节点。注意,此时D将被放置在灰色集合中!因为有这样一条规则:当一个指针域变化时,则该指针指向的对象需要变色。因为所有新建对象都需要将其地址赋值给一个引用,所以它们会立即变成灰色。
      在这里插入图片描述

    3. 在Go中,GC进程和正常程序进程是并行的,它们在计算机中交替运行。此时GC过程开始运行,根对象A、B都被移到灰色集合中。
      在这里插入图片描述

    4. 扫描内存对象,GC收集器会扫描灰色集合的对象,将扫描到的对象标记为黑色,并将其子对象标记为灰色。我们选择对象A进行扫描,将A移到黑色集合,由于D本身就在灰色集合,所以不用移动。无论哪个阶段,GC都可以计算出剩余对象的移动次数为2×[白色集合对象数]+[灰色集合对象数]。理解这个公式也不难,因为灰色对象最后要全部移到黑色集合中,白色对象要先移到灰色集合中,然后才能移入黑色集合,这就是系数2的由来。每次GC扫描都至少要进行一次移动,直到灰色集合中对象数为0,也就是剩余对象移动次数为0才罢休。
      在这里插入图片描述

    5. 程序继续运行,我们又新建了对象E,并作为对象C的下一个节点,同样对象E也会被分配到灰色集合。这一步增加了GC阶段数,也就是GC扫描的次数,因此会导致GC清除阶段的推迟。
      在这里插入图片描述

    6. 此时我们让B指向E,这样一来,对象C将变得不可达。按照第4步GC收集器扫描内存对象的过程,由于灰色集合中没有对象指向C,因此,对象C将永远残留在白色集合中,最后被GC收集器回收掉。
      在这里插入图片描述

    7. GC扫描继续进行,这一次扫描对象D。将对象D移到黑色集合中,但是D没有子对象了,所以直接将D移入黑色集合中就行了。
      在这里插入图片描述

    8. 回到正常程序流程,我们将对象B的next指针置空,断开B与E的关联。按道理E也变为不可达了,应该被清除掉,但是E却在灰色集合中,下一次GC扫描就会被移入黑色集合,不会回到白色集合中,也就不能被回收了。确实是这样,这一轮的GC的确不能将E回收,但是没关系,下一轮的GC就可以将E回收了。
      在这里插入图片描述

    9. GC扫描继续运行,这一次扫描对象E,它也没有子对象,直接将它移入黑色集合就好。注意,这里并不会将对象C移入黑色集合,因为C是E的上层对象,而不是下层对象,简单的说,E的指针并没有指向C。
      在这里插入图片描述

    10. GC收集器扫描对象B,也是孤家寡人一个,直接移入黑色集合完事儿。
      在这里插入图片描述

    11. 此时灰色集合已经空了,可以进行GC清除了。当年地藏菩萨发宏愿:地狱不空,誓不成佛!如今地狱空了,该成佛了。这是GC收集器将回收白色集合中对象的内存空间,因为它们是绝对不可达的,百分之百的垃圾,可以放心的清除它们。至于对象E,他虽然也是不可达的,但是由于它在黑色区域中,因此此时还不能清除它,需要等到下一轮GC清除时才能将它清除。
      在这里插入图片描述

    12. 重置GC,这一轮的GC清除已经完成了,需要为下一轮的GC做好准备。这个准备就是把黑色集合的对象全部再移回白色集合。但实际上并不需要移动,只需要把黑色集合变成白色集合,把白色集合变成黑色集合就行了,也就是把这两个集合的颜色互换一下,不用移动对象。这样一来,对象E就在白色集合中了,并且在下一次GC扫描的时候不会再被移走,将一直残留在白色集合中等着被清除。
      在这里插入图片描述

    以上就是三色标记-清扫算法的全部过程了。

    展开全文
    puss0 2021-02-14 19:42:56
  • u013256816 2021-10-11 00:29:49
  • zero__007 2021-03-15 15:41:03
  • huorongbj 2021-08-07 00:21:42
  • tiancaideshaonian 2021-10-20 22:39:14
  • wtopps 2021-03-12 18:10:32
  • lycyingO 2021-09-21 00:38:18
  • long13631 2021-11-03 21:30:12
  • star1210644725 2021-04-14 23:20:17
  • Gui_yunuo 2020-06-12 19:00:19
  • weixin_43125854 2020-07-27 10:45:09
  • CSDN_WYL2016 2020-09-08 14:18:37
  • waltonhuang 2020-04-16 10:11:51
  • z69183787 2020-09-14 19:57:07
  • weixin_42049278 2021-06-07 22:49:14
  • weixin_44242433 2021-10-07 07:38:24
  • sinat_40292249 2021-12-27 17:05:34
  • z69183787 2020-09-13 09:44:14
  • stone_tomcate 2020-04-17 21:19:00
  • weixin_28948785 2021-03-18 09:40:17
  • zhaanghao 2021-09-27 14:51:15
  • u010800201 2020-07-30 16:36:46

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,536
精华内容 1,814
关键字:

三色标记