Garbage Collection 문서 원본 보기

상위 문서: [[Dynamic Memory Allocation]] 

==개요==
C의 malloc 패키지와 같은 명시적 할당기(explicit allocator)를 사용할 경우, 애플리케이션은 malloc과 free 호출을 통해 힙 블록을 할당하고 해제한다. 어떤 블록이 더 이상 필요하지 않게 되었을 때 그 블록을 해제하는 책임은 애플리케이션에게 있다. 할당된 블록을 해제하지 않는 것은 흔한 프로그래밍 오류이다. 예를 들어, 다음과 같은 C 함수는 처리를 수행하는 동안 임시 저장 공간을 할당한다:
<syntaxhighlight lang="c">
void garbage() {
  int *p = (int *)Malloc(15213);
  return; /* 이 시점에서 배열 p는 가비지이다 */
}
</syntaxhighlight>
p는 프로그램에서 더 이상 필요하지 않기 때문에 garbage가 반환되기 전에 해제되었어야 한다. 하지만 프로그래머는 그 블록을 해제하는 것을 잊어버렸다. 이 블록은 프로그램이 실행되는 동안 계속 할당된 상태로 남아 있게 되고, 이후의 할당 요청들을 처리할 수 있었던 힙 공간을 쓸모없이 점유하게 된다. 이러한 블록들을 가비지(garbage)라고 한다.

가비지 컬렉터(garbage collector)는 프로그램이 더 이상 필요로 하지 않는 할당된 블록을 자동으로 해제하는 동적 저장소 할당기이다. 힙 저장소를 자동으로 회수하는 과정은 가비지 컬렉션(garbage collection)이라고 한다. 가비지 컬렉션을 지원하는 시스템에서는, 애플리케이션이 힙 블록을 명시적으로 할당은 하되, 결코 명시적으로 해제하지 않는다. C 프로그램의 문맥에서 보면, 애플리케이션은 malloc은 호출하지만 free는 호출하지 않는다. 대신, 가비지 컬렉터는 주기적으로 가비지 블록들을 식별한 후, 그 블록들을 다시 free list로 돌려놓기 위해 적절히 free를 호출한다.

해당 문서에서는 Mark-and-Sweep 방식의 가비지 컬렉션에 대해 설명한다. 

==Garbage Collector Basics==
[[파일:A garbage collector’s view of memory as a directed graph.png|섬네일|Figure 1. A garbage collector’s view of memory as a directed graph]]
가비지 컬렉터는 메모리를 그림 figure 1과 같은 형태의 directed reachability graph로 간주한다. 이 그래프의 노드들은 루트 노드(root node) 집합과 힙 노드(heap node) 집합으로 나뉜다. 각 힙 노드는 힙에 있는 할당된 블록에 해당한다. 또한 간선 p → q는 블록 p의 어떤 위치가 블록 q의 어떤 위치를 가리킨다는 의미이다. 

어떤 루트 노드로부터 노드 p까지 가는 경로(directed path)가 존재한다면, 노드 p가 도달 가능(reachable)하다고 한다. 특정 시점에서, 도달 불가능한 노드들은 애플리케이션이 다시 사용할 수 없는 가비지에 해당한다. 가비지 컬렉터의 역할은 도달 가능성 그래프에 대한 어떤 표현을 유지하고, 주기적으로 도달 불가능한 노드들을 해제하고 자유 리스트로 되돌림으로써 이들을 회수하는 것이다. 

애플리케이션은 힙 공간이 필요할 때마다 일반적인 방식으로 malloc을 호출한다. malloc이 조건에 맞는 자유 블록을 찾을 수 없으면, 가비지를 회수하여 자유 리스트로 돌려놓기 위해 가비지 컬렉터를 호출한다. 

==Mark&Sweep Garbage Collectors==
Mark & Sweep 가비지 컬렉터는 mark 단계와 sweep 단계로 구성된다. 마크 단계에서는 루트 노드들의 도달 가능하고 할당된 모든 노드들을 mark하고, 그 다음 sweep 단계에서는 표시되지 않은 모든 할당된 블록들을 해제(free)한다. 일반적으로, 블록 헤더의 여분의 하위 비트 중 하나가 해당 블록이 표시되었는지 아닌지를 나타내는 데 사용된다. 

