[CS] 가비지 컬렉션

본 글은 Computer System A Programmer's Perspective(퍼스트북)을 참고하여 작성하였습니다.

C 표준 라이브러리는 일반적으로 malloc 라이브러리 같은 명시적(explicit) 할당기를 사용해서 malloc과 free를 호출해서 힙 블록을 할당하고 반환한다. 더 이상 사용하지 않는 블록을 반환하는 것은 프로그램의 책무이다. 할당한 블록을 반환하지 않는 것은 일반적인 프로그래밍 에러다.

반면에, 묵시적(implicit) 할당기들은 언제 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출할 수 있을 것을 요구한다. 묵시적 할당기는 가비지 컬렉터(garbage collector)라고 알려져 있으며, 자동으로 사용하지 않는 할당된, 할당된 블록을 반환시켜주는 작업을 가비지 컬렉션(garbage collection) 이라고 부른다. 예를 들어, List, ML, Java 같은 고수준 언어들은 가비지 컬렉션을 사용한다.

가비지 컬렉터

• garbage collector

• 가비지: 사용하지 않는 블록들

• 가비지 컬렉션: 자동으로 힙 저장장치를 반납하는 과정

• 더 이상 프로그램에서 사용하지 않는 블록들을 자동으로 반환하는 동적 저장장치 할당기

• 가비지 컬렉션을 지원하는 시스템에서 응용 프로그램은 명시적(explicit)으로 힙 블록을 할당하지만, 결코 명시적(explicit)으로 이들을 반환하지 않는다.

가비지 컬렉터 모델

• 방향성 도달 그래프로 메모리를 추상화한다.
• 그래프의 노드들은 루트 노드들과 힙 노드들로 나뉜다.
• 루트 노드는 힙으로의 포인터를 포함하는 힙에 속하지 않는 위치들에 대응된다.
• 예를 들어, 가상메모리의 읽기-쓰기 데이터 영역 내 레지스터, 스택 변수, 전역 변수가 있다.
• 힙 노드는 힙 내 한 개의 할당된 블록에 대응된다.
• 방향성 에지 edge p -> q는 블록 p 내부의 위치가 블록 q 내부의 위치를 가리킨다는 것을 의미한다.
• 만일 어떤 루트 노드에서 힙 노드 p로 가는 경로가 존재할 때, p는 도달할 수 있다고 말한다.

가비지 컬렉터의 역할

응용프로그램은 어떤 시점에서든 도달할 수 없는 노드를 다시는 사용할 수 없는 가비지에 대응시킨다. 가비지 컬렉터의 역할은 이 도달성 그래프의 표시(mark)를 관리하는 것과 도달 불가 노드(가비지)들을 free시켜서 반환하고, 이들을 가용 리스트로 돌려주는 것이다.

Java에서의 가비지 컬렉터

ML과 자바를 위한 가비지 컬렉터는 응용 프로그램이 어떻게 포인터를 생성하고 사용하는지에 대해 긴밀하게 제어하며, 도달성 그래프의 정확한 표시를 유지한다.

C, C++에서의 가비지 컬렉터

C와 C++ 같은 언어들을 위한 가비지 컬렉터는 일반적으로 도달성 그래프의 정확한 표현을 유지할 수 없다. 이와 같은 컬렉터를 일반적으로 "보수적인 가비지 컬렉터"라고 부른다. 그 이유는 각 도달 가능 블록은 정확히 도달 가능으로 식별되지만, 일부 도달 불가 노드들은 부정확하게 도달 가능으로 식별될 수도 있기 때문이다.

가비지 컬렉터 기초

응용 프로그램은 힙이 필요할 때마다 일반적으로 malloc을 호출한다. 만일 malloc이 size에 맞는 가용 블록을 찾을 수 없다면, 일부 가비지를 free하여 가용 리스트로 회수하기 위해 가비지 컬렉터를 호출한다.

핵심 아이디어는 "가비지 컬렉터가 응용 프로그램 대신에 free를 호출한다"는 것이다. 컬렉터로의 리턴이 호출될 때, malloc은 size가 맞는 가용 블록을 다시 찾아본다. 그럼에도 찾지 못한다면, 커널에 추가적인 메모리를 요청한다. 궁극적으로 malloc은 요청한 블록의 포인터를 리턴하거나(성공), NULL 포인터를 리턴한다(실패).