标记-清除算法
标记清除算法是一个经典的算法，思路也比较直接和简单。
需要一个全局变量 free_list , 是一个链表，用来存储空闲的块
申请空间
在空闲列表中遍历，如果找到”合适”的，就把这一节摘下来，然后裁剪成 size 的大小，返回，然后将剩下的边角料给放回到列表里。
如果没有合适的，就执行垃圾回收，然后再次尝试在空闲列表中寻找。找到了就返回，没找到就报错。
关于“合适” 也有一些讲究。有三种常用的方法：
- 最先匹配： 从头遍历链表，第一个大于等于 size 的节点用来分配。
- 最优匹配：从头遍历链表，分配大于等于 size 节点中的空间最小的节点，也就是让剩余的空间尽可能小。
- 最差匹配： 每次都找最大的分配。
第一种方案是比较常用的。最优匹配可能会造成很多无法利用的小碎片，最差匹配可能面对大的对象时无力分配。
垃圾回收
- 从根出发，dfs 找到所有能够直接或间接引用到的对象，然后标记其为 True
- 遍历堆中的对象，如果标记为 True，就置为 Flase，然后跳到下一个对象。如果标记为 False, 那么就把它串到空闲列表上。
在第二步的时候有个有趣的优化，就是如果我们发现当前回收的对象是和它左边的对象的地址是连续的，那么我们直接把它和左边的对象合并成一个对象就可以了，这样就可以减少链表的长度。
从定义出发，如果根无法直接或间接引用的对象，就是垃圾。
优点
实现简单。而且可以兼容保守式 gc（因为这种方法不会移动对象的位置，对象申请时候在哪就在哪）
缺点
首先是效率低，每次垃圾清扫都要遍历堆中所有对象。分配对象时候的时间复杂度也取决于链表的长度。
然后是这种方法可能会形成很多碎片，也就是在一个个活动对象之间存在着很小的空间，就难以利用。
最后是和写时复制不兼容。因为要改动对象的头。比如子进程刚刚创建，和父进程共享所有的对象，只要不发生写入，那么对象就不会复制。然后执行标记的时候，就会把所有的活动对象都会影响到，会触发 linux 的复制机制，导致了性能的降低。
优化
这本书中讲了许多针对标记清除算法的优化。
多链表搜索
算法的瓶颈之一是链表搜索效率低。如果我们设定一个上限 limit，针对长度在 [2, limit] 区间内的长度分别设置一个链表，然后将所有大于 limit 的分块放在一个单独的链表中。这样就提高了搜索效率。
似乎 c++里面的 STL 的分配器也采用了相似的思路。通过一个内存池和若干空闲链表来分配内存，每次空闲链表为空的时候就去内存池申请，申请多个空间（比如要 2 个空间，就申请 20 个空间），将多余的部分放在链表中，就不必每次都问内存池了。然后当内存池不足的时候就进行 malloc，如果 malloc 也失败，就尝试把其他链表给回收了，然后凑出内存。
BiBop
BiBop 是 Big Bag Of Pages 的缩写。表示将内存中分成若干个块，每个块内我们让其只存储特定字长的对象。比如第 1 块只存长度为 3 的对象，第 2 块只存长度为 4 的对象。这样块内其实就没有碎片了，但是由于块是预先划分的，所以可能导致了别的块内存不足而某些块的内存闲置了。我们会在之后再次见到这个算法。
位图标记
这个优化主要是针对前文提到的对写时复制不兼容的问题。
我们发现之前的不兼容是因为标记在了对象的本身上（其实标记成 0 还是 1 无所谓，主要是这个标记活动对象的动作导致了无谓的复制）。
我们尝试将标记不要打在对象本身，而是单独拿一个位图，也就是一个位数组，来存储这个标记。比如我们把位图放在最后，然后将前面全部的字都按顺序映射到位图中的一个位。显然一个对象可能对应多个连续的位。
在 dfs 的时候遍历指针得到对象，这一步和之前一样。但是在打标记的时候就打到对应的位上，也就是打到一个对象的首地址对应的位上，这样就不会触发复制。
在遍历堆来寻找不活动对象的时候，就直接遍历位图，没有标记的就是垃圾。考虑到缓存，遍历位图和清空位图上的位可以达到很高的效率。
在多个堆的时候要给每一个堆都设置一个位图。
延迟清除法
由于每次垃圾回收所需要的计算都很大，实际上我们只需要找到一个合适的空间就能进行下去，没必要一次就把所有的空闲空间都找到。
所以我们在遍历堆的时候，找到一个合适的空间就直接停止，返回这个空间，下次不够了先别标记，先继续上次的位置找，找到了就返回，找到头了还没有就标记，然后从头开始再扫，这次要是还没找到就报错。
但是实际上这个未必能提升速度，比如上次暂停的位置正好是垃圾堆的最后，再次遍历的时候就要遍历很多活动对象，然后找不到，再次标记，然后才能知道。所以就耗费了大量的时间，未必有直接找快。
