Garbage collection

※ Implicit Memory Management : Garbage Collection

 

Garbage Collection : 힙이 할당된 storage 를 자동으로 회수한다.

많은 dynamic langauges 에서 공통적으로 :

 

• Python, Ruby, Java, Perl, ML, Lisp, Mathematica

C 및 C++ 에 대한 Variants ("conservative" 가비지 수집기)가 있다.

그러나 모든 가비지를 반드시 수집할 수는 없다.

 

void foo() {
	int *p = malloc(128);
	return ; /* p block is now garbage */
}

위 코드는 memory leak 을 유발하는 함수이다.

이러한 상황은 다음과 같이 나타낼 수 있다.

 

 

stack에 foo()의 int * 타입의 p가 선언이 되며 128 개의 word 만큼 malloc 을 했다.

그 후에 리턴을 하게 되면 선언된 p가 pop이 되기 때문에 heap 영역에 존재하는 128 개의 word 는

point 당하지 않고 garbage 상태로 계속해서 heap 에 남게 된다.

이러한 foo() 함수를 지속적으로 호출하게 될 경우 heap 영역에 garbage 가 늘어나게 되어

결국 memory-leak 이 발생하게 된다.

따라서 이러한 garbage 를 수거하기 위해 garbage collection 이 나타나게 된 것이다.

 

 

※ Garbage Collection

 

메모리 관리자는 메모리가 확보될 수 있는 시기를 어떻게 알 수 있을까?

 

• 조건에 따라 달라지기 때문에 일반적으로 미래에 어떤 것이 사용될지 알 수 없다.
• 그러나 특정 블록에 대한 포인터가 없으면 해당 블록을 사용할 수 없다는 것을 알 수 있다.

포인터에 대해 특정 가정을 해야 한다.

 

• 메모리 관리자는 포인터와 비포인터를 구분할 수 있다.
• 모든 포인터가 블록의 시작을 가리킨다.
• 포인터를 숨길 수 없다. (ex: 강제로 int로 만든 다음 다시 되돌린 경우)

 

※ Classical GC Algorithms

 

Mark-and-sweep collection (McCarthy, 1960)

 

• 블록을 이동하지 않음 (또한 "compact" 하지 않는 경우).

Reference counting (Collins, 1960)

 

• 블록을 이동하지 않음 

Copying collection (민스키, 1963년)

 

• 블록을 이동시킨다.

Generation Collectors (리버만과 휴이트, 1983년)

 

• lifetime을 기준으로 한 collection
• 대부분의 할당은 곧 garbage가 된다.
• 따라서 최근에 할당된 메모리 영역에 회수 작업을 집중한다.

 

위에서 본 foo() 함수와 같이 대부분의 동적 할당은 곧바로 garbage 가 되는 경우가 다반사다.

따라서 Generational Collectors 알고리즘은 이러한 특성을 통해 최근에 할당된 메모리 영역에

가비지 회수 작업을 집중도록 하는 것을 알 수 있다.

 

 

※ Memory as a Graph

 

 

메모리를 directed graph 라고 본다.

 

• 각 블록은 그래프의 노드이다.
• 각 포인터는 그래프의 간선이다.
• 힙에 대한 포인터를 포함하는 힙에 없는 위치를 루트 노드라고 한다. (ex : 레지스터, 스택의 위치, 전역 변수)

루트에서 해당 노드로 가는 경로가 있으면 노드(블록)에 연결할 수 있다.

그러나, 연결할 수 없는 노드는 garbage 이다(응용 프로그램에서 필요 없음).

 

 

※ Mark and Sweep Collecting

 

malloc/free 패키지 위에 구축 가능하다.

 

• 공간이 부족해질 때까지 malloc를 사용하여 할당

공간이 부족할 때 :

 

• 각 블록의 head 부분에 추가 mark bit 를 사용한다.
• Mark: 루트에서 시작하여 도달 가능한 각 블록에 mark bit 를 설정한다.
• Sweep: 모든 블록들을 탐색하여 mark 되지 않은 블록들을 free 해준다.

 

 

 

※ Assumptions For a Simple Implementation

 

Application

 

• new(n) : 모든 위치가 지워진 새 블록으로 포인터를 반환한다.
• read(b,i) :블록 b 의 위치 i를 레지스터로 읽는다.
• write(b,i,v) : 블록 b의 위치 i에 v를 작성한다.

각 블록에는 header word가 있다.

 

• 블록 b에 대해 b[-1] 로 지정됨
• 서로 다른 collector 에서 서로 다른 용도로 사용됨

Garbage Collector 에서 사용하는 명령어들

 

• is_ptr(p) : p가 포인터인지 결정한다.
• length(b) : 헤더를 포함하지 않고, 블록 b의 길이를 반환한다.
• get_roots() : 모든 루트를 반환한다.

 

 

♠ 메모리 그래프의 DFS 를 사용하여 표시

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; 
}

is_ptr(p) 를 통해 p가 포인터가 아닐 경우 리턴한다.

그리고 markBitSet(p) 를 통해 해당 포인터 p가 마킹된 경우 또한 리턴한다.

마킹되지 않은 포인터 p를 mark 한 후에 DFS 를 통해 마킹을 진행한다.

 

 

♠ 길이를 사용하여 next 블럭 찾기

ptr sweep(ptr p, ptr end) { 
	while (p < end) {
		if (markBitSet(p)) 
			clearMarkBit();
		else if (allocateBitSet(p)) 
			free(p);
		p += length(p); 
	}
}

포인터 p부터 end 까지 while 루프를 돌면서 다음과 같은 작업을 진행한다.

 

• 포인터 p가 mark 된 경우 : clearMarkbit() 을 통해 mark 를 해제한다.
• 포인터 p가 allocate 된 경우 : mark 되지 않고 동시에 allocate 된 상태라면 garbage 이므로 free(p) 를 호출한다.
• p += length(p) 를 통해 길이를 사용하여 next block 을 찾아가면서 sweeping 을 한다.

 

※ Conservative Mark & Sweep in C

 

C 프로그램을 위한 "conservative garbage collector"

 

• is_ptr() 는 할당된 메모리 블록을 가리키는지 확인하여 word 가 포인터인지 여부를 판단한다.
• 그러나 C에서 포인터는 블록의 중간을 가리킬 수 있다.

 

그럼 어떻게 이 블록의 시작을 찾을 수 있을까?

 

• Balanced binary tree 를 사용하여 할당된 모든 블록을 추적할 수 있음 (key = start-of-block)
• Balanced-tree pointer 를 헤더에 저장할 수 있음 (추가로 두 가지 word 사용)