4

私が取り組んでいる単純なスクリプト言語 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;
    }
}
4

2 に答える 2

8

灰色は「ライブだがスキャンされていない」ことを意味します。灰色のブロックのすべての子孫がまだ黒としてマークされているわけではありません。インクリメンタルガベージ コレクタでは灰色が必要です。これは、マーク アンド スイープ GC が、次に少しのマーキングを行う機会を得たときに、行っていたことを継続するのに役立ちます。

GC が非インクリメンタルである場合、必ずしも灰色が必要ではないように見えるかもしれません。遭遇したライブ ブロックのすべての子に対して常に再帰を行うことができます。ただし、別のより微妙な問題は、この単純な非増分再帰アルゴリズムがスタックをオーバーフローする可能性があることです。灰色は、スタックではなくヒープに次にアクセスするものに関する情報を保存できるようにすることにも役立ちます。

この目的で灰色を使用したとしても、効率化のためにまだアクセスしていないブロックのバッファーを保持することを妨げるものではありません。単純な再帰実装との唯一の違いは、バッファーが既にいっぱいになったときに更新を停止し、バッファーがいっぱいになった後に空になった場合にヒープを線形にスキャンして灰色のオブジェクトを探すことです。

于 2012-02-15T05:45:56.970 に答える