标记清除算法
标记清除算法
基本原理：从跟开始将可能被引用的对象用递归地方式进行标记，然后将没有标记到的对象作为垃圾进行回收。
标记是通过对象内部的标志（Flag）来实现，被标记的对象所能够引用的对象
也被打上标记（Mark Phase）。重复此步骤，可以将从跟开始可能被间接引用的对象全部打上标记。被标记的对象视为“存活”对象。
mark_phase () {
// 挨个遍历所有的 GC Roots
for (r: roots) {
mark(r)
}
}
mark (obj) {
if (obj.mark == FALSE) {
obj.mark = TRUE
// 遍历子节点
for (child: obj.children) {
mark(child)
}
}
}
将全部对象按顺序扫描一遍，将没有被标记的对象进行回收。这一操作被称为清除阶段（Sweep phase）。在扫描的同时，还需要将存活对象的标记清除掉，以便为下一次GC操作做好准备。标记清除算法的处理时间，是和存活对象数与对象总数的总和相关的。
sweep_phase () {
cursor = $heap_start; // $heap_start表示堆首地址
while (cursor < $head_end) {
if (cursor.mark == TRUE) {
cursor.mark = FALSE // 重置标记状态，准备下一次的 GC
} else {
// 将当前对象空间释放，连接到空闲链表头部
cursor.next = $free_list
$free_list = cursor
}
cursor += cursor.size // 跳过当前对象所占空间，指向下一个对象
}
}
优点：
不会给赋值器带来任何额外的读写开销；
具有较高的吞吐量；
具有较高的空间利用率（相比于复制算法和引用计数法）；
不用移动对象，可与保守式回收器兼容；
缺点：
长期运行的程序堆可能会逐渐碎片化；
分配速度受限，因为分块不连续，每次分配时都必须遍历空闲链表，找到足够大的块；
与C-o-W不兼容：标记-清除算法每次进行标记时都要对对象执行写入操作，从而触发写时复制，这样会导致频繁发生本不应该的发生的复制；
优化
多个空闲链表：按照分块的大小创建多个空闲链表，比如≤2,2< ≤4, 4< ≤8等等，从而节约查找时间。
Big Bag of Pages：把堆分割成固定大小的块，每一块的大小可以不同，但一个特定大小的块只能配置同样大小的对象。
位图标记法：将标志位与对象分离，可以实现与C-o-W兼容，而且重置标记为速度提升，效率更高。
延迟清除：在标记结束后，不一定立马进行清除操作，而是延迟到下一次为新对象分配空间时，将寻找可用空间加清除垃圾的任务放到分配空间的过程中。延迟清除采用一个全局变量来记录上一次清理后返回的分块结束的位置：
- 当要申请新空间时，先检当前这个对象的标志位，如果被标记了则检查下一个；
- 如果没被标记，则检查当前这个分块的大小够不够用，如果够用就直接返回分块并停止清除；
- 如果不够，就继续找下一个如果没找到，就申请空间失败
