为什么GC中有白色/灰色/黑色？

Question

我正在使用一个简单的脚本语言API实现标记和清除垃圾收集,我正在阅读有关垃圾收集的各种实现.像Lua这样的API使用带有白色,灰色和黑色列表的标记和扫描.

问题是,我似乎无法找到解释为什么有这样的列表以及为什么将它们放入这些特定的颜色.

在我目前的,琐碎的实现中,我只是使用"死"或"活"状态.在扫描中,删除死对象.我正在使用本机堆,因此我没有在GC中进行任何移动.

我是用C写的.

// Performs a full garbage collection
void GorCollect(GorContext *ctx)
{
    Value *v, *end;
    Collectable *c, *n;

    // mark stack references
    end = ctx->stack + ctx->stackTop + 1;
    v = ctx->stack;
    while(v != end)
    {
        if (gvisgc(v) && v->v.gc) // mark if a collectable obj
            Mark(v->v.gc);
        v = v++;
    }

    // mark global references
    if (ctx->global)
        Mark((Collectable *)ctx->global); // ctx->global is a collectable obj

    // perform sweep
    c = ctx->gchead; // full list of collectable objs
    ctx->gchead = 0;
    while(c) {
        n = c->next;    
        // destroy unmarked collectable
        if (!c->marked)
            FreeCollectable(ctx, c);

        // rebuild gc list (singly-linked)
        else
        {
            c->marked = 0;
            if (!ctx->gchead)
                c->next = 0;
            else
                c->next = ctx->gchead;
            ctx->gchead = c;
        }
        c = n;
    }
}

Answer 1

灰色表示"活着但未扫描":并非所有灰色块的后代都标记为黑色.增量垃圾收集器中需要灰色.它有助于标记和扫描GC继续它下次有机会进行一些标记时所做的事情.

如果您的GC是非增量的,那么它可能会让您觉得您不一定需要灰色:您可以简单地总是递归到您遇到的任何活动块的所有孩子身上.然而,另一个更微妙的问题是这种天真的非增量递归算法可能会溢出堆栈.灰色还有助于存储有关堆中下一个访问内容的信息,而不是堆栈.

即使您为此目的使用灰色,也不会阻止您保留要访问的块的缓冲区以提高效率.与初始递归实现的唯一区别在于,当缓冲区已经满时,您将停止更新缓冲区,如果缓冲区在已满后变为空,则会线性扫描堆中的灰色对象.