垃圾收集器 ParNew&CMS 和底层三色标记算法说明 - 垃圾收集算法的底层实现

三色标记

在并发标记的过程中,因为标记期间应用线程还在继续跑,对象间的引用可能发生变化,多标和漏标的情况就有可能发生.漏标的问题主要引入了三色标记算法来解决.
三色标记算法是把GC Roots可达性分析遍历对象过程中遇到的对象,按照"是否访问过"这个条件标记成以下三种颜色:

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

public class ThreeColorRemarkDemo {

    public static void main(String[] args) {
        A a = new A();
        // 开始做并发标记
        D d = a.b.d; // 读
        a.b.d = null; // 写
        a.d = d; // 写
    }
}

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

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

class C{}

class D{}

漏标问题复现:

假设A a = new A();后开始做并发标记,从a指向A.从A执行B.从B指向C,此时将A和C记为黑色.B由于还没有扫描到D记为灰色.

a.b.d = null;将B和D之间的引用给干掉了.

在并发标记的过程中,应用线程是可以正常执行的.代码此时将a.d = d;但是由于A是黑色.在后面重新标记的过程中是不会扫描黑色的就会出现漏标的问题.

多标-浮动垃圾

在并发标记过程中,如果由于方法运行结束导致部*部变量(GC Roots)被销毁,这个GC Roots引用的对象之前又被扫描过(被标记为非垃圾对象).那么本轮GC不会回收这部分内存,这部分本该回收但是没有回收的内存,被称之为"浮动垃圾",浮动垃圾并不会影响垃圾回收的正确性,只是需要等到下一轮回收中才被清除.
另外,针对并发标记(还有并发清理)开始后产生的新对象,通常做法是直接全部当成黑色,本轮不会进行清除.这部分对象期间可能也会变成垃圾.这也算是浮动垃圾的一部分.

漏标-读写屏障

漏标会导致被引用的对象被当成垃圾误删除,这是严重bug,必须解决,有以下两种解决方案:

• 增量更新(Incremental Update):当黑色对象插入新的指向白色对象的引用关系时,就将这个新插入的引用记录下来,等并发扫描结束之后,再将这些记录过的引用关系中的黑色对象为根,重新扫描一次.这可以简化理解为:黑色对象一旦插入了指向白色对象的引用之后,它就变回灰色对象了.
• 原始快照(Snapshot At The Beginning,SATB):当灰色对象要删除指向白色对象的引用关系时,就将这个要删除的引用记录下来,再并发扫描结束之后,再将这些记录过的引用关系中的灰色对象为根,再重新扫描一次.这样就能扫描到白色的对象,将白色对象直接标记为黑色(目的就是让这种对象再本轮gc清理中能存活下来,待下一轮gc的时候重新扫描,这个对象也有可能是浮动垃圾)

以上无论是对引用关系记录的插入还是删除,虚拟机的记录操作都是通过 写屏障 实现的.