Mark and Sweep 알고리즘이란?
Mark and Sweep(표시 후 쓸기) 알고리즘은 '더 이상 필요하지 않은 객체'가 아니라 '도달할 수 없는(unreachable) 객체'를 찾아내는 방식으로 동작합니다. 이 알고리즘은 참조 카운팅(Reference Counting) 알고리즘을 개선한 형태로, 자바스크립트 엔진에서 널리 사용되는 대표적인 가비지 컬렉션 기법입니다.
알고리즘의 3가지 핵심 단계
- 루트(Root): 일반적으로 루트는 코드에서 사용되는 전역 변수를 의미합니다. 자바스크립트에서는 window 객체가 루트 역할을 할 수 있습니다. 이 알고리즘은 전역 객체인 루트를 시작점으로 삼아 각 객체에 도달 가능한지 여부를 판단합니다.
- 이후 알고리즘은 모든 루트와 그 자식 객체들을 순차적으로 검사합니다. 검사 과정에서 조건에 따라 도달 가능한 객체는 '표시(marked)'되고, 도달할 수 없는 객체는 '표시되지 않은(unmarked)' 상태로 남습니다.
- 마지막으로 표시되지 않은 객체, 즉 도달할 수 없는 객체들은 가비지 컬렉터에 의해 메모리에서 회수됩니다.
마크(Mark) 단계
마크 단계에서는 어떤 요소가 표시되었고 어떤 요소가 표시되지 않았는지 확인할 수 있습니다. 예제 1처럼 obj1 객체에 'hello'라는 프로퍼티를 할당했다고 가정해 보겠습니다. 이 알고리즘이 사용하는 루트, 즉 전역 객체는 obj1과 그 프로퍼티 'hello'에 도달할 수 있으므로 두 값 모두 표시됩니다.
예제 1
var obj1 = {
pro1: "hello" // 루트에서 도달할 수 있으므로 표시됨
}반면 예제 2처럼 해당 객체에 null 값을 할당하면 어떻게 될까요? 새롭게 할당된 'null'은 표시되지만, 이전에 할당했던 'hello' 프로퍼티는 더 이상 도달할 수 없어 표시되지 않습니다. 따라서 마크 단계가 끝나는 시점에는 null이 할당된 객체는 표시된 상태이고, 'hello' 프로퍼티는 표시되지 않은 상태라고 결론지을 수 있습니다.
예제 2
obj1 = null // null은 표시됨(도달 가능), hello는 표시되지 않음(도달 불가)
스윕(Sweep) 단계
이름 그대로 스윕 단계는 도달할 수 없는 객체들을 '쓸어내는(sweep)' 작업을 수행합니다. 앞서 마크 단계에서 'hello' 프로퍼티가 표시되지 않은 상태, 즉 도달 불가능한 상태가 되었음을 확인했습니다. 도달할 수 없는 객체는 가비지 컬렉션 대상이 되므로, 'hello' 프로퍼티는 이 단계에서 메모리로부터 회수됩니다.
Mark and Sweep 알고리즘은 프로그램이 직접 또는 간접적으로 접근 가능한 객체들의 전체 집합을 추적(tracing)하기 때문에 '추적 가비지 컬렉터(tracing garbage collector)'라고도 불립니다.
순환 참조는 더 이상 문제가 아니다
다음 예제에서 함수 호출이 종료되면 obj1과 obj2 두 객체는 도달 가능한 어떤 것으로부터도 참조되지 않으므로 가비지 컬렉션 대상이 됩니다. 따라서 가비지 컬렉터는 obj1과 obj2가 차지하던 메모리를 해제합니다. 참조 카운팅 방식에서는 서로를 참조하는 순환 구조 때문에 메모리가 해제되지 않는 문제가 있었지만, Mark and Sweep 방식은 루트에서의 도달 가능성만을 기준으로 판단하기 때문에 이러한 순환 참조 문제를 자연스럽게 해결합니다.
예제
function f() {
var obj1 = {};
var obj2 = {};
obj1.p = obj2; // obj1이 obj2를 참조
obj2.p = obj1; // obj2가 obj1을 참조 → 순환 참조 발생
}
f();한계점
때로는 언제, 어떤 메모리를 해제할지 개발자가 직접 결정할 수 있다면 매우 편리합니다. 하지만 객체의 메모리를 해제하려면 해당 객체를 명시적으로 도달 불가능한 상태로 만들어야 하는데, 현재 자바스크립트에서는 가비지 컬렉션을 직접 트리거하는 방법이 제공되지 않습니다. 즉, 메모리 해제 시점은 오직 자바스크립트 엔진의 가비지 컬렉터가 판단할 수 있습니다.