标记-清除算法

定义

标记-清除算法由标记和清除两阶段构成，标记阶段是把所有活动对象做上标记，清除阶段是清除未被标记的对象。

标记阶段

使用深度优先搜索算法遍历所有对象逐个标记（深度优先搜索比广度优先搜索更能降低内存使用量）

标记阶段伪代码

// 主方法
mark_sweep {
    // 标记阶段
    mark_phase();
    // 清除阶段
    sweep_phase();
}

// 标记阶段方法
mark_phase() {
    // 遍历并标记所有根及其子节点
    for (r : $root) {
        mark(*r);
    }
}

// 标记方法
mark(obj) {
    // 防止重复标记
    if (obj.mark == FALSE) {
         // 标记活动对象
        obj.mark = TRUE;
        // 遍历并标记所有子节点
        for (child : children(obj)) {
            mark(*child);
        }
    }
}

执行GC前堆的状态

设置标志位处理

标记阶段执行结束后

清除阶段

遍历整个堆，回收未被标记的对象

清除阶段伪代码

// $head_start 堆起始地址
// $head_end 堆结束地址
// $free_list 空链表起始地址
sweep_phase() {
    // 设置堆起始位置
    sweeping = $heap_start;
    // 遍历堆，清除未被标记对象
    while (sweeping < $head_end) {
        // 活动对象，本次GC跳过，重置标记位，进入下一次GC
        if (sweeping.mark == TRUE) {
            sweeping.mark = FALSE;
        } else {
            // 回收对象，作为分块添加到空闲链表
            sweeping.next = $free_list;
            $free_list = sweeping;
        }
        // 继续循环
        sweeping += sweeping.size;
     }
}

清除阶段结束后堆状态

分配

将回收的内存再次利用

分配伪代码

new_obj(size) {
    // 遍历 $free_list，寻找大于等于 size 的分块
    chunk = pickup_chunk(size,$free_size);
    if (chunk != NULL) {
        return chunk;
    } else {
        // 分配失败处理机制（输出错误日志，或扩大堆空间）
        allocation_fail();
    }
}

分配策略

First -fit、Best -fit、Worst -fit 的不同
first-fit：返回最开始发现大于等于size的分块；
best-fit：返回大于等于size的最小分块；
worst-fit：找出空闲链表中最大的分块，将其分割为size大小和剩余大小的两个分块。
但因为 Worst -fit 很容易生成大 量小的分块，所以不推荐大家使用此方法。
除去 Worst -fit，剩下的还有 Best -fit 和 First -fit 这两种。当我们使用单纯的空闲链表时， 考虑到分配所需的时间，选择使用 First -fit 更为明智。

合并

将所有连续的小分块连接成一个大分块，合并在清楚阶段进行。

执行合并的清除阶段伪代码

// $head_start 堆起始地址
// $head_end 堆结束地址
// $free_list 空链表起始地址
sweep_phase() {
    sweeping = $heap_start;
    while (sweeping < $heap_end) {
        if (sweeping.mark == TRUE) {
            sweeping.mark = FALSE;
        } else {
            // 检测分块是否连续，若连续，合并成一个分块
            if (sweeping == $free_list + $free_list.size) {
                $free_list.size += sweeping.size;
            } else {
                sweeping.next = $free_list;
                $free_list = sweeping;
            }
        }
        sweeping += sweeping.size;
    }
}

多空闲链表

利用分块大小不同的空闲链表，即创建只连接大分块的空 闲链表和只连接小分块的空闲链表

一个空闲链表状态

多个空闲链表状态

多空闲链表分配伪代码

// 假设有100个空闲链表，2-100位固定大小分块链表，101为不固定大小分块链表
new_obj(size) {
    // 计算目标空闲链表下标
    index = size / (WORD_LENGTH / BYTE_LENGTH);
    if (index <= 100) {
        if ($free_list[index] != NULL) {
            // 从目标链表中获取大小合适的分块
            chunk = $free_list[index];
            // 移动链表
            $free_list[index] = $free_list[index].next;
            return chunk;
        }
    } else {
        // 遍历空闲链表，找到大于等于size的分块
        chunk = pickup_chunk(size, $free_list[101]);
        if (chunk != NULL) {
            return chunk;
        }
    }
    // 执行分配失败策略
    allocation_fail();
}

多空闲链表清除阶段伪代码

sweep_phase() {
    // 初始化空闲链表
    for (i : 2..101) {
        $free_list[i] = NULL;
    }
    // 设置堆起始地址，开始遍历堆
    sweeping = $heap_start;
    while (sweeping < $heap_end) {
        // 已标记，标识活动对象
        if (sweeping.mark == TRUE) {
            sweeping.mark = FALSE;
        } else {
            // 计算待回收对象对应的空闲链表下标
            index = sweeping.size / (WORD_LENGTH / BYTE_LENGTH );
            // 把待回收对象添加到空闲链表
            if (index <= 100) {
                sweeping.next = $free_list[index];
                $free_list[index] = sweeping;
            } else {
                sweeping.next = $free_list[101];
                $free_list[101] = sweeping;
            }
        }
        sweeping += sweeping.size;
}

BiBOP法

将大小相近的对象整理成固定大小的块进行管理

位图标记

在标记的时候，不在对象的头里置位，而是在这个表格中的特定场所置位。位图表格的实现方法有多种，例如散列表和树形结构等。为了简单起见，这里我们采 用整数型数组。

mark函数伪代码

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);
        }
    }
}

在这里，WORD_LENGTH 是个常量，表示的是各机器中 1 个字的位宽(例如 32 位机器的 WORD_LENGTH 就是 32)。obj_num 指的是从位图表格前面数起，obj 的标志位在第几个。例如上图中的 E，它的 obj_num 值就是 8。然而请大家注意，下图中位的排列顺序和上图是相反的。因此，E 的标志位是从 bitmap_table[0] 的右边起第 9 个位。

延迟清楚法

缩减因清除操作而导致的 mutator 最大暂停时间的方法。在 标记操作结束后，不一并进行清除操作，而是如其字面意思一样让它“延迟”，通过“延迟”来防止 mutator 长时间暂停。

new_obj伪代码

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 < $heap_end) {
        if ($sweeping.mark == TRUE) {
            $sweeping.mark = FALSE;
        else {
            // 找到大于等于size的分块
            if ($sweeping.size >= size) {
                chunk = $sweeping;
                $sweeping += $sweeping.size;
                return chunk;
            }
        }
        $sweeping += $sweeping.size;
    }
    // 未找到，重置起始位置，返回NULL
    $sweeping = $heap_start;
    return NULL;
}