GC 的世界中有三种基本的算法，分别是：

标记清除
引用计数
GC 复制

其他的 GC 算法都是在这三种算法上进行修改，优化得来。本文将要介绍的是标记-清除算法。

标记清除算法介绍

像字面意思一样，标记-清除算法分为两步：标记和清除。其中标记和清除使用伪代码分别可以写出来如下：

标记

mark_phase() {
    for (r: $roots)
       mark(*r)
}
mark(obj){
    if(obj.mark == FALSE)
        obj.mark == TRUE
        for(child: children(obj))
            mark(*child)
}

清除

sweep_phase() {
    sweeping = $head_start    //从堆头开始清除
    while (sweeping < $head_end)
        if (sweeping.mark == TRUE) //如果当前对象是活跃对象
            sweeping.mark = FALSE
        else  //如果当前对象是可清除对象，则将其加入到 free_list 中
            sweeping.next = $free_list   
            $free_list = sweep
        sweeping += sweeping.size
}

对于标记清除算法，最基本的，将某个对象是否已经被标记，以及对象的大小等等这些信息都保存在头部，从上面的代码中，我们可以知道头部至少有三个域：标记位(名为 mark)、对象大小（名为 size）以及下一个对象的头部地址（名为 next）– 有 size 和 next 两个域，是因为下一个对象不一定在物理上是连续的。如下图所示

其中淡蓝色的表示还在使用的空间，白色的表示空闲空间。

标记算法的选取

在标记部分，我们从 root 节点触发，然后逐一标记哪个节点不再使用，哪些节点还需要在继续存活。在上述代码中，我们给出的是 DFS 搜素算法，那么对于这一块我们可以比较 DFS 和 BFS 的区别，大致可以用下图表示：

主要区别在于：DFS 需要保存的内存使用量更低

分配内存

所有的标记、清除等都是为了分配内存服务的，如果我们不需要再分配内存的话，那么就可以不进行前面哪些活动了。下面说说如何分配内存的：

new_obj(size) {
    chunk = pickup_chunk(size, $free_list) // 从上面的空闲列表中找一个合适的内存块
    if (chunk != NULL)
        return chunk
    else
        allocation_fail() //内存不够
}

上面的代码表示整个分配内存的过程，其中 pickup_chunk 表示从空闲列表中找出一个合适的内存块，返回给申请者。

对于找出一个合适的内存块，我们已知的至少有三种方法：

First-fit 返回最先找到的一个内存块
Best-fit 找到一个大于需要内存的最小内存块
Worst-fit 找到一个大于需要内存的最大内存块

上面三种每一种都有不同的应用场景，也各有优劣。

合并

对于清除阶段，我们会遍历堆中所有的内存区域，将不需要的加入到 free_list 中，对于连续出现的两个内存块，我们并没有进行任何操作，那么下一次我们申请内存的时候，可能会由于没有足够大的内存块而失败。比如我们有两个大小分别为 3，4 的内存块，然后，我们需要申请一个内存大小为 5 的内存块，在之前的算法中是会失败的。这就牵涉到清除阶段的合并了，将连续的内存块进行合并形成大的内存块。上面的清除阶段算法改成如下所示

sweep_phase() {
    sweeping = $head_start    //从堆头开始清除
    while (sweeping < $head_end)
        if (sweeping.mark == TRUE) //如果当前对象是活跃对象
            sweeping.mark = FALSE
        else  //如果当前对象是可清除对象，则将其加入到 free_list 中
            if(sweeping == $free_list + $free_list.size) //邻接块的合并
                $free_list.size + sweeping.size
            else
                sweeping.next = $free_list
                $free_list = sweep
        sweeping += sweeping.size
}

优缺点

基本算法基本描述完成，接下来可以看看这种算法的优缺点分别是什么，以及是否有办法进行优化

优点：

实现简单。算法简单，能够明显知道是否有问题，而且更容易和其他算法进行结合
与保守式 GC 算法兼容。在保守式 GC 算法中，对象是不能被移动的，刚好 GC 标记-清除算法不需要移动对象。

缺点：

