컴퓨터 시스템 : CSAPP 9장 정리 - 9.10 가비지 컬렉터 기초

9.10 가지비 컬렉션 (Garbage Collection)

명시적 할당자(예: C의 malloc 패키지)에서는 프로그램이 malloc과 free 호출을 통해 힙 블록을 직접 할당하고 해제한다. 따라서 프로그램이 더 이상 필요 없는 블록을 명시적으로 해제하지 않으면 메모리 누수가 발생한다.

예를 들어, 다음과 같은 C 함수가 있다고 가정한다:

void garbage() {
    int *p = (int *)Malloc(15213);
    return; /* 이 시점에서 p는 쓰레기가 된다 */
}

이 경우, p는 함수가 끝날 때 더 이상 참조되지 않지만, 개발자가 free(p) 호출을 빠뜨렸기 때문에 이 블록은 프로그램이 종료될 때까지 힙 공간을 차지하게 된다.

가지비 컬렉터는 이런 문제를 해결하기 위해 만들어졌다. 프로그램이 명시적으로 할당은 하지만, 해제는 하지 않는다. 대신 가지비 컬렉터가 주기적으로 필요 없는 블록(즉, 가비지)을 찾아서 자동으로 해제한다. 이 과정을 가지비 컬렉션(garbage collection)이라 한다.

가지비 컬렉션은 1960년대 초 MIT에서 John McCarthy가 개발한 Lisp 시스템에서 시작되었다. 오늘날 Java, ML, Perl, Mathematica 같은 현대 언어 시스템에서도 필수적인 부분이다. 이 절에서는 특히 기존 malloc 패키지 위에 구축할 수 있는 Mark & Sweep 알고리즘에 집중한다​.

---

9.10.1 Garbage Collector Basics

가지비 컬렉터는 메모리를 방향 그래프(directed graph)로 바라본다. 이 그래프는 루트 노드와 힙 노드로 나뉜다.

• 힙 노드(heap node): 힙에 할당된 각 블록을 나타낸다.
• 루트 노드(root node): 힙 외부에 있는 포인터를 담는 위치를 나타낸다. 예를 들어 레지스터, 스택 변수, 전역 변수 등이 루트 노드가 된다.

그래프에서 어떤 노드 p가 루트 노드로부터 도달 가능한 경우, p를 도달 가능(reachable) 하다고 한다. 반대로, 루트 노드로부터 경로가 없는 노드들은 더 이상 프로그램에서 사용할 수 없고, 이는 가지비(garbage)가 된다.

가지비 컬렉터는 이 도달 가능성 그래프(reachability graph)를 관리하여, 주기적으로 도달할 수 없는 블록을 해제하고 이를 자유 블록 리스트에 반환한다​.

그림으로 요약하면, 루트 → 힙 노드로 이어진 경로가 없는 노드는 가지비로 간주하여 제거한다.

---

9.10.2 Mark & Sweep Garbage Collectors

Mark & Sweep 가지비 컬렉터는 두 단계로 동작한다:

1. 마크 단계(mark phase): 루트 노드들의 모든 도달 가능하고 할당된 후손 노드들을 표시한다.
2. 스윕 단계(sweep phase): 마크되지 않은 할당된 블록을 해제한다.

보통 블록 헤더의 사용하지 않는 하위 비트 중 하나를 사용하여 블록이 마크되었는지 여부를 나타낸다​.

---

마크 함수(mark function)와 스윕 함수(sweep function) 의 의사 코드는 다음과 같다:

void mark(ptr p) {
    if ((b = isPtr(p)) == NULL)
        return;
    if (blockMarked(b))
        return;
    markBlock(b);
    len = length(b);
    for (i = 0; i < len; i++)
        mark(b[i]);
    return;
}

void sweep(ptr b, ptr end) {
    while (b < end) {
        if (blockMarked(b))
            unmarkBlock(b);
        else if (blockAllocated(b))
            free(b);
        b = nextBlock(b);
    }
    return;
}

마크 함수는 루트 노드 각각에 대해 한 번 호출한다.

