쓰레기 수집

 


1. 개요
2. 작동 방식에 따른 분류
2.1. 추적 기반 쓰레기 수집
2.1.1. 점진적 쓰레기 수집
2.1.2. 세대별 쓰레기 수집
2.1.3. 현황
2.2. 참조 횟수 카운팅 쓰레기 수집
3. 한계
4. 유사품
5. 쓰레기 수집이 적용된 프로그래밍 언어


1. 개요

Garbage Collection, GC. 영어를 그대로 읽어 가비지 컬렉션이라고도 부른다.
메모리 관리 방법 중 하나로, 프로그래머가 동적으로 할당한 메모리 영역 중 더 이상 쓰이지 않는 영역을 자동으로 찾아내어 해제하는 기능이다. 존 매카시가 1959년에 LISP의 메모리 관리를 위해 처음 만들었다고 알려져 있다.
옛날의 언어들은 BASIC처럼 동적인 메모리 할당 기능이 아예 없거나[1] FORTRAN이나 C처럼 프로그래머가 할당한 뒤 수동으로 해제까지 해 줘야 하는 방식이었는데, 사람이 하는 일이 항상 완벽할 수는 없는지라 메모리를 할당해놓고 필요없어진 뒤에도 해제를 안 해서 메모리 누수가 생기거나, 혹은 거꾸로 해제했던 메모리를 실수로 다시 사용하거나, 해제했던 메모리를 또 해제한다거나 하는 온갖 실수가 일어나 수많은 버그가 양산되곤 했다. 더욱이, 일반적으로 버그는 재현가능하고 오류가 있는 부분으로부터 가까운 곳에서 터져야 잡기 쉬운데, 메모리 관련 버그는 한참 떨어진 곳에서 터지는 데다가 재현불가능한 경우도 있어서 프로그래머에게 지옥같은 디버깅을 선사해준다.
그리고 이러한 문제를 해결하기 위해서 제시된 것이 쓰레기 수집이다. 보통 쓰레기 수집 기능을 채택한 언어의 경우 프로그래머에게 직접적인 메모리 할당과 해제를 하게 하는 대신에 쓰레기 수집기에서 제공하는 할당과 해제를 사용하게 하여 프로그램이 실행되는 중간중간에 쓸모가 없어진 메모리, 즉 쓰레기를 알아서 수집한다.

2. 작동 방식에 따른 분류


2.1. 추적 기반 쓰레기 수집

Tracing Garbage Collection. 가장 많이 사용되는 쓰레기 수집 기법으로 대부분 경우에 다른 수식어 없이 쓰레기 수집이라고 언급되면 이 방식을 말하는 것이다.
추적 기반이라는 이름답게 프로그램을 실행하다가 특정한 타이밍에 현재 할당된 모든 메모리를 조사하여 그것이 현재 접근 가능한지 불가능한지 분류한 뒤, 접근이 불가능한 메모리를 쓰레기라고 간주하여 해제시키는 방식이다. 보통 항상 접근 가능한 메모리를 root라고 하는데, 여기서부터 검사를 시작하여 메모리가 참조하는 메모리를 확인하는 것을 반복하여 접근 가능/불가능을 나누게 된다.
위 설명 그대로 구현하는 방법 중 naïve mark-and-sweep이 가장 단순한 방식이다. 이 방법은 프로그램 실행 중 적당한 타이밍에 GC를 실행시켜 접근 가능한 메모리에 마킹(mark)을 한 후 마킹이 안 된 메모리는 전부 할당 해제(sweep)하는 방식이다. 이 방식대로면 부가적인 작업 없이도 접근 가능/불가능을 완벽하게 분류해서 해제하는 것이 가능하지만, 중간에 메모리가 변경되면 마킹을 다시 해야하기 때문에 프로그램을 통째로 정지(stop-the-world)시켜야 한다. 이 때문에 이 방식을 채택하면 프로그램이 실행되는 도중에 잠깐 멈추는 시간이 생긴다.
실시간으로 빠르게 동작해야 하는 프로그램에서 뚝뚝 끊기는 것은 큰 단점이다. 그래서 이를 개선하기 위해 한번에 처리하는 대신 조금씩 조금씩 수집을 하거나(점진적), 객체의 사용 시간을 계산해 다른 영역으로 나누어 수집하는 방식(세대별)을 사용하게 된다.

