Reference Counting GC (Part two :Partial Mark & Sweep)

部分标记清除算法

部分标记清除算法

Partial Mark & Sweep,Rafael D.Lins,1992

之前我们说过，引用计数的循环引用问题。这个问题可以通过标记清除算法辅助解决。但是这种方法效率很低，标记清除是单纯的为了回收有循环引用的垃圾，而这种垃圾又是很少的。单纯的GC标记清除算法又是以全部堆为对象的，所以会产生许多无用的搜索。

对此我们还有一个办法，那就是只对“可能有循环引用的对象群”使用GC标记清除算法。对其他对象进行内存管理时使用引用计数法。这种方法称为（Partial Mark & Sweep）。不过他有个特点，它的目的是查找非活动对象。

前提

在部分标记-清除算法中，对象会被涂成4种不同的颜色来进行管理。每个颜色的含义如下所示。

黑BLACK：绝对不是垃圾的对象(对象产生是的初始颜色)
白WHITE：绝对是垃圾的对象
灰GRAY：搜索完毕的对象
阴影HATCH：可能是循环垃圾的对象

事实上并没办法去给对象涂颜色，而是往头中分配2位空间，然后用00～11的值对应这4个颜色，以示区分。本书中用obj.color 来表示对象obj 的颜色。 obj.color 取 BLACK、WHITE、GRAY、HATCH 中的任意一个值。

假设有一个堆，里面对象和引用关系如下图所示。

有循环引用的对象群是ABC和DE，其中A和D由根引用。此外这理由C和E引用F。所有对象的颜色现在还是初始的黑色。

dec_ref_cnt()函数

通过mutator删除由根到A的引用。这个引用由update_ptr()函数产生。跟以往的计数法一样，为了将对象A的计数器减量，在uodate_ptr()函数中嗲用dec_ref_cnt()函数。不过在部分标记清除算法中，dec_ref_cnt()函数和以往有少许不同。

dec_ref_cnt(obj){
    obj.ref_cnt--
    if(obj.ref_cnt == 0 )
        delete(obj)
    else if(obj.color != HATCH)
        obj.color = HATCH
        enqueue(obj, $hatch_queue)
}

如果要删除的对象在队列中，那么这里使用delete()函数也需要将该对象从队列中删除。算法在对obj的计数器进行减量操作后，检查obj的颜色。当obj的颜色不是阴影的时候，算法会将其涂上阴影并追加到队列中。当obj的颜色是阴影的时候，obj已经被追加到队列中了，所以程序什么都不做。执行该函数后堆如下图所示。

由根到A的引用被删除了，指向A的指针被追加到队列（$hatch_queue）之中。A被涂上了阴影。

这个队列的存在是为了连接那些可能是循环引用的一部分对象。被连接的对象会被作为GC标记-清除算法的对象，是的循环引用的垃圾被回收。

new_obj()函数

new_obj(size){
    obj = pickup_chunk(size) // 创建对象
    if(obj != NULL)
        obj.color = BLACK
        obj.ref_cnt = 1
        return obj
    else if(is_empty($hatch_queue) == FALSE) // 如果$hatch_queue不为空
        scan_hatch_queue() // 标记清除回收垃圾
        return new_obj(size)  // 重新分配
    else
        allocation_fail()
}

当可以分配时，对象就会被涂回黑色。当分配无法顺利进行的时候，程序会调查队列是否为空。当队列不为空时，程序会通过scan_hatch_ queue() 函数搜索队列，分配分块。scan_hatch_queue() 函数执行完毕后，程序会递归地调用 new_obj() 函数再次尝试分配。 如果队列为空，则分配将会失败。

scan_hatch_queue()函数

scan_hatch_queue() 函数在找到阴影（可能循环引用的垃圾）对象前会一直从队列中取出对象。

scan_hatch_queue(){
    obj = dequeue($hatch_queue)
    if(obj.color == HATCH)
        paint_gray(obj)
        scan_gray(obj)
        collect_white(obj)
    else if(is_empty($hatch_queue) == FALSE)
        scan_hatch_queue()
}

如果取出的对象obj被涂上了阴影，程序就会将obj作为参数，依次调用paint_gray()、scan_gray()、collect_white()函数。从而找出循环引用的垃圾并将其回收。

当obj没有被涂上阴影时候，程序只对再次调用scan_hatch_queue()函数。

paint_gray()函数

从 scan_hatch_queue() 函数调用的3个函数中，首先调用的就是 paint_gray() 函数。它干的事情非常简单，只是查找对象进行计数器的减量操作而已。

