Почему белый / серый / черный в GC? - PullRequest
Новая
       40

Почему белый / серый / черный в GC?

5 голосов
/ 15 февраля 2012

Я реализую сборку мусора по меткам-зачисткам в простом API языка сценариев, над которым я работаю и читаю о различных реализациях сборки мусора.Такие API, как Lua, используют метку-зачистку с белыми, серыми и черными списками.

Проблема в том, что я не могу найти объяснение, почему существуют такие списки и почему они включены в эти конкретныеcolors.

В моей текущей тривиальной реализации я просто использую "мертвые" или "живые" состояния.В ходе очистки мертвые объекты удаляются.Я использую встроенную кучу, поэтому я не делаю никаких движений в моем 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;
    }
}

Ответы [ 2 ]

8 голосов
/ 15 февраля 2012

Серый означает «живой, но не отсканированный»: еще не все потомки серого блока отмечены как черные. Серый цвет необходим в инкрементальном сборщике мусора. Он помогает ГК с разметкой и размахом продолжить то, что он делал, в следующий раз, когда у него будет возможность немного пометить.

Если ваш сборщик мусора не является инкрементным, то вам может показаться, что вам не обязательно нужен серый цвет: вы всегда можете просто указать все дочерние элементы любого живого блока, с которым вы сталкиваетесь. Однако другая, более тонкая проблема заключается в том, что этот наивный неинкрементный рекурсивный алгоритм может переполнить стек. Серый цвет также помогает, позволяя хранить информацию о том, что следует посетить в куче, а не в стеке.

Даже если вы используете серый цвет для этой цели, это не мешает вам сохранять буфер блоков, которые еще предстоит посетить для эффективности. Единственное отличие от простой рекурсивной реализации состоит в том, что вы прекращаете обновлять буфер, когда он уже заполнен, и линейно сканируете кучу на наличие серых объектов, если буфер становится пустым после заполнения.

0 голосов
/ 20 апреля 2016

Прежде всего, это наборы, а не списки, и каждый объект в куче в любой момент находится в одном из наборов.

Во-вторых, в любой реализации mark & ​​sweep они используются, но они могут быть подразумеваемыми . Вы не предоставляете реализацию для Mark, но в этой функции вы перемещаете свои объекты в своих наборах.

Вот реализация для фазы пометки моего сборщика мусора: 

/* Initally, the white set contains all objects, the black and
   grey sets are empty. */
stack *st = m->mark_stack;
/* First all roots are added to the gray set. */
for (size_t i = 0; i < m->roots->used; i++) {
    ptr p = m->roots->array[i];
    if (p != 0) {
        /* Mark the root and move it to the gray set. */
        AT(p) |= 1;
        st_push(st, p);
    }
}
while (st->used) {
    /* Think of popping the object from the mark stack as moving
       it from the gray to the black set. */
    ptr p = st_pop(st);
    P_FOR_EACH_CHILD(p, {
        if (!GET_MARK(p_child)) {
            /* Then mark each non-black child and move it to the
               gray set. */
            AT(p_child) |= 1;
            st_push(st, p_child);
        }
    });
}
/* When control has reached this point, the gray set is empty and
   the whole heap has been divided into black (marked) and white
   (condemned) objects. */

Вместо этого мы могли бы использовать явные структуры данных для трех наборов. Но для марки «останови мир» и «развертки» эта реализация гораздо эффективнее.

...