왜 GC에서 흰색/회색/검은 색입니까?

Question

나는 간단한 스크립트 언어 API에서 마크 앤 스위프 가비지 콜렉션을 구현 중이며 다양한 가비지 콜렉션 구현에 대해 읽고있다. 루아와 같은 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

그레이는 "라이브하지만 검색되지"를 의미한다. 회색 색상은 증분 쓰레기 수거통에 필요합니다. 그것은 mark-and-sweep GC가 다음에 마킹을 할 기회를 얻었을 때 그 작업을 계속하는 데 도움이됩니다.

GC가 비 증분 인 경우 회색 색상이 반드시 필요하지는 않은 것처럼 보일 수 있습니다. 만나는 라이브 블록의 모든 하위 항목에 간단하게 항상 반복 할 수 있습니다. 그러나 또 다른 미묘한 문제는이 순진한 비 증분 재귀 알고리즘이 스택을 오버플로 할 수 있다는 것입니다. 회색 색상은 스택 대신 힙에서 다음에 방문 할 항목에 대한 정보를 저장할 수있게 도와줍니다.

이 목적으로 회색을 사용하더라도 효율성을 위해 방문한 채로 남아있는 블록 버퍼를 유지할 수 있습니다. 순진한 재귀 구현의 유일한 차이점은 버퍼가 이미 가득차면 버퍼 업데이트를 중지하고 버퍼가 가득차면 버퍼가 비게되면 회색 객체에 대해 힙을 선형 적으로 스캔한다는 것입니다.

Answer 2

첫 번째는 세트가 아니고 목록이 아니며 힙의 각 객체는 언제나 세트 중 하나에 있습니다.

둘째로, 모든 마크 & 스윕 구현에서 사용 중이지만, 암시적인 일 수 있습니다. 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의 경우이 구현이 훨씬 효율적입니다.