2.3.2　标记清除算法

复制算法的空间利用率有限，但效率较高，并且GC执行过程包含了压缩，所以不存在内存碎片化问题。另外一种GC算法是标记清除，对于内存的管理可以使用链表的方式，当应用需要内存时从链表中获得一块空闲空间并使用，当GC执行时首先遍历整个空间中所有的活跃对象，然后再次遍历内存空间，将空间中所有非活跃对象释放并加入空闲链表中。以图2-4的内存状态为例，标记清除算法执行结束后的示意图如图2-8所示。

图2-8　标记清除算法执行结束后的内存示意图

标记清除算法的内存使用率相对来说较高，但是还有一些具体情况需要进一步分析。由于标记清除算法使用链表的方式分配内存，因此需要考虑分配的效率及内存分配时内存碎片化的情况。具体来说，空间链表中存放尚未使用或者已经释放的内存块，这些内存块的大小并不相同。从空闲链表中请求内存块时，需要遍历链表找到一个内存块。另外，由于链表中内存块大小不相同，因此可能没有和请求大小一样的内存块，此时需要找到一个比请求内存大的内存块才能满足应用的需要，这就需要额外的控制策略，是找到一个和请求内存尽可能接近（best-fit）的内存块，还是找一个最大（worst-fit）的内存块，或者是第一个满足需求（first-fit）的内存块？不同策略导致分配时的碎片化情况有所不同。

除了考虑分配效率和分配时内存碎片化的情况，还需要考虑回收的情况。特别是回收时空闲内存的合并，是否允许相邻的空间内存块合并？合并需要花费额外的时间，同时也会影响内存的碎片化。

在JVM中并发标记清除采用了该算法，为提高分配效率使用了多条链表及树形链表，分配策略使用best-fit方法，回收时提供了5种策略并辅以预测模型控制空闲内存块的合并。更多细节参考第4章。