동시성 마크-스윕

동시성 마크-스윕의 마크 단계는 프로그램의 실행과 동시에 진행되며, 루트 셋으로부터 시작하여 도달 가능한 모든 라이브 오브젝트를 식별하는 과정이다. 이 단계의 핵심 목표는 사용 중인 메모리와 사용되지 않는 메모리를 구분하는 것이며, 가비지 컬렉터는 애플리케이션 스레드가 메모리를 계속 읽고 쓰는 동안 백그라운드에서 이 작업을 수행한다.

마크 단계는 일반적으로 트라이컬러 표기법을 사용하여 오브젝트의 상태를 추적한다. 초기에는 모든 오브젝트가 흰색(미방문)으로 표시된다. 루트 셋에서 시작하여 그래프 순회를 통해 접근 가능한 오브젝트들은 회색(처리 중)으로, 최종적으로는 검은색(처리 완료 및 도달 가능)으로 표시된다. 이 과정에서 쓰기 배리어가 중요한 역할을 하여, 애플리케이션 스레드가 검은색 오브젝트를 수정하여 흰색 오브젝트를 참조하게 될 경우, 해당 참조를 기록하여 마킹이 누락되지 않도록 보장한다.

이 방식의 주요 장점은 프로그램의 실행을 완전히 멈추지 않고 가비지 컬렉션을 진행할 수 있다는 점이다. 이를 통해 스톱-더-월드로 인한 긴 일시 정지 시간을 크게 줄일 수 있어, 대화형 애플리케이션이나 실시간 시스템에서 유리하다. 그러나 마킹이 진행되는 동안 애플리케이션의 힙 상태가 계속 변경되기 때문에, 알고리즘이 정확성을 유지하기 위해 추가적인 동기화 메커니즘이 필요하며, 이는 구현 복잡도를 증가시키는 요인이 된다.

스윕 단계는 마크 단계에서 표시되지 않은, 즉 루트 셋으로부터 도달할 수 없는 모든 객체를 메모리에서 해제하는 단계이다. 이 단계는 가비지 컬렉션 주기의 후반부를 담당하며, 실제로 사용되지 않는 메모리 공간을 회수하여 메모리 할당자가 재사용할 수 있도록 만든다.

스윕 단계의 핵심 작업은 힙 전체를 순회하며 각 메모리 블록의 상태를 확인하는 것이다. 마크 단계에서 '활성' 또는 '도달 가능'으로 표시된 객체는 그대로 두고, 표시되지 않은 객체가 차지하고 있는 공간을 '사용 가능 목록'에 추가한다. 이 과정에서 메모리 단편화가 발생할 수 있으며, 일부 구현에서는 인접한 빈 공간을 병합하는 메모리 압축 작업을 함께 수행하기도 한다.

동시성 마크-스윕에서 스윕 단계는 일반적으로 마크 단계와 병렬로 실행될 수 있으며, 애플리케이션 스레드와도 동시에 수행된다. 이를 위해 트라이컬러 표기법을 사용하여 객체의 상태를 명확히 구분하며, 쓰기 배리어를 통해 애플리케이션 스레드가 스윕 중인 객체를 실수로 참조하지 않도록 보호한다. 이렇게 함으로써 애플리케이션의 실행이 완전히 멈추는 스톱-더-월드 현상을 최소화한다.

스윕이 완료되면, 회수된 메모리는 새로운 객체 할당 요청을 처리하는 데 즉시 사용될 수 있다. 이 단계는 시스템의 전체 메모리 사용량을 줄이고 메모리 부족 오류를 방지하는 데 직접적으로 기여한다.

트라이컬러 표기법은 동시성 마크-스윕 알고리즘에서 사용되는 핵심 기법으로, 가비지 컬렉션 과정 중 객체의 상태를 세 가지 색상으로 구분하여 추적한다. 이 표기법은 가비지 컬렉션 스레드와 애플리케이션 스레드가 동시에 실행되는 동안에도 메모리 상태를 안전하게 관리할 수 있도록 한다. 각 색상은 객체의 가비지 컬렉션 관련 상태를 나타내며, 일반적으로 흰색, 회색, 검은색으로 표현된다.

흰색 객체는 아직 가비지 컬렉터에 의해 조사되지 않았거나, 조사가 끝난 후에도 루트 셋으로부터 도달할 수 없는 가비지로 판단된 객체를 의미한다. 회색 객체는 가비지 컬렉터가 방문은 했으나, 해당 객체가 참조하는 다른 객체들은 아직 조사되지 않은 상태를 나타낸다. 검은색 객체는 가비지 컬렉터가 완전히 조사를 마쳤고, 이 객체가 참조하는 모든 객체들도 조사가 완료된 안전한 상태임을 표시한다.