2.1.1. 점진적 쓰레기 수집

점진적 쓰레기 수집(Incremental Garbage Collection)은 마킹과 해제를 한번에 하지 않고 여러 번에 걸쳐서 수행하는 방식을 말한다. 이렇게 하면 프로그램을 통째로 정지하는 것에 비해 수집과 해제라는 한 사이클에 걸리는 시간은 더 오래 걸릴 수 있지만, 한번 GC를 수행할 때 프로그램이 정지하는 시간은 줄일 수 있다.
위에서 설명한 mark-and-sweep에서도 점진적 쓰레기 수집을 어느정도 적용 가능하다. 마킹이 끝난 뒤에 접근이 불가능하다고 알려진 메모리는 절대 다시 접근 가능해질 수 없다. 따라서 해당 메모리의 할당 해제는 언제 해도 상관 없으므로 여러번에 걸쳐서 수행해도 된다.
다만, 마킹을 점진적으로 하려면 삼색기법 등의 다른 방법을 동원해야 한다.
삼색기법(tri-color marking)은 기존에 접근 가능/불가능이라는 2가지로만 마킹을 했던 것과 달리 해당 메모리 내부 조사 여부에 따라 추가적으로 나눠서 3가지로 마킹한다. 보통은 접근 가능한지 알 수 없는 메모리를 흰색, 접근 가능하지만 해당하는 메모리에서 참조하는 메모리의 마킹을 하지 않은 경우 회색, 접근 가능하며 해당 메모리가 참조하는 메모리의 마킹도 끝났으면 검은색으로 마킹을 한다. 처음에는 root를 조사하다가 흰색인 메모리를 발견하면 회색으로 마킹을 한다. root를 모두 마킹했으면 회색으로 마킹된 메모리를 조사하여 해당 메모리가 참조하는 모든 메모리를 회색으로 마킹을 한다. 이 작업이 끝나면 처음 회색이었던 메모리를 검은색으로 바꾼다. 만약 회색으로 마킹된 메모리가 존재하지 않으면 모두 흰색이나 검은색일 것이고, 접근 가능 여부가 결정된다. 이런 식으로 하면 임의로 GC를 중단하여도 다음번에 회색인 메모리부터 다시 조사하면 되므로 여러번에 걸쳐서 GC를 수행할 수 있다.
하지만 이 경우에도 마킹과 마킹 중간에 메모리 내의 참조가 수정이 되면 잘못 마킹되는 것이 생길 수가 있다. 예를 들어서 root가 A를, A가 B를 참조하며, A 외에 B로 접근 가능한 메모리가 없다고 하자. 이 상태에서 GC를 수행하여 A, B가 검은색으로 마킹되고 GC가 정지했다고 하자. 이후 다시 GC가 수행되면 할당 해제를 해야하는데, 다음 GC 수행 전에 흰색으로 마킹된 상태인 C에 대해, A가 B에 대한 참조를 제거하고 C를 참조하게 바꾼다고 해보자. 그러면 B는 접근이 불가능한데 검은색이고 C는 접근 가능한데 흰색이다. 이 문제를 해결하기 위해 보통은 read-barrier나 write-barrier를 사용하여 root 메모리에 읽거나 쓰는 것에 제약을 둔다. 보통은 읽는 것보다는 쓰는 것이 적게 일어나므로 write-barrier가 사용된다. 예시로 위의 경우에는 A의 참조가 C가 되도록 씌어진 것이므로, C의 마킹을 회색으로 바꾸면 된다. 그러면 B는 당장 할당해제 되지는 않지만 적어도 C가 해제되는 일은 없앨 수 있다.
마킹을 하지 않고 아예 메모리를 옮겨버리는 방법도 있다. Cheney's Algorithm이 바로 그 대표적인 예시이자 대표적인 Copying GC 알고리즘이다. 이 방식은 처음에 메모리를 두 개의 같은 크기의 공간으로 나눠서 할당을 하고 시작한다. 하나를 A, 하나를 B라고 하면, 처음에는 모든 메모리를 A에 할당을 한다. 그러다가 A가 가득 차는 등으로 인해 GC가 실행되면 A에서 접근 가능한 메모리를 전부 B로 복사한다. 이 과정이 끝나면 B에는 A에서 접근 가능한 메모리들의 사본만이 있게 되고 A는 메모리를 비워버린다. 그 다음에는 B에 할당을 하다가 GC가 실행되면 A로 복사하고...를 반복하게 된다. 이 방식에서도 조사 중 접근 가능한 것을 바로바로 옮겨버리면 어디까지 조사했는지 알 수 있으므로 점진적으로 GC를 수행할 수 있다. 가장 큰 장점은 메모리를 재배열 할 수 있다는 것이다. 물론 위 삼색기법도 메모리 재배열이 불가능한 것은 아니지만, 이 방식은 GC가 완료되면 새로운 공간에 단편화 없이, 접근 가능한 순서에 가깝게 재배열이 되기에 캐시 효율이 높아지게 된다. 그러다보니 세대별 GC와 같이 비교적 많이 사용되는 방식이다. 또한 아예 메모리를 할당해두고 시작하기 때문에 힙 영역의 메모리 할당을 스택처럼 빠르게 할 수 있다는 장점도 있다. 하지만 메모리 공간을 많이 사용하게 되며, 복사를 해야되기 때문에 메모리의 주소가 바뀌어 버리므로 포인터를 이용한 접근을 포기하거나 주소 바뀔 때마다 모든 메모리의 주소를 갱신해야하며, 복사하는 과정에서의 오버헤드도 무시하긴 힘들다는 단점도 있다.
이 방법을 이상하게(?) 활용하는 경우가 바로 Scheme의 R5RS 구현체 중 하나인 Chicken Scheme이다.# 이 녀석의 특징이라면 함수를 호출만 하고 리턴을 하지 않은 채로 콜스택에 계속 쌓는다. 보통 힙에 동적할당 하는 것도 alloca등을 이용해서 스택에 정적할당 시켜버리는 방식을 사용한다. 그러다가 스택이 터지기 직전쯤에 이걸 중단하고 다음에 호출할 함수들을 longjmp로 호출을 시작한 스택프레임까지 점프해버린다. 이 때 스택에 있는 메모리에 대해 GC를 실행하여 살아있는 객체들을 힙으로 옮기게 된다. 이렇게 하는 이유는 몇가지 있는데, C 표준에서 꼬리 재귀 최적화를 지원하지 않다보니 이를 trampoline(다른 함수를 순서대로 계속 호출해주는 함수를 만들고, 그 내부에서 실행되는 함수가 다음에 호출되는 함수를 반환해서 꼬리재귀를 구현하는 방식) 없이 구현하기 위함도 있고, 아래의 세대별 GC를 구현하기 위한 것도 있다.