paint_gray(obj){
    if(obj.color == (BLACK|HATCH))
        obj.color = GRAY // 搜索完毕的颜色
        for(child :children(obj))
            (*child).ref_cnt--
            paint_gray(*child)
}

程序会把黑色或者阴影对象涂成灰色，对子对象进行计数器减量操作，并调用paint_gray()函数。把对象涂成灰色是为了防止程序重复搜索。在scan_hatch_queue()函数中执行paint_gray()函数后，堆状态如下图所示。

这里通过 paint_gray() 函数按对象A、B、C、F的顺序进行了搜索。下面让我们来详细看一下

在a中，A被涂成了灰色。虽然程序对A执行减量操作，但是B却减少了。对B执行减量操作C又减少了（被引用的减少）。当查找到F时候ABC就已经都是0了。

部分标记 - 清除算法的特征就是要涂色的对象和要进行计数器减量的对象不是同一对象，据此就可以很顺利地回收循环垃圾。

scan_gray()函数

它会搜索灰色对象，把计数器值为 0 的对象涂成白色。

scan_gray(obj){
    if(obj.color == GRAY)
        if(obj.ref_cnt > 0 )
            paint_black(obj)
        else
            obj.color = WHITE
            for(child :children(obj))
                scan_gray(child)
}

程序会从第一个灰色的对象开始找，找到后如果计数器为0就将颜色改为白色，计数器大于0就会执行paint_black()。然后递归去验证孩子。

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

从那些可能被涂成了灰色的有循环引用的对象群中，找出已知不是垃圾的对象，并将其归回原处。执行完后堆状态如下图。

形成了循环垃圾的对象 A、B、C 被涂成了白色，而有循环引用的非垃圾对象 D、 E、F 被涂成了黑色。

collect_white()函数

collect_white() 函数回收白色对象了。

collect_white(obj){
    if(obj.color == WHITE)
        obj.color = BLACK
        for(child :children(obj))
            collect_white(*child)
        reclaim(obj)
}

循环垃圾也可喜地被回收了。堆状态如下图。

限定搜索对象

部分标记清除算法的优点，就是限定了要搜索的对象。也就是“可能是循环垃圾的对象”。那么要怎么发现这样的对象群呢？

初始状态是root->A->B->C，我们添加为root->A->B->C->A，最后把root->A去掉，就形成了A->B->C->A这样的循环引用。也就是说满足下列两种情况就可以认定为是循环引用的垃圾。

产生循环引用
删除从外部到循环引用的引用（在上图中外部就是根，删除了根对循环ABCA的引用）

部分标记清除算法中用dec_ref_cnt()函数来检查计数器的值，如果减量后不为0，就说明这个对象可能是循环引用的一份子。会让这个对象连接到队列，方便以后寻找他。

paint_gray()函数的要点

此方法是用于标识该对象是否被遍历过。会把obj为黑色或阴影的对象变为灰色。然后对obj的孩子对象进行计数器的减量操作，并递归调用该方法，obj自身没有被减量操作。假如说我们队obj进行减量操作，会发生如下情况。

// ![](https://img2018.cnblogs.com/blog/1426997/201811/1426997-20181120142508728-1186301020.png)

bad_paint_gray(obj) 对obj进行操作的方法
bad_paint_gray(obj){
    if(obj.color == (BLACK|HATCH))
        obj.ref_cnt-- // 就是这里啊
        obj.color = GRAY
        for(child :children(obj))
            bad_paint_gray(*child)
}

使用该方法也可以进行垃圾回收，最后计数器的值全就为0了（有引用还为0？）不过如下图所示该方法无法顺利执行。

在搜索完C对象时候，所有对象都会被标记为灰色，并且计数器值是0。之后通过scan_gray()对该堆进行遍历，又全部涂成了白色。之后又经过collect_white()又全部被回收。

因此在部分标记算法中，paint_gray()不首先对A直接进行减量而是从B开始的。

当搜索完C时对象A的计数器值为1所以A不能被回收。在这之后，paint_black()函数会把对象A到C全部涂黑，也会对B和C的计数器进行增量操作，这样对象就完全回到了原始的状态。

也就是说，如果直接就对A进行计数器的减量会发生误删的情况，本来并不是循环引用就会被突然回收掉。

部分标记清除算法的局限性

这个算法不仅付出很大成本搜索对象，还需要查找三次对象，分别是mark_gray()、sacn_gray()、collect_white()。这很大程度的增加了内存管理所花费的时间。还因此对引用计数法最大暂停时间短的优势造成的破坏性的影响。