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로 인한 메모리 오버헤드가 발생한다.

Generaitional GC

대부분의 프로그램에서 최근에 생성한 객체는 해제될 가능성이 매우 높다. 따라서 세대 GC는 객체를 세대로 나누고, 대부분의 주기에서 세대의 하위 집합만 Mark and sweep의 대상으로 지정한다. 객체가 나이가 먹으면 다음 세대로 승격되며, 높은 세대일 수록 GC주기를 길게 하거나, 메모리 오버헤드가 큰 상황에서만 GC를 돌린다. 이러한 방식은 휴리스틱한 접근으로, 대다수의 현대 GC들은 이 방식을 사용하고 있다.

Stop-the-world vs Incremental vs Concurrent

Stop-the-world 방식은 수집 주기를 실행하기 위해 프로그램의 실행을 완전히 중지하므로 GC가 실행되는 동안 새 개체가 할당되지 않으며, 새로운 참조가 만들어 지지도 않는다. 이 방식은 GC가 실행하는 동안 프로그램이 예측할수 없는 중지 시간을 가지는 단점을 가진다. 따라서 이 방식은 주로 Latency sensitive한 프로그램보다 일반 대화형 프로그램에 사용된다. 이 방식은 Incremental방식보다 구현이 간단하고 빠르게 동작하는 장점이 있다.

Incremental & Concurrent방식은 GC를 개별 단계로 수행하여, 각 단계 사이에 혹은 일부 단계에서 프로그램의 실행이 허용된다. Concurrent GC는 프로그램 Stack을 스캔할때 이외에는 프로그램 실행을 전혀 중지하지 않는다. 그러나 각각의 단계 처리에 대한 합은 Stop-the-world방식보다 느린것이 보통이다. 이 두 방식은 세심한 Concurrency에 대한 고려가 필요로 하기 때문에, Concurrent programming에 대한 고려가 필요하며 Scalability에 대하여 고려할 점이 존재한다.

Precise vs Conservative GC

일부 GC는 객체의 모든 포인터(참조)를 올바르게 식별할 수 있으며, 이를 precise(정확하거나 정확한) GC라 하며, 반대는 Conservative(보수) GC라고 부른다. Conservative GC들은 메모리의 임의의 비트 패턴이 포인터로 해석될 경우, 포인터가 할당된 객체를 가리킬 수 있다고 가정한다. 이 방식은 잘못된 포인터 식별로 인하여 사용되지 않는 메모리가 해제되지 않는 False positive가 발생할 수 있다. Conservative GC가 필요한 예로는 C/C++ 언어가 있는데, C 언어를 사용하면 입력된 (보이드가 아닌) 포인터를 입력되지 않은 (보이드가 아닌) 포인터로 캐스팅할 수 있으며, 그 반대의 경우도 발생함으로, Precise한 추적보다는 Conservative한 GC를 사용하여서 포인터를 수정해야 한다. Precise GC는 보통 언어와 함께 디자인 되는 경우가 많으며 언어의 Type정보를 통하여서 Precise하게 GC를 수행한다.

GC 성능에 영향을 미치는 요인

보통 GC의 성능과 메모리 사용량은 Trade-off를 가지는 경우가 많다. Application의 성능 특성과, 요구사항에 따라서 다양한 GC들을 적용시킬 수 있으며, 이에 따라서 성능과 메모리 오버헤드를 최적화 시킬 수 있다. 예를 들어서 임베디드 환경에서는 메모리 사용량을 최적화 해야 하는 경우가 많음으로, GC를 사용하게 될 경우에 성능의 희생으로 메모리 사용량을 최소화시킬 수 있다. 또한 Real-time system에서 사용하기 위해서 GC가 사용하는 리소스의 최대양을 제한하여 사용할 수도 있으며, 이러한 시스템에서는 최악의 경우에도 일정 수의 Computing resource가 main application에 사용됨을 보장한다. 또한 멀티코어 아키텍쳐에서는 Concurrent thread가 GC에 의하여 Critical한 성능 하락을 방지하도록 non-blocking concurrent GC를 사용하는 경우도 있다. 관련해서 각각의 Application특징마다 서로 다른 특성을 가지는 GC들이 개발 및 연구되고 있다.

같이 보기

1. Garbage collection
2. Use after free

참조

1. https://papago.naver.net/website?locale=ko&source=en&target=ko&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FMark%25E2%2580%2593compact_algorithm
2. https://blog.siner.io/2021/12/26/garbage-collection/