碎片化。在标记-清除的过程中，会不断的产生碎片，虽然在清除阶段有合并过程，但还是不够。
分配速度。由于在标记-清除算法中分块不是连续的，因此每次分配都需要遍历空闲列表，找到足够大的分块，最坏的情况需要每次都遍历整个空闲列表。
与写时复制技术不兼容。标记-清除算法中的标记阶段，会修改对象的头部，因此和写时复制技术不兼容，可能导致很多不必要的复制。

改进

既然我们了解到了该算法的优缺点，那么在此基础上如何进行改进呢？

针对上面的缺点分别有如下几点改进

多个空闲链表

简单的说，就是将原来一个空闲链表变成现在的多个空闲链表，加快分配的速度。
我们之前分配内存的时候，需要查询整个空闲链表来寻找一个合适的内存块，现在我们将不同大小的内存块挂在不同的链表下面，这样我们就能够直接去合适的链表中查找了。如下图所示

我们有用于 2 个字的空闲链表，有用于 3 个字的空闲链表。这样当需要分配 3 个字的空间时，我们直接去对应的链表查找即可。

这里有一个注意的点，需要保持多少个链表呢？一般来说，根据经验，一般会将小于某个阈值的分别生成一个链表，大于该阈值的所有内存块放到一个链表中。比如所有小于 100 字的都有一个单独的链表，而所有大于等于 100 字的内存块都挂在 100 字这个链表下。

BiBOP 法

另外一种优化方法，就是将大小相近的内存块放到一起，如下图所示

这样的形式，我们也知道去哪个地方查找需要的内存块，但是这个方法有一点不好，就是会形成很多内存碎片，比如我们分配的很多大小为 2 个字的空间，但是所有的申请中最小的都是 3 个字，这个时候这些 2 个字的空间都是浪费的

位图标记

位图标记法主要改善的是“和 copy-on-write 技术不兼容”，将标记位从头部抽离出来了。如下图所示

这样标记的时候就不会修改头部位置了。伪代码大致如下：

mark(obj) {
    obj_num = (obj - $heap_start) / WORD_LENGTH
    index = obj_num / WORD_LENGTH
    offset = obj_num % WORD_LENGTH
    
    if (($bitmap_tbl[index] & (1 << offset)) == 0) // 未被标记
        $bitmap_tbl[index] |= (1 << offset)
        for (child: children(obj))
            mark(*child)
}

在参考条目[1] 中有描述这个算法的第二个优势：清除操作更高效。描述如下：以往的清除操作都必须遍历整个堆，把非活动对象连接到空闲链表，同时取消活动对象的标志位。

我的理解现在还是需要遍历整个堆，而且需要取消标志位，只是现在标志位变成了连续的，这样处理起来会高效一点。

另外，如果有多个堆的情况下，就需要多个 bitmap 了

延迟清除法

在清除操作中，我们需要遍历整个堆，也就是处理时间和堆的大小成正比。在清除阶段，内存空间不能访问，这就牵涉到最大暂停时间。而延迟清除法（lazy sweep）则可以缩短清除操作导致的最大暂停时间。

new_obj(size) {
    chunk = lazy_sweep(size) //先通过延迟清除法，查找是否以满足条件的内存块
    if (chunk != NULL)
        return chunk
    mark_phase() //标记阶段
    
    chunk = lazy_sweep(size) //再次通过延迟清除法，寻找一个满足条件的内存块
    if (chunk != NULL)
        return chunk
    
    allocation_fail()
}

至于 lazy_sweep 函数如下所示：

lazy_sweep(size) {
    while($sweeping < $headp_end)
        if ($sweeping.mark == TRUE) //TRUE 表示活动对象
            $sweeping.mark = FALSE
        else if ($sweeping.size >= size)
            chunk = $sweeping
            $sweeping += $sweeping.size
            return chunk
        $sweeping += $sweeping.size
    $sweeping = $head_start
    return NULL
}

注意，其中的 sweeping 时候全局变量，因此遍历的起始位置是上次结束的地方。

延迟清除法有一个缺点就是。如果空闲内存块和活动对象块基本分成两个大的部分的话（如下图所示），那么对于某次清除活动对象周围的空间时，就会增加暂停时间。

上图中淡蓝色的表示活动对象，白色的表示空闲对象，当清除到活动对象附近的时候，就会增加本次的最大暂停时间。

参考

《垃圾回收的算法与实现》第二章

Enjoy it ? Donate me ! 欣赏此文？支持一下呗

GC 标记-清除算法