지난 1편에 이어,
이번 글부터 본격적으로
Garbage Collection(이하 GC, 가비지 컬렉션)의 알고리즘에 대해 작성한다.
작동 방식에 따라 크게 아래 두 가지로 분류 가능한데,
1. 추적 기반 GC (Tracing Garbage Collection)
2. 참조 횟수 카운팅 GC (Reference Counting Garbage Collection)
2번부터 먼저 알아본다.
Reference Counting GC
개념
Reference Counting GC는
GC의 초기 알고리즘으로,
"Garbage를 발견하는 것"에 초점이 맞추어져 있다.
어느 한 메모리가 다른 메모리를
얼마나 많이 참조하는지 횟수를 세어서
메모리 접근 가능과 불가능을 나누는 방식이다.
예를 들어,
A 메모리가 B 메모리를 참조하면
B 메모리의 참조 횟수에 1을 더하고,
A 메모리가 B 메모리 참조를 중단하면
B 메모리 참조 횟수에서 1을 뺀다.
만약 1을 뺐을 때, 참조 횟수가 0이 되면
해당 메모리에 아무도 접근을 못 하는 것이므로
해당 메모리를 해제한다.
아래 그림을 통해 직관적으로 이해 가능하다.
장점
위 개념만 봐도 알겠지만,
이후에 소개할 타 알고리즘에 비해 구현이 매우 간단한 편이다.
또한 접근이 불가능하게 되자마자,
즉, 참조 횟수가 0이 되자마자 소멸된다는 장점도 있다.
추후 소개할 Tracing GC(추적 기반 GC)의 경우에는
실제로 접근이 불가능해지는 시점과
그러한 접근이 불가능해지는 것을 알아내는 시점이
상당히 떨어져 있는데,
Reference Counting GC 방식에서는
접근이 불가능해지자마자 바로 소멸에 들어가게 되니
소멸자 구현이 가능한 C++이나 Python 같은 언어에서 종종 채택된다.
그래서 'stop-the-world' 시간이 분산되어
실시간 작업에 거의 영향을 주지 않고 즉시 메모리에서 해제가 되지만,
아래의 단점들이 존재한다.
단점
크게 두 가지 단점이 존재한다.
첫 번째로, 오버헤드 측면이다.
위의 설명대로 구현할 경우,
모든 대입문에 참조 횟수를 변경하도록 작성해야 하는데
이러한 부분이 프로그램을 굉장히 느리게 만든다.
특히 참조 횟수를 + 하는 부분보다 - 하는 부분에서
정수 감소, 조건문, 함수 호출 등이 실행될 수 있어서
대입이 빈번히 일어나는 곳에서는
극악의 퍼포먼스가 발생할 수 있다.
그 외에도 참조 횟수를 저장함으로 인해
캐시 효율이 낮아질 수도 있다.
두 번째로, 순환 참조(Cyclic Reference) 이슈다.
단어 뜻 그대로, 메모리들이 서로 순환하며 참조한다는 것인데,
예를 들면 아래와 같다.
메모리 A가 메모리 B를 가리키고,
메모리 B가 메모리 A를 가리키면
두 메모리의 참조 횟수는 모두 1이다.
하지만 만약 다른 어떠한 메모리에서도
메모리 A나 B에 접근 가능한 루트가 없다고 가정하면,
둘 다 GC에 의해 해제되어야 한다.
그러나 메모리 A와 B 모두 서로를 참조하고 있어,
참조 횟수가 0이 아니기 때문에 해제가 불가능해져
그대로 메모리 누수가 된다.
조금은 다른 예지만,
아래 그림을 통해 순환 참조에 대해
좀 더 직관적으로 이해 가능하다.
사용 언어
현재는 PHP와 Swift 언어에서 주된 GC 기법으로
Reference Counting GC를 사용 중이다.
C++이나 Rust 같은 언어들은
선택적으로 사용할 수 있도록 기능을 제공하기도 한다.
다음 글에서는
Tracing GC에 대해 알아본다.
끝!