2.1.2. 세대별 쓰레기 수집

위 같은 방법들이 제시되던 중, 객체에 메모리를 할당해서 더 안 쓰는 쓰레기가 될 때까지 걸리는 시간을 추적했을 때 대부분의 객체는 잠깐 쓰고 금세 버려지며, 반대로 오래 살아남아서 쓰이는 경우는 그렇게 많지 않다는 경향을 발견했다.
따라서 위 경향에 맞추어 잠깐 쓰고 사라져도 되는 객체를 상대적으로 크기가 작은 New 영역에 할당하고, New 영역에서 기준 시간 이상으로 오래 살아남은 객체가 있다면 Old 영역으로 이동시켜 "세대" 구분을 하는 방법이 사용되고 있다.[2] 대부분의 쓰레기는 New 영역에서 발생하므로, 상대적으로 작은 영역만 추적하면 적은 시간과 비용만 들여서 필요한 메모리를 짧은 시간 안에 확보할 수 있는 것이다.
이 세대를 나누는 기준은 구현마다 상당히 다른 편이다. 위의 Chicken Scheme처럼 스택영역을 New로 쓸 수도 있는 것이고, 힙에 임의로 할당해서 쓸 수도 있다. 이 크기는 보통 해당 플랫폼이나 언어가 최소로 필요로 하는 메모리보다 조금 많게 잡는 편이다. 몇몇 구현의 경우에는 New/Old로의 2개가 아니라 임의의 갯수만큼 나누는 경우도 있다. 예를 들어서 맨 처음 할당된 Old를 0세대, 그 다음을 1세대, ..., 그 다음을 n세대 처럼 말이다.
순수 함수형 언어의 경우에는 이 방식을 조금 특이하게 이용할 수 있다. 다른 언어와 달리 순수 함수형 자료구조에서는 값이 불변이므로 어떤 시점에서 생성된 객체가 이후에 생성될 객체를 가리킬 수가 없다. 즉, 어떤 세대의 값을 참조하는 것은 그 세대나 그 이후 세대밖에 없는 것이다. 이러한 특성을 이용하여 GC의 수행 속도를 올릴 수도 있다.
이렇게 전체를 수집하는 Major-GC와 New 영역만 수집하는 Minor-GC로 나눠서 GC를 수행할 수 있고, 위의 Cheney's Algorithm을 접목하여 단편화를 줄일 수도 있는 등 여러 모로 이점이 많기에 추적 기반 GC를 사용하는 현재의 많은 언어들(Java, C\#, Go 등)은 이 기법을 사용하고 있다.