이 방법의 핵심은 애플리케이션 스레드가 힙 메모리를 수정하는 동안에도 컬러 불변식을 유지하는 데 있다. 주요 불변식 중 하나는 "검은색 객체는 흰색 객체를 참조하지 않는다"는 규칙이다. 만약 애플리케이션 스레드가 검은색 객체의 필드를 수정하여 새로 생성된 흰색 객체나 기존의 흰색 객체를 가리키도록 하면, 이 불변식이 깨지게 된다. 이를 해결하기 위해 쓰기 배리어가 사용되어, 이러한 참조 변경을 가비지 컬렉터가 인지하고 해당 흰색 객체를 회색 객체로 다시 표시하도록 한다.

트라이컬러 표기법을 통해 동시성 마크-스윕 알고리즘은 애플리케이션의 실행을 길게 중단시키지 않으면서도, 루트 셋으로부터 도달 가능한 모든 라이브 객체를 정확하게 표시할 수 있다. 마크 단계가 완료되면, 여전히 흰색으로 남아 있는 객체들은 어떤 루트 셋에서도 도달할 수 없는 가비지로 최종 판단되어, 이후의 스윕 단계에서 회수된다. 이 방식은 스톱-더-월드 현상을 현저히 줄여 실시간 시스템이나 대화형 애플리케이션의 응답성을 향상시키는 데 기여한다.

동시성 마크-스윕 알고리즘에서 읽기/쓰기 배리어는 애플리케이션 스레드(또는 사용자 스레드)와 가비지 컬렉터 스레드가 동시에 메모리 객체를 접근할 때 발생할 수 있는 문제를 방지하는 핵심 메커니즘이다. 이 배리어는 애플리케이션 코드가 실행되는 동안 객체 참조를 읽거나 쓸 때 특별한 검사 코드를 삽입하여, 가비지 컬렉션의 마크 단계가 진행 중임에도 불구하고 메모리 상태의 일관성을 유지하도록 보장한다.

읽기 배리어는 주로 마크 단계에서 활성화된다. 애플리케이션 스레드가 힙 메모리로부터 객체 참조를 읽을 때마다, 읽기 배리어 코드가 실행되어 해당 참조가 아직 마크되지 않았다면 즉시 마크하는 작업을 수행한다. 이는 애플리케이션 스레드가 가비지 컬렉터가 아직 발견하지 못한 라이브 객체를 접근하는 순간, 그 객체를 라이브로 표시함으로써 실수로 수집되는 것을 막는다. 반면, 쓰기 배리어는 애플리케이션 스레드가 객체 필드에 새로운 참조를 기록할 때 실행된다. 이는 주로 객체 그래프의 구조가 변경될 때 발생하며, 예를 들어 카드 테이블과 같은 기법을 업데이트하여 변경된 메모리 영역을 기록함으로써 후속 가비지 컬렉션 사이클의 효율성을 높이는 데 기여한다.

이러한 배리어의 구현은 런타임 시스템과 컴파일러에 깊이 통합되어 있다. 자바 가상 머신의 핫스팟 JIT 컴파일러나 .NET CLR의 JIT 컴파일 과정에서는 배리어 코드를 최적화하여 성능 오버헤드를 최소화하려고 노력한다. 배리어의 존재는 동시성 가비지 컬렉션이 스톱-더-월드 현상을 극복할 수 있게 해주지만, 그 자체로 인해 애플리케이션 실행 속도에 약간의 지연을 초래한다는 트레이드오프가 존재한다.

동시성 마크-스윕의 가장 큰 장점은 애플리케이션의 실행을 완전히 멈추지 않고 가비지 컬렉션을 수행할 수 있다는 점이다. 이는 스톱-더-월드 방식의 마크-스윕이나 참조 카운팅과 대비되는 특징으로, 가비지 컬렉션 작업이 백그라운드에서 병렬적으로 이루어진다. 결과적으로 애플리케이션의 응답 지연 시간이 현저히 줄어들어, 사용자와의 상호작용이 중요한 데스크톱 애플리케이션이나 실시간 처리가 요구되는 서버 환경에서 유리하다.

또한, 이 방식은 힙 메모리의 단편화를 방지하는 데 효과적이다. 스윕 단계에서 사용되지 않는 객체들을 정리하고 연속된 여유 공간을 확보함으로써 메모리 사용 효율을 높인다. 이는 장시간 실행되는 시스템에서 메모리 누수를 방지하고 안정성을 유지하는 데 기여한다. 자바 가상 머신과 닷넷 프레임워크의 가비지 컬렉터는 이러한 장점을 활용하여 복잡한 메모리 관리를 개발자로부터 추상화한다.

마지막으로, 트라이컬러 표기법과 읽기 배리어 같은 기법을 통해 동시성을 안전하게 구현한다는 점도 장점이다. 이는 컬렉션 과정에서 발생할 수 있는 레이스 컨디션을 방지하고, 애플리케이션 스레드와 가비지 컬렉터 스레드가 서로의 작업을 방해하지 않도록 조율한다. 따라서 멀티코어 프로세서 시스템에서 자원을 효율적으로 사용하며 성능을 극대화할 수 있다.

