✅什么是三色标记算法？

典型回答

三色标记算法是一种JVM中垃圾标记的算法，他可以减少JVM在GC过程中的STW时长，他是CMS、G1等垃圾收集器中主要使用的标记算法。

在出现三色标记算法之前，JVM中垃圾对象的标记主要采用可达性分析算法及引用计数法。但是这两种算法存在以下问题：

1、循环引用问题，如果两个对象互相引用，就形成了一个环形结构，如果采用引用计数法的话，那么这两个对象将永远无法被回收。

2、STW时间长，可达性分析的整个过程都需要STW，以避免对象的状态发生改变，这就导致GC停顿时长很长，大大影响应用的整体性能。

为了解决上面这些问题，就引入了三色标记法。

三色标记法将对象分为三种状态：白色、灰色和黑色。

白色：该对象没有被标记过。

灰色：该对象已经被标记过了，但该对象的引用对象还没标记完。

黑色：该对象已经被标记过了，并且他的全部引用对象也都标记完了。

三色标记法的标记过程可以分为三个阶段：初始标记（Initial Marking）、并发标记（Concurrent Marking）和重新标记（Remark）。

初始标记：遍历所有的根对象，将根对象和直接引用的对象标记为灰色。在这个阶段中，垃圾回收器只会扫描被直接或者间接引用的对象，而不会扫描整个堆。因此，初始标记阶段的时间比较短。（Stop The World）
并发标记：在这个过程中，垃圾回收器会从灰色对象开始遍历整个对象图，将被引用的对象标记为灰色，并将已经遍历过的对象标记为黑色。并发标记过程中，应用程序线程可能会修改对象图，因此垃圾回收器需要使用写屏障（Write Barrier）技术来保证并发标记的正确性。（不需要STW）
重新标记：重新标记的主要作用是标记在并发标记阶段中被修改的对象以及未被遍历到的对象。这个过程中，垃圾回收器会从灰色对象重新开始遍历对象图，将被引用的对象标记为灰色，并将已经遍历过的对象标记为黑色。（Stop The World）

在重新标记阶段结束之后，垃圾回收器会执行清除操作，将未被标记为可达对象的对象进行回收，从而释放内存空间。这个过程中，垃圾回收器会将所有未被标记的对象标记为白色（White）。

以上三个标记阶段中，初始标记和重新标记是需要STW的，而并发标记是不需要STW的。其中最耗时的其实就是并发标记的这个阶段，因为这个阶段需要遍历整个对象树，而三色标记把这个阶段做到了和应用线程并发执行，大大降低了GC的停顿时长。

扩展知识

并发标记的写屏障

并发标记过程中，应用程序线程可能会修改对象图，因此垃圾回收器需要使用写屏障（Write Barrier）技术来保证并发标记的正确性。

写屏障是一种在对象引用被修改时，将其新的引用信息记录在特殊数据结构中的机制。在三色标记法中，写屏障技术被用于记录对象的标记状态，并且只对未被标记过的对象进行标记。

当应用程序线程修改了一个对象的引用时，写屏障会记录该对象的新标记状态。如果该对象未被标记过，那么它会被标记为灰色，以便在垃圾回收器的下一次遍历中进行标记。如果该对象已经被标记为可达对象，那么写屏障不会对该对象进行任何操作。

通过使用写屏障技术，可以使得三色标记法过程中标记更加准确。然而，尽管写屏障对于维护垃圾收集器的准确性至关重要，它们仍然存在一些局限性。

性能开销：写屏障会引入额外的性能开销，因为每次对象引用更新时都需要执行额外的代码。这种开销可能导致系统性能下降，尤其是在高度并发的场景中。
并发修改的挑战：在高度并发的应用中，对象的引用可能会频繁变化。写屏障需要在每次引用变化时及时更新信息，但在极端并发条件下，可能难以捕捉到所有的变化。
保守策略导致的多标：为了避免误删除有效对象，一些垃圾收集器可能采取保守策略，在存在不确定性时选择保留对象。这可能导致实际上已经不再使用的对象被错误地标记为存活。
优化策略的双刃剑：为了减轻性能开销，某些垃圾收集器可能采用优化策略，例如只在特定条件下激活写屏障。这种优化有可能导致某些引用更新被错过，影响标记的准确性。

