背景

相比之前的标记清除算法，其GC执行期间需要把整个程序完全暂停，不能异步执行GC操作。对实时性要求比较高的系统来说，这种需要长时间挂起的标记清除算法是不可接受的，而三色标记算法就很好的解决了这个问题。

三色标记最大的好处是可以异步执行，从而可以以中断时间极少的代价或者完全没有中断操作来进行整个GC。

定义

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

漏标问题

image.png

什么时候，会产生对象消失的问题，即原本应该是黑色的对象被误标为白色？

当且仅当以下两个条件同时满足：
赋值器插入了一条或多条从黑色对象到白色对象的新引用；
赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。

解决

只需要破坏这两个条件任意一个即可，两种解决方案：
增量更新（Increamental Update）和原始快照（Snap shot At The Begining, SATB）

增量更新

CMS 基于 增量更新（Increamental Update）来做并发标记

增量更新（Increamental Update）：当黑色指向白色的引用被建立时，就利用写屏障将这个新的引用关系记录下来，等扫描结束后，再以这些记录中的黑色对象为根，重新扫描一次。相当于黑色对象一旦建立了指向白色对象的引用，就会变为灰色对象。

不会产生浮动垃圾，但是重新扫描灰色对象的效率较低

原始快照

G1 基于 原始快照（Snap shot At The Begining, SATB）来实现的

原始快照（Snap shot At The Begining, SATB）：原始快照要破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的白色对象作为灰色对象，重新扫描一次

会产生浮动垃圾，但是无需扫描整个引用链效率较高

对比增量更新和原始快照

原始快照关注的是引用删除，增量更新关注的是引用增加。

为啥G1不使用增量更新算法

因为使用增量更新算法，那变成灰色的对象还要重新扫描一遍，效率太低了，所以G1在处理并发标记的过程比CMS效率要高，这个主要是解决漏标的算法决定的。