Mark and sweep

개요

Mark and sweep (Tracing)은 Garbage collection에서 특정 루트 객체의 일련의 참조에 의해서 도달할 수 있는 객체를 추적하고 나머지를 Garbage로 간주하는 기법으로, 가장 일반적으로 GC를 구현하기 위해서 사용되는 알고리즘이다.

객체에 대한 도달 가능성

직접 또는 다른 도달 가능한 개체의 참조를 통해 프로그램에서 하나 이상의 변수에 의해 참조되는 경우 개체에 도달할 수 있다. 모든 프로그램은 다음 두가지 방식을 통해서 객체에 도달할 수 있다.

Root: 루트 객체는 현재 스택에서 참조되는 모든 객체, 로컬 변수, 매개 변수, 전역 변수등이 포함된다.
Root에 의해서 일련의 참조과정에서 참조되는 모든 객체: Root변수가 참조하는 포인터, 그리고 그 포인터가 재귀적으로 참조하는 모든 객체들은 도달 가능하다고 간주된다.

객체에 대한 도달 가능성의 정의는 Semantic에 대한 고려 없이는 최적이 아니다. Syntactic으로는 도달 할 수 있는 객체가, Semantic적으로는 도달할 수 없는 객체일 수도 있다.

auto x = Foo();
auto y = Bar();
x = new Empty();
if (x.is_not_empty())
    x.do_something(y);
exit(0);

위의 프로그램에서 의미론적으로는 y는 쓰레기이다. 그러나 구문적으로는 y는 도달 가능성이 있는 객체로써 쓰레기로 간주되지 않는다. 이러한 프로그램의 Semantic을 분석하여 Mark and sweep를 최적화하는 것은 연구주제로써 연구되고 있다. 그러나 대부분의 Pratical한 GC들은 Syntactic을 분석하여 GC를 수행하는 접근방식을 채택하고 있다.

기본 알고리즘

주기적으로 가비지를 추적하거나, 여유 메모리가 없을때 가비지 컬렉터를 수행하는 경우가 일반적이다.

기본적인 Mark and sweep

기본적인 Mark and sweep방식에서는 메모리의 각 개체에 가비지 컬렉션 전용으로 예약된 플래그(일반적으로 단일 비트)가 있다. 이 플래그는 수집 주기 동안을 제외하고는 항상 지워집니다. 첫 번째 단계는 트리가 전체 '루트 집합'을 순회하고 루트가 가리키는 각 개체를 '사용 중'으로 표시하는 "Mark"단계이다. 루트 집합을 통해 도달할 수 있는 모든 개체가 표시되도록 해당 개체가 가리키는 모든 개체가 마킹된다.

두 번째 단계인 Sweep단계에서는 모든 메모리를 처음부터 끝까지 스캔하여 사용 중이거나 사용된 모든 블록을 검사한다. '사용 중'으로 표시되지 않은 블록은 어떤 루트에도 도달할 수 없으며 메모리가 해제된다. 사용 중으로 표시된 개체의 경우 사용 중인 플래그가 지워져 다음 사이클을 준비한다.

이 방법에는 몇 가지 단점이 있다. 가장 주목할 점은 수집 중에 전체 시스템을 일시 중단해야 한다는 것이다. 이로 인해 프로그램이 주기적으로(일반적으로 예측 불가능하게) '동결'되어 일부 실시간 및 시간에 중요한 애플리케이션을 사용할 수 없게 될 수 있다. 또한 전체 작동 메모리를 검사해야 하며, 대부분은 두 번 검사해야 하므로 페이징 메모리 시스템에 문제가 발생할 수 있다.

삼색표시

이러한 성능 문제 때문에 대부분의 최신 가비지 컬렉터는 3색 표시 추상화의 일부 변형을 통해서 구현한다.

우선 흰색, 검은색 및 회색의 세 가지 세트를 다음과 같은 규칙을 통해서 생성한다.

