CSAPP (p.901 ~ 911)
Virtual Memory
Garbage Collection
프로그램에 의해 더 이상 사용되지 않는 할당 블록(garbage)을 자동으로 free 시켜주는 dynamic storage allocator
힙 저장공간을 자동으로 되찾는 과정을 garbage collection이라고 부름
응용 프로그램은 explicit하게 힙 블록을 free하지 않고, garbage collector가 주기적으로 garbage 블록을 식별하고 free 시켜줌
Garbage Collector Basics
garbage collector는 메모리를 directed reachability graph의 관점에서 바라봄
그래프의 노드는 루트 노드와 힙 노드로 나누어짐
각 힙 노드는 힙의 할당 블록에 대응되고, 노드 p에서 q로 향하는 간선은 블록 p의 어떤 지점에서 블록 q의 어떤 지점을 가리킨다는 것을 의미함
루트 노드는 힙 내부로의 포인터를 포함하는 힙 외부 지점에 대응되고, 예시로는 레지스터, 스택에 저장된 지역 변수, 글로벌 변수가 있음
노드 p가 도달 가능하다(reachable)는 것은 어떤 루트 노드에서 p로 가는 유향 경로(directed path)가 존재함을 의미함
임의의 시점에서 도달 불가능한 노드는 응용 프로그램에 의해 다시는 사용되지 못하는 garbage에 해당함
garbage collector의 역할은 reachability graph를 유지하고, 주기적으로 도달 불가능한 노드를 free 시켜서 free list에 되돌리는 것임
C나 C++과 같은 언어는 런타임에 메모리 내에 타입 정보가 없기 때문에 reachability graph를 정확하게 만드는 것이 불가능함
이러한 collector들을 conservative garbage collector라고 부름
도달 가능한 노드는 도달 가능하다고 식별하지만, 도달 불가능한 노드를 도달 가능하다고 식별하는 경우가 있다는 점에서 conservative함
collector는 free 블록을 찾을 수 없는 경우에 온디맨드 방식으로 작동할 수도 있고, 별개의 스레드에서 응용 프로그램과 병렬 실행될 수도 있음
Mark&Sweep Garbage Collector
Mark&Sweep garbage collector는 루트 노드로부터 도달 가능한 할당 블록을 마킹하는 mark phase와 마킹되지 않은 할당 블록을 free 시키는 sweep phase로 구성됨
Conservative Mark&Sweep for C programs
Mark&Sweep은 블록 위치를 변경하지 않기 때문에 garbage collector를 사용하는 C 프로그램에 적합하다고 할 수 있음
하지만 mark phase에서 isPtr 함수(원형은 void *isPtr(void *p)과 같고 p가 할당 블록 payload의 내부를 가리키면 해당 블록의 시작 지점을 가리키는 포인터를 반환함)가 필요한데, 해당 함수를 C언어로 구현함에 있어 몇 가지 문제가 있음
- C언어는 메모리에 타입 정보를 태그하지 않기 때문에
isPtr의 인자로 주어진p가 실제로 포인터인지 판별할 수 있는 명시적인 방법이 없음 p가 포인터임을 알아냈다고 하더라도p가 할당 블록의 payload 내부를 가리키는지 판별할 수 있는 명시적인 방법이 없음
2번 문제는 할당 블록 집합을 균형 이진 트리로 관리함으로써 해결 가능함
각 블록 노드에 대해 왼쪽 서브트리에는 더 낮은 주소에 위치한 블록들이, 오른쪽 서브트리에는 더 높은 주소에 위치한 블록들이 위치함
각 할당 블록 헤더에는 자식 노드를 가리키기 위한 2개의 포인터가 추가적으로 필요하고, 헤더의 size 필드를 사용해서 주어진 포인터가 해당 블록 범위에 포함되는지 판별할 수 있음
균형 이진 트리를 사용하면 루트 노드로부터 도달 가능한 모든 노드를 마킹할 수 있고, 이는 garbage collector의 구현 필요조건임 (도달 가능한 할당 블록을 마킹하지 않아서 free 시키는 경우가 존재하면 안 되기 때문)
그러나 루트 노드나 도달 가능한 할당 블록의 payload가 다른 할당 블록의 payload 범위의 주소값을 가진 스칼라(int, float 등)를 포함하고 있는 경우, collector는 이 데이터가 스칼라인지 포인터인지 추론할 방법이 없으므로 해당 블록을 conservative하게 도달 가능하다고 마킹할 수밖에 없음
이 방법은 응용 프로그램의 correctness에는 영향을 주지 않지만 불필요한 외부 단편화를 유발함
