자동 메모리 회수

가비지 컬렉션(Garbage Collection)은 컴퓨터 저장 공간을 자동으로 회수하는 기술입니다. 많은 시스템에서는 프로그래머가 “free”나 “dispose” 같은 명령어를 사용해 힙 메모리를 직접 해제해야 하지만, 가비지 컬렉션 시스템은 프로그래머를 이런 부담에서 해방시켜줍니다. 가비지 컬렉터의 역할은 더 이상 사용되지 않는 데이터 객체를 찾아내서, 그 공간을 실행 중인 프로그램이 다시 쓸 수 있게 만드는 것이죠. 어떤 객체가 포인터를 따라가는 어떤 경로로도 실행 중인 프로그램에 도달할 수 없다면, 그 객체는 가비지(회수 대상)로 간주됩니다. 반대로 살아있는(live) 객체, 즉 잠재적으로 도달 가능한 객체들은 컬렉터가 보존해줍니다. 덕분에 프로그램이 이미 해제된 객체를 가리키는 “댕글링 포인터(dangling pointer)”를 따라가는 일은 절대 일어나지 않습니다.

이 논문은 단일 프로세서 가비지 컬렉터의 기본 기법부터 고급 기법까지 전반적으로 살펴봅니다. 병렬이나 분산 컬렉션은 다루지 않지만, 점진적(incremental) 기법들을 통합된 분류 체계로 제시하여 병렬 및 분산 컬렉션을 이해하는 기반을 마련합니다. 우리는 주로 절차적 언어와 객체지향 언어의 가비지 컬렉션에 초점을 맞추지만, 여기 담긴 많은 내용이 함수형이나 논리 프로그래밍 언어 같은 다른 시스템의 가비지 컬렉션을 이해하는 배경 지식이 될 것입니다.

왜 필요할까?

가비지 컬렉션은 완전히 모듈화된 프로그래밍을 위해 필수적입니다. 불필요한 모듈 간 의존성을 피할 수 있거든요. 어떤 데이터 구조를 다루는 소프트웨어 루틴은, 특별히 조율이 필요한 경우가 아니라면, 다른 루틴들이 같은 구조를 어떻게 사용하는지 알 필요가 없어야 합니다. 만약 객체를 명시적으로 해제해야 한다면, 어떤 모듈이 다른 모듈들이 특정 객체에 더 이상 관심이 없는 시점을 알아야 하는 책임을 져야 합니다.

객체의 생존 여부는 전역적인 속성이기 때문에, 이런 방식은 본래 지역적으로 이해 가능하고 유연하게 조합 가능했을 루틴에 비지역적인 부가 작업을 끼워 넣게 됩니다. 이런 부가 작업은 추상화를 방해하고 확장성을 떨어뜨립니다. 새 기능을 구현할 때마다 부가 작업 코드를 갱신해야 하니까요. 부가 작업 자체의 런타임 비용도 상당할 수 있고, 경우에 따라서는 동시성 애플리케이션에서 추가적인 동기화가 필요해질 수도 있습니다.

명시적 메모리 할당이 만들어내는 불필요한 복잡성과 미묘한 상호작용은 특히 골치 아픕니다. 프로그래밍 실수가 프로그래밍 언어의 기본 추상화를 깨뜨리면서 에러를 진단하기 어렵게 만들기 때문이죠. 적절한 시점에 메모리를 회수하지 못하면 느린 메모리 누수(leak)가 발생할 수 있습니다. 회수되지 않은 메모리가 프로세스가 종료되거나 스왑 공간이 고갈될 때까지 점진적으로 쌓이는 거죠. 반대로 메모리를 너무 일찍 회수하면 매우 이상한 동작이 나타날 수 있습니다. 옛날 포인터가 여전히 존재하는데 객체의 공간이 완전히 다른 객체를 저장하는 데 재사용될 수 있거든요. 따라서 같은 메모리가 두 개의 다른 객체로 동시에 해석되면서, 하나를 업데이트하면 다른 것이 예측할 수 없이 변경되는 일이 벌어집니다.

