GC 기본 알고리즘 — Mark-Sweep, Mark-Compact, Copying

지난 글에서 GC가 객체의 생사를 어떻게 판정하는지 — 도달 가능성과 GC Roots, 그리고 모든 GC가 짊어지는 Stop-The-World 비용 — 큰 그림을 그렸습니다. 이번 글에서는 그 판정 결과를 가지고 실제로 메모리를 회수하는 방법으로 한 단계 내려갑니다. 현대의 GC가 아무리 복잡해 보여도, 그 내부는 결국 세 가지 기본 알고리즘 — Mark-Sweep, Mark-Compact, Copying — 의 조합으로 이루어져 있습니다. 이 세 가지의 동작 원리와 각자의 트레이드오프를 이해하면, 이후에 만날 Serial·Parallel·G1 같은 실제 컬렉터들이 “왜 그렇게 설계되었는지”가 자연스럽게 보입니다.

Mark — 살아 있는 것을 표시한다

모든 추적 기반(tracing) GC의 첫 단계는 Mark입니다. GC Roots(스택의 지역 변수, static 필드, JNI 참조 등)에서 출발해 참조를 따라가며 닿을 수 있는 모든 객체에 “생존” 표시를 남깁니다. 도달 가능성 그래프를 한 번 순회하는 작업이며, 표시되지 않은 객체는 모두 쓰레기로 간주됩니다.

이 순회를 정밀하게 다루기 위해 흔히 삼색 추상화(tri-color abstraction) 를 사용합니다. 객체를 세 가지 색으로 나누는 개념입니다.

색	의미
흰색(white)	아직 방문하지 않음 — 추적이 끝나면 쓰레기
회색(gray)	방문했지만 그 자식 참조는 아직 다 보지 않음
검정(black)	자신과 자식 참조까지 모두 처리 완료 — 생존 확정

Mark는 Roots를 회색으로 칠하며 시작해, 회색 객체를 하나씩 꺼내 그 자식을 회색으로 칠하고 자신은 검정으로 바꾸는 과정을 회색이 없어질 때까지 반복합니다. 끝나고도 흰색으로 남은 객체가 회수 대상입니다. 이 삼색 모델은 단순한 Mark뿐 아니라, 애플리케이션과 GC가 동시에 도는 동시(concurrent) 수집에서 “검정이 흰색을 직접 가리키면 안 된다”는 불변식(invariant)을 논하는 토대가 되므로 이름만이라도 기억해 두면 좋습니다.

Mark 단계의 비용은 생존 객체 수에 비례합니다. 죽은 객체는 건드리지도 않기 때문입니다. 이 사실은 뒤에서 알고리즘을 고를 때 중요한 기준이 됩니다.

Sweep — 죽은 것을 회수한다, 그리고 단편화

Mark가 끝나면 힙 전체를 훑으며 표시되지 않은 객체들의 공간을 회수합니다. 이것이 Sweep입니다. 회수된 영역은 free list라는 빈 공간 목록에 등록되어, 이후 새 객체 할당 시 재사용됩니다.

Mark-Sweep는 객체를 옮기지 않는다는 장점이 있습니다. 생존 객체의 주소가 그대로이므로 참조 갱신이 필요 없고, 구현도 비교적 단순합니다. 하지만 치명적인 약점이 있습니다. 죽은 객체가 차지하던 자리에 구멍(hole) 이 그대로 남아, 생존 객체와 빈 공간이 뒤섞인 외부 단편화(external fragmentation) 가 발생합니다.

문제는 빈 공간의 총합이 충분해도 그것이 잘게 흩어져 있으면 큰 객체를 할당하지 못한다는 점입니다. 또한 할당할 때마다 free list를 뒤져 “충분히 큰 구멍”을 찾아야 하므로(first-fit, best-fit 등) 할당 비용도 올라갑니다. 개념적으로 free list 기반 할당은 다음과 같은 모습입니다.

// free list: 흩어진 빈 구멍들의 연결 리스트
free_list -> [addr=0x100, size=48] -> [addr=0x180, size=32] -> [addr=0x240, size=64]

allocate(size = 56):
    for block in free_list:        // 리스트를 순회하며
        if block.size >= 56:       // 들어갈 만큼 큰 구멍 탐색
            return block            // → 0x240(size=64)만 가능
    return OOM                      // 총합은 충분해도 못 찾으면 실패

총 빈 공간은 144바이트나 되지만 56바이트짜리 하나조차 들어갈 구멍이 하나뿐입니다. 이것이 단편화가 만드는 실제 손해입니다.

Mark-Compact — 단편화를 정리하지만 비싸다

단편화를 근본적으로 없애려면 생존 객체들을 힙의 한쪽 끝으로 밀어붙여(compact) 빈 공간을 하나의 연속된 덩어리로 모으면 됩니다. 이것이 Mark-Compact입니다. 위 SVG의 3단계가 보여주듯, 흩어진 A·B·C·D·E를 앞쪽으로 차곡차곡 이동시키면 뒤쪽에 거대한 연속 영역이 생깁니다.

연속된 빈 공간이 생기면 할당이 극도로 단순해집니다. free list를 뒤질 필요 없이, “다음 빈 위치”를 가리키는 포인터를 객체 크기만큼 전진시키기만 하면 됩니다. 이를 bump pointer 할당이라 부릅니다.

// bump pointer 할당 — 단편화 없는 연속 영역에서만 가능
Object allocate(int size) {
    if (top + size > end) {   // 남은 공간 부족하면
        triggerGC();          // GC 유발
    }
    Object obj = (Object) top; // 현재 top이 곧 새 객체 주소
    top += size;               // 포인터를 크기만큼 전진 (bump)
    return obj;                // free list 탐색 불필요 → 매우 빠름
}