2.1.3. 현황

GC를 제공하는 대부분의 언어가 이 Tracing GC를 채택하고 있다. JVM이나 .NET Framework 등의 가상머신이라던가 Python이나 Ruby, Perl 등 스크립트 언어들도 이를 사용하며, OCaml, Go 등의 네이티브로 컴파일되는 언어도 쓰레기 수집 기능을 사용한다.
한편 꼭 필요한 경우 완전한 비동기 GC를 만드는 것도 가능하기는 하다. Erlang의 가상레지스터인 BEAM의 경우가 그러한데, 메모리를 마이크로 프로세스라는 작업 단위로 쪼개서 할당하고 각 마이크로 프로세스 사이에 공유메모리를 엄격하게 통제하고 모든 변수에 불변성을 주어서 관리비용을 최대한 줄인 결과 하드웨어적인 가용자원만 확보되면 GC의 작동이 프로그램을 중단시키는 일이 없어지도록 만들었다. 다만 이건 매우 극단적인 경우로 GC로 인한 속도변화가 없어지는 대신 전체적인 속도에서 손해를 본다.[3] 결국 GC 자체는 어떻게 만들어도 비교적 비싼 작업이라는 소리다.

2.2. 참조 횟수 카운팅 쓰레기 수집

Reference Counting. 다른 메모리가 어떤 메모리를 얼마나 많이 참조하는지 횟수를 세어서 접근 가능과 불가능을 나누는 방식이다. 이 방식에 따르면, 한 메모리에서 다른 메모리를 참조하면 그 다른 메모리의 참조 횟수에 1을 더하고 참조를 중단하면 참조 횟수에 1을 뺀다. 만약 1을 뺀 경우 참조 횟수가 0이 되면 해당 메모리에 아무도 접근을 못 하는 것이므로 해당 메모리를 해제하는 방식이다.
위 설명을 보면 알겠지만 구현이 매우 간단한 편이다. 그러다보니 C에 구현한 구현체도 많이 찾아볼 수 있으며, C++에서는 
std::shared_ptr
라는 템플릿 클래스로 제공해준다. 또한 '''접근 불가능하게 되자마자 소멸된다'''는 장점도 있다. 추적 기반 GC의 경우 실제로 접근 불가능해지는 시점과 접근 불가능하다는 것을 알아내는 시점이 상당히 떨어져 있는데, 참조 횟수 카운팅 방식에서는 접근이 불가능해지자마자 바로 소멸에 들어가게 된다. 그러다보니 소멸자를 구현할 수 있는 C++이나 Python 같은 언어에서 종종 채택된다.
다만 이 방식에는 심각한 문제점이 존재하는데, 하나는 오버헤드고, 나머지 하나는 순환 참조다. 위 설명대로 할 경우 모든 대입문에 참조 횟수를 변경하도록 작성해야 하는데, 이게 생각보다 프로그램을 많이 느리게 만든다. 특히 횟수를 올리는 부분보다는 횟수를 내리는 부분에서 정수 감소, 조건문, 함수 호출 등이 실행될 수 있어서 대입이 빈번히 일어나는 곳에서는 배보다 배꼽이 커질 수 있다. 그 외에도 참조 횟수를 저장함으로 인해 캐시효율이 낮아질 수도 있다.
또한 순환 참조(Cyclic Reference)라는 문제가 있다. 예를 들어서 A에서 B를 가리키고 B에서 A를 가리키면 모두 참조 횟수는 1일 것이다. 그런데 A나 B에 접근할 수 없는데 둘 다 참조 횟수가 0이 아니라서 해제할 수가 없으며 그대로 메모리 누수가 된다. 그렇다고 카운팅을 안 하는 참조를 제공하면 해제된 메모리를 참조할 수 있다는 문제가 생기다보니, C++, PHP, Swift 등의 언어에서는 기존의 참조를 강한 참조(strong reference)라고 하고 약한 참조(weak reference)라는 개념을 만들어서 둘을 구분한다. 이 경우, 메모리는 강한 참조와 약한 참조 횟수가 모두 0이 될 때까지 존재하지만, 강한 참조가 0이 되면 해당 메모리에서 다른 메모리로의 참조를 제거한다. 다만 이 방법에서는 weak/strong을 신경써야 하다보니 Tracing GC만큼 편하지 않으며, 오버헤드가 더 커지게 된다.
반대로 아예 순환 참조를 해결하기 위해서 위의 Tracing GC 같은 추적 기법을 도입하기도 한다. Python과 Perl, Kotlin/Native가 대표적인 예시로 GC 사이클 검사를 따로 한다.
현재는 PHP와 Swift 언어에서 주 쓰레기 수집 기법으로 이 방식을 채택하고 있으며, C++이라든가 Rust 같은 언어들은 선택적으로 사용할 수 있게 해당 기능을 제공하고 있다.[4] C에서도 GObject 등 참조 횟수 카운팅을 지원하는 라이브러리가 존재한다.