이런 프로그래밍 에러는 반복적으로 나타나지 않는 경우가 많아 디버깅이 매우 어렵습니다. 프로그램이 비정상적인 방식으로 부하를 받기 전까지는 전혀 나타나지 않을 수도 있죠. 할당자가 우연히 특정 객체의 공간을 재사용하지 않으면, 댕글링 포인터가 문제를 일으키지 않을 수 있습니다. 나중에 출시된 후에야, 애플리케이션이 다른 메모리 요구사항을 만들거나 다른 할당 루틴과 링크될 때 충돌할 수 있습니다. 느린 누수는 프로그램이 정상적으로 사용되는 동안에는 - 어쩌면 수년간 - 눈에 띄지 않을 수 있습니다. 너무 많은 추가 공간이 사용되기 전에 프로그램이 종료되니까요. 하지만 이 코드가 장기 실행 서버 프로그램에 통합되면, 서버는 결국 가용 메모리를 소진하고 충돌하게 됩니다. 장기 실행 서버 프로그램은 예외 처리로 인한 누수에도 특히 취약합니다. 예외 처리 코드가 중단된 작업이 할당한 모든 객체를 해제하지 못할 수 있고, 이런 가끔씩 발생하는 실패가 진단하기 극히 어려운 누수를 일으킬 수 있습니다.

최근에는 명시적 할당 언어에서 누수된 객체의 출처를 찾아주는 도구들이 나왔고, 이들은 매우 유용합니다. 안타깝게도 이런 도구들은 특정 프로그램 실행 중 실제 누수만 찾아낼 뿐, 드문 실행 패턴으로 인한 잠재적 누수는 찾지 못합니다. 누수된 객체의 출처를 찾는다고 해서 항상 문제가 해결되는 것도 아닙니다. 프로그래머는 여전히 객체를 해제해야 하는 지점을 결정할 수 있어야 하는데, 그런 지점이 존재하지 않을 수도 있습니다. 존재하지 않는다면 프로그램을 재구성해야 합니다. 이런 종류의 “가비지 디버깅”은 아무것도 안 하는 것보단 낫지만, 매우 불완전하고 프로그램이 바뀔 때마다 반복해야 합니다. 특정 탐지 가능한 누수만 제거하는 것보다, 일반적으로 누수를 완전히 제거하는 게 바람직합니다.

명시적 할당과 회수는 더 미묘한 방식으로도 프로그램 에러를 유발합니다. 프로그래머들은 적당한 수의 객체를 정적으로 할당하는 경우가 흔한데, 이렇게 하면 힙에 할당하고 언제 어디서 회수할지 결정할 필요가 없어지기 때문입니다. 하지만 이는 프로그램에 고정된 제약을 가하게 되어, 이런 제약이 초과될 때 - 어쩌면 컴퓨터 메모리와 데이터 셋이 훨씬 커진 수년 후에 - 프로그램이 실패하게 만듭니다. 이런 “취약성”은 코드의 재사용성을 크게 떨어뜨립니다. 문서화되지 않은 한계가 코드를 실패하게 만들기 때문인데, 심지어 추상화와 일관되게 사용되고 있는 경우에도 말이죠. 예를 들어, 많은 컴파일러가 “일반적인” 프로그래밍 관행에 대한 가정을 위배하는 자동 생성 프로그램을 마주치면 실패합니다.

이런 문제들 때문에 많은 애플리케이션 프로그래머들은 명시적 저장 공간 관리의 골칫거리를 피하고자 대규모 소프트웨어 시스템 내에서 애플리케이션 특화 가비지 컬렉션을 구현합니다. 많은 대형 프로그램이 참조 카운팅(reference counting)을 구현하는 자체 데이터 타입을 가지고 있습니다. 일회성 애플리케이션을 위해 코딩되기 때문에, 이런 컬렉터들은 불완전하고 버그가 많은 경우가 많습니다. 따라서 가비지 컬렉터 자체가 신뢰할 수 없는 경우가 많고, 프로그래밍 언어에 통합되지 않아 사용하기도 어렵습니다. 이런 문제에도 불구하고 이런 임시방편이 존재한다는 사실은 가비지 컬렉션의 가치를 증명하며, 가비지 컬렉션이 프로그래밍 언어 구현의 일부가 되어야 함을 시사합니다.