所以，三色标记法即使在并发标记过程中用了写屏障，还是可能会带来多标和少标的问题。

多标的问题

所谓多标，其实就是这个对象原本应该被回收掉的白色对象，但是被错误的标记成了黑色的存活对象。从而导致这个对象没有被GC回收掉。

这个一般发生在并发标记过程中，该对象还是有引用的，但是在过程中，应用程序执行过程中把他的引用关系删除了，导致他变成了一个垃圾对象。

多标的话，会产生浮动垃圾，这个问题一般都不太需要解决，因为这种垃圾一般都不会太多，另外在下一次GC的时候也都能被回收掉。

怎么解决漏标的问题

所谓漏标，和多标刚好相反，就是说一个对象本来应该是黑色存活对象，但是没有被正确的标记上，导致被错误的垃圾回收掉了。

这种情况一旦发生是很危险的，一个正常使用的对象被垃圾回收掉了，这对系统来说是灾难性的问题，那么如何解决呢？

具体的解决方式，在CMS和G1中也不太一样。CMS采用的是增量更新方案，G1则采用的是原始快照的方案。

漏标的问题想要发生，需要同时满足两个充要条件：

1、至少有一个黑色对象在自己被标记之后指向了这个白色对象

2、所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用

那么，增量更新方案就是破坏了第一个条件，而原始快照方案就是破坏了第二个条件。

增量更新

“至少有一个黑色对象在自己被标记之后指向了这个白色对象”，这个条件如果被破坏了，那么就不会出现漏标的问题。所以：

如果有黑色对象在自己标记后，又重新指向了白色对象。那么我就把这个黑色对象的引用记录下来，在后续「重新标记」阶段再以这个黑色对象为根，对其引用进行重新扫描。通过这种方式，被黑色对象引用的白色对象就会变成灰色，从而变为存活状态。

举个例子：在清理房间时，你已经检查了某个抽屉（对象）并决定里面的东西都是需要的（标记为黑色）。但是，在你继续清理其他地方时，家人回来并在这个抽屉里放了一些新的东西。增量更新就像是他们给你留了一个便条，提醒你“这个抽屉有变化，请重新检查”，确保你不会错过任何东西。

这种方式有个缺点，就是会重新扫描新增的这部分黑色对象，会浪费多一些时间。但是其实这个浪费还好，因为本来这种漏标的情况就并不是特别常见，所以这部分需要重新扫描的黑色对象也并不多。

增量更新就是实时记录变化，确保每一次变化都会被重新检查，避免漏掉任何可能被错误视为垃圾的活跃对象。

原始快照

"所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用"，这个条件如果被破坏了，那么就不会出现漏标的问题。所以：

如果灰色对象在扫描完成前删除了对白色对象的引用，那么我们就在灰色对象取消引用之前，先将灰色对象引用的白色对象记录下来。

在后续「重新标记」阶段再以这些白色对象为根，对它的引用进行扫描，从而避免了漏标的问题。通过这种方式，原本漏标的对象就会被重新扫描变成灰色，从而变为存活状态。

使用原始快照的方式，就像是在你开始清理房间时拍了一张照片，记录下所有需要保留的物品（即那一刻认为的“活跃”对象）。然后无论家人后来如何在房间内移动或添加物品，你的任务只需要根据照片上的记录来完成。即使物品的位置和数量发生了变化，它不会影响你这次清理的判断依据。

但是这种方式可能会把本来真的要取消引用的对象给错误的复活了，从而产生浮动垃圾。但是就像前面说的，多标的问题是可以忽略的。

原始快照就是基于GC开始时的状态做决策，忽略之后的变化，确保GC的稳定性和一致性，但可能需要更多的内存来记录快照信息。

原文: https://www.yuque.com/hollis666/xkm7k3/lva8a9gfhagbrw2g