Tracing Garbage Collection
애플리케이션의 메모리는 OS 로부터 빌려온 자원이다. 다시말해 OS로부터 할당받아 사용하고 사용한 후 반환해야한다. 사용량은 제한적이고 제대로 사용하지 못하면 OS 가 애플리케이션을 종료시켜 시스템 전반으로 문제가 퍼지는 것을 방지한다.
Garbage Collection
프로그래밍에서 메모리는 수동으로 관리되기도 하고 자동으로 관리되기도 한다. 수동 메모리 관리는 C 언어가 대표적이다. C 언어는 코드에서 malloc() / free() 를 통해 개발자가 메모리를 할당하고 반환한다. 이런 방식은 유연하지만 사용이 까다로워서 종종 코딩에서 실수가 발생한다.
이와 달리, 자동 메모리 관리기법은 메모리를 자동으로 할당하고 사용이 끝난 메모리를 알아서 반환한다. 많은 언어 런타임들은 자동 메모리 관리 기능을 탑재하고 있으며 Garbage Collection(GC) 은 이런 자동 메모리 관리 기법 중 하나다.
메모리를 효율적으로 해제하기 위해, 동작은 일시적으로 중단된다. 이는 프로그램의 동작이 메모리의 할당, 해제, 이동 등의 작업으로 구성되기 때문이다. 따라서, 메모리를 정리하는 작업(Garbage Collection, GC)은 성능에 부정적인 영향을 미칠 수 있으며, 이를 “Stop-the-World”라고도 한다.
GC 알고리즘은 이러한 성능 저하를 최소화하기 위해 지속적으로 개선되어 왔다. 특히, 최신 GC 알고리즘들은 메모리 관리의 효율성을 높이고 애플리케이션의 일시 중단 시간을 줄이기 위해 병렬 처리, 증분 처리(incremental), 또는 백그라운드 처리를 사용하는 경우가 많다.
Tracing Garbage Collection
Tracing GC 는 여러 언어에서 가장 널리 사용되는 수집 기법이어서, 보통 GC 라 하면 이 기법을 이야기한다.
도달범위 (Reachability)
Tracing Garbage Collection 기법은 뿌리에서부터 각 객체까지의 “도달범위"를 추적한다. 출발은 루트집합(Set of roots)이라 칭하는데, 이들은 call stack 내의 지역변수, 파라미터 또는 전역변수라 할수 있다. 도달 대상은 이 변수들이 직접 참조하는 객체들이거나, 참조의 참조, 즉 간접 참조하는 객체들이다. 이 도달 범위에 없는 객체들은 더이상 사용되지 않으므로 GC 에서 버려질 수 있는 것이다.
도달범위:
- 함수 인자로 받은 객체 → 그 객체가 내부적으로 참조하는 다른 객체 → 계속 이어지는 간접 참조들
Tracing GC 의 종류와 발전
- Mark and Sweep
- 1960년대 개발
- Scavenge
- 두개의 영역으로 분리한 후 한 영역의 객체를 다른 영역으로 복사한 다음, 한 영역 전체를 비움
- Generational Hypothesis
- 휴리스틱
- Generational Scavenge
- 1980년대 개발
Mark-and-Sweep
mark-and-sweep 은 1960년대 개발된 방식이다. 객체의 닿을 수 있음을 평가(Mark)하고, 닿지 않는 객체는 지우는(Sweep) 기법이다. 이 두단계를 분리하여 수행한다. 전체 객체에 대해 진행하기 때문에 성능이 느린것으로 평가된다. 또한 객체를 지우면 듬성듬성하게 메모리에 빈 영역이 발생(단편화, fragmentation)한다.
Scavenge
Scavenge 는 메모리를 두개의 영역(semispaces)으로 분리하고, 도달가능성을 평가 후 도달할 수 있는 객체는 다른 영역으로 복사하는 기법이다. 복사 절차가 끝나면 원본 영역에 남은 데이터는 모두 쓰레기로 간주할 수 있게 된다. 객체마다 순회하며 sweep 할 필요가 없고 공간 전체를 반환할 수 있으므로 mark-and-sweep 보다 좋은 성능을 보이고 단편화 문제에서도 비교적 자유롭다.
세대가설과 Scavenge
1984년에는 Generational Scavenge 알고리즘이 발표되었는데, 이 알고리즘은 세대가설(Generational Hypothesis) 이라는 휴리스틱으로 동작한다. 이 가설은 할당된지 얼마 되지 않은 - 나이가 어린 - 객체들은 금방 소멸하고 시간이 오래된 - 나이가 많은 - 객체는 상대적으로 늦게 소멸한다는 가설이다. 따라서 가장 젊은 객체들이 위치할 공간과 나이 많은 객체들이 위치할 공간을 분리하고, GC 가 동작하는 주기도 다르게 가져가면 성능과 용량 사이에서 더 만족할 만한 결과를 얻을 수 있다는 것이다. 특히 나이 어린 객체들의 공간을 수거하는 작업을 Minor Collection, 나이 많은 객체들의 공간을 수거하는 작업을 Major Collection 이라 부른다.
현재 많은 수의 언어엔진들이 Generational Scavenge 알고리즘을 채택하고 있다. JavaScript의 크롬 V8 엔진은 이러한 Generational Scavenge의 대표적인 사례다:
- Minor Collection: Young 세대의 메모리를 대상으로 Scavenge 알고리즘을 적용하여, 새롭게 생성된 객체 중 사용되지 않는 객체를 빠르고 효율적으로 제거한다.
- Young 세대의 크기가 작아 GC가 자주 발생하지만, 이로 인해 메모리 회수가 빠르고 비용이 낮다.
- 살아남은 객체는 Old 세대로 승격(promotion)된다.
- Major Collection: Old 세대의 메모리를 대상으로 mark-and-sweep 알고리즘을 사용하여 도달 가능한 객체만 남기고 나머지 객체를 제거한다.
- Old 세대에서는 객체 수명이 길어 GC 발생 빈도가 적으며, 대규모 메모리를 정리하는 과정에서 Stop-the-World 시간이 상대적으로 길어질 수 있다.
- 이를 보완하기 위해 병렬 처리(parallelism)와 점진적 수집(incremental GC) 같은 최적화 기술을 적용하고 있다.