深入理解三色标记、CMS、G1垃圾回收器

三色标记算法 

简介 

        三色标记算法是一种常见的垃圾收集的标记算法，属于根可达算法的一个分支，垃圾收集器CMS，G1在标记垃圾过程中就使用该算法

        三色标记法（Tri-color Marking）是垃圾回收中用于并发标记存活对象的核心算法，通过颜色状态跟踪对象可达性，解决并发标记期间因应用线程修改引用导致的漏标或多标问题

1. 白色（White）​：未访问对象（可能是垃圾）
2. ​灰色（Grey）​：已访问对象，但其子引用（成员变量）未被扫描
3. ​黑色（Black）​：已访问对象，且其子引用已完全扫描

核心规则：

• 黑色对象不会直接指向白色对象​（否则会漏标）
• 所有存活对象最终会被标记为黑色，白色对象可安全回收

运行过程

①开始前，所有对象都在白集合中

 ②被根对象GC ROOT直接引用的对象变成灰色，放进灰集合中

 ③上一步灰色的对象全部变成黑色，进黑色集合中，而灰色的直接引用对象变成灰色进灰集合

④依旧参照上一步 

 ⑤直到灰集合中没有对象，所有的要存活对象都被扫描过了，白色的对象为垃圾会被回收掉 

 多标和漏标问题

        在并发标记阶段，垃圾收集器线程和用户线程同时运行，此时E，F已经被扫描了，E变成黑色，F变成灰色，但是接下来用户线程执行了E.F = null，会导致EF之间连线断开，但是此时F已经变成灰色，但现在实际上F要成为白色的，又不能从灰->白，黑->灰，所以F就是多标了(本应该是垃圾，但是被标记救活了)，F就成了浮动垃圾，但是多标问题危害不大，因为下个垃圾回收周期就会把他们清除掉

        依旧是在并发标记阶段，垃圾收集器线程和用户线程同时运行，此时E，F已经被扫描了，E变成黑色，F变成灰色，但是接下来用户线程执行F.G = null   E.G = G，会导致FG之间连线断开，而EG之间建立连线，因为黑色对象不能指向白色对象(因为黑色对象的意思就是已经被扫描过，不会再扫描)，就会导致G一直是白色最后会被回收掉，但实际上G是有用的对象，所以G就是漏标了(本应该是存活对象，但是没被标记被回收了)，这个漏标的危害就会很高，因为在实际上这个对象还是要用的，就可能会导致空指针NullpointException

漏标问题是如何解决的

首先漏标必须保证两个必要条件：

        ①至少有一个黑色对象指向白色对象（黑色对象E  ----> 白色对象G 之间有连线）

        ②所有指向该对象的灰色对象都断开连接（灰色对象 F ----> 白色对象G 之间的连线断开）

所以CMS和G1就是破坏其中一个条件来解决漏标问题。      

CMS解决漏标问题---增量更新方案

        就是把黑色对象指向白色对象 中的黑色对象变成灰色，然后以灰色对象D为根节点，扫描整个引用链

G1解决漏标问题---原始快照方案

         在并发标记阶段，灰色对象对白色对象的连接断开了，会把白色对象给记录下来，在最终标记阶段，会把白色对象变成灰色，然后再以灰色对象为根节点，去扫描整个引用链

CMS(Concurrent Mark-Sweep)

 简介

CMS（Concurrent Mark Sweep）收集器是一种以获取最短回收停顿时间为目标的收集器。它通过并发标记-清除算法，减少应用程序的停顿时间，适合对延迟敏感的应用场景。

在CMS之前的垃圾回收器，要么就是串行垃圾回收方式(Serial GC)，要么就是关注系统吞吐量(Parallel Scavenge)。

工作流程

        ①初始标记(STW)：标记所有的GC ROOT以及被根对象直接引用的对象

        ②并发标记：垃圾回收器将遍历对象图，从GC Roots向下追溯，标记所有可达的对象。这个过程是四个阶段中耗时最长的，但是不需要停顿用户线程，可以与垃圾收集线程一起并发运行。

特点：

        与应用线程并发执行。

        可能产生浮动垃圾​（标记期间应用程序新产生的垃圾）

为了解决这个问题，CMS采用了卡表。当应用线程试图修改老年代的某个对象引用时，把这些发生变化的对象所在的Card标识为Dirty，这样后续就只需要扫描这些Dirty Card的对象，从而避免扫描整个老年代。

        ③重新标记(STW)：修正并发标记期间因应用线程运行导致的对象引用变化，实际上是要扫描整个堆内存的，但是实际上，由于各种优化技术，比如增量更新（Incremental Update）和卡表(Card Table)，重新标记阶段可以只扫描部分区域。

        ④并发清除：垃圾回收器删除未被标记的对象，并回收他们占用的内存空间，同样，该步骤也是与应用线程并发执行的

优缺点分析

        优点：①低停顿，是以响应时间优先的垃圾回收器

                   ②适用延迟敏感场景：如实时交易系统、Web服务

       缺点：①使用的是标记-清除算法，会产生内存碎片

                  ②比较消耗CPU资源的，对处理器资源是比较敏感的，在并发阶段，它不会导致用户线程停顿，但会占用一部分线程（或者说处理器的计算能力）来进行垃圾回收，从而导致应用程序变慢，降低总吞吐量。

G1(Garbage First)

 简介

G1，全名叫：Garbage First。是垃圾收集器技术发展历史上的里程碑式的成果，从整体来看是基于标记-整理算法实现的收集器，但从局部（两个Region之间）上看又是基于复制算法实现。开创了收集器面向局部收集的设计思路和基于Region的内存布局形式。所以G1相对于CMS的最主要的两大特点：

        ①基于Region的内存布局

每一个Region都可以扮演不同的角色，并且当一个对象超过0.5个Region大小的时候，就会被判定为大对象，会放到Humorous区域中

        ②可预测的停顿时间模型

G1将Region作为单次回收的最小单元，即每次收集到的内存空间都是Region大小的整数倍

G1收集器会去跟踪各个Region里面的垃圾堆积的「价值」大小，价值即回收所获得的空间大小以及回收所需时间的经验值，然后在后台维护一个优先级列表。

每次根据用户设定允许的收集停顿时间（-XX：MaxGCPauseMillis指定，默认值是200毫秒），优先处理回收价值收益最大的那些Region，保证了G1收集器在有限的时间内获取尽可能高的收集效率。

        并且对于跨Region之间对象引用是通过在每一个Region中维护一个记忆集RSet去存储对象之间的引用关系

工作流程

        ①初始标记(STW)：标记从 GC Roots 直接可达的对象

        ②并发标记：根据引用链去标记所有存活对象，使用原始快照方式处理并发期间的对象变化

        ③最终标记(STW)：处理 SATB 中的剩余引用，修正标记结果

        ④筛选回收(STW)：根据用户期望的停顿时间来制定回收计划

优缺点分析

        优点：①不会产生内存碎片

                   ②可预测的时间停顿模型

        缺点：①内存占用，RSet和卡表会占用一定的内存

                   ②写屏障开销，维护 RSet 和卡表引入额外 CPU 开销。