学习
实践
活动
工具
TVP
写文章
专栏首页盛开在夏天的太阳12.垃圾收集底层算法--三色标记详解

12.垃圾收集底层算法--三色标记详解

垃圾收集底层算法--三色标记详解

一、并发标记的问题

CMS垃圾收集算法使用了三色标记,我们以CMS垃圾收集为例来说明。CMS垃圾收集的流程如下:

一共有5步:初始标记、并发标记、重新标记、并发清除(包括:并发清理、线程重置)。其中初始标记和重新标记都会Stop The World。在并发标记的过程中,因为标记期间应用线程还在继续跑,对象间的引用可能发生变化,多标和漏标的情况就有可能发生。

二、 什么情况会多标--浮动垃圾?

什么情况下回多标呢?来分析多标的情况。如下图:

在并发标记的过程中,从栈出发,找到所有的GC Root, 于是我们找到了math对象,此时,math对象在堆中的开辟了一块空间,堆中这块空间也都是游泳池的,也就是说他们都不是垃圾。然而就在并发标记的过程中,应用线程也在继续执行,这时候可能math这个对象已经没有引用关系了,那么math就变成垃圾了,但是堆中的空间却没有标记为垃圾,所以收集的时候就不会被收集走。这就是多标的情况。

多标产生的后果是什么呢?就是产生浮动垃圾。

当有多标的时候,该如何解决呢?其实可以不用特殊解决,等待下一次垃圾会,重新进行标记,这块空间就会被回收了。

浮动垃圾:在并发标记过程中,会出现由于方法运行结束,导致一部分局部变量(GC Root)被销毁,而这个GC Root引用的对象之前被垃圾收集器扫描过 ,并且被标记为非垃圾对象,那么本轮GC不会回收这部分内存。这部分本应该回收但是没有回收到的内存,被称之为“浮动 垃圾”

浮动垃圾并不会影响垃圾回收的正确性,只是需要等到下一轮垃圾回收中才被清除。 另外,针对并发标记(还有并发清理)开始后产生的新对象,通常的做法是直接全部当成黑色,本轮不会进行清除。这部分 对象期间可能也会变为垃圾,这也算是浮动垃圾的一部分。

三、什么情况会少标漏标呢 -- 三色标记?

为了处理多标和漏标的情况,我们引入了“三色标记”,在通过可达性分析遍历对象标记GC Root的过程中所遇到的对象,分为三类。这三类对象分别被标记为不同的颜色,即:“黑色”、“灰色”,“白色”。他们分别代表什么含义呢?

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

下面通过案例来分析对象的颜色。

public class ThreeColorRemark {

    public static void main(String[] args) {
        A a = new A();

        // 开始做并发标记
        D dd = a.b.d;
        a.b.d = null;
        a.d = dd;
    }
}

class A {
    B b = new B();
    D d = null;
}

class B {
    C c = new C();
    D d = new D();
}

class C {

}

class D {

}

这里面有四个对象,A, B, C, D。在main方法中,首先new了一个A对象。此时的a对象是一个GC Root,在初始标记的时候会被标记为GC Root。假设,当进入并发阶段的时候,刚刚执行完了A a = new A();这句话时,A应该是什么颜色的呢?

分析上面的代码, 我们要定格时间。

假设:时间定格在执行了A a = new A(); B b = new B(); D d = null; C c = new C(); 但是还没有执行D d = new D();的阶段。

我们这里假设一个极端情况。这句话,A对象中的两个成员变量b和d,首先执行b,指向了堆中new B()的地址。而d没有指向任何对象引用,所以,不需要实例化。这样a对象中两个成员变量,全部都遍历完了,所以a对象会被标记为黑色。黑色的含义是垃圾收集器扫描了这个对象和这个对象里的所有的引用对象,很显然此时a对象不是垃圾。不会被回收。

当执行b对象指向new B()对象的时候,B对象中有两个引用对象,分别是c和d。假设现在程序刚好执行到C c = new C();这句代码,那么此时c对象指向了堆中new C()的引用。就在这一刻,也就是执行了C c = new C();而没有执行D d = new D();这句代码的时候,B是灰色的。灰色表示已经被垃圾收集器扫描过,但是里面的引用没有被全部扫描完,这时这个对象就应该成为下一个扫描的目标,也是不能被回收的。而C是黑色的,因为C里面没有对象,被全部扫描完了。

