并发标记与三色标记

三色标记

在三色标记法之前有一个算法叫 Mark-And-Sweep（标记清除）。这个算法会设置一个标志位来记录对象是否被使用。最开始所有的标记位都是 0，如果发现对象是可达的就会置为 1，一步步下去就会呈现一个类似树状的结果。等标记的步骤完成后，会将未被标记的对象统一清理，再次把所有的标记位设置成 0 方便下次清理。

这个算法最大的问题是GC执行期间需要把整个程序完全暂停，不能异步进行GC操作。因为在不同阶段标记清扫法的标志位 0 和 1 有不同的含义，那么新增的对象无论标记为什么都有可能意外删除这个对象。对实时性要求高的系统来说，这种需要长时间挂起的标记清扫法是不可接受的。所以就需要一个算法来解决GC运行时程序长时间挂起的问题，那就三色标记法。

三色标记最大的好处是可以异步执行，从而可以以中断时间极少的代价或者完全没有中断来进行整个GC。
三色标记法很简单。首先将对象用三种颜色表示，分别是白色、灰色和黑色。

• 黑色：根对象，或者该对象与它的子对象都被扫描过。
• 灰色：对本身被扫描，但是还没扫描完该对象的子对象。
• 白色：未被扫描对象，如果扫描完所有对象之后，最终为白色的为不可达对象，既垃圾对象。

三色标记的问题

GC 并发情况下的漏标问题

CMS 中的解决方案

Incremental Update 算法
当一个白色对象被一个黑色对象引用，将黑色对象重新标记为灰色，让垃圾回收器重新扫描

G1中的解决方案

SATB（snapshot-at-the-beginning）

刚开始做一个快照，当B和C消失的时候要把这个引用推到GC的堆栈，保证C还能被GC扫描到，最重要的是要把这个引用推到GC的堆栈，是灰色对象指向白色的引用，如果一旦某一个引用消失掉了，我会把它放大栈（GC方法运行时数据也是来自栈中），我其实还是能找到它的，我下回直接扫描他就行了，那样白色就不会漏标。对应G1的垃圾回收过程中的：

最终标记（Final Marking）

对用户线程做另一个短暂的暂停，用于处理并发阶段结束后仍遗留下来的最后那少量的SATB记录（漏标对象）。

对比

• SATB 算法是关注引用的删除。（B->C 的引用）
• Incremental Update 算法关注引用的增加。（A->C 的引用）
• G1 如果使用 Incremental Update 算法，因为变成灰色的成员还要重新扫，重新再来一遍，效率太低了。
• 所以 G1 在处理并发标记的过程比 CMS 效率要高，这个主要是解决漏标的算法决定的。

G1中的技术细节

跨带引用

堆空间通常被划分为新生代和老年代。由于新生代的垃圾收集通常很频繁，如果老年代对象引用了新生代的对象，那么回收新生代的话，需要跟踪从老年代到新生代的所有引用，所以要避免每次 YGC 时扫描整个老年代，减少开销。

RSet（记忆集）

• 记录了其他 Region 中的对象到本 Region 的引用,
• RSet 的价值在于使得垃圾收集器不需要扫描整个堆,找到谁引用了当前分区中的对象，只需要扫描 RSet 即可。
• RSet 本身就是一个 Hash 表，如果是在 G1 的话，则是在一个 Region 区里面。

安全点与安全区域

安全点的设置其实就是为了垃圾回收器开始工作的时候，让业务代码去最近的安全点挂起（不是强制性的中断，而是业务线程主动式的中断），这样才能方便回收。

一般在下列情况设置安全点：

方法调用、循环跳转、异常跳转等，一般是这些指令(地方)才会产生安全点主动式中断。