爲什麼GC中的白色/灰色/黑色？

我正在使用簡單的腳本語言API實現標記和清理垃圾收集，我正在研究垃圾收集的各種實現。 API（如Lua）使用白色，灰色和黑色列表進行標記和掃描。爲什麼GC中的白色/灰色/黑色？

的問題是，我似乎無法找到爲什麼有這樣的列表，爲什麼他們投入這些特定顏色的解釋。

在我目前的，簡單的實現，我簡單地用「死」或「活着」的狀態。在掃描中，死對象被刪除。我正在使用本地堆，所以我沒有在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; 
    } 
}

來源

2012-02-14 Nick Bedford

'爲什麼他們被放入這些特定的顏色 - 因爲它們很漂亮！ – asaelr 2012-02-14 23:27:09

搜索「標記並掃描白色灰黑色」使我轉向：http://www.memorymanagement.org/glossary/t.html#tri-color.marking。該頁面提到了算法的一個重要屬性是「正確的」，所以我的猜測是，天真的方法有一些邊緣案例，它打破了。 – millimoose 2012-02-14 23:30:42

另外：http://en.wikipedia.org/wiki/Mark_and_sweep#Naive_mark-and-sweep列表作爲天真的方法的主要缺點在於它不能而不暫停該過程來執行。 – millimoose 2012-02-14 23:32:29

灰色表示「活而不掃描」：不是灰色塊的所有後代已被標記爲黑呢。遞增垃圾收集器中灰色是必需的。它有助於標記式和掃描式GC在下一次有機會進行標記時繼續進行。

如果您的GC是不增量，那麼不妨看看你喜歡你不一定需要灰色：你可以簡單地始終在您遇到任何活塊的所有孩子遞歸。然而，另一個更微妙的問題是，這種天真的非遞增遞歸算法可能會使堆棧溢出。灰色也有助於通過允許存儲有關在堆中下一次訪問的信息而不是堆棧信息。

即使你使用了灰色爲了這個目的，它不會阻止你保持仍待參觀了效率塊的緩衝區。與簡單的遞歸實現唯一的區別是，當緩衝區已滿時停止更新緩衝區，並且如果緩衝區在滿了之後變空，則爲灰色對象線性掃描堆。

來源

2012-02-15 05:45:56

我正試圖圍繞算法如何在沒有完整掃描的情況下工作。我的意思是，如果我將一個聚合對象標記爲灰色，但其中一個子對象標記爲白色，那麼如何避免必須遍歷整個樹以確保白色對象不在其他位置引用。如何避免掃描整個參考層次結構並沒有意義。除非標記階段只是增量，並且標記完全掃描後必須完成掃描？在這種情況下，您必須管理標記之間的新引用。 – 2012-02-17 01:07:03

「除非標記階段只是漸進式，並且標記完全掃描後必須完成掃描？」當然，在增量式標記 - 掃描GC中，算法仍然在完整標記階段和完整掃描階段之間交替。這就是標記和掃描的工作原理。我相信Paul Wilson撰寫的文章「Uniprocessor Garbage Collection Techniques」應該回答你的問題。 – 2012-02-17 08:14:20

首先，它們是一組，而不是列出並在堆中的每個對象是在所述集合中的恰好一個的任何時間。

其次，在任何標記&掃描實施它們正在使用，但它們可能是暗示。你不提供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. */

我們可以轉而使用明確的數據結構爲三組。但是對於一個停止世界標記&掃描gc，這種實現更有效率。

來源

2016-04-19 21:48:42

爲什麼GC中的白色/灰色/黑色？

回答

相關問題