java - 가비지 컬렉션(Garbage Collection)

가비지 컬렉션, Garbage Collection

개요

가비지 컬렉션Garbage Collection이란, 시스템에서 더 이상 사용하지 않는 동적 할당된 메모리 블럭 혹은 개체를 찾아 자동적으로 다시 사용 가능한 자원으로 회수하는 것을 말한다. 시스템에서 가비지 컬렉션을 수행하는 부분을 가비지 컬렉터Garbage Collector라고 하며, 최초의 가비지 컬렉터는 1958년에 존 매카시John McCarthy에 의해 리습Lisp 언어의 일부로 구현되었다. 가비지 컬렉션은 약자로 GC라고 부르기도 한다.

일반적인 가비지 컬렉터 알고리듬Algorithm은 다음과 같이 동작한다.

1. 더 이상 프로그램에서 사용하지 않을 개체Object를 찾아낸다.

2. 해당 개체가 사용하는 리소스를 회수한다.

그러나 실제로 어떤 개체가 마지막으로 사용되었고, 따라서 더 이상 사용되지 않을 것이란 사실을 알아내기는 일반적으로 불가능하다. 프로그램에 앞으로 주어질 입력을 무시하더라도 특정 개체가 유효한지 알아내는 일반적인 알고리듬은 없다. (정지 문제Halting Problem 참고) 따라서 더 이상 프로그램에서 사용하지 않을 개체를 찾아내기 위해서 가비지 컬렉터는 매우 확실하고 보수적인 방법을 사용하는데, 그것은 해당 개체를 참조할 수 있는 방법이 있는가를 알아내는 것이다. 프로그램에서 어떤 개체에 접근할 방법이 없는 이상 그 개체는 더 이상 누구도 사용할 수 없고, 따라서 그 개체는 유효하지 않다고 판단하는 것이다.

이것이 현재 구현되어 있는 가비지 컬렉터들이 사용하는 보편적인 전략이고, 이런 방법으로 참조 불가능한 개체를 회수하는 가비지 컬렉터를 트레이싱 가비지 컬렉터Tracing Garbage Collector라고 부른다. 레퍼런스 카운트Reference Count 역시 가비지 컬렉션의 일종으로 볼 수도 있지만 좁은 의미로 가비지 컬렉터라는 단어를 사용할 때는 트레이싱 가비지 컬렉터만을 의미하기 한다. 개체 간의 참조 관계를 살펴보고 참조할 수 없는 개체를 살펴보기 위해서 가비지 컬렉터는 개체 내의 포인터 레이아웃을 알 필요가 있고, 따라서 프로그래밍 언어에 통합되어 있는 경우가 많다.

가비지 컬렉션을 도입했을 때 가장 눈에 띄는 장점 중 하나는 가비지 컬렉션이 메모리 릭Memory Leak이나 이중 해제Double Free, 너무 빠른 해제Premature Free와 같이 수정하기 까다롭지만 저지르기는 쉬운 실수에 대한 강력한 방어 수단이 된다는 점이다. 이런 실수를 했을 때 프로그램이 어떤 문제를 일으킬 지, 또 언제 이런 문제가 발생할 지를 웬만해서는 알 수 없기 때문에 이 두 가지 버그들은 다른 일반적인 버그보다 대처하기가 어렵고, 그렇기 때문에 실제로 개발자들이 이런 버그들을 찾아내는 데 도움을 주는 작업만을 전문적으로 수행하는 도구(Compuware BoundsChecker, Rational Purify 등)가 많이 있다. 결과적으로 가비지 컬렉션은 이런 문제가 일어났을 때 추적하는 노력을 제거할 뿐 아니라 프로그램의 복잡도Complexity를 낮추기 때문에 전체적인 생산성에도 긍정적인 영향을 준다.

알고리듬

트레이싱 가비지 컬렉터는 가비지 컬렉션 사이클GC Cycle을 수행한다. 가비지 컬렉션 사이클은 보통 메모리가 부족해질 때, 즉 동적 할당이 실패할 때 수행되고, 삼색 표시Tri-Color Marking이라고 불리는 다음과 같은 과정으로 진행된다.

1. 백색, 회색, 검은 색 집합을 만든다. 이 집합들은 사이클 내내 유지된다. 

2. 검은 색 집합은 초기에 비어있고, 회색 집합에는 루트Root라고 불리는 특별한 개체를 넣는다. 흰색 집합에는 그 외 모든 개체를 넣는다.

