垃圾回收的三色标记算法
目录
1、介绍
1.1、发展
1.2、基本原理
2、执行过程
2.1、初始标记 (Initial Marking)
2.2、并发标记 (Concurrent Marking)
2.3、重新标记 (Remark)
2.4、垃圾清理阶段
3、并发标记
3.1、浮动垃圾
3.2、漏标
前言
三色标记（Tri-color Marking）是JVM垃圾回收器中用于追踪存活对象的核心算法，尤其广泛应用于CMS、G1等现代垃圾收集器。
属于是jvm的垃圾回收算法里面的标记-清除（Mark-Sweep）算法家族的重要演进成果，但它与传统标记-清除有显著区别，演进而非隶属。
如下图所示：
由上图可知，两者的区别和联系。
1、介绍
1.1、发展
属于增量式状态转换标记，而非一次性全量标记，清除阶段仍基于传统标记-清除的思想。
引用计数（1959）
↓
标记-清除（1960）
↓
标记-整理（1960s）
↓
分代收集（1984）
↓
三色标记（1976）→ 并发标记（1990s）
↓
颜色指针（2010s）三色标记算法通过引入中间状态（灰色）和状态转换机制，使标记过程可以暂停和恢复，从而实现了并发标记这一重大突破，这是传统标记-清除算法无法做到的。
两者在思想上一脉相承，但在实现方式和应用场景上已有本质区别。
1.2、基本原理
三色标记算法将对象分为三种颜色：黑色 (Black)、灰色 (Gray) 和白色 (White)。每种颜色代表了对象的不同状态。如下图所示:
1.白色 (White)：
含义：
表示未被访问过的对象，即尚未被标记的对象。
变化：
在初始标记阶段，所有对象都是白色的。
2.灰色 (Gray)：
含义：
表示正在被访问的对象，即已经被标记，但其引用还没有被完全追踪的对象。
变化：
在并发标记过程中，当一个对象被首次标记时，它会变成灰色。然后，从灰色对象开始，追踪其引用的对象。
3.黑色 (Black)：
含义：
表示完全访问过的对象，即已经被标记并且其所有引用都已被追踪的对象。
变化：
当一个灰色对象的所有引用都被追踪完毕后，它会变成黑色。
2、执行过程
2.1、初始标记 (Initial Marking)
描述：
将所有对象标记为白色，并将所有GC Roots（如类静态变量、活动线程栈中的局部变量等）直接引用的对象标记为灰色。
特点：这个阶段需要暂停所有的应用程序线程。
2.2、并发标记 (Concurrent Marking)
描述：从标记过的对象开始，递归地追踪其引用的对象，并将其标记。
特点：这个阶段不需要暂停应用程序线程，可以与应用程序并发执行。
标记过程：
从灰色对象开始，遍历其引用的对象，将它们也标记为灰色（如果它们还未被标记）。同时，将已经遍历过的灰色对象及其引用的所有对象都标记为黑色。
这个过程会递归进行，直到没有新的灰色对象被标记。
2.3、重新标记 (Remark)
描述：
由于并发标记过程中可能存在新的对象被创建或引用关系发生变化，因此需要再次检查并标记这些变化。这个过程可能需要STW，但时间通常较短。
特点：这个阶段需要暂停应用程序线程，以确保标记准确无误。
目的：确保垃圾回收完成后没有遗漏的垃圾对象。
2.4、垃圾清理阶段
清理所有白色对象，即那些未被引用的对象，释放它们占用的内存空间。
3、并发标记
在并发标记过程中，由于用户线程和垃圾回收线程同时运行，可能会产生以下问题：
3.1、浮动垃圾
在并发标记过程中，用户线程可能会创建新的对象或断开现有对象的引用，导致部分对象被错误地标记为存活（实际上是垃圾），这些对象被称为浮动垃圾。
浮动垃圾不会影响应用程序的正确性，但会占用内存，直到下一轮GC被清理。
如下图，A在之前扫描已经完成标记，并且标记为黑色，但是垃圾处理过程共，又取消了对A的对象引用。
类似于A这种称为浮动垃圾：
3.2、漏标
当灰色对象断开了对白色对象的引用，并且黑色对象重新引用了该白色对象时，可能会发生漏标。
漏标会导致本应存活的对象被错误地回收，影响应用程序的正确性。
为了解决漏标问题，JVM采用了读屏障和写屏障技术来记录引用关系的变化，并在并发标记结束后重新扫描这些变化，确保没有漏标对象。
在E标为灰色的时候，G还未扫描，但是E取消了对G的引用，此时D又引用了G，但是D已经标记为黑色，不会重新扫描。
这就会引发很严重的问题，G此时是有引用的，但是现在会当成垃圾被处理掉。
总结
三色标记算法是Java垃圾回收中的一种重要技术，通过将对象分为白色、灰色和黑色三种颜色来有效管理内存中的对象。
它支持并发垃圾回收，减少了垃圾回收过程中的停顿时间，提高了应用程序的性能和响应能力。
然而，在并发标记过程中仍然存在浮动垃圾和漏标等挑战，需要通过读屏障、写屏障等技术来解决。
参考文章：
1、谈谈对JVM的理解_谈谈你对jvm的理解-CSDN博客