【垃圾回收】三色标记算法原理及应用

【垃圾回收】三色标记算法原理及应用

引用

CSDN

1.

https://blog.csdn.net/qq_40298670/article/details/145617157

三色标记算法是Java虚拟机中一种重要的垃圾回收理论模型，通过将对象标记为白色、灰色和黑色，实现对内存中垃圾对象的识别和回收。本文将详细介绍三色标记算法的原理、存在的问题及其解决方案，并探讨其在CMS和G1等垃圾收集器中的具体应用。

1、算法介绍

三色标记算法是一种用于垃圾回收的理论模型。它将所有对象分为三色：

• 白色：该对象没有被标记过，在标记开始时，堆内存中的对象都是白色的。标记结束后，仍为白色则被认为是垃圾对象。
• 灰色：该对象已经被标记过（存活的对象，不会被清理），但该对象下引用的子对象没有全被标记完，表示这个对象正在枚举中。是一个过渡状态。
• 黑色：该对象已经被标记过，该对象下引用的子对象也全被标记完（程序需要的对象）。

三色标记过程：

1. 初始时，堆中所有对象都是白色
2. 从GC Roots开始枚举，它们所有的直接引用变为灰色，自己变为黑色
3. 遍历所有灰色对象，将这个对象所有的直接引用变为灰色，然后这个对象变为黑色；如果这个灰色对象没有直接引用，那么直接变成黑色
4. 重复步骤3直到没有灰色对象，分析完成后仍然是白色的对象就是不可达的对象，可以作为垃圾被清理

上述灰色状态可以想象成队列，先变成灰色的先遍历。

2、存在的问题

浮动垃圾：在并发标记的过程中，若一个已经被标记为灰色或黑色的对象被其他用户线程操作，变成了垃圾。由于不会重复扫描，这个对象不是白色，不会被清除，成为了浮动垃圾。浮动垃圾对系统影响不大，可以留着下一次GC进行处理。

对象漏标问题：在并发标记的过程中，一个业务线程将一个未被扫描过的白色对象断开引用，同时黑色对象引用了该对象；因为黑色对象表示其所有子对象已经被标记过，导致该对象被不是垃圾，却要被当做垃圾回收。

3、问题的解决方案

问题分析：

漏标问题的产生有两个充要条件：

1. 至少一个黑色对象新增了白色对象的引用
2. 所有灰色对象指向该白色对象的引用都断开了

增量更新方案

增量更新方案主要破坏了第一个条件，即从新增引用的这一侧去解决问题。在并发标记阶段，如果一个黑色对象新增了一个白色对象的引用，会通过写屏障机制记录这一变化，会把黑色对象记录下来。

上例中，新增引用D->G，则会记录D。在重新标记阶段，会把黑色对象D标记为灰色，然后以灰色对象D为根节点重新标记，这样白色对象G就会依次变为灰色、黑色，漏标问题就解决了。

这样一来重新标记阶段需要STW，否则GC可能永远也做不完了。

缺点：会重新扫描以黑色对象D为根节点的整个引用链，会浪费多一点时间。

CMS垃圾收集器就是使用的增量更新方案。

原始快照方案

原始快照破坏了第二个条件，即从减少引用的这一侧去解决问题的。在并发标记阶段，如果一个灰色对象断开了白色对象的引用，会记录被置空的对象（白色对象），记录下来的这个对象就称为原始快照。

上例中，灰色对象E断开了对白色对象G的引用，这时会把白色对象G记录下来，在最终标记阶段，会把白色对象G标记为灰色，然后以灰色对象G为根节点，扫描整个引用链，如此以来原来的白色对象G就会被依次标记为灰色、黑色，漏标的问题就解决了。

缺点：如果没有黑色对象指向白色对象，白色对象就变成了浮动垃圾，等下次GC回收。

G1垃圾收集器使用的原始快照的方案。

4、垃圾收集器的应用

CMS垃圾收集器

CMS目标是追求最短停顿时间，是针对老年代垃圾回收的。采用的标记清除算法。其工作原理分为以下几个阶段：

1. 初始标记，根节点直接引用的对象标记为灰色（短暂的STW）
2. 并发标记，递归扫描灰色对象引用的对象并标记为灰色，原灰色对象标记为黑色（GC线程和应用线程同时工作）
3. 重新标记，增量更新方案矫正并发标记阶段的错误（短暂的STW）
4. 并发清除，清除白色的对象，内存回收

这样做可以尽量减少垃圾回收对应用程序的暂停时间，标记-清除算法直接清理垃圾对象，不需要移动对象，执行速度快。但会导致内存高度碎片化。此外，CMS的并发能力比较依赖于CPU资源，并发回收时会抢站用户线程，导致用户程序性能下降。

G1垃圾回收器

G1是针对整堆的垃圾回收器，解决了内存碎片化问题。它将内存划分成多个固定大小的区域，每个区域都可以充当Eden、Survivor、Old、Humongous，采用复制算法。兼顾响应时间和吞吐量。每个Region都是通过指针碰撞分配空间的。

G1允许用户指定期望的最大GC暂停时间（MaxGCPauseMillis），G1会基于此目标智能地选择哪些Region进行回收，以平衡暂停时间和碎片整理效率。其工作原理如下：

1、年轻代垃圾回收，新建对象分配到Eden区，当Eden需要垃圾回收时，触发Young GC，STW，采用复制算法，将Eden区和Survivor区中存货的对象复制到新的Survivor区或晋升到老年代。

2、并发标记阶段，当老年代占内存比例超过阈值（默认是45%），触发并发标记，这个阶段分为多个子阶段：

（1）初始标记（Initial Marking）：仅仅只是标记一下GC Roots能直接关联到的对象
（2）并发标记（Concurrent Marking）：从GC Root开始对堆中对象进行可达性分析
（3）最终标记（Final Marking）：原始快照方案处理并发阶段结束后仍遗留SATB记录
（4）筛选回收（Live Data Counting and Evacuation）：根据用户期望的停顿时间和每个Region的垃圾比例来制定回收计划

注：1）3）4）初始标记，最终标记，筛选回收都存在STW，用户线程都停止。

3、混合收集
选择回收的Region进行回收，STW，存活对象复制到新Region

4、全局回收
当老年代内存不足或其他回收策略无法满足时触发，STW，标记整理。Full GC停顿时间较长，应尽量避免。