가비지 컬렉션이 명시적 힙 관리에 비해 상당히 비싸다는 믿음이 널리 퍼져 있지만, 여러 연구에서 가비지 컬렉션이 때로는 명시적 할당 해제보다 저렴하고, 보통은 그것과 경쟁력이 있다는 것이 밝혀졌습니다. 나중에 설명하겠지만, 잘 구현된 가비지 컬렉터는 고성능 시스템에서 명시적 힙 할당 해제에 비해 실행 중인 프로그램을 (매우 대략적으로) 약 10% 정도만 느리게 만들어야 합니다. 상당수의 프로그래머가 이런 비용을 받아들일 수 없다고 여기지만, 많은 다른 이들은 편의성, 개발 시간, 신뢰성 측면의 이점에 대한 작은 대가라고 믿습니다.

하지만 신뢰할 만한 비용 비교는 어렵습니다. 부분적으로는 명시적 할당 해제의 사용이 프로그램 구조에 영향을 미치는 방식이 그 자체로 비용이 들 수 있고, 소프트웨어 개발 프로세스에도 영향을 미칠 수 있기 때문입니다.

예를 들어, 명시적 힙 관리는 할당 해제 결정을 지역적으로 내릴 수 있도록 객체를 추가로 복사하는 동기를 부여하는 경우가 많습니다. 즉, 각 모듈이 정보의 자체 복사본을 만들어서 완료되면 해제할 수 있게 하는 거죠. 이는 추가 힙 할당을 발생시킬 뿐만 아니라, 객체의 정체성이 저장하는 값만큼 중요할 수 있는 객체지향 설계 전략을 훼손합니다. 이런 추가 복사의 효율성 비용을 측정하기는 어렵습니다. 가비지 컬렉션이 있을 때와 없을 때의 같은 프로그램을 공정하게 비교할 수 없기 때문입니다. 가비지 컬렉션을 가정했다면 프로그램이 다르게 작성되었을 테니까요.

장기적으로, 불량한 프로그램 구조는 추가 개발 및 유지보수 비용을 발생시킬 수 있고, 프로그래머 시간이 애플리케이션의 시간 중요 부분을 최적화하는 대신 세련되지 못한 코드를 유지하는 데 쓰이게 할 수 있습니다. 가비지 컬렉션이 명시적 할당 해제보다 비용이 더 들더라도, 인적 자원 절약이 시스템의 다른 측면에 대한 관심 증가로 보상받을 수 있습니다.

이런 이유로, 가비지 컬렉션 언어는 오랫동안 복잡한 데이터 구조를 사용하는 정교한 알고리즘 프로그래밍에 사용되어 왔습니다. Lisp와 Prolog 같은 많은 가비지 컬렉션 언어는 원래 인공지능 프로그래밍에 인기가 있었지만, 범용 프로그래밍에도 유용하다는 것이 밝혀졌습니다. 함수형 및 논리 프로그래밍 언어는 일반적으로 가비지 컬렉션을 통합하는데, 예측 불가능한 실행 패턴 때문에 저장 공간 할당 해제를 명시적으로 프로그래밍하기가 특히 어렵기 때문입니다. 영향력 있는 객체지향 프로그래밍 언어인 Smalltalk는 가비지 컬렉션을 통합했습니다. 최근에는 Eiffel, Self, Dylan 같은 많은 범용 언어에, 그리고 Modula-3와 Oberon 같이 부분적으로 저수준 시스템 프로그래밍을 위해 설계된 언어에도 가비지 컬렉션이 통합되었습니다. C와 C++에 가비지 컬렉션을 추가하는 애드온 패키지도 여러 개 존재합니다.

우리는 언어 구현에 내장되거나 라이브러리에서 루틴을 가져와 언어에 접목된 가비지 컬렉터에 초점을 맞춥니다. 일반적인 방식은 힙 할당 루틴이 메모리 요청이 쉽게 충족되지 않을 때 필요에 따라 공간을 회수하기 위한 특별한 작업을 수행하는 것입니다. “할당 해제자”에 대한 명시적 호출은 불필요합니다. 할당자 호출에 컬렉터 호출이 암묵적으로 포함되기 때문이죠. 할당자는 필요한 공간을 확보하기 위해 필요에 따라 가비지 컬렉터를 호출합니다.