3. 한계

어떤 방식의 쓰레기 수집을 사용하든 실행 시간에 작업을 하는 이상 성능 하락을 피할 수는 없다. 참조 횟수 카운팅 방식은 상시로 성능 저하가 발생하며, 추적 기반 방식은 성능 저하가 발생하는 간격이나 길이를 조절할 수 있을지는 몰라도 성능 저하 자체는 존재한다.
또한 쓰레기 수집기가 존재하더라도 메모리 누수는 발생할 수 있다. 이는 쓰레기 수집기가 더 이상 접근이 불가능한 객체만 회수하기 때문이다. 설령 두 번 다시 사용하지 않는 객체라 할지라도, 프로그래머의 실수로 그 객체로 접근할 수 있는 경로가 하나라도 남게 되면 쓰레기 수집기는 객체를 사용할 가능성이 있다고 판단하고 회수하지 않는다. 게다가 만약 이러한 객체가 프로그램의 실행 도중 계속해서 누적되어 간다면, 프로그램은 메모리 부족으로 결국 뻗고 말 것이다. 이 문제는 근본적으로 쓰레기 수집기가 객체가 계속 사용될지 아닐지 스스로 판단할 수 없기 때문에, 객체에 접근할 수 있는 경로가 있을 경우 무조건 사용하는 객체로 간주해서 발생하는 문제다.[5] 실제로 쓰레기 수집을 제공하는 언어를 사용한다 하더라도, 프로그램이 복잡해질수록 이러한 종류의 메모리 누수가 발생하는 것이 드물지 않다. 쓰레기 수집기가 많은 경우에 알아서 처리하긴 하지만 만능은 아니란 것.

4. 유사품

