쓰레기 수집 (컴퓨터 과학)

쓰레기 수집(garbage collection 가비지 컬렉션^[*], GC)은 메모리 관리 기법 중의 하나로, 프로그램이 동적으로 할당했던 메모리 영역 중에서 필요없게 된 영역을 해제하는 기능이다. 영어를 그대로 읽어 가비지 컬렉션이라 부르기도 한다. 1959년 무렵 리스프의 문제를 해결하기 위해 존 매카시가 개발하였다.

개요

쓰레기 수집은 동적 할당된 메모리 영역 가운데 더 이상 사용할 수 없게 된 영역을 탐지하여 자동으로 해제하는 기법이다. 더 이상 사용할 수 없게 된 영역이란, 어떤 변수도 가리키지 않게 된 영역을 의미한다.

자바, C#, 그리고 일부 스크립트 언어들은 처음부터 쓰레기 수집 기법을 염두에 두고 설계되어, 언어 정의에 쓰레기 수집이 포함되어 있다. C, C++ 등의 프로그래밍 언어는 수동 메모리 관리를 가정하고 설계되었으나, 쓰레기 수집을 지원하는 구현도 존재한다. D와 같은 어떤 언어들은 쓰레기 수집을 지원하지만, 필요에 따라 쓰레기 수집을 하지 않고 수동으로 메모리를 관리할 수 있다.

장단점

쓰레기 수집이 지원되는 환경에서는 프로그래머가 동적으로 할당한 메모리 영역의 전체를 완벽하게 관리할 필요가 없어진다. 쓰레기 수집은 다음과 같은 버그를 줄이거나 완전히 막을 수 있다.

• 유효하지 않은 포인터 접근: 이미 해제된 메모리에 접근하는 버그를 가리킨다. 만약 이 포인터가 해제되고 새로운 값이 할당되었다면, 잘못된 값을 읽어오게 된다.
• 이중 해제: 이미 해제된 메모리를 또다시 해제하는 버그를 가리킨다. 일부 메모리 할당 알고리즘에서는, 해제된 메모리를 다시 해제하려고 시도하는 것은 오류를 일으킬 수 있다.
• 메모리 누수: 더 이상 필요하지 않은 메모리가 해제되지 않고 남아있는 버그를 가리킨다. 메모리 누수가 반복되면 메모리 고갈로 프로그램이 중단될 수 있다. (접근 가능한 메모리가 증가하여 메모리가 고갈되는 문제는 쓰레기 수집으로도 막을 수 없다)

반면, 쓰레기 수집 기법은 다음과 같은 단점을 갖고 있다.

• 어떤 메모리를 해제할지 결정하는 데 비용이 든다. 객체가 필요없어지는 시점을 프로그래머가 미리 알고 있는 경우에도 쓰레기 수집 알고리즘이 메모리 해제 시점을 추적해야 하므로, 이 작업은 오버헤드가 된다.
• 쓰레기 수집이 일어나는 타이밍이나 점유 시간을 미리 예측하기 어렵다. 때문에 프로그램이 예측 불가능하게 일시적으로 정지할 수 있다. 이런 특성은 특히 실시간 시스템에는 적합하지 않다.
• 할당된 메모리가 해제되는 시점을 알 수 없다. 자원 할당과 변수 초기화를 일치하는 RAII(Resource Acquisition is Initialization) 스타일의 프로그래밍에서는, 이것은 자원 해제 시점을 알 수 없다는 것을 의미한다.

포인터 추적 방식

대부분의 쓰레기 수집 기법은 포인터 추적 방식을 사용한다. 포인터 추적 방식은 한 개 이상의 변수가 접근 가능한 메모리는 앞으로 사용할 수 있는 메모리로 간주하고, 그 밖의 메모리를 해제하는 방식을 가리킨다.

접근 가능한 객체

접근 가능한 객체는 어떤 변수가 직접 가리키는 메모리, 또는 간접적으로 가리키는 메모리를 의미한다. 접근 가능한 메모리는 다음과 같이 재귀적으로 정의할 수 있다.

1. 변수가 가리키는 객체. 여기서 변수는 콜 스택에서 정의된 지역 변수와 전역 변수를 모두 포함한다.
2. 접근 가능한 객체가 가리키는 모든 객체는 마찬가지로 접근 가능하다.

여러 가지 포인터 추적 기법

포인터 추적 기법에는 여러 가지 변종이 존재한다. 어떤 언어들은 다음 기법들 가운데 여러 가지 전략을 함께 사용하기도 한다.

표시하고 쓸기 (mark and sweep)

