部分标记-清除算法只对可能有循环引用的对象群使用标记-清除，对其他对象还继续使用引用计数法。但是与普通的标记-清除算法不同，部分标记-清除算法查找的是非活动对象，这样就可以解决循环引用无法回收的问题了。

算法术语

在部分标记-清除算法中，对象会被涂成4中不同的颜色来进行管理：

黑色：black，绝对不是垃圾的对象，对象产生时的初始颜色
白色：white，绝对是垃圾的对象
灰色：gray，搜索完毕的对象
阴影：shadow，可能是循环垃圾的对象

算法把颜色存储在对象头obj.color中，这是一个枚举类型，取BLACK、WHITE、GRAY、SHADOW中的任意一个值。

此外，我们还需要引入一个队列shadow_queue，来存储可能是循环垃圾的对象。

算法过程

跟普通的引用计数法相比，最主要的改进点就是当对象引用减少的时候，我们不仅需要及时清理引用为0的对象，对于减少引用后计数器不为0的对象，也需要记录下来后续对循环引用进行判断。

创建对象

创建对象的时候，如果堆中有空间，则直接分配，并将对象标记为黑色。如果没有空间，那么就需要扫描shadow_queue队列把可能是循环引用的对象回收：

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


func new_obj(size) {
    obj = pickup_chunk(size, free_list)
    if (chunk != NULL) {
        remove_node(free_list, obj)
        obj.color = BLACK
        obj.ref_cnt = 1
        return obj
    } else if (!is_empty(shadow_queue)) {
        scan_shadow_queue(shadow_queue)
        return new_obj(size)
    }
    allocation_fail()
}

如果扫描shadow_queue队列后还是无法释放空间，那么就会分配失败。我们分配完的对象存储情况如图：

初始分配

减少引用计数

我们调用dec_ref_cnt这个函数来减少对象的引用：

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


func dec_ref_cnt(obj) {
    obj.ref_cnt--
    if (obj.ref_cnt == 0) {
        for (child in children(obj)) {
            dec_ref_cnt(child)
        }
        reclaim(obj, free_list)
    } else if (obj.color != SHADOW) {
        obj.color = SHADOW
        enqueue(obj, shadow_queue)
    }
}

当obj减少引用后引用数仍不为0，我们就将其标记为阴影，并推到shadow_queue队列中。如果已经标记过为阴影，则什么都不做，因为这个对象已经存在于shadow_queue队列中了。

此时，我们删除由根到A对象的引用，此时A对象引用计数器不为0，将其标记为阴影，并加入到shadow_queue中：

减量引用

扫描阴影队列

我们需要一直扫描阴影队列，对其中每个对象进行判断是否是垃圾：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func scan_shadow_queue(shadow_queue) {
    obj = dequeue(shadow_queue)
    if (obj.color == SHADOW) {
        paint_gray(obj)
        scan_gray(obj)
        collect_white(obj)
    } else if (!is_empty(shadow_queue)) {
        scan_shadow_queue(shadow_queue)
    }
}

paint_gray

首先我们调用paint_gray函数，标记对象已经被搜索过：

1
2
3
4
5
6
7
8
9


func paint_gray(obj) {
    if (obj.color == BLACK || obj.color == SHADOW) {
        obj.color = GRAY
        for (child in children(obj)) {
            (*child).ref_cnt--
            paint_gray(*child)
        }
    }
}

同时对该对象所引用的所有子对象，都将其子对象引用计数器减一，并递归执行paint_gray函数，将对象标记为灰色表示对象已经被搜索过，防止重复的处理。这样如果存在循环引用，就会递归的把引用环中的对象计数器都减一。

paint_gray

scan_gray

在scan_gray函数中，会搜索灰色的对象，并把计数器为0的对象标记为白色，表明这是一个垃圾，否则将其涂黑为正常对象：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func scan_gray(obj) {
    if (obj.color != GRAY) {
        return
    }
    if (obj.ref_cnt > 0) {
        paint_black(obj)
    } else {
        paint_white(obj)
    }
}

paint_black函数从那些可能被涂成了灰色的有循环引用的对象群中，找出已知不是垃圾的对象，并将其引用计数器还原：

1
2
3
4
5
6
7
8
9


func paint_black(obj) {
    obj.color = BLACK
    for (child in children(obj)) {
        (*child).ref_cnt++
        if ((*child).color != BLACK) {
            paint_black(*child)
        }
    }
}

paint_white函数把垃圾对象标记为白色，并继续扫描其引用的子对象：

1
2
3
4
5
6


func paint_white(obj) {
    obj.color = WHITE
    for (child in children(obj)) {
        scan_gray(*child)
    }
}

经过scan_gray函数后，有循环引用的垃圾对象就标记为了白色，正常对象标记为了黑色。

scan_gray

collect_white

最后通过collect_white函数回收标记为白色的对象：

1
2
3
4
5
6
7
8
9


func collect_white(obj) {
    if (obj.color != WHITE) {
        return
    }
    for (child in children(obj)) {
        collect_white(*child)
    }
    reclaim(obj)
}

最终循环引用的对象群A、B、C被成功回收了：

scan_gray

我们删除从根到对象D的引用，再次重复以上操作，循环引用对象群D、E也成功被回收了：

不足

部分标记-清除算法虽然能完美的解决循环引用问题，但是需要遍历的从阴影队列搜索对象，被队列记录的对象不全都是垃圾对象，，所以要搜索的对象绝对不在少数。这个算法总计需要查找3次对象，也就是说需要对从队列取出的阴影对象分别执行1次mark_gray函数、scan_gray函数以及collect_white函数，大大增加了内存管理所花费的时间。

实际运用

虽然增加了gc的暂停时间，但是部分标记-清除算法使得引用计数法可以真正的使用在实际环境中。比如 PHP的GC算法，就是使用部分标记-清除算法来解决循环引用的。

GC部分标记-清除法

What's On This Page

算法术语

算法过程

创建对象

减少引用计数

扫描阴影队列

paint_gray

scan_gray

collect_white

不足

实际运用