보통은 실행 시간에 메모리를 관리하는 것을 쓰레기 수집이라고 하는데, 컴파일을 하는 시점에 어떻게 메모리를 관리할지 결정하는 방식도 존재하긴 한다. 다만 이 방식 대부분은 GC라고 부르지는 않는 편이다.
그 중 가장 대표적인 방식이 소유권(Ownership)을 이용한 방식이다. 이 방식의 핵심 아이디어는 소유권을 통해서만 해당 메모리에 접근이 가능하며, 소유권은 복사가 불가능하고 이동만 가능하다는 것이다. 이 방식을 구현해둔 것으로는 C++의 
std::unique_ptr
템플릿 클래스나 Rust가 있다.
C++의 경우 어떤 스코프 내에서 할당된 로컬 객체는 해당 스코프를 벗어날 때에 해제(destructor 호출)된다는 C++의 특성을 이용한다. 생성자와 소멸자에서 자원 획득과 해제를 관리하는 프로그래밍 방법론을 RAII[6]라고 부르며 올바른 코딩 습관으로 장려하고 있다. RAII의 장점은 꽤나 많은데, 첫째로 잘 만들면 new, delete를 직접 하지 않아도 되고, 둘째로 어떠한 경로로 벗어나도 추가 문장 없이 올바르게 소멸시켜주며, 셋째로 초기화와 소멸 전후 작업을 쉽게 적용할 수 있으며 넷째로 예외가 터져도 소멸자는 꼭 호출된다는 점이다. 다른 방법으로는 예외 발생 시 메모리 누수를 무슨 수를 써도 막을 수가 없다. 혹시 예외를 아예 쓰지 않는 프로젝트라고 해도 RAII가 좋다는 점은 명백하다. if나 return 전후의 반복되는 해제 코드를 깔끔히 없애준다.
언리얼 엔진은 표준 C++의 
std::shared_ptr
템플릿 클래스와 유사한 쓰레기 수집 기능을 엔진 차원에서 자체적으로 지원한다. 각 C++ 클래스에 
UCLASS()
매크로와 
(파일명).generated.h
파일을 포함시키고, 
GetWorld()->SpawnActor<>()
나 
NewObject<>()
[7] 메소드를 이용해 객체를 생성하면 언리얼 엔진이 일정 주기마다 해당 객체의 참조 카운트를 세서 0일 경우 자동으로 메모리 해제를 시켜준다. 
std::shared_ptr
과 다르게, 접근이 불가능해지자마자 즉각 소멸에 들어가는 것은 아니다.
Rust의 경우는 위 아이디어를 극단적으로 활용한 케이스다. 반드시 모든 할당된 메모리는 한 곳에서만 소유권을 가질 수 있으며, 값은 기본적으로 복사가 아닌 이동이며, 참조를 빌려주면 다시 해당 스코프로 반환을 해야하는 등의 제약을 둠으로써 컴파일 타임에 메모리의 해제를 결정한다. 덕분에 실행 시간에서의 오버헤드가 거의 없는 편이지만, 그 대가로 C의 포인터보다 더 높은 학습 난이도[8]와 엄격한 문법[9]이 따라온다.

5. 쓰레기 수집이 적용된 프로그래밍 언어

나무위키에 문서가 작성된 프로그래밍 언어로 한정한다.

[1] 때문에 이런 언어들이 해 주는 메모리 관리란 그냥 전역변수 혹은 기껏해야 호출 스택에 의한 지역변수 관리 정도가 전부였다. 정 아쉬우면 BASIC의 PEEK/POKE 명령 같은 걸로 '''메모리 할당도 프로그래머가 직접 하던지'''...[2] Generational Garbage Collection이라 한다. 혹은 반쯤은 야매 용어지만, Old & New(또는 Old & Young) 방식이라고도 한다.[3] 만드는 것도 어렵다. 외계인 고문하던 리즈시절 에릭슨에서 수년간 개발해서 겨우 상용화한 것.[4] 안드로이드 프레임워크의 C++ 부분이 이 방법을 쓰고 있다. 'RefBase'라는 클래스가 참조 카운팅 기능을 제공하고 다른 모든 클래스는 이를 상속받도록 설계되어 있다.[5] 모든 경우의 수에서 더 이상 사용되지 않는 모든 객체를 찾아내는 하나의 알고리즘은 존재할 수 없으며, 이는 이미 수학적으로 증명되어 있는 사실이다. 때문에 쓰레기 수집기에선 접근 가능한 경로가 하나라도 있으면 사용할 가능성이 있다고 보수적으로 판단할 수밖에 없다.[6] resource acquisition is initialization[7] UObject를 직접 상속하는 클래스일 때 사용[8] 그나마 포인터는 C언어가 널리 사용되고 있는 것과 더불어 다른 프로그래밍을 하다가도 나오는 개념이라서 익숙하지만 현재 Rust의 메모리 관리 기법은 굉장히 생소한 편이다.[9] 참조/수정 가능한 참조 등을 적절히 골라서 써야하며 컴파일러가 모호하다 싶으면 수명도 명시해서 기재하야 하는 등 상당히 빡빡한 문법이다.

분류