대부분의 컬렉터는 컴파일러(또는 인터프리터)의 협력도 필요로 합니다. 객체 형식이 가비지 컬렉터에 의해 인식 가능해야 하고, 실행 코드가 특정 불변성을 보존해야 하기 때문입니다. 가비지 컬렉터의 세부 사항에 따라, 컴파일 타임에 특정 추가 정보를 내보내고 런타임에 다른 명령어 시퀀스를 실행하도록 컴파일러의 코드 생성기를 약간 변경해야 할 수 있습니다. 널리 퍼진 오해와 달리, 컴파일된 언어 사용과 가비지 컬렉션 사이에는 충돌이 없습니다. 최신 가비지 컬렉션 언어 구현은 정교한 최적화 컴파일러를 사용합니다.

2단계 추상화

가비지 컬렉션은 실행 중인 프로그램이 다시는 접근할 수 없는 데이터 객체가 차지하는 공간을 자동으로 회수합니다. 이런 데이터 객체를 가비지라고 부릅니다. 가비지 컬렉터의 기본 기능은 추상적으로 말하자면 두 부분으로 구성됩니다:

살아있는 객체와 가비지를 어떤 식으로든 구별하기(가비지 탐지)
가비지 객체의 저장 공간을 회수하여 실행 중인 프로그램이 사용할 수 있게 만들기(가비지 회수)

실제로 이 두 단계는 기능적으로나 시간적으로 얽혀 있을 수 있고, 회수 기법은 탐지 기법에 크게 의존합니다.

일반적으로 가비지 컬렉터는 다른 시스템에서 사용하는 것보다 다소 보수적인 “생존” 기준을 사용합니다. 최적화 컴파일러에서는 제어 흐름 및 데이터 흐름 분석으로 판단할 때 실행 중인 프로그램이 다시는 사용할 수 없는 지점에 값이 죽은 것으로 간주될 수 있습니다. 가비지 컬렉터는 일반적으로 루트 집합(root set)과 이 루트로부터의 도달 가능성(reachability)으로 정의되는 더 단순하고 덜 동적인 기준을 사용합니다.

가비지 컬렉터가 호출되는 순간, 활성 변수들은 살아있는 것으로 간주됩니다. 일반적으로 여기에는 정적으로 할당된 전역 또는 모듈 변수뿐만 아니라 활성화 스택의 활성화 레코드에 있는 지역 변수, 그리고 현재 레지스터에 있는 모든 변수가 포함됩니다. 이 변수들이 순회를 위한 루트 집합을 형성합니다. 이 변수들 중 하나에서 직접 도달 가능한 힙 객체는 실행 중인 프로그램이 접근할 수 있으므로 보존되어야 합니다. 또한 프로그램이 그런 객체로부터 포인터를 따라가 다른 객체에 도달할 수 있으므로, 살아있는 객체로부터 도달 가능한 모든 객체도 살아있습니다. 따라서 살아있는 객체의 집합은 단순히 루트로부터의 포인터 방향 경로 상에 있는 객체의 집합입니다.

루트 집합에서 도달할 수 없는 객체는 가비지, 즉 쓸모없는 것입니다. 프로그램이 그 객체에 도달할 수 있게 하는 합법적인 프로그램 작업 시퀀스가 없기 때문입니다. 따라서 가비지 객체는 계산의 미래 과정에 영향을 줄 수 없으며, 그 공간은 안전하게 회수될 수 있습니다.

객체 표현

이 논문의 대부분에서, 힙 객체가 자체 식별 가능하다는 단순화된 가정을 합니다. 즉, 런타임에 객체의 타입을 결정하기 쉽다는 것입니다. 정적 타입 가비지 컬렉션 언어의 구현은 일반적으로 힙 객체에 숨겨진 “헤더” 필드가 있습니다. 즉, 객체 자체의 형식을 디코딩하는 데 사용할 수 있는 타입 정보를 포함하는 추가 필드입니다. (이는 다른 객체에 대한 포인터를 찾는 데 특히 유용합니다.) 이런 정보는 컴파일러가 쉽게 생성할 수 있는데, 컴파일러는 객체 필드 참조에 대한 올바른 코드를 생성하기 위해 이 정보를 가지고 있어야 하기 때문입니다.