3. 회색 집합에서 개체 하나를 꺼내서, 이 개체에서 포인터 연산 한 번으로 닿을 수 있는 (보통은 멤버) 모든 흰색 개체를 회색 집합에 넣는다.

4. 회색 집합에서 꺼낸 개체를 검은 색 집합으로 옮긴다.

5. 회색 집합에 개체가 남아 있으면 3으로, 남아 있지 않으면 사이클을 종료한다.

여기서 루트는 프로그램이 즉각적으로 접근할 수 있는 특별한 개체들이고, 일반적으로 전역 개체, 스택Stack 내의 개체, 레지스터Register 내의 개체를 의미한다. 루트 내에 있는 개체로부터 참조 가능한 개체는 다시 접근 가능한 개체로 간주된다. 말하자면, 프로그램이 즉시 접근 가능한 개체로부터 포인터 연산을 반복하여 참조 가능한 개체는 모두 접근 가능한 개체인 것이고, 가비지 컬렉션 사이클은 루트로부터 참조 가능한 개체를 모두 찾아내는 과정으로 간주할 수 있다. 이 과정에서 흰색 집합은 자원 회수 대상이 되는 개체가 들어있는 집합이고, 검은 색 집합은 사용 가능성이 있으므로 회수하지 않는 개체의 집합이 된다. 사이클이 모두 종료되면 3번 과정에 의해서 흰색 집합에 있는 어떤 개체도 검은 색 집합에 있는 개체로부터 참조될 수 없다는 점에 주목하자. 이제 흰색 집합에 남은 개체는 프로그램에서 접근할 수 없는 개체이고 따라서 참조될 수 없으므로 가비지 컬렉터는 이 개체들을 해제하게 된다.

가비지 컬렉션 사이클을 수행하는 방법은 몇 가지로 구분할 수 있다.

표시하고 치우기Mark-and-Sweep는 각 개체에 현재 이 개체가 흰색인지, 회색인지, 아니면 검은 색인지를 표시할 수 있는 플래그를 만들어두고 가비지 컬렉션 사이클 동안 이 플래그를 마킹해서 결과적으로 남은 흰색 개체를 지워주는 방법인데, 메모리 상에서 개체의 배치가 달라지지 않기 때문에 추가적인 메모리를 필요로 하지 않지만 단편화Fragmentation가 생길 수 있다는 문제점이 있다.

멈추고 복사Stop-and-Copy는 메모리 상에 활성 영역과 비 활성 영역을 구분한 뒤, 활성 영역에 대한 가비지 컬렉션 사이클이 끝나면 검은 색 집합 내의 모든 개체를 비활성 영역으로 옮기고, 이전 활성 영역을 비활성 영역으로 표기하고, 비활성 영역을 활성 영역으로 사용한다. 표시하고 치우기에서 볼 수 있던 단편화가 해결되는 반면 가비지 컬렉션 사이클 동안 메모리 사용량이 두 배로 증가한다는 문제점이 있다. 또한 개체를 복사하는 데 상당한 양의 퍼포먼스 부담을 갖게 된다.

표시하고 압축Mark-and-Compact은 가비지 컬렉션 대상인 개체를 모두 수집한 뒤, 남아 있는 개체를 하위 주소로 이동하면서 빈 공간을 남기지 않는 방법이다. 단편화를 제거하면서도 멈추고 복사와 같이 메모리 사용량 부담을 지지 않을 수 있는 방법이다.

표시하고 치우기를 사용하는 가비지 컬렉터는 개체를 메모리 공간 상에서 실제로 이동하지 않으므로 고정 가비지 컬렉터Non-Moving Garbage Collector라고 부르고, 멈추고 복사나 표시하고 압축과 같은 방법을 사용하는 가비지 컬렉터는 이동 가비지 컬렉터Moving Garbage Collector라고 부른다. 이동 가비지 컬렉터를 사용할 경우 가비지 컬렉션 사이클마다 모든 개체의 참조를 조정할 수 없으므로, 개체 참조는 핸들을 가리키고 있고, 핸들을 다시 한 번 더 참조하면 실제 포인터를 얻어올 수 있도록 구현되어 있어야 한다. 이렇게 구현할 경우 메모리 공간 상에서 개체를 재배치한 뒤 핸들이 참조하고 있는 포인터만 바꾸면 실제 개체가 갖고 있는 참조를 수정하지 않고도 개체의 재배치를 완료할 수 있기 때문이다.

성능상의 문제점