힌색 집합 또는 디멘티드 집합은 메모리를 재활용할 수 있는 대상이 되는 개체의 집합이다. 즉 아직 검은색 혹은 회색에 들어가지 않은 객체들을 모아놓은 집합이다. 최종적으로 회색세트가 비워지면, 힌색 집합에 남아 있는 객체들은 가비지로 간주된다.
회색 세트에는 루트에서 도달할 수 있는 모든 개체가 포함되어 있지만 "흰색" 객체에 대한 참조가 있는지 아직 검색되지 않은 객체들을 모은다. 루트에서 도달할 수 있는 것으로 알려져 있기 때문에 쓰레기 수거가 불가능하며 스캔 후 검은색 집합에 들어가게 된다.
검은색 집합은 흰색 집합의 객체에 대한 참조가 없고 루트에서 연결할 수 있는 개체 집합이다.

많은 알고리즘에서 처음에 검은색 집합은 비어 있는 것으로 시작하고 회색 집합은 루트에서 직접 참조되는 객체 집합이며 흰색 집합은 다른 모든 개체를 포함한다. 메모리의 모든 객체는 항상 정확히 세 세트 중 하나에 있다. 알고리즘은 다음과 같이 진행된다.

회색 집합에서 임의의 객체를 선택한다.
선택된 객체가 참조하는 객체를 힌색에서 회색으로 이동한다.
선택된 객체를 검은색 집합으로 이동한다.
회색 세트가 비워질 때까지 마지막 세 단계를 반복한다.
회색 세트가 비워지면, 힌색 집합에 있는 모든 객체는 가비지이다.

삼색 정리에 의해서, 검은색 집합에 있는 객체들은 힌색 집합에 있는 객체를 참조하지 않는다. (삼색 정리에 의하면, 모든 지도를 삼색으로만 색칠할 수 있다.) 3색 방식은 집합의 크기를 모니터링 함으로써, 주기적으로 가비지 컬렉션을 수행할 수 있으며, on-the-fly로 시스템을 중지하지 않고도 수행할 수 있다. 따라서 위의 기본적인 Mark and sweep방식과는 다르게, 스레딩을 통해서 Application과는 병렬적으로 작업할 수 있다는 장점이 있다.

최적화 방식

Pointer reallocation

가비지로 판별된 도달할 수 없는 객체들이 있을 경우, 가비지 컬렉터는 이 객체들을 해제하고 그 객체의 포인터를 Reuse할수도 있고, 아니면 나머지 가비지가 아닌 참조까지 모두 업데이트 하여서 객체들을 새로운 공간으로 할당하는 Reallocation방식을 사용할 수도 있다. Reallocation방식은 추가적인 Memcpy와 객체 참조에 대한 업데이트가 필요하기 때문에, 비효율적으로 보일 수 있으나, Reallocation방식은 다음과 같은 성능 이점을 제공하기 때문에 많은 GC들이 Reallocation방식을 채택하고 있다.

Free된 영역을 기록하고 검색하기 위한 추가적인 메타데이터 유지가 필요 없다. 따라서 메타데이터 유지를 위한 추가적인 메모리 오버헤드가 없다.
같은 이유로, Allocation시에 메타데이터 추적이 필요 없음으로, 빠르게 메모리 할당을 할 수 있다. 만약 Reallocation을 하지 않는다면 메모리가 파편화 되어 Free-list유지에 상당한 비용이 소요된다.
메모리를 Compact하게 사용할 수 있어서 cache efficient한 메모리 할당을 할 수 있다.

그러나 Reallocation방식은 다음과 같은 단점이 있다.

Reallocation이 일어날 경우 기존 Pointer는 무효화 되기 때문에 반드시 참조를 통한 접근만 허용해야 한다.
Pointer arithmetic이 불가능하다.
추가적인 Memcpy로 인한 메모리 오버헤드가 발생한다.

Copying vs. mark-and-sweep vs. mark-and-don't-sweep