Lisp와 Smalltalk 같은 동적 타입 언어는 태그된(tagged) 포인터를 사용합니다. 하드웨어 주소의 약간 축약된 표현이 사용되며, 누락된 주소 비트 대신 작은 타입 식별 필드가 들어갑니다. 이를 통해 짧은 불변 객체들(특히 작은 정수)을 주소로 실제로 참조하는 대신 필드의 “주소” 부분에 직접 저장된 고유한 비트 패턴으로 표현할 수 있습니다. 이런 태그된 표현은 이런 “즉시(immediate)” 객체 중 하나나 힙의 객체에 대한 포인터를 포함할 수 있는 다형적 필드를 지원합니다. 보통 이런 짧은 태그는 힙에 할당된 객체의 헤더에 있는 추가 정보로 보강됩니다.

순수 정적 타입 언어의 경우, 루트 집합 변수의 타입을 제외하고는 객체별 런타임 타입 정보가 실제로 필요하지 않습니다. 그럼에도 불구하고 헤더는 정적 타입 언어에도 자주 사용됩니다. 적은 비용으로 구현을 단순화하기 때문입니다. 기존의 (명시적) 힙 관리 시스템도 비슷한 이유로 객체 헤더를 사용하는 경우가 많습니다.

🔍 배경 지식

1. 댕글링 포인터(Dangling Pointer) 문제의 역사

1960년대 초기 프로그래밍 언어들(특히 ALGOL)이 동적 메모리 할당을 도입하면서 댕글링 포인터 문제가 심각한 이슈로 떠올랐습니다. 이미 해제된 메모리를 가리키는 포인터를 사용하면 프로그램이 예측 불가능하게 동작하거나 충돌했죠. 이 문제를 해결하기 위해 1959년 John McCarthy가 Lisp 언어에 최초의 가비지 컬렉터를 구현했습니다. 당시에는 매우 혁신적인 아이디어였고, 초기에는 “너무 느리다”는 비판을 받았지만, 프로그램의 안정성과 개발 편의성 측면에서 큰 가치를 인정받으며 현대 언어들의 표준 기능으로 자리잡았습니다.

2. 참조 카운팅(Reference Counting)의 장단점

본문에서 언급된 참조 카운팅은 가장 오래되고 직관적인 가비지 컬렉션 방식 중 하나입니다. 각 객체가 자신을 참조하는 포인터의 개수를 기록하고, 참조 횟수가 0이 되면 즉시 메모리를 해제하는 방식이죠. Python이나 Objective-C 같은 언어가 이 방식을 사용합니다. 장점은 메모리 회수가 즉각적이고 예측 가능하다는 것이지만, 치명적인 단점이 있습니다. 바로 순환 참조(circular reference) 문제입니다. 두 객체가 서로를 참조하면 둘 다 참조 횟수가 0이 되지 않아 영원히 메모리에 남게 됩니다. 이 때문에 현대의 고성능 가비지 컬렉터들은 참조 카운팅 대신 “도달 가능성 기반” 방식을 주로 사용합니다.

3. 세대별 가비지 컬렉션의 등장

1980년대 중반, 연구자들이 발견한 흥미로운 패턴이 있습니다. 대부분의 객체는 생성된 직후 곧 쓸모없어지고(유아 사망률), 오래 살아남은 객체는 계속 살아남을 가능성이 높다는 것이었죠. 이를 “세대 가설(Generational Hypothesis)”이라고 합니다. 이 통찰을 바탕으로 등장한 것이 세대별(Generational) 가비지 컬렉션입니다. 새로 생성된 객체들(“젊은 세대”)을 자주 검사하고, 오래된 객체들(“늙은 세대”)은 가끔만 검사하는 방식이죠. Java의 HotSpot VM이나 .NET의 CLR이 이 방식을 사용하며, 현대 가비지 컬렉터의 성능을 획기적으로 향상시킨 핵심 기법입니다. 이 덕분에 본문에서 언급한 “약 10%의 성능 오버헤드”라는 놀라운 효율성이 가능해졌습니다.