同样是刚刚那个时刻(执行了C c = new C();而没有执行D d = new D();这句代码的时候),此时因为还没有执行D d = new D(); 这句话,所以D是白色的,表示还没有被扫描到。最开始所有对象都是白色的,也就是A,B,C,D都是白色的,当垃圾收集器扫描完所有的对象以后,有些对象还是白色的,就说明垃圾收集器扫描不到它,那么这就是垃圾,会被回收。

来看看此次时间定格时各个对象的状态。

需要注意的是:上面是定格在gc过程中的某一个时刻。整个GC并没有结束,所以,b是灰色,d是白色只是在那定格的一瞬间。

总结:黑色表示GC已经分析完了,灰色对象表示还没有分析完,白色对象表示没有对其进行分析过。当所有的GC都完成了,还是有对象是白色的,那么这些对象就是不能被触达的对象,就是我们要回收的目标对象。

就在这个时候,又执行了另外一句代码a.d=a.b.d; a.b.d=null; 也就是这时候a对象增加了对d的引用。而对象b对d的引用断开了。如下图:

这时候会发生什么呢?垃圾收集器在扫描的时候,黑色对象a是不会被再次扫描的,再次扫描的目标对象是灰色对象b。这时候,b已经不再引用d了,所以b此时所有对象都已经扫描过,也会变成黑色。而d呢?这时候d其实还被a引用着,但是,垃圾收集器不会去扫描黑色对象了,所以,也不会知道d还被a引用着。这时候,d就还是白色对象,一直是白色对象,不会被垃圾收集器扫描到。这样,d会被当做垃圾清理掉。d其实不是垃圾对象啊,被清理掉还能行?这就是误删除。jvm早期版本会有这样的情况发生,现在基本不会出现了。

其实这种漏标的问题也可以通过代码解决:

// 开始做并发标记
D dd = a.b.d;
a.b.d = null;
a.d = dd;

首先,我们先把a.b.d拿出来赋值给一个新的对象,然后再去掉a.b对d的引用关系,并设置a.d=d.这样d就不会被当做一个垃圾对象回收掉了,因为有一个根对象引用了对象d。

上面是从代码层面解决的,有没有办法从jvm底层解决这种漏标的问题呢?

四、从jvm底层解决漏标问题

漏标会导致被引用的对象被当成垃圾给清理掉,这会产生严重的bug,对于这种漏标的问题,jvm底层利用了CPU的读写屏障来实现的解决方案主要有两种:

  • 一种是增量更新(Incremental Update) ;
  • 另一种是原始快照(Snapshot At The Beginning,SATB) 。

4.1 增量更新

从名字来看,增量更新, 是对新增引用进行处理。下面来看看定义:

当黑色对象插入新的指向白色对象的引用关系时, 就将这个新插入的引用记录下来, 等并发扫描结束之 后, 再将这些记录过的引用关系中的黑色对象为根, 重新扫描一次。 这可以简化理解为, 黑色对象一旦新插入了指向白色对象的引用之后, 它就变回灰色对象了。

也就是说,在黑色对象新增了一个指向白色对象的引用时,会将这个引用记录下来,会有一个集合,专门用来放黑色对象新增的对白色对象的引用,在并发标记的时候并不处理,等并发标记技术以后,进入重新标记阶段,重新标记过程会Stop The World,在处理这个集合,将集合中引用关系中的黑色对象为根,进行重新扫描一次,这次扫描,白色对象就会变成黑色对象或者灰色对象,不会被垃圾回收掉了。

4.2 原始快照

原始快照,不是对新增对象的处理,而是对原始对象的处理,下面来看看定义:

就是当灰色对象要删除指向白色对象的引用关系时, 就将这个要删除的引用记录下来, 在并发扫描结束之后, 再将这些记录过的引用关系中的灰色对象为根, 重新扫描一次,这样就能扫描到白色的对象,将白色对象直接标记为黑 色(目的就是让这种对象在本轮gc清理中能存活下来,待下一轮gc的时候重新扫描,这个对象也有可能是浮动垃圾) ,无论是对引用关系记录的插入还是删除, 虚拟机的记录操作都是通过写屏障实现的。

来看这张图说明:

当扫描到对象b对d的引用删除的之前, 会将这个要被删掉的引用保存一个快照,然后放到集合里。上图b到d的引用时如何被清掉的呢?做了一个赋值操作:

