垃圾回收的算法与实现学习笔记五、GC标记-清除算法

一、分配

1、分配：是指将回收的垃圾进行再利用，清除阶段将垃圾对象连接到空链表。

2、搜索空闲链表并寻找大小合适的分块 => 分配。

new_obj(size) {
    chunk = pickup_chunk(size, $free_list); // 寻找分块 找到大小相同的直接分配 大的分割 分配
    if (chunk != NULL)
        return chunk;
    else
        allocation_fail();
}

3、First-fit、Best-fit、Worst-fit区别。

1）First-fit:最初发现大小等于size的分块时就会立即返回该分块。

2）Best-fit:遍历空链表,返回大小等于size的最小分块。

3）Worse-fit:找出空闲链表中最大的分块，将其分割成mutator申请的大小和分割后剩余的大小=> 目的：将分割后剩余的分块最大化。缺点很容易产生大量小的分块。

4、使用单纯的空链表时，考虑分配所需的时间，选择First-fit更为明智。

二、合并

1、合并：根据分配策略的不同处理后可能会产生大量的小分块。如果他们是连续的，就可以将它们连接起来形成大分块。

2、“连接连续分块” => 合并（coalescing），合并在清除阶段进行。

sweep_phase() {
    sweep = $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;
}