표시하고 쓸기 기법은 포인터 추적 기법 가운데 가장 단순한 기법이다. 먼저 각 메모리 할당 영역에 표시를 위해 1 비트의 메모리를 남겨 둔다. 표시 단계에서, 모든 변수가 가리키는 영역을 "사용 중"으로 표시하고, 그 영역에서 가리키는 또다른 영역 또한 "사용 중"으로 표시한다. 이와 같이 모든 메모리 영역을 표시하고 나면, 표시되지 않은 영역을 접근 불가능한 메모리 영역이 된다. 접근 불가능한 메모리 영역들을 쓸기 단계에서 모두 해제한다.

이 기법의 단점은, 표시 단계에서 메모리 내용이 변경되지 않아야 하기 때문에 전체 시스템의 실행이 정지된다는 것이다. 또한 전체 메모리 영역을 검사해야 하므로 메모리 페이징을 사용하는 운영체제에서 프로그램의 성능이 저하될 수 있다.

삼색 표시 기법

표시하고 쓸기 기법의 단점을 보완하기 위해, 많은 언어들은 삼색 표시 기법을 사용한다. 삼색 표시 기법은 기본적으로 표시하고 쓸기와 같은 기법이지만, 표시 단계에서 2가지가 아닌 3가지(흰색, 회색, 검은색) 정보 중 하나로 메모리를 표시한다. 이 기법은 다음과 같은 순서로 이루어진다.

1. 각각의 객체를 흰색, 회색, 검은색으로 분류한다.
   • 흰색은 더 이상 접근 불가능한 객체를 가리킨다.
   • 회색은 접근 가능한 객체이지만, 이 객체에서 가리키는 객체들은 아직 검사되지 않았음을 의미한다.
   • 검은색은 이 영역에서 가리키는 객체들이 흰색 객체를 가리키지 않음을 의미한다.
   • 알고리즘이 시작할 때는 변수가 가리키는 객체들이 회색으로 표시되며, 그 외의 모든 객체는 흰색으로 표시된다.
2. 회색으로 표시된 객체 가운데 하나를 선택하여 검은색으로 표시하고, 이 객체가 가리키는 모든 객체를 회색으로 표시한다.
3. 회색 객체가 하나도 남지 않을 때까지 위 과정을 반복한다.
4. 남은 흰색 객체는 접근 불가능한 객체이므로, 모두 해제한다.

이 알고리즘은 단순한 표시하고 쓸기 알고리즘과 달리, 프로그램이 실행 중에도 병행하여 수행할 수 있다. 또한, 메모리가 고갈되었을 때 쓰레기 수집을 실행하는 것이 아니라 주기적으로 수집하는 것도 가능하다.

객체 이동 기법

객체 이동 기법은, 해제할 객체 표시가 완료된 후 해제되지 않은 객체를 그대로 두는 것이 아니라, 다른 영역으로 복사하는 기법을 가리킨다. 원래대로 유지해도 무방한 객체를 복사하는 것은 언뜻 비효율적으로 여겨질 수도 있으나, 다음과 같은 실용적인 장점을 가지고 있다.

• 해제된 후 재사용 가능한 영역과 사용 중인 영역을 표시하기 위해 추가적인 작업을 할 필요가 없다. 따라서 해제된 영역을 포인터로 관리하는 방식에 비해 할당과 해제가 빠르게 이루어진다.
• 할당된 메모리들이 단편화되는 것을 막을 수 있다.
• 연결 리스트와 같은 연결형 자료구조에서, 서로 연결된 객체들이 메모리 상에서 가까운 위치에 할당될 확률이 높아진다. 이는 캐시와 관련하여 성능 향상에 도움이 된다.

반면, 메모리 이동 기법은 주기적으로 포인터의 내용이 바뀌므로 포인터 연산을 사용할 수 없게 된다는 단점이 있다.

세대 단위 쓰레기 수집

많은 연구자들은 프로그램에서 새롭게 할당된 영역일수록 금방 해제될 확률이 높다는 관찰을 보고하였다. 세대 단위 쓰레기 수집 기법은 이런 특성을 이용하여, 각각의 객체를 할당된 시간에 따라 세대별로 구분하여, 각 세대별로 서로 다른 메모리 영역에 객체를 할당한다. 만약 한 세대의 메모리 영역이 꽉 차면, 이 메모리 영역에서 살아남은 객체를 더 오래된 메모리 영역으로 옮긴다. 새로 할당된 영역에서는 대부분의 객체들이 빠르게 해제되고 오래된 영역에서는 객체들이 변하지 않을 확률이 높으므로, 이 기법은 메모리의 일부 영역만을 주기적으로 수집하게 되는 장점이 있다. 자바, 닷넷 프레임워크 등 현대적 언어들은 대부분 이 기법을 사용한다.