애플리케이션 쪽에서 아래와 같은 인터페이스를 사용한다고 가정하자. 
<syntaxhighlight lang="c">
new(n) // n개의 위치가 모두 0으로 초기화된 새로운 블록을 할당하고 포인터 반환
read(b,i) // 블록 b의 i번째 위치의 값을 읽어서 레지스터에 넣음
write(b,i,v) // 블록 b의 i번째 위치에 값 v를 저장
</syntaxhighlight>
이제 우리는 Mark & Sweep을 설명하기 위해 다음과 같은 함수들이 있다고 가정할 것이다. 여기서 ptr은 typedef void *ptr;로 정의된다고 가정한다:
<syntaxhighlight lang="c">
isPtr(ptr p) //만약 p가 할당된 블록의 어떤 워드를 가리킨다면, 해당 블록의 시작 주소 b를 반환한다. 그렇지 않으면 NULL을 반환한다.
length(ptr b) //블록 b의 크기(워드 단위, 헤더 제외)를 반환한다.
get_roots() //모든 루트 포인터를 반환 (전역 변수, 스택 포인터 등)
</syntaxhighlight>
이때 mark와 sweep는 아래와 같이 구현된다. 
<syntaxhighlight lang="c">
ptr mark(ptr p) {
    if (!is_ptr(p)) return;              // 포인터 아니면 무시
    if (markBitSet(p)) return;           // 이미 마크되어 있으면 무시
    setMarkBit(p);                       // 마크 비트 설정
    for (i = 0; i < length(p); i++)      // 블록 안의 각 위치에 대해
        mark(p[i]);                      // 재귀적으로 마크 호출
    return;
}
</syntaxhighlight>
mark 단계에서는 mark() 함수를 루트 노드마다 한 번씩 호출한다. 만약 p가 할당되었고 아직 표시되지 않은 힙 블록을 가리키지 않는다면, mark() 함수는 즉시 반환된다. 그렇지 않은 경우, 해당 블록을 표시하고, 그 블록 내에 있는 각 워드마다 재귀적으로 mark() 함수를 호출한다. 각 mark() 함수 호출은 어떤 루트 노드의 표시되지 않은, 도달 가능한 노드를 표시한다. mark 단계가 끝난 시점에서, 표시되지 않은 할당 블록은 반드시 도달 불가능하다는 것이 보장되며, 따라서 sweep 단계에서 회수해야 하는 가비지이다. 
<syntaxhighlight lang="c">
ptr sweep(ptr p, ptr end) {
    while (p < end) {
        if (markBitSet(p))
            clearMarkBit();
        else if (allocateBitSet(p))
            free(p);
        p += length(p);  // 다음 블록으로 이동
    }
}
</syntaxhighlight>
Sweep 단계는 위에 나온 sweep 함수를 한 번 호출함으로써 수행된다. sweep() 함수는 힙 내의 모든 블록을 순회하면서, 가지비를 해제(free)한다. 

==Conservative Mark&Sweep for C Programs==
Mark & Sweep은 C 프로그램에서 가비지 컬렉션을 수행하기에 적절한 방법이다. 그 이유는 이 방식이 블록을 이동시키지 않기 때문이다. 하지만 그러나 C 언어는 isPtr 함수 구현에 있어 몇 가지 흥미로운 문제점을 가진다:
# C는 메모리 위치에 타입 정보를 태깅(tagging)하지 않는다.
#* 따라서, isPtr이 자신의 입력 인자 p가 포인터인지 아닌지를 확인할 명확한 방법이 없다.
# 설령 p가 포인터임을 알더라도, isPtr이 p가 실제로 할당된 블록의 payload를 가리키는지 아닌지를 확인할 방법도 없다.
후자의 문제에 대한 한 해결책은 할당된 블록들의 집합을 균형 이진 트리(balanced binary tree)로 유지하는 것이다. 이 트리는 다음과 같은 조건을 만족해야 한다:
* 왼쪽 서브트리의 모든 블록들은 더 낮은 주소에 위치하고,
* 오른쪽 서브트리의 모든 블록들은 더 높은 주소에 위치한다.
[[파일:Left and right pointers in a balanced tree of allocated blocks.png|섬네일|Figure 2. Left and right pointers in a balanced tree of allocated blocks]]
이 구조를 위해서는 figure 2와 같이 각 할당 블록의 헤더에 left와 right 필드가 추가되어야 한다. 이 필드들은 각각 다른 할당 블록의 헤더를 가리키는 포인터이다. isPtr(ptr p) 함수는 이 트리를 사용하여 할당된 블록들 중 p가 어디에 속하는지 이진 탐색(binary search)을 수행한다. 탐색 과정에서, 블록의 헤더에 있는 size 필드를 이용해 p가 해당 블록 범위 안에 속하는지를 판단한다. 


==각주==