GC algorithm design seems like more of an art than a science – constantly trading off various parameters based on the priority of expected usage models
垃圾回收算法有很悠久的历史。早在 20 世纪 60 年代，Lisp 就开始采用垃圾回收器来自动管理内存。但是出于现实复杂的度、效率的考虑以及程序员的执念，使得自动管理内存在当时并没有流行起来。直到 90 年代出现 java 大法。现在的大部分高级语言，如 Python、Object-C、Swift、C# 等都有相应的垃圾回收机制，只是在回收垃圾的实现上有差异。
垃圾回收算法最简单的是标记-清除算法（Mark-Sweep），很多的算法都是基于它的。本文还将介绍
- 标记-整理算法（Compacting Collecting）
- 交换复制算法（Semi-Space）
- 增量算法（Incremental Collecting）
- 分代算法（Generational Collecting）
介绍算法之前，我们先了解一下 GC-root
java 中对象之间的引用可以用一张有向图来标识。指向的是被引用的对象。
蓝色圆圈表示 object， 蓝色矩形表示 GC-Root
从 GC-Root 出发，可以被直接或间接引用的对象，被称作是可达的
而无法通过 GC-Root 被引用到的对象就是不可达的
可以被当作 GC-Root 的对象有：
- 虚拟机栈（栈帧中的本地变量表）中引用的对象。
- 方法区中类静态属性引用的对象。
- 方法区中常量引用的对象。
- 本地方法栈中JNI（即一般说的Native方法）引用的对象。
标记-清除
标记-清除算法有两个过程：一个是标记，一个是清除。
标记过程就是从 GC-Root 出发，遍历堆，标记出不可达对象。清除过程将被标记为不可达的对象清除。算法需要对堆做遍历，是非常耗时的。而且清除过程完成后，可能出现很多的碎片。当为大对象分配空间是，这些碎片将无法提供充足的空间，导致提前触发垃圾回收
mark_sweep_collect() =
mark(root)
sweep()
mark(o) =
If mark-bit(o)=0
mark-bit(o)=1
For p in references(o)
mark(p)
EndFor
EndIf
sweep() =
o = 0
While o < N
If mark-bit(o)=1
mark-bit(o)=0
Else
free(o)
EndIf
o = o + size(o)
EndWhile
标记-整理
标记-整理算法可以解决标记-清除碎片化的问题。标记过程和标记-清理算法是一样的。但是在清除阶段，标记-整理算法会在清除垃圾的同时，把剩下的对象整理到一起。整理出一块连续的空间来给新分配的对象使用
交换复制
交换复制算法把内存空间分为大小相等的两个部分。一个称为 from-space，一个称为 to-space，这两个名称不是固定对应一个空间的。起始状态，只有 from-space 存有对象，to-space 为空。新对象将分配在 to-space。算法执行：将存活的对象，从 from-space 移动到 to-space 。此时，from-space 对应的空间改名为 to-space ，to-space 改名为 from-space。这样一直都有一块连续的空间 to-space 用于分配新对象，解决了碎片问题。但是，吐过存活的对象过多，复制效率变低。因为将空间一分为二，所以空间使用率也降低。
initialize() =
tospace = 0
fromspace = N/2
allocPtr = tospace
allocate(n) =
If allocPtr + n > tospace + N/2
collect()
EndIf
If allocPtr + n > tospace + N/2
fail “insufficient memory”
EndIf
o = allocPtr
allocPtr = allocPtr + n
return o
collect() =
swap( fromspace, tospace )
allocPtr = tospace
root = copy(root)
copy(o) =
If o has no forwarding address
o’ = allocPtr
allocPtr = allocPtr + size(o)
copy the contents of o to o’
forwarding-address(o) = o’
ForEach reference r from o’
r = copy(r)
EndForEach
EndIf
return forwarding-address(o)
增量算法
增量算法的提出主要是为了减少一次执行垃圾回收的时间，提高程序的响应度。前一篇文章提到过，java 执行垃圾回收会停止所用应用线程，只留下 gc 执行垃圾回收。如果碰巧这时你在写一篇博客，那么你的输入和修改将在这段时间内被停止响应。这段时间越长，用户体验就越差。增量算法，每次为新对象分配空间时都会执行一次小规模的垃圾回收。把垃圾回收分摊到每次分配空间，减少了用户等待时间。
分代收集
浅析 java 垃圾回收（一）中介绍了 HotSpot 的垃圾回收机制就是分代收集。根据对象存活周期的不同将内存划分为几块。一般是把Java堆分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用“标记—清理”或者“标记—整理”算法来进行回收。
来对比一下上面几种算法
绿色代表读操作，黄色代表写操作，黑色代表空闲
再来说一说，引用计数
引用计数简单来说就是，每个对象都有一个记录被引用次数的计数器。当对象被引用时，它引用计数器就加 1。当引用计数器为 0 时，对象就会被回收
引用计数算法虽然简单，但是存在循环引用问题
看以下代码
public class ReferenceCountingGC{
public Object instance=null；
private static final int_1MB=1024*1024；
/**
*这个成员属性的唯一意义就是占点内存，以便能在GC日志中看清楚是否被回收过
*/
private byte[]bigSize=new byte[2*_1MB]；
public static void testGC（）{
ReferenceCountingGC objA=new ReferenceCountingGC（）; //counter_A = 1
ReferenceCountingGC objB=new ReferenceCountingGC（）; //counter_B = 1
objA.instance=objB; //counter_A = 2
objB.instance=objA; //counter_B = 2
objA=null; //counter_A = 1
objB=null; //counter_B = 1
System.gc（）;
}
}
观察上面代码，会发现 objA 和 objB 句柄被设置为 null 时，对象 A 和 B 之间仍有互相引用，且计数值都为 1。尽管现在已经无法访问到对象 A 和 B ，但是因为计数值不为 0 ，所以它们不会被回收。
HotSpot 中不使用引用计数器算法，所以不会出现这个问题。上述代码，只要离开了方法 testGC( ) ，对象 A 和 B 就无法通过 GC-Root 的引用链被访问，所以他们会被回收。
参考
[1] Garbage Collection Algorithms