대신 Compact에는 두 가지 비용이 따릅니다. 첫째, 생존 객체를 물리적으로 이동(memory copy) 하는 비용. 둘째, 이동한 객체를 가리키던 모든 참조의 주소를 갱신(pointer update) 하는 비용입니다. 객체 하나를 옮기면 그것을 가리키던 다른 객체·스택·static의 참조를 전부 새 주소로 고쳐야 하므로, 힙을 여러 번 훑어야 할 수도 있습니다. 그래서 Mark-Compact는 단편화는 없애지만 단계당 시간이 길어, 멈춤 시간(pause)이 늘어나는 경향이 있습니다.

Copying — 반쪽 힙으로 단편화를 회피한다

세 번째 알고리즘은 발상이 다릅니다. 힙을 From-space와 To-space 둘로 나누고, 한쪽만 사용합니다. From이 가득 차면 그 안의 생존 객체만 To로 복사하면서 차곡차곡 채우고, From은 통째로 버립니다. 그리고 둘의 역할을 교환(swap)합니다 — 다음 번엔 To가 활성 공간이 됩니다.

Copying의 매력은 세 가지를 한 번에 얻는다는 점입니다.

• 단편화 없음: 생존 객체를 To에 빈틈없이 채워 넣으므로 결과는 항상 압축된 상태입니다.
• Sweep 단계 없음: 죽은 객체를 일일이 회수하지 않습니다. From을 통째로 비워버리면 끝입니다.
• 빠른 할당: 결과가 압축되어 있으니 bump pointer로 할당할 수 있습니다.

게다가 Copying의 비용은 생존 객체 수에만 비례합니다(죽은 객체는 복사하지 않으므로 비용이 0). 즉 생존율이 낮을수록 압도적으로 빠릅니다.

대신 분명한 대가가 있습니다. 언제나 힙의 절반을 비워둬야 한다는 것입니다. To-space는 평소엔 노는 공간이므로 메모리 효율이 절반으로 떨어집니다. 또한 생존율이 높으면 복사할 양이 많아져 이점이 줄어듭니다. 그래서 Copying은 “대부분의 객체가 금방 죽는” 영역 — 즉 다음 글에서 다룰 Young 영역 — 에 특히 잘 맞습니다.

세 알고리즘의 트레이드오프

같은 “쓰레기 회수”라는 목표를 두고 세 알고리즘은 서로 다른 자원을 희생합니다.

알고리즘	단편화	할당 속도	객체 이동	메모리 오버헤드	비용이 비례하는 대상
Mark-Sweep	발생	느림(free list)	없음	작음	힙 전체(sweep)
Mark-Compact	없음	빠름(bump)	있음(+포인터 갱신)	작음	생존 객체(이동)
Copying	없음	빠름(bump)	있음(복사)	큼(힙 절반)	생존 객체(복사)

요약하면 트레이드오프의 세 축은 처리량(throughput), 단편화, 메모리 오버헤드입니다. Mark-Sweep는 메모리를 아끼지만 단편화와 느린 할당을 감수합니다. Mark-Compact는 단편화를 없애는 대신 이동·갱신 비용으로 멈춤 시간이 길어집니다. Copying은 속도와 무단편화를 모두 얻지만 메모리의 절반을 헌납합니다. 어느 하나가 절대적으로 우월하지 않다는 점이 핵심입니다.

실제 컬렉터는 이들을 조합한다

중요한 사실은, 실제 JVM의 GC들이 이 셋 중 하나를 그대로 쓰지 않는다는 점입니다. 대신 상황에 맞게 조합합니다.

• Serial / Parallel GC: 객체가 금방 죽는 Young 영역엔 Copying을, 오래 사는 객체가 모인 Old 영역엔 Mark-Compact를 적용합니다. 영역별로 생존율 특성이 다르다는 점을 활용한 것입니다.
• G1 GC: 힙을 작은 region 단위로 쪼개고, region 간 복사(Copying의 변형)로 점진적으로 단편화를 정리합니다.

이런 조합이 가능한 이유는 다음 글에서 다룰 약한 세대 가설(weak generational hypothesis) — “대부분의 객체는 생성되자마자 죽는다” — 덕분입니다. 객체의 수명 분포에 따라 영역을 나누고, 각 영역에 가장 어울리는 알고리즘을 붙이는 것이 세대별 GC의 출발점입니다.

다음 예시처럼 JVM 옵션으로 어떤 조합의 컬렉터를 쓸지 직접 선택할 수 있습니다.

# 사용 중인 GC 확인
java -XX:+PrintCommandLineFlags -version

# 컬렉터 명시적 선택
-XX:+UseSerialGC      # Young: Copying, Old: Mark-Compact (단일 스레드)
-XX:+UseParallelGC    # 위와 같은 구성을 멀티 스레드로 (처리량 중시)
-XX:+UseG1GC          # region 기반, Java 9+ 기본값

이번 글에서 다룬 Mark, Sweep, Compact, Copying은 GC라는 건물의 벽돌입니다. 앞으로 만날 모든 컬렉터는 이 벽돌들을 어떤 영역에, 몇 개의 스레드로, 멈춤을 얼마나 허용하며 쌓느냐의 차이일 뿐입니다.

---

지난 글: 가비지 컬렉션 개요 — 도달 가능성과 GC의 큰 그림

다음 글: 세대별 GC — 약한 세대 가설과 Minor/Major GC

읽어주셔서 감사합니다. 😊