참조 횟수 계산 방식

 이 부분의 본문은 참조 횟수 계산 방식입니다.

일부 쓰레기 수집 기법은 참조 횟수 계산 방식을 사용한다. 참조 횟수 계산 방식은 각 객체에서 참조 횟수를 기억하여, 참조 횟수가 0이 되면 해당 객체를 해제하는 방식을 가리킨다. 파이썬 표준 구현인 CPython에서 이 방식을 사용한다. C++에서는 스마트 포인터라는 특수한 객체를 이용해 이 기법을 구현할 수 있다.

참조 횟수 계산 방식은 다음과 같은 장점을 가지고 있다.

• 객체가 접근 불가능해지는 즉시 메모리가 해제되므로, 프로그래머가 객체의 해제 시점을 어느 정도 예측할 수 있다.
• 객체가 사용된 직후에 메모리를 해제하므로, 메모리 해제 시점에 해당 객체는 캐시에 저장되어 있을 확률이 높다. 따라서 메모리 해제가 빠르게 이루어진다.

위와 같은 장점 때문에, 참조 횟수 계산 방식은 메모리 관리 뿐 아니라 다른 자원 할당 기법에도 종종 사용된다. 예를 들어 하드 디스크 블록의 할당과 해제를 담당하는 파일시스템의 경우, 포인터 추적 방식의 쓰레기 수집은 디스크라는 매체의 특성 상 오랜 시간을 소모하게 된다. 그러나 참조 횟수 계산 방식은 할당된 블록을 해제하는 시점에 해당 블록을 가리키는 포인터가 운영체제의 버퍼에 로딩되어 있으므로, 빠르게 블록을 해제할 수 있다.

반면 참조 횟수 계산 방식에는 다음과 같은 단점이 있다.

• 두개 이상의 객체가 서로를 가리키고 있을 경우, 참조 횟수가 0이 되지 않게 된다. 이를 순환 참조라고 하며, 메모리 누수의 원인이 된다. CPython은 이 문제를 해결하기 위해 순환 참조를 감지하는 알고리즘을 사용한다. 또한 자료구조에서 약한 참조(참조 횟수를 증가시키지 않는 포인터)를 사용하여 이 문제를 해결할 수도 있다.
• 멀티스레드 환경에서는, 스레드간에 공유하는 객체의 참조 횟수 계산을 위해 원자적 명령을 사용하거나 락을 걸어야 한다. 이 문제를 회피하기 위해 스레드 단위 지역 변수로 참조 횟수를 따로 관리하면서, 스레드의 참조 횟수가 0이 될때만 전역 참조 횟수를 확인하는 방식을 사용할 수 있다. 리눅스 커널에서 이 방식을 사용한다.
• 참조 횟수가 0이 될때, 해당 객체가 가리키는 다른 객체들 또한 동시에 0으로 만드는 작업이 일어난다. 이 과정은 경우에 따라 많은 시간이 걸릴 수도 있기 때문에 실시간 시스템에는 적합하지 않을 수 있다.

쓰레기 수집 기법을 사용하는 언어

많은 현대 언어들이 쓰레기 수집 기법을 사용한다. C와 C++는 쓰레기 수집 기법을 사용하지 않지만, 라이브러리를 통해 쓰레기 수집 기법을 사용할 수 있다.

ML, 하스켈, 얼랭 등 대부분의 함수형 프로그래밍 언어는 쓰레기 수집 기법을 지원한다. 특히 리스프는 쓰레기 수집 기법을 최초로 사용한 언어이다.

자바, 스몰토크, 자바스크립트 등의 객체지향 언어들은 대부분 쓰레기 수집이 내장되어 있다. 그러나 델파이와 C++는 쓰레기 수집을 사용하지 않는다. 오브젝티브-C는 쓰레기 수집을 사용하지 않았으나, OS X에서 구현된 ObjC 2.0에서는 애플에서 내부적으로 개발한 쓰레기 수집기가 사용된다. 루비 등의 일부 동적 타입 언어 또한 쓰레기 수집을 지원하며, 파이썬, PHP 등의 언어는 참조 횟수 계산 방식을 사용한다.

프로그래밍 초보자를 위해 설계된 베이직 등의 언어 또한 까다로운 메모리 관리를 자동으로 지원하기 위해 쓰레기 수집 기법을 사용한다. 초창기 마이크로컴퓨터에서 구현된 베이직의 경우 쓰레기 수집이 이뤄지는 동안 프로그램이 오랫동안 정지하는 등의 동작을 보였다.

같이 보기

• 메모리 관리
• 메모리 누수
• 참조 횟수 계산 방식