트레이싱 가비지 컬렉션 알고리듬의 가장 문제점은 접근 가능한 개체를 알아내기 위해서 전체 개체를 모두 순회하는 데 상당히 오랜 시간이 걸린다는 점이다. 가비지 컬렉션이 필요한 상황이 언제일지 미리 알 수 없기 때문에, 이런 특성은 즉각적인 반응성을 요구하는 애플리케이션에서는 큰 문제점으로 간주될 수 있다. 성능상의 이유로 한 번에 모든 개체를 추적하지 않고 중단했다가 다시 시작할 수 있는 가비지 컬렉션 방법을 점진적 가비지 컬렉션Incremental GC이라고 한다.

가비지 컬렉션 사이클은 중간에 중단할 수 없으면서 완전히 수행되는 시간이 길다는 문제를 해결하기 위해서 여러가지 방법이 도입되는데, 보편적으로 사용되는 것 중 하나가 세대별 가비지 컬렉션Generational GC이다. 세대별 가비지 컬렉션은 다음과 같은 가정을 기반으로 동작한다.

1. 새로 생긴 개체는 오래 사용하지 않을 가능성이 클 것이다..

2. 개체가 오래 사용될수록 그 뒤로도 계속 사용될 가능성이 클 것이다.

3. 새로 생긴 개체는 특정 기간 동안 서로를 빈번하게 참조하는 경향이 있을 것이다.

4. 메모리의 일부만 정리하는 것은 전체를 정리하는 것보다 비용이 낮을 것이다.

세대별 가비지 컬렉션에서는 가비지 컬렉션 사이클 한 번을 거칠 때마다 수거되지 않은 개체들이 한 세대씩 나이를 먹는다. 다음 차례에는 가장 어린 세대에 대해서만 가비지 컬렉션을 수행할 수 있게 되는데, 이 때에는 흰색 집합에 가장 어린 세대의 개체만 넣어두고, 어린 세대로부터 상위 세대에 대한 참조가 발견될 경우, 가정 3에 의해서 상위 세대의 개체는 하위 세대의 개체를 참조할 가능성이 낮으므로 해당 상위 세대의 개체가 참조하는 개체는 추적하지 않는 방식으로 좀 더 적은 연산을 수행하게 된다. 이 때, 상위 세대의 개체가 하위 세대를 참조할 가능성이 전혀 없는 것이 아니기 때문에, 사용중인 어린 세대 개체를 해제하지 않기 위해서 상위 세대의 참조가 변경될 때마다 하위 세대를 참조하는지 확인하여 따로 추적해야 할 대상으로 간주하는 추가적인 연산이 필요하다.

가비지 컬렉터의 문제 중 또 다른 것은 이것이 참조 근접성Locality of Reference을 훼손한다는 점이다. 사용하지 않는 개체가 어떤 것인지 찾아내기 위해서, 오랫동안 사용하지 않은 개체들을 모두 순회하게 되는데, 가비지 컬렉터가 사용 여부를 판단하기 위해서 개체를 순회하는 것은 최근의 컴퓨터 시스템이 도입하고 있는 여러 단계의 캐시Cache 효율성을 심각하게 위협할 수도 있다. (순회하는 개체 중에는 심지어 가상 메모리 부족으로 페이지 파일에 저장된 것도 있을 수 있다) 따라서 가비지 컬렉션을 지원하는 언어를 사용할 때는 해당 언어가 사용하는 컴퓨터 아키텍처와 OS에 최적화되어 있는지 확인할 필요가 있다.

가비지 컬렉션을 지원하는 언어

가비지 컬렉션은 현재 많은 언어에 의해서 지원되고 있다. 대표적인 것으로 자바Java, Smalltalk, C#, VB.net, Managed C++ 등의 개체 지향Object-Oriented 언어들이 있고, 루아Lua, 파이선Python과 같은 스크립트 언어도 언어의 특성상 가비지 컬렉션을 지원한다. C/C++에서도 사용할 수 있는 공개 소스 가비지 컬렉터가 있다.

참고
메모리 관리
Jonathan Bartlett, 2004
A Garbage Collector for C and C++
Hans Boehm
Early Storage Reclaimation in a Tracing Garbage Collector
Tomothy Harris, 1999
Garbage Collection
Wikipedia
Garbage Collection: Automatic Memory Management in the Microsoft .NET Framework : Part 1
Jeffrey Richter, MSDN Magazine, November 2000
Garbage Collection: Automatic Memory Management in the Microsoft .NET Framework : Part 2
Jeffrey Richter, MSDN Magazine, December 2000
Java 애플리케이션 성능과 확장성 향상시키기 (1)
김경한, 한국 썬 2003년 소식지
Memory Management Glossary

출처 - http://beforu.egloos.com/1134737