图解GC（垃圾回收）三种增量式垃圾回收

   通常的GC算法很繁重，一旦GC开始执行，我们原本该进行的程序就被迫停止。也就是说，繁重的GC原本是辅助程序变成了主程序，而本该执行的主程序变成了辅程序。这就是臭名昭著的停止型GC，英文名称很酷叫：Stop the world GC。针对繁重的GC算法，人们提出增量式垃圾回收算法。增量：incremental，意味着慢慢变化，也就是说增量式垃圾回收算法是慢慢回收，一点一点与主程序交替执行而不是直接霸占主程序的运行时间。

三色标记算法

三色标记算法由图灵奖得主Dijkstra等人提出。三种颜色所包含的意思如下：

白色：未搜索过的对象

灰色：正在搜索的对象

黑色：搜索完成的对象

我们以标记-清除算法为例说明。GC初始所有对象都标记为白色，GC一开始由根开始遍历搜索对象，GC发现对象但还没搜索的标记为灰色，灰色对象依次从栈取出并且子对象也标记为灰色，当其所有子对象标记灰色时，他自己就标记为黑色。这里，标记为黑色的对象则表示搜索完毕，GC这一轮就不再对其搜索。GC结束时就不存在灰色对象，黑色为活动对象，白色为垃圾。这里三色的概念不仅用于标记-清除算法，也可以用于其它算法。但是这种简单处理的三色标记算法会有BUG，我们以下图为例：

当GC执行到图1的时候，这是候GC时间片结束，系统执行主程序，将图1的对象引用且换到图3的状态，此刻接着执行GC。由于A已被标记为黑色则不在对A的子对象搜索，灰色B对C的指向被取消此时B子对象搜素完毕也将标志黑色，而C本是被A指向由于没被GC发现则被当作垃圾清理。为了解决这种BUG在这里解决问题的关键也在于运用写入屏障。，一下将介绍3为科学家提出的3中解决方案。

Dijkstra

Dijkstra提出在GC切换为主程序后如果新引用的对象newobj没有被标记，那么就将其标记后堆在标记栈里。也就是说，如果Newobj是白色的，那么被新引入后则标记为灰色。

结果如上图所示。这样在下一次启动GC的时候由于C是灰色也就是未完成搜索的对象，则GC就不会将C视为垃圾处理，但是这里A已经是黑色对象，所以GC也不会对C进行搜索。接下来标记-清除-分配的流程和典型的标记-分配算法没什么两样，需要注意的是停止型GC是在分块完全枯竭后才启动的，然后增量式垃圾回收是逐步推荐GC的。

缺点：这个算法中即使C之后变成了垃圾，结果垃圾对象C以及C引用的其他垃圾都会被遗留下来。

Steele

steele算法中的写入屏障要比Dijkstra严格，但是他能减少错误标记的对象。steele算法在标记过程中发出引用的对象是黑色对象，且新引用的目标对象为灰色或白色，那么我们就把发出引用的对象涂为白色。

这个算法相比于Dijkstra，由于A被重新标记为灰色，那么下次启动的GC就会从根开始从A向C进行搜索，这样就弥补了Dijkstra算法的不足之处。

汤浅太一

汤浅提出的写入屏障的算法也称为“快照GC”。因为这种算法是以GC开始时对象间的引用关系为基础来执行GC的。根据汤浅的算法，在GC开始时回收垃圾，保留GC开始时的活动对象和GC执行过程中的分配对象。

汤浅的算法结果和Dijkstra结果一样，但是在第二步中过程却和Dijkstra不一样。Dijkstra在图一到图二将C标记为灰色，而汤浅的算法在图2到图3标记为灰色。而这样的顺序就能巧妙的避免标记遗漏的问题。汤浅的算法虽然简单也保留了很多对象，但是最后事实上却无意保留了很多无用的对象。