a.b.d = null;

也就是,当执行到这句赋值操作的时候,会先暂停赋值,执行另一个操作--写屏障操作,将这个即将要删除的引用提取出来,保存到一个集合里,然后在执行赋值操作。然后再下一次重新标记的时候,将集合中这些引用关系中的灰色对象作为根,进行重新扫描,这样就可以扫描到白色对象了,将这些白色对象全部标记为黑色对象。标记为黑色对象的目的就是在本轮垃圾回收的时候存活下来,等待下一轮gc的时候重新扫描,这个对象有可能是浮动垃圾。

4.3 写屏障

无论是增量更新还是原始快照,都是通过写屏障来实现的。

增量更新和原始快照都是对引用的操作,一个是新增引用,一个是删除引用,不管是新增还是删除,最终都要把他们收集到集合里去。那么如何收集呢?其实就是在赋值操作之前或者赋值操作之后,把引用丢到集合中去。 在赋值操作的前面或者后面做一些事情,这个过程我们把它叫做代码的操作屏障。

下面来看看赋值屏障的伪代码,以给某个对象的成员变量赋值为例,底层代码大概是这样的::

/**
 * @param field 某对象的成员变量,如 a.b.d
 * @param new_value 新值,如 null
 */
 voidoop_field_store(oop*field,oopnew_value){
 	 *field = new_value; // 赋值操作
 }

所谓的写屏障,其实就是指在赋值操作前后,加入一些处理(可以参考AOP的概念):

voidoop_field_store(oop*field,oopnew_value){
    pre_write_barrier(field); // 写屏障‐写前操作
    *field = new_value;
    post_write_barrier(field, value); // 写屏障‐写后操作
}
  • 写屏障实现原始快照

原始快照是记录对引用的删除。比如在执行a.b.d=null的时候,利用写屏障,将原来B成员变量的引用 对象D记录下来:

// 写屏障代码
void pre_write_barrier(oop*field){
    oop old_value = *field; // 获取旧值
    remark_set.add(old_value); // 记录原来的引用对象
}
  • 写屏障实现增量更新

当对象A的成员变量的引用发生变化时,比如新增引用(a.d = d),我们可以利用写屏障,将A新的成员变量引用对象D 记录下来:

void post_write_barrier(oop*field,oopnew_value){ 
  remark_set.add(new_value); // 记录新引用的对象
}

这两块都是屏障代码,一个是在写前执行,一个是在写后执行。 删除操作要在写前执行, 赋值操作要在写后执行。

下面来看看hotspot源码是如何实现写屏障的,找到oop.inline.hpp文件

/**
 * c++底层调用的赋值方法 
 */
template <class T> inline void oop_store(volatile T* p, oop v) {
  update_barrier_set_pre((T*)p, v);   // cast away volatile
  // Used by release_obj_field_put, so use release_store_ptr.
  oopDesc::release_encode_store_heap_oop(p, v);
  update_barrier_set((void*)p, v);    // cast away type
}

这就是一个赋值操作。update_barrier_set_pre((T)p, v);是一个写前屏障,update_barrier_set((void)p, v);是一个写后屏障。也就是说在赋值之前和之后增加了一段操作代码。其实可以看出来这段代码和我们的伪代码差不多。名字虽不同,但是含义是一样的。

再看看SATB在hotspot源码中是如何实现写屏障的。

void G1SATBCardTableModRefBS::enqueue(oop pre_val) {
  // Nulls should have been already filtered.
  assert(pre_val->is_oop(true), "Error");

  if (!JavaThread::satb_mark_queue_set().is_active()) return;
  Thread* thr = Thread::current();
  if (thr->is_Java_thread()) {
    JavaThread* jt = (JavaThread*)thr;
    jt->satb_mark_queue().enqueue(pre_val);
  } else {
    MutexLockerEx x(Shared_SATB_Q_lock, Mutex::_no_safepoint_check_flag);
    JavaThread::satb_mark_queue_set().shared_satb_queue()->enqueue(pre_val);
  }
}

我们看到这句话satb_mark_queue_set().shared_satb_queue()->enqueue(pre_val); 将旧值放到队列里。这时为什么会放到队列里面呢?为了提高效率。因为是写操作,在写操作之前和之后增加逻辑,是会影响原来代码的效率的,为了避免对源代码的影响,放入到队列中进行处理。

