三色标记算法原理

简介 什么是三色标记算法jvm垃圾回收期使用的,在并行标记的时候的一种算法,CMS/G1中的核心算法。把对象从逻辑上分为三种颜色,分别是黑色,灰色,白色黑色:自身和成员变量均已标记灰色:自身被标记,成员变量未被标记白色:未被标记的对象它主要用于收集器内存管理,适用于任何的垃圾收集器,也就是通用的算法。我们通过G1回收器来了解这个算法,我们都知道G1收集器分为三个步骤新生代回收过程当新生代eden区内存满

什么是三色标记算法


jvm垃圾回收期使用的,在并行标记的时候的一种算法,CMS/G1中的核心算法。

把对象从逻辑上分为三种颜色,分别是黑色,灰色,白色

黑色:自身和成员变量均已标记

灰色:自身被标记,成员变量未被标记

白色:未被标记的对象

它主要用于收集器内存管理,适用于任何的垃圾收集器,也就是通用的算法。

我们通过G1回收器来了解这个算法,我们都知道G1收集器分为三个步骤


新生代回收过程

当新生代eden区内存满的时候,G1年轻代收集器会采用并行多线程的方式清理堆内存垃圾,这时候会暂停所有用户的线程,让后新生代存活的对象会拷贝到S区或者老年代中。但是在G1中,它使用的是标记复制算法

新生代GC+并发标记过程

在新生代进行回收时,进行GCRoot初始化标记与CMS实现原理基本相同,老年代达到堆内存空间阈值时,会实现并发标记(不会stw),jvm配置参数-XX:InitiatingHeapOccupancyPercen=45%,在使用再次标记(修正的时候)的时候,G1中采用了比CMS更快的初始快照算法:snapshot一at一the一beginning (SATB)。三色标记算法,前面提到过三色一共有三个颜色,黑、灰、白。

并发标记不会触发stw

这里要注意的是:CMS中使用,漏标采用增量更新,G1中使用,漏标采用SATB

混合收集

当越来越多的对象晋升到老年代的时候,为了避免堆内存耗尽,会触发混合收集器,即Mixed GC。在此收集中,最终标记和拷贝存活,均会触发stw。

回收整个Young Region(新生代区域),部分的老年代区域,如果G1无法有足够的空间复制对象的时候,有可能会引发FullGc

所以也就是说,G1收集器一共有四个回收步骤。最后一个是FullGC。


三色标记算法原理


初始的时候,会将所有对象都在白色容器中;

当收集器在做初始标记的时候,会暂停所有的用户线程,标记与GCRoot直接关联的对象;并且放入到灰色盒子中。

在并发标记中(用户线程与GC线程同时运行),将与GCRoot直接关联的对象和直接关联的对象的引用对象移动灰色容器中,如果该对象没有引用到其他对象或者其他对象已经标记过,则该对象放到黑色容器中。

重复以上这些操作,到灰色容器为空时,则停止。

在重新标记时,将与GCRoot直接关联的对象的引用对象移动灰色容器中,重复此操作,到灰色容器为空时,则停止。结束后,如果在白色容器中任然存在的对象,则认为就是与GCRoot没有直接关联,则认为就是为不可达对象,可以被垃圾回收线程清理。

在这里面,如果我们在多线程的环境下,那么会产生两个问题,漏标和多标。

我们先来说说多标的问题。


多标的产生

在多线程的情况下,因为我们的并发标记是用户线程和GC线程可以同时运行的,

所以当GC线程先执行遍历到A对象,那么A对象已经存放到灰色容器中,突然用户线程修改了A对象中的属性B对象,并设置为Null,这时候B对象已经是为垃圾对象了(因为没有被引用),但是B对象已经存放到灰色容器中,然后GC线程运行,遍历到B对象的时候,因为它被标记的不是白色,所以GC线程不认为B对象是垃圾对象,这个过程我们可以称作为多标-浮动垃圾,但是又有人疑问了,后面不是有一个重新标记吗?为什么不能把浮动垃圾变为白色的呢?前面的三色标记法,已经提到过,在重新标记的过程中,遍历方式是–>"将与GCRoot直接关联的对象的引用对象移动灰色容器中,重复此操作,到灰色容器为空时,则停止",但是我们的B对象在之前初始标记的时候是灰色对象,所以我们直接从B对象开始遍历引用链了,所以无法标记为白色。其实这种问题并不大,多标最多就是产生一次垃圾,下次回收的时候就可直接回收了,问题不大,漏标才是最大的问题。我们来看看漏标


漏标的产生


漏标的问题满足两个条件:


至少有一个黑色对象指向了白色对象

所有灰色对象扫描完整个链时,删除之前所有白色对象。

当遍历的B对象(与GCRoot间接相连的对象,与A对象直接相连)的时候,B对象已经存放到灰色容器中,突然用户线程修改B对象属性C对象设置为Null; 那么B对象与C对象断开链接,则C对象则会变为垃圾对象,但是用户线程修改A对象(与GCRoot直接相连的对象,与B对象直接相连)的属性C = C对象,但是A对象已经为黑色不会继续遍历,就会导致C对象会被GC线程线程定义为垃圾对象清理,这个过程称作为漏标问题。


这个问题相比于多标是很严重的问题,因为漏标会将需要使用的对象清空。

那么在CMS收集器和G1收集器是怎么处理这两个问题的呢?


CMS收集器中处理漏标问题:


使用增量更新,满足了第一个条件(灰色对象不在关联白色对象的时候),当黑色对象关联该白色对象的时候,会通过“写屏障”记录该黑色对象, 在重新标记的时候,以该黑色对象变为灰色,从新开始修正标记,但是这种方案能够确保垃圾都被清理,缺点就是效率非常低,因为会扫描到整个黑色对象所有引用。


G1收集器中处理漏标问题:

使用原始快照SATB(Snapshot At The Beginning)


原始快照:简单理解就是备份


如果用户线程在灰色对象断开一个白色对象的时候,会记录原始快照,在重新标记的时候,以白色对象变为灰色对象扫描整个链。如果该白对象没有被其他对象关联,那么此次并不会被清理,而是在下次再进行回收,此次就幸存了。G1收集器宁愿产生浮动垃圾,但是可以提高效率




原文链接:https://blog.csdn.net/weixin_43911969/article/details/115914329


上一篇: 熔断限流

下一篇: 高并发解决方案

Top Top