• 주어진 포인터 p가 할당된 힙 블록을 가리키지 않거나 이미 마크된 경우, 즉시 리턴한다.
• 그렇지 않으면 블록을 마크하고, 블록 안의 모든 워드(단어)에 대해 재귀적으로 mark를 호출한다.
• 이렇게 하면 루트 노드로부터 도달 가능한 모든 후손 블록이 마크된다.

스윕 함수는 힙을 선형적으로 순회하면서 마크되지 않은 할당 블록(가지비)을 해제한다.

• 블록이 마크되어 있다면 마크를 해제(unmark)한다.
• 블록이 할당되었지만 마크되지 않았다면 free를 호출하여 블록을 해제한다.

책에서는 작은 힙 예제를 그림으로 보여준다:

• 초기 힙에는 6개의 블록이 있으며 모두 할당된 상태다.
• 루트는 블록 4를 가리키고, 블록 4는 블록 3과 6을 가리키며, 블록 3은 블록 1을 가리킨다.
• 마크 단계 후, 블록 1, 3, 4, 6은 마크된다.
• 스윕 단계 후, 블록 2와 5는 해제되어 자유 리스트로 반환된다​.

---

9.10.3 Conservative Mark & Sweep for C Programs

Mark & Sweep 방식은 C 프로그램의 가지비 수집에 적합하다. 이 방식은 블록을 이동시키지 않고 제자리에서 동작하기 때문이다. 그러나 C 언어는 isPtr 함수 구현에 몇 가지 흥미로운 문제를 야기한다.

• 첫 번째 문제는, C 언어가 메모리 위치에 타입 정보를 태깅하지 않는다는 점이다. 따라서 어떤 값 p가 포인터인지 아닌지를 isPtr 함수가 명확히 판단할 방법이 없다.
• 두 번째 문제는, p가 포인터라는 것을 안다고 하더라도, 그것이 실제로 할당된 블록의 유효한 내부 위치를 가리키는지 여부를 알아낼 방법이 없다는 점이다​.

이를 해결하는 한 가지 방법은 모든 할당 블록을 균형 이진트리(balanced binary tree)로 관리하는 것이다. 이 트리는 다음 불변 조건(invariant)을 유지한다:

• 왼쪽 서브트리의 모든 블록은 현재 블록보다 작은 주소를 가진다.
• 오른쪽 서브트리의 모든 블록은 현재 블록보다 큰 주소를 가진다.

이를 위해 각 할당 블록의 헤더에 두 개의 추가 필드(왼쪽 포인터, 오른쪽 포인터)를 추가한다. isPtr 함수는 이 트리를 이용하여 이진 탐색을 수행하며, 현재 블록의 크기 정보를 이용해 주어진 포인터 p가 해당 블록 안에 속하는지 확인한다​.

보수적 수집기의 특징

이 방법은 정확하게 루트로부터 도달 가능한 모든 노드를 마크할 수 있다는 점에서 "정확(correct)" 하다.

• 즉, 필요한 블록을 잘못 해제하여 프로그램이 망가지는 일은 없다.
• 그러나 이 방식은 "보수적(conservative)"이다. 실제로는 도달할 수 없는 블록도 잘못해서 마크할 수 있다.
  • 예를 들어, 어떤 할당 블록 안에 있는 int 값이 우연히 다른 블록의 주소값과 같을 수 있다. 이 경우, 가지비 컬렉터는 이 값을 포인터라고 오인하여 해당 블록을 살아있는 것으로 간주할 수 있다.

결국,

• 프로그램의 정확성(correctness)에는 문제가 없지만,
• 일부 가지비가 수집되지 않아 외부 단편화(external fragmentation)가 발생할 수 있다​.

---

요약

• C 언어는 타입 정보가 없어 포인터 판별이 불확실하다.
• 따라서 C용 Mark & Sweep 컬렉션은 보수적으로 동작해야 한다.
• 정확성은 유지하지만, 가지비를 완벽하게 수집하지 못할 수 있다.