4.4 读屏障

oopoop_field_load(oop*field){
	 pre_load_barrier(field); // 读屏障‐读取前操作
   return *field; 
}

读屏障是直接针对第一步:D d = a.b.d,当读取成员变量时,一律记录下来:

voidpre_load_barrier(oop*field){
	 oop old_value = *field;
	 remark_set.add(old_value); // 记录读取到的对象
}

现代追踪式(可达性分析)的垃圾回收器几乎都借鉴了三色标记的算法思想,尽管实现的方式不尽相同:比如白色/黑色 集合一般都不会出现(但是有其他体现颜色的地方)、灰色集合可以通过栈/队列/缓存日志等方式进行实现、遍历方式可 以是广度/深度遍历等等。

五、各种垃圾收集器对漏标的处理方案

对于读写屏障,以Java HotSpot VM为例,其并发标记时对漏标的处理方案如下:

  • CMS:采用的是写屏障 + 增量更新
  • G1: 采用的是写屏障 + 原汁快照(SATB)
  • ZGC:采用的是读屏障

工程实现中,读写屏障还有其他功能,比如写屏障可以用于记录跨代/区引用的变化,读屏障可以用于支持移动对象的并 发执行等。功能之外,还有性能的考虑,所以对于选择哪种,每款垃圾回收器都有自己的想法。

六、记忆集和卡表

1.记忆集(Remember Set)

在新生代触发Minor GC进行GC Root可达性扫描的时候,可能会碰到跨代引用。比如:新生代的一个对象被老年代引用了,这个时候,在垃圾回收的时候,我们不应该把这块空间回收掉。那怎么办呢?要去扫描一遍老年代么?这显然不行,效率太低了。为了解决这个问题,GC在扫描的时候,会把老年代引用的对象放在一个叫做记忆集的集合中。

这样在垃圾回收的时候,除了会扫描GC Root下的对象,还会扫描一遍记忆集中的引用。记忆集是存储在新生代的空间,保存着老年代对新生代内存的引用关系。记忆集就是为了解决对象的跨代引用问题。

垃圾收集过程中, 收集器只需要通过记忆集来判断某一块非收集区域是否存在指向收集区域的指针即可,无需了解跨代引用指针的全部细节。

2.卡表(Card Table)

hotspot使用的是卡表(cardtable)来实现记忆集。卡表其实就是记忆集的一个实现,卡表和记忆集的关系就像HashMap和Map的关系。记忆集相当于一个概念,而jdk中是通过卡表来实现的。到底是如何实现的呢?

