GC标记-清除算法是最早被发明的GC算法，跟字面意思一样，算法由两个阶段组成：标记阶段和清除阶段。标记阶段把所有活动对象都做上标记，然后再清除阶段把没有被标记的对象回收。

算法过程

可以用代码描述描述整个过程：

1
2
3
4


func mark_sweep() {
    mark_phase()
    sweep_phase()
}

算法除了标记和清除过程，对于对象的分配我们也需要做相应的策略。

初始状态

标记阶段

每个对象的头中，都会有一个marked变量来表明当前对象是否已经被标记。我们遍历堆中根引用的所有对象，为堆中所有的活动对象打上标记：

1
2
3
4
5


func mark_phase() {
    for (obj in roots) {
        mark(obj)
    }
}

mark函数会递归的标记对象以及其引用的对象，这样就能把所有的活动对象都标记上：

1
2
3
4
5
6
7
8
9


func mark(obj) {
    if (obj.marked) {
        return
    }
    obj.marked = true
    for (child in children(obj)) {
        mark(*child)
    }
}

标记状态

标记阶段程序会标记所有的活动对象，所以标记花费的时间是与活动对象总数成正比的。

清除阶段

清除阶段gc会遍历整个堆，回收那些没有被标记的对象，使其能够再次被利用：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func sweep_phase() {
    free_list = NULL
    sweeping = HEAP_START
    while (sweeping < HEAP_END) {
        if (sweeping.marked) {
            sweeping.marked = 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
    }
}

我们引入一个空闲链表free_list，用于串联所有的非活动对象。清除阶段从堆的首地址HEAP_START开始，按顺序一个一个遍历对象，如果对象没有被标记，就把它串联到空闲链表中。对于相邻的分块，我们直接合并即可。对象头中的next指针用于串联所有的非活动对象。同时将活动对象的marked标志重置，以便下一次进行GC。

清除状态

清除阶段所花费时间与堆大小成正比。堆越大，清除阶段所花费的时间就会越长。

对象分配

我们已经把垃圾对象连接到空闲链表，分配对象时只需要在空闲链表中遍历并寻找大小合适的分块就可以了。如果找不到合适的分块，就分配失败（当前策略），或者执行压缩堆操作。

1
2
3
4
5
6
7
8


func new_obj(size) {
    obj = pickup_chunk(size, free_list)
    if (chunk != NULL) {
        remove_node(free_list, obj)
        return obj
    }
    allocation_fail()
}

我们使用pickup_chunk函数遍历空闲链表free_list，寻找大于或等于size的分块，如果找到和size大小相同的分块，则直接返回该分块，否则将该分块分割，返回size大小，剩余的链接到空闲链表中：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func pickup_chunk(size, free_list) {
    fit_chunk = free_list
    while (fit_chunk != NULL) {
        if (fit_chunk.size == size) {
            break
        }
        if (fit_chunk.size > size) {
            resize_chunk(free_list, fit_chunk, size)
            break
        }
        fit_chunk = fit_chunk.next
    }
    return fit_chunk
}

分配策略有三种：First-Fit、Best-Fit、Worst-Fit：

First-Fit：分配空闲链表中最先发现的大于等于size大小的分块
Best-Fit：分配空闲链表中大于等于size大小的最小分块
Worst-Fit：分配空闲链表中最大的分块，目的是剩余的分块数量最大化。

其中，Worst-Fit容易生成大量的小分块，不推荐使用。First-Fit需要的时间最短，Bset-Fit分配后碎片化的几率最小。

优点

GC标记-清除算法有两个优点：

实现简单

算法实现简单，那么与其他的算法组合也就相应的简单了。
保守GC

算法不会移动对象，非常适合搭配保守的GC算法。

缺点

GC标记-清除算法的缺点也很明显：

碎片化

在GC标记-清除算法的使用过程中会逐渐产生被细化的分块，不久后就会导致无数的小分块散布在堆的各处，我们称这种状况为碎片化。如果发生碎片化，即使堆大小足够，也会因为一个个散落的分块导致分配对象失败。
分配速度

分配对象时，每次都需要遍历空闲链表，找到足够大的分块，最坏情况是每次都要遍历到最后。
写时复制技术不兼容

Linux中进程fork时，大部分内存空间都不会被复制，只有发生内存修改时才会发生复制，这个技术就是写时复制。因为GC标记-清除算法会频繁的修改对象的头信息中标志位，就会发生不必要的复制。

改进

BiBOP法

BiBOP是Big Bag Of Pages的缩写，就是将堆分成几个块，每个块都管理只管理相同或者相近大小的对象。对应的空闲链表也有多个，每个空闲链表只链接相同大小的垃圾对象。

BiBOP

因为每个块都只能分配相近大小的对象，所以就不会出现大小不均匀的分块，这样能提高堆的使用效率，但是BiBOP法也不能完全的消除碎片化，在块中还是可能会出现碎片。而且如果对象大小分布较极端，就会出现某些分块中活动对象较少，也不能有效利用堆。

使用多个空闲链表能提高对象的分配速度，不用遍历所有的空闲链表，只需要在对应大小的空闲链表中遍历就可以了。

位图标记法

在标记垃圾对象时，我们是直接标记对象的头，这样就与写时复制技术不兼容。所以在标记的时候，不在头部标记，而是在一个位图表格中进行标记，因为位图表格一般都很小，写时复制时只会复制位图表格，不会造成很大影响。

位图表格的实现方式有很多种，比如散列表、树、整形数组等。一般来说，我们为堆的每个字（对象分配的最小占用字节数）都分配一个位，如果堆有多个，那么为每一个堆都分配一个位图。

位图标记

位图标记法除了能兼容写时复制技术，在清除阶段也有优势，可以一次性的将所有标记位清除以供下一次标记，使清除效率更高效。

What's On This Page