Garbage Collection
상위 문서: Dynamic Memory Allocation
개요
C의 malloc 패키지와 같은 명시적 할당기(explicit allocator)를 사용할 경우, 애플리케이션은 malloc과 free 호출을 통해 힙 블록을 할당하고 해제한다. 어떤 블록이 더 이상 필요하지 않게 되었을 때 그 블록을 해제하는 책임은 애플리케이션에게 있다. 할당된 블록을 해제하지 않는 것은 흔한 프로그래밍 오류이다. 예를 들어, 다음과 같은 C 함수는 처리를 수행하는 동안 임시 저장 공간을 할당한다:
void garbage() {
int *p = (int *)Malloc(15213);
return; /* 이 시점에서 배열 p는 가비지이다 */
}
p는 프로그램에서 더 이상 필요하지 않기 때문에 garbage가 반환되기 전에 해제되었어야 한다. 하지만 프로그래머는 그 블록을 해제하는 것을 잊어버렸다. 이 블록은 프로그램이 실행되는 동안 계속 할당된 상태로 남아 있게 되고, 이후의 할당 요청들을 처리할 수 있었던 힙 공간을 쓸모없이 점유하게 된다. 이러한 블록들을 가비지(garbage)라고 한다.
가비지 컬렉터(garbage collector)는 프로그램이 더 이상 필요로 하지 않는 할당된 블록을 자동으로 해제하는 동적 저장소 할당기이다. 힙 저장소를 자동으로 회수하는 과정은 가비지 컬렉션(garbage collection)이라고 한다. 가비지 컬렉션을 지원하는 시스템에서는, 애플리케이션이 힙 블록을 명시적으로 할당은 하되, 결코 명시적으로 해제하지 않는다. C 프로그램의 문맥에서 보면, 애플리케이션은 malloc은 호출하지만 free는 호출하지 않는다. 대신, 가비지 컬렉터는 주기적으로 가비지 블록들을 식별한 후, 그 블록들을 다시 free list로 돌려놓기 위해 적절히 free를 호출한다.
해당 문서에서는 Mark-and-Sweep 방식의 가비지 컬렉션에 대해 설명한다.
Garbage Collector Basics
가비지 컬렉터는 메모리를 그림 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)한다. 일반적으로, 블록 헤더의 여분의 하위 비트 중 하나가 해당 블록이 표시되었는지 아닌지를 나타내는 데 사용된다.
애플리케이션 쪽에서 아래와 같은 인터페이스를 사용한다고 가정하자.
new(n) // n개의 위치가 모두 0으로 초기화된 새로운 블록을 할당하고 포인터 반환
read(b,i) // 블록 b의 i번째 위치의 값을 읽어서 레지스터에 넣음
write(b,i,v) // 블록 b의 i번째 위치에 값 v를 저장
이제 우리는 Mark & Sweep을 설명하기 위해 다음과 같은 함수들이 있다고 가정할 것이다. 여기서 ptr은 typedef void *ptr;로 정의된다고 가정한다:
isPtr(ptr p) //만약 p가 할당된 블록의 어떤 워드를 가리킨다면, 해당 블록의 시작 주소 b를 반환한다. 그렇지 않으면 NULL을 반환한다.
length(ptr b) //블록 b의 크기(워드 단위, 헤더 제외)를 반환한다.
get_roots() //모든 루트 포인터를 반환 (전역 변수, 스택 포인터 등)
이때 mark와 sweep는 아래와 같이 구현된다.
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;
}
mark 단계에서는 mark() 함수를 루트 노드마다 한 번씩 호출한다. 만약 p가 할당되었고 아직 표시되지 않은 힙 블록을 가리키지 않는다면, mark() 함수는 즉시 반환된다. 그렇지 않은 경우, 해당 블록을 표시하고, 그 블록 내에 있는 각 워드마다 재귀적으로 mark() 함수를 호출한다. 각 mark() 함수 호출은 어떤 루트 노드의 표시되지 않은, 도달 가능한 노드를 표시한다. mark 단계가 끝난 시점에서, 표시되지 않은 할당 블록은 반드시 도달 불가능하다는 것이 보장되며, 따라서 sweep 단계에서 회수해야 하는 가비지이다.
ptr sweep(ptr p, ptr end) {
while (p < end) {
if (markBitSet(p))
clearMarkBit();
else if (allocateBitSet(p))
free(p);
p += length(p); // 다음 블록으로 이동
}
}
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)로 유지하는 것이다. 이 트리는 다음과 같은 조건을 만족해야 한다:
- 왼쪽 서브트리의 모든 블록들은 더 낮은 주소에 위치하고,
- 오른쪽 서브트리의 모든 블록들은 더 높은 주소에 위치한다.
이 구조를 위해서는 figure 2와 같이 각 할당 블록의 헤더에 left와 right 필드가 추가되어야 한다. 이 필드들은 각각 다른 할당 블록의 헤더를 가리키는 포인터이다. isPtr(ptr p) 함수는 이 트리를 사용하여 할당된 블록들 중 p가 어디에 속하는지 이진 탐색(binary search)을 수행한다. 탐색 과정에서, 블록의 헤더에 있는 size 필드를 이용해 p가 해당 블록 범위 안에 속하는지를 판단한다.
