垃圾回收机制的算法实现——增量式垃圾回收算法

一、 增量式垃圾回收

垃圾回收其实就是对不需要的内存对象进行清理，前面提到的GC算法，无论哪种，基本都是过一段时间对所有的内存空间对象进行一次大扫除。 这种的GC缺点是一旦开始启动，管理程序可能就停止了，表现就是可能好多程序都没响应。可在服务端，这是大忌。增量式（incremental）出现就是解决这个问题的，这种垃圾回收采用和应用程序交替进行的方式来工作，表现就像是GC在不断的定时迭加操作。从而尽量减轻应用程序的停止时间，这就是增量式回收的特点。
在增量式回收里，比较容易接触到的就是三色标记算法。

二、三色标记算法

三色标记算法，顾名思义，它有三种颜色：
白色：内存中未搜索的对象，初始默认都是白色
灰色：正在搜索的对象，ing正在GC
黑色：已经搜索完成的对象，也就是活动的对象
GC在启动时，默认所有的内存中的对象都是白色，然后GC开始搜索，把所有能从根抵达的内存的对象标记并推送到栈中，由于这些对象只是发现而未有真正搜索，所以它们是灰色的对象。然后GC会将其从栈中取出对其进行搜索，将其子对象涂成灰色，一直到所有子对象都搜索完成后，将其置成黑色（可以理解成一个不断搜索的过程，只要灰色对象所有的子对象都搜索完成，就设置成黑色对象，也就是说一灰色对象可能是一条链，然后链上的灰色对象一个个搜索完成了，又一个个置成黑色，比如最后一个子对象，灰色，它没有子对象，搜索完成，它也置成黑色）。

三、写入屏障和优缺点

三色标记法有一个细节需要说明，由于它是交替运行，就有可能出现在暂停GC时，内存对象发生了变化，造成一些问题的出现。看一个例子：

这种情况下，A在GC暂停前被涂成了黑色，其子对象B被涂成了灰色，然后暂停（左图）。程序开始执行，将引入状态更改为中间图的情况，即将A到B的引用，改成A到C的引用，然后删除B到C的引用。此时变为右图的情况，然后重新开始GC，A已经搜索完成不会再搜索其子对象，那么C被遗漏，而B因为没有了子对象，搜索就会被标记为黑色。结果遗漏的对象可能被误处理。
另外还有一个就是如果已经搜索过的黑色和灰色对象突然被抛弃为垃圾，GC无法处理，此时只有等到下一次GC再说了。所以可能会产生一些冗余垃圾。不过这可以理解，毕竟还是可以回收的。
那么如何解决这个遗漏的内存泄露问题呢？就是使用写入屏障。常见的写入屏障有三种：
1、Dijkstra
这种写入屏障，在将A到B的引用变更到A到C引用时，将C同时置成灰色对象并推入栈中，这样再次GC时仍然可以继续搜索。但是一旦C及其子对象真正成为垃圾，就无法回收。
2、Steele
Steele这种写入屏障更狠，直接在A到C时，将A和C同时变更为灰色对象，这样就可以继续对A和C进行搜索。但它的缺点就是写入的代价更大，对判断条件更严格。
3、汤浅算法
这个也叫快照算法，它和Dijkstra的算法不同在于，前者是在转移引用后就将C标记为灰色，而汤浅算法则是在删除B到C的引用时再将C变成灰色对象，然后推到栈中。它同样保留了不少的无用对象，造成内存白白的浪费。
从上面三个写入屏障可以看出，哪种解决方式，都是在某些方面的取舍和代价的平衡的结果。

优点：
非常明显是缩小了最大暂停时间，由于程序和GC的交替运行，这个是一定的结果。
缺点：
缺点就是，降低了吞吐量。所以它只适合那些对最大暂停时间敏感的GC应用场景，需要注意一下。

四、实际应用

如果对JVM比较熟悉，其中CMS和G1中都采用了三色标记，这个还是比较多的。对其的相关具体分析，待后面再详细分析源码再说。

五、总结

增量式垃圾回收其实是一个比较好的垃圾回收算法，为什么说它是一个比较好的算法呢？主要原因在于它其实是一个动态的算法，可以根据实际场景来动态修正交替的时间比。只要适合实际的应用就好。一如解决问题的动态和静态的方式一样，两者结合优势会更明显，在以后实际的应用的GC中大家可以看到，相关的算法大多还是融合分段使用。
我们既要技术创新，也要工程创新，只要是创新，我们都欢迎！