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

가비지 컬렉터는 메모리를 그림 9.49와 같은 형태의 directed reachability graph로 간주한다. 이 그래프의 노드들은 루트 노드(root node) 집합과 힙 노드(heap node) 집합으로 나뉜다. 각 힙 노드는 힙에 있는 할당된 블록에 해당한다. 또한 간선 p → q는 블록 p의 어떤 위치가 블록 q의 어떤 위치를 가리킨다는 의미이다.

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