garbage collection의 주요 알고리즘과 동작방식
Algorithm of garbage collection and its working flow
Dec 21, 2023
0. 서론
자바스크립트 엔진은 눈에 보이지 않는 곳에서 자동으로 메모리 관리를 수행한다.
원시 값, 객체, 함수 등 우리가 만드는 모든 것은 메모리를 차지한다.
C, C++과 같은 언어들은 개발자가 직접 함수를 통해 메모리를 동적으로 할당하고 제거해 줘야 한다.
하지만, Java, Python, JavaScript 같은 경우 자체 엔진에서 자동적으로 메모리를 정리해 준다.
그렇다면 JavaScript의 Garbage collecor는 사용하지 않는 메모리들을 어떻게 찾아내고 삭제할까?
지금부터 Garbage Collection의 주요한 알고리즘을 알아보자.
1. Reference Counting
Reference Counting(이하 RC)은 말 그대로 참조된 경우의 수를 카운트하는 알고리즘이다.
시작하기에 앞서 예시를 통해 참조라는 개념에 대해 이해해보자.
1.1 참조
let a = [1, 2];위 코드가 실행 될 때, 메모리 부분에서 어떻게 동작하는지 그림으로 살펴보자.
보다시피 변수 자체에 값이 들어가는 것이 아니라 변수는 메모리 주소를 참조하고 있고, 우리가 할당한 값은 메모리 안에 저장되어 있다.
이 내용을 바탕으로 아래 예시를 살펴보면,
let a = [1, 2];
let b = a;
b.push(5);
그림과 같은 결과가 나온다는 것을 알 수 있다.
변수는 메모리 주소를
참조 하고, 값은 메모리 안에 저장된다.참조의 개념에 대해 간략하게 알아봤으니 Reference Counting 알고리즘에 대해 알아보자.
알고리즘의 주요 개념은,
- RC 알고리즘을 사용할 때, 선언된 모든 객체들은 Rc라고 하는 별도의 숫자를 가지게 된다.
- 처음 선언할 때 그 숫자는 1이 된다.
- 이 카운트의 값이 0이 되는 순간 메모리에서 지워진다.
function run(){
let a = {}; // Rc(a) = 1
{
let b = {}; // Rc(b) = 1
a.test = b; // Rc(b) = 2
}
// Rc(b) = 1
}
run();
// Rc(a) = 0, remove a!
// Then, Rc(b) = 0, remove b!
- run 함수의 내부를 보면, a라는 오브젝트를 하나 선언했다. 이 때, Rc(a) = 1이 된다.
- 그리고 괄호 내부에 b라는 오브젝트를 선언했고 Rc(b) = 1이 된다.
- 그리고 a.test에 b를 할당한다. 이 때, b를 참조하는 경우가 b라는 변수와 a.test를 통해 접근이 가능하기 때문에 Rc(b) = 2가 된다.
- 중괄호를 벗어나는 순간에 b라는 변수는 블록 스코프이기 때문에 Rc - 1을 해준다. Rc(b) = 1이 된다.
- 마지막으로, run함수의 실행이 종료되는 시점에서는 a와 b가 참조하는 메모리에 접근이 불가능하기 때문에 Rc(a) = 0, Rc(b) = 0이 된다.
장점
- 컨셉이 간단하고 구현하기도 쉽다.
- 객체마다 레퍼런스 카운트를 하나씩 주고 실시간으로 계산만 하면 되기 때문이다.
- 프로그래밍 언어를 새로 만들거나, 언어에 GC기능을 추가 하려고 할 때 많이 이용된다.
단점
- GC가 제대로 동작하지 않는 예외 상황들이 존재한다.
{
let a = {}; // Rc(a) = 1
let b = {}; // Rc(b) = 1
a.test = b; // Rc(b) = 2
b.test = a; // Rc(a) = 2
}
// Rc(a) = 1 / Rc(b) = 1 ??2. Mark & Sweep
Mark & Sweep 알고리즘은 도달 가능성(reachability)이라는 개념을 사용해 메모리 관리를 수행한다.
Mark & Sweep은 다음 단계를 거쳐 수행된다.
- 가비지 컬렉터는 루트(root) 정보를 수집하고 이를 ‘mark(기억)’ 한다.
- 루트가 참조하고 있는 모든 객체를 방문하고 이것들을 ‘mark’ 한다..
- mark 된 모든 객체에 방문하고 그 객체들이 참조하는 객체도 mark 한다. 한번 방문한 객체는 전부 mark 하기 때문에 같은 객체를 다시 방문하는 일은 없다.
- 루트에서 도달 가능한 모든 객체를 방문할 때까지 위 과정을 반복한다.
- mark 되지 않은 모든 객체를 메모리에서 삭제한다.
예제 1번
let user = {
name: "John",
};
전역 변수 user는 {name: “john”}(이하 john)이라는 객체를 참조한다. john은 현재 global에서 도달가능하기 때문에 메모리에 유지한다.
만약 user의 값을 다른 값으로 덮어쓰면 참조가 사라진다.
let user = {
name: "John",
};
user = 10;
그림을 보면 user가 참조하고 있는 메모리 주소가 변경되면서 더이상 John을 참조하지 않는다. 따라서 John은 도달 불가능한 상태가 되어 메모리에서 제거된다.
예제 2번
let user = {
name: "John",
};
let admin = user;
위 코드는 admin 변수에 user를 복사한 상황이다.
이 상황에서 admin의 값을 다른 값으로 덮어써보자.
let user = {
name: "John",
};
let admin = user;
admin = 10;
위 그림처럼 John은 user라는 변수를 통해 여전히 접근이 가능하기 때문에 메모리에서 삭제되지 않는다. 이 상태에서 user를 다른 값으로 덮어쓰면 John은 메모리에서 삭제된다.
예제 3번
function marry(man, woman) {
woman.husband = man;
man.wife = woman;
return {
father: man,
mother: woman,
};
}
let family = marry(
{
name: "John",
},
{
name: "Ann",
}
);
함수 marry는 매개변수로 받은 두 객체를 서로 참조하게 하면서 ‘결혼’시키고, 두 객체를 포함하는 새로운 객체를 반환한다. 메모리 구조는 위 그림과 같이 나타낼 수 있다.
현재 상태는 모든 객체가 도달 가능한 상태다.
여기서 참조 두 개를 지우게 되면,
delete family.father;
delete family.mother.husband;
John으로 들어오는 참조는 모두 사라져 John은 도달 불가능한 상태가된다. 여기서 John에서 외부로 나가는 참조(wife)는 도달 가능성에 영향을 주지 않는다. 따라서 John은 메모리에서 제거된다.
가비지 컬렉션 후 메모리 구조는 오른쪽그림과 같다.
예제 4번
위와 같은 환경일 때, 가장 최 상단의 family의 참조를 변경하게 되면,
family = null;
그림에서 보이는 것처럼 어떠한 객체에도 도달할 수가 없다. 따라서 표시된 영역은 메모리에서 제거된다.
루트에서 페인트를 붓는다고 상상하면 이 과정을 이해하기 쉽다.
루트를 시작으로 참조를 따라가며 페인트가 채워지고, 페인트가 채워지지 않는 객체들은 모두 제거된다.
장점
- Reference Counting에서는 해결할 수 없는 문제(순환참조)를 해결할 수 있다.
단점
- GC를 돌릴 때마다 선언된 객체 전체를 살펴봐야 한다.
- 프로그램이 무거워진다.
- 최적화 과정이 필요하다.
참고
Share article