동시성 마크-스윕의 가장 큰 단점은 스톱-더-월드 현상을 완전히 제거하지 못한다는 점이다. 마크 단계와 스윕 단계는 애플리케이션 스레드와 병행하여 실행되지만, 특정 시점에서는 여전히 짧은 정지가 필요할 수 있다. 예를 들어, 루트 셋을 식별하거나 트라이컬러 표기법에서 특정 상태 전환을 안전하게 수행하기 위해 애플리케이션 실행을 잠시 멈추어야 하는 경우가 발생한다. 이로 인해 완벽한 실시간 시스템에는 부적합할 수 있다.

또한, 알고리즘이 복잡하여 구현 난이도가 높고, 가비지 컬렉터와 애플리케이션 스레드가 동시에 메모리를 접근하기 때문에 추가적인 동기화 오버헤드가 발생한다. 읽기 배리어나 쓰기 배리어와 같은 메커니즘을 사용하여 데이터 일관성을 유지해야 하며, 이는 프로그램 실행 속도를 저하시키는 요인이 된다. 특히 배리어가 빈번하게 호출되는 환경에서는 성능 저하가 두드러질 수 있다.

마지막으로, 동시성으로 인해 플로팅 가비지 문제가 발생할 수 있다. 마크 단계가 진행되는 동안 애플리케이션 스레드가 객체 참조 관계를 변경하면, 이미 살아있다고 표시된 객체가 실제로는 더 이상 참조되지 않는 상황이 생길 수 있다. 이렇게 수집되지 못하고 남는 가비지는 다음 가비지 컬렉션 사이클까지 메모리를 점유하게 되어 메모리 사용 효율을 낮춘다.

동시성 마크-스윕과 대비되는 전통적인 방식은 스톱-더-월드 마크-스윕이다. 이 방식은 가비지 컬렉션을 수행하는 동안 애플리케이션의 모든 실행 스레드를 완전히 정지시키는 특징을 가진다. 이 정지 시간 동안 가비지 컬렉터는 안전하게 메모리 공간을 탐색하고 사용하지 않는 객체를 식별하며 회수한다.

이 방식의 가장 큰 장점은 구현이 단순하고 안정적이라는 점이다. 애플리케이션 스레드가 실행을 멈추기 때문에 힙 메모리의 상태가 변하지 않아, 객체 간의 참조 관계를 명확하게 파악할 수 있다. 이로 인해 동시성이나 병렬성을 고려하지 않아도 되어 가비지 컬렉션 알고리즘의 설계와 디버깅이 상대적으로 용이하다.

그러나 모든 스레드의 실행을 중단시키기 때문에 발생하는 정지 시간은 명백한 단점이다. 이 정지 시간은 힙의 크기나 살아 있는 객체의 수에 비례하여 길어질 수 있으며, 이는 실시간 시스템이나 사용자 상호작용이 중요한 GUI 애플리케이션에서 응답 지연을 유발할 수 있다. 이러한 단점을 해결하기 위해 점진적 가비지 컬렉션이나 동시성 마크-스윕과 같은 더 발전된 기법들이 연구되고 적용되었다.

세대별 가비지 컬렉션은 객체의 생존 기간에 대한 경험적 관찰, 즉 대부분의 객체는 생성 후 매우 짧은 시간 내에 더 이상 사용되지 않는다는 사실에 기반한 가비지 컬렉션 알고리즘이다. 이 방식은 힙 메모리를 두 개 이상의 세대로 나누어 관리하며, 일반적으로 젊은 세대와 늙은 세대로 구분한다. 새로 생성된 객체는 대부분 젊은 세대에 할당되고, 여러 번의 가비지 컬렉션 사이클을 거쳐 생존한 객체만이 늙은 세대로 승격된다.

이 알고리즘의 핵심은 각 세대에 대해 서로 다른 빈도와 전략으로 가비지 컬렉션을 수행하는 것이다. 젊은 세대는 객체 할당이 빈번하고 대부분의 객체가 금방 가비지가 되기 때문에, 마이너 GC라고 불리는 비교적 빠르고 빈번한 수집이 이루어진다. 반면, 늙은 세대는 객체 생존률이 높아 풀 GC 또는 메이저 GC라고 불리는 덜 빈번하지만 더 오래 걸리는 수집이 수행된다. 이렇게 함으로써 애플리케이션의 전체 정지 시간을 줄이고 처리량을 높일 수 있다.

세대별 가비지 컬렉션은 자바 가상 머신, .NET CLR, 그리고 여러 스크립트 언어의 런타임 시스템에서 널리 채택된 기본 메모리 관리 전략이다. 동시성 마크-스윕 알고리즘이 가비지 수집 작업을 애플리케이션 실행과 병행하는 데 초점을 맞춘다면, 세대별 가비지 컬렉션은 수집의 효율성을 높이기 위해 메모리 영역을 분할하고 차별화된 관리 정책을 적용한다는 점에서 차이가 있다. 두 접근법은 상호 배타적이지 않으며, 현대의 많은 가비지 컬렉터는 세대별 구분과 동시성 수집 기법을 결합하여 사용하기도 한다.