卡表是使用字节数组实现的,卡表的每一个元素对应着其标志的内存区域里一块待定大小的内存块。这些待定的内存块就是“卡页”。堆空间分为新生代和老年代,卡表会把老年代划分为一块一块小的格子,这些小格子就是“卡页”。卡页划分是按照512字节大小进行划分的。如果有一个卡页引用了新生代的对象,那么就将这个卡页就会被标记为“dirty”。卡表是一个数组,里面记录了所有卡页的状态,用010101来标记卡页是否引用了新生代对象。如果是就标记为1,不是就保持原来的0. 数组里除了存放卡页的状态,还有卡页的地址。在垃圾收集器进行扫描的时候,除了扫描GC Root之外,还会扫描卡表里那些状态为1的卡页里的对象。 卡页是在老年代,维护卡页的卡表是在年轻代。

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://www.cnblogs.com/ITPower/复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 内存管理篇(三):Go垃圾回收之三色标记算法

    三色标记法(tricolor mark-and-sweep algorithm)是传统 Mark-Sweep 的一个改进,它是一个并发的 GC 算法,在Gola...

    灰子学技术
  • 一文带你弄懂 JVM 三色标记算法!

    最近和一个朋友聊天,他问了我 JVM 的三色标记算法。我脑袋一愣发现竟然完全不知道!于是我带着疑问去网上看了几天的资料,终于搞清楚啥事三色标记算法,它是用来干嘛...

    陈树义
  • 各种垃圾回收算法及收集器

    该算法分为“标记”和“清除”阶段:首先比较出所有需要回收的对象,在标记完成后统一回收掉所有被标 记的对象。它是最基础的收集算法,后续的算法都是对其不足进行改进得...

    在下是首席架构师
  • JVM 调优 2:GC 如何判断对象是否为垃圾,三色标记算法应用原理及存在的问题?

    本文进入我们进入 JVM 调优系列 2,GC 如何判断对象是否为垃圾,这个是面试中的高频面试题,同时对于 GC 的三色标记算法属于 GC 算法的核心内容,...

    白鹿第一帅
  • JVM 垃圾回收算法和 CMS 垃圾回收器

    本文核心主要是讲述:JVM 中的几种垃圾回收算法理论,以及多种垃圾收集器,并且详细参数 CMS 垃圾收集器的实现、优缺点等,最后也会解释一下三色标记法与读写屏障...

    没有故事的陈师傅
  • 图文结合,白话Go的垃圾回收原理

    前面两篇文章介绍了Go语言的内存分配策略以及Go协程动态扩充和收缩栈内存的原理,今天这篇文章我们主要来聊一下内存管理的另外一大块内容:垃圾回收。

    KevinYan
  • JVM 调优系列 2:GC 如何判断对象是否为垃圾,三色标记算法应用原理及存在的问题

    本文进入我们进入 JVM 调优系列 2,GC 如何判断对象是否为垃圾,这个是面试中的高频面试题,同时对于 GC 的三色标记算法属于 GC 算法的核心内容,我们将...

    白鹿第一帅
  • 《面试八股文》之 JVM 20卷

    「《面试八股文》之 JVM 20卷」 它来了,整理大部分经常会问到的考点,整整 20 问,当然,moon 给出的答案也是相当丰富的,虽然只有 20 问,但是本文...

    用户1263954
  • Go 语言笔试面试题(实现原理)

    init() 函数是 Go 程序初始化的一部分。Go 程序初始化先于 main 函数,由 runtime 初始化每个导入的包,初始化顺序不是按照从上到下的导入顺...

    码农编程进阶笔记
  • 内存管理设计精要

    持久存储的磁盘在今天已经不是稀缺的资源了,但是 CPU 和内存仍然是相对比较昂贵的资源,作者在 调度系统设计精要 中曾经介绍操作系统和编程语言对 CPU 资源的...

    labuladong
  • Go语言垃圾回收机制剖析

    垃圾回收(Garbage Collection,GC) 是Go语言的核心特性之一,是实现内存自动管理的一种形式。golang的自动垃圾回收屏蔽了复杂且容易出错的...

    windealli
  • 关于 CMS 垃圾回收器,你真的懂了吗?

    前段时间有个小伙伴去面试,被问到了 CMS 垃圾回收器的详细内容,没答出来。实际上,CMS 垃圾回收器是回收器历史上很重要的一个节点,其开启了 GC 回收器关注...

    陈树义
  • 自动的内存管理系统实操手册——Golang垃圾回收篇

    导语 | 现代高级编程语言管理内存的方式分自动和手动两种。手动管理内存的典型代表是C和C++,编写代码过程中需要主动申请或者释放内存;而PHP、Java 和Go...

    腾小云
  • JVM - CMS深度剖析

    它非常符合在注重用户体验的应用上使用,它是HotSpot虚拟机第一款真正意义上的并发收集器,它第一次实现了让垃圾收集线程与用户线程(基本上)同时工作 。

    小小工匠
  • 一篇搞懂JAVA与GO垃圾回收

    导语 现代高级编程语言管理内存的方式分自动和手动两种。手动管理内存的典型代表是C和C++,编写代码过程中需要主动申请或者释放内存;而 PHP、Java 和 G...

    腾讯VTeam技术团队
  • GO GC 垃圾回收机制

    垃圾回收(Garbage Collection,简称GC)是编程语言中提供的内存管理功能。

    孤烟
  • Stop The World 是何时发生的?

    Python判断对象存活的算法用的是引用计数法,而Java则使用的是可达性分析法。

    Java识堂
  • 垃圾收集算法及细节

    这是我们一贯认为的垃圾收集方式,在大多的商业虚拟机中几乎都遵循着分代收集的理论。分代收集理论建立在以下三个方面。

    胖虎
  • 浅析 Golang 垃圾回收机制

    Google 搜索 Golang GC 排名靠前的文章都讲的不错,从设计到实现,从演进到源码,一应俱全。但是庞杂的信息会给人一种恐惧感,让人望而却步。本文尝试使...

    郭旭东

扫码关注腾讯云开发者

领取腾讯云代金券