Garbage Collection(이하 GC)는 heap에서 할당된 저장공간의 자동화된 회수이다: 응용프로그램은 free를 해 줄 필요가 없다
파이썬, 루비, 자바 등 많은 동적 언어에서 사용한다.
C나 C++에도 보수적인Conservative GC 비슷한 무언가가 있지만 모든 garbage를 collect하지는 못한다.
묵시적 메모리 관리자는 어떻게 메모리가 free될 수 있는지 알 수 있을까?
일반적으로 우리는 미래에 어떻게 될지 알지 못한다.
하지만 우리는 특정한 블록이 연결된 포인터가 없다면 사용되지 않을 것이라는 것을 알 수 있다.
포인터에 대해 특정한 추측을 해야 한다.
메모리 관리자는 포인터와 non-pointer를 구분할 수 있다.
모든 포인터들은 블록의 시작을 가리킨다.
포인터를 숨길 수 없다.
메모리를 그래프로 표현하기
우리는 메모리를 directed graph로 볼 수 있다.
각 블록은 그래프의 노드가 된다.
각 포인터는 그래프의 에지가 된다.
힙으로의 포인터를 포함하는 힙 외부의 공간들을 root 노드라고 한다. (예: 레지스터, 스택 상의 공간, 전역변수 등)
노드(블록)이 어떤 노드에 연결되어 있다면 reachable하다.
Non-reachable 노드들은 garbage다.
Mark and Sweep Collecting
malloc/free 패키지 위에서 빌드할 수 있다: space 밖으로 나갈 때까지 malloc을 사용해서 할당한다.
space 밖으로 나갈 때:
각 블록의 헤드에 추가적인 mark bit를 사용한다.
Mark : root에서 시작해 각 reachable 블록에 mark bit을 set한다.
Sweep : 모든 블록을 스캔해서 mark되지 않은 블록들을 free한다.
단순한 구현을 위한 가정
응용프로그램
new(n) : 모든 장소가 clear된 상태에서 새로운 블록을 가리키는 포인터를 return한다.
read(b, i) : 레지스터 내의 블록 b의 주소 i를 읽는다.
write(b, i, v) : 블록 b의 주소 i에 v를 쓴다.
각 블록은 헤더 워드를 가진다.
블록 b에 대해서 b[-1]의 주소를 가진다.
각 collector에서 각각 다른 목적으로 사용한다.
GC에서 사용되는 인스트럭션
is_ptr(p) : p가 포인터인지 결정한다.
length(b) : 헤더를 제외한 블록 b의 길이를 return한다.
get_roots() : 모든 root들을 return한다.
메모리 그래프에서 DFS를 사용해 mark하기
ptr mark(ptr p) {
if (!is_ptr(p)) return; // do nothing if not pointer
if (markBitSet(p)) return; // check if already marked
setMarkBit(p); // set the mark bit
for (i=0; i < length(p); i++) // call mark on all words
mark(p[i]); // in the block
return;
}
다음 블록을 찾기 위해 length를 사용해 sweep하기
ptr sweep(ptr p, ptr end) {
while (p < end) {
if markBitSet(p)
clearMarkBit();
else if (allocateBitSet(p))
free(p);
p += length(p);
}
C에서의 보수적인 Mark & Sweep
C 프로그램을 위한 "보수적인conservative GC"
is_ptr()은 한 워드가 포인터인지를 그것이 메모리에서 한 할당된 블록을 가리키는지 확인함으로써 결정한다.
하지만 C 포인터는 블록의 중간을 가리킬 수도 있다.
그래서 어떻게 블록의 시작을 찾을래?
모든 할당된 블록들을 추적하기 위해 균형 이진 트리를 사용할 수 있다. (키는 블록의 시작)
