SP - 6.5 Implicit Memory Management

  이번 포스팅에선 Implicit Memory Management에 대해 다뤄보겠다. 6.1 포스팅에서 우리는 Implicit Memory Allocator에 대해 아주 간단히 언급한 바 있다. Application이 Allocate만 하고, Free는 하지 않는 Dynamic Memory Allocator로, 프로그래머가 직접 할당하지만, 메모리 해제는 내부적으로 자동 수행되는 방식이라고 설명했다. 사용하지 않는 Heap 영역을 Programming Language가 직접 알아서 확인하고, 수거하는 것이다. Java의 Garbage Collection이 이러한 예시에 해당한다고 했다. 우리는 이번 포스팅에서 이 개념을 다룰 것이다. 하지만 걱정말라, 쉬어가는 Time이라고 느껴질 정도로 가볍게만 다룰 것이다.

Garbage Collection

Garbage Collection : Automatic Reclamation(수정) of Heap-Allocated Storage, which means an Application never has to try to free. ★

  Garbage란 무엇인가? 아래의 예시가 가장 쉽게 Garbage Heap Memory 상황을 보여준다.

void garbage_generator(void) {
	int *p = (int*)malloc(sizeof(int));
    return;							// What the hell are you doing?
}									// p is now pointing 'Garbage'

• p는 Local Variable이므로 Stack에 할당된다.

  • 함수가 종료되면 자동적으로 p의 메모리는 해제된다.

• malloc에서 반환된 값은 'Heap에 동적 할당된 Memory Block의 시작 주소'이다.

• 함수가 종료되면, p는 사라지고, 이는 'Heap에 있는 Memory Block을 가리키는 유일한 Pointer가 사라졌음'을 의미한다.

Garbage : 실제 사용은 하지 않지만, 그대로 Heap 공간에 자리만 차지하고 있는 쓰레기 공간

이러한 공간이 쌓이게 되면 메모리 공간이 부족해진다.

• C에선 이러한 Garbage가 생기면 Programmer 입장에서 할 수 있는 일이 별로 없다. 따라서 Programmer는 명시적으로 free 함수를 통해 메모리 해제를 반드시 수행해야 하는 것이다.

  • 하지만, 언급한 것처럼, Java와 같은 특정 언어는 Garbage Collector를 내장해 프로그래머가 굳이 해제를 일일이 하지 않아도 되게 만들어준다.

• 일반적으로 Python, Java, Ruby와 같은 Dynamic Binding Language에서 이러한 기능을 제공한다.

  • C와 C++에도 이와 유사한 기능을 수행하는 Collector가 내장되어 있긴 하다. 하지만 이들은 상기한 언어들에서 제공하는 수준의 Garbage Collecting을 수행하진 못한다.

Let's make it!

  우리가 직접 C에서 구동하는 Garbage Collector를 설계해보자(실제 구현은 하지 않을 것). 우선, 다음과 같은 Issue들에 대해 고민해봐야한다.

• Memory가 Free되어도 되는 시점을 Memory Manager가 어떻게 알 수 있을까?

  • Program Execution Order를 미리, 완벽히 알지 않는 이상, 이를 예측하긴 힘들다.

    • 하지만, 현실에선 다양한 조건 분기, 재귀 등에 의해 우리는 Program Execution Order를 알 수 없는 경우가 많다.

  • 하지만, 우리는 다음과 같은 명백한 사실 하나는 알고 있다.

  특정 Memory Block in Heap을 가리키는 Pointer가 Heap 외부에 더 이상 없으면, 해당 Block은 앞으로 사용될 일이 없고, Free되어도 무방하다. (Garbage) ★★★

  • 이러한 Idea를 기반으로 설계해볼 수 있겠다!

• 설계의 편의를 위해, Pointer에 대해 다음과 같은 제약 사항을 적용시키자.

  • 우리의 Memory Manager는 Pointer와 Non-Pointer를 구분할 수 있다.

    • 현실 C에서 이는 실현 가능성이 낮다.

  • 모든 Pointer는 오로지 Block의 맨 앞만 가리킨다.

    • 'ptr = ptr + 3;'과 같은 행위를 하지 않겠다는 것이다.

  • Pointer Hiding은 존재하지 않는다.

    • Pointer Hiding : Pointer를 같은 크기의 int Type으로 Coercion or Casting하는 행위. 반대로 int를 Pointer로 돌리는 행위까지 포함)

  • 모든 Pointer는 Heap 공간의 Block만 가리킨다.

(너무 많은 조건을 거는 것 같은가? 맞다. 그리고 이는 곧 C에서 왜 Garbage Collector를 제공하지 않는지에 대한 대답이 된다)

  여담으로, 역사적으로 다양한 Garbage Collector 구현 Algorithm들이 개발되어 왔다. McCarthy의 Mark-and-Sweep부터 시작해 최근의 Generational Collectors까지. 우리는 이 중 가장 Traditional한 Classic Theory인 'Mark-and-Sweep'에 주목한다.

Mark-and-Sweep

Background - Directed Graph

  Mark-and-Sweep 방식에선 Memory를 '유향 그래프(Directed Graph)'로 바라본다.

• 각 Memory Block은 Graph의 Node이다.

• 각 Pointer는 Graph의 Edge이다.

• 전역 변수, Register, Stack 변수로 선언된 Heap 외부 Pointer는 Root Node가 된다.

  • 여기선, Root Node가 여럿 존재할 수 있다. 즉, 유향 그래프가 복수로 존재한다.

• Heap 외부에 마련된 Noot Node에서 Heap 내부에 마련된 Heap Node들을 가리키고 있다. 만약, 어느 순간, 외부에서 내부를 Linking할 Path가 사라지면, Heap 내부에 Not-Reachable한 Node들이 생길 것이다. 이들이 바로 'Garbage'인 것이다.
  • 우리는 여기서 Idea를 얻을 수 있다.

    Reachable과 Not-Reachable을 구분할 수 있다면, 우리는 Garbage Collector를 구현할 수 있을 것이다.

    여기서 고안된 방법이 바로 Mark-and-Sweep이다.

Design Mechanism

• Mark-and-Sweep Algorithm의 가장 큰 특징은 '중간에는 Free를 하지 않는다는 점'이다.

  • 공간이 부족해질 때, 즉, malloc이 실패할 것으로 예정될 때에 Free를 수행한다. ★★
    • malloc이 실패할 때 Garbage Collector를 Trigger하여 Garbage를 수집한다.

• 이전에 확인하 바 있듯, Implicit / Explicit / Segregated 모두 Header가 필요하다.

  • Header Word의 LSB 하위 일부 비트는 Unused라 했다.
    • 여기에 Mark Bit를 만든다. ★★★

• Mark : Root node에 대해 DFS를 수행해 발견되는 각 Reachable Node Block들의 Header에 'Mark Bit'를 Set한다. ★

  • 즉, Mark Bit가 1이면, Reachable하다는 것이다.

• Sweep : Heap의 모든 Block을 일일이 "순회"해 Mark Bit가 Unset인 Block들을 모조리 Free한다. ★★★

  • 아무래도, Implicit이 유리할 것!

~> 이것이 바로 Mark-and-Sweep Algorithm의 핵심 논리이다.

Virtual Implementation

  위의 아이디어를 가상의 함수들을 이용해 구현해보자.

• 가상 함수

  • new(n) : 모든 Location이 Clear된 New Block의 Pointer를 반환한다.
  • read(b, i) : b라는 Block의 i Location을 읽어서 Register에 넣는다.
  • write(b, i, v) : b라는 Block의 i Location에 v라는 값을 넣는다.
  • is_ptr(p) : p라는 변수가 Pointer인지 일반 변수인지 판단한다.
    • 다시 말하지만, 이는 현실 C에서 (완벽하게) 구현하기 거의 불가능하다.
  • length(b) : b라는 Block의 Length를 반환한다. Header Word를 제외하고 말이다.
  • get_roots() : 모든 Root Nodes를 반환한다.

• 추가 가정

  • 모든 Block은 Header Word를 가진다.

/* Mark Routine */ 
/* Memory Graph에 대한 DFS를 수행해 Marking한다. */
ptr mark(ptr p) {
	if (!is_ptr(p)) return; 		// Pointer가 아닌 변수는 무시!    
	if (markBitSet(p)) return; 		// Pointer가 이전에 Marking되었는지 확인
										// for Recursion of DFS
	setMarkBit(p); 					// Mark Bit를 Set한다.
    
	for (i=0; i < length(p); i++) 	// p의 Location을 쭉 훑으면서
		mark(p[i]); 				// Pointer가 있으면 쭉 쫓아가면서 Marking!
        
	return;
}


/* Sweep Routine */
/* Heap을 쭉 훑으면서 Unmarked Block을 해제한다. */
ptr sweep(ptr p, ptr end) {
	while (p < end) {				// Heap을 쭉 돌면서
		if markBitSet(p)			// Mark Bit가 Set되어 있으면
			clearMarkBit();			// Mark Bit를 Clear (해제가 아니다)
		else if (allocateBitSet(p)) // Mark Bit가 Unset이면,
			free(p);				// free한다. (Garbage Collection)
            
		p += length(p);				// 다음 Block으로 넘어간다.
	}
}

• 위와 같은 Design을 통해 C에서 Mark-and-Sweep 기반 Garbage Collector를 구현해볼 수 있을 것이다.

Reality

  하지만, 앞서 계속 언급했듯이 C에선 사실 위와 같은 Garbage Collector를 '완벽히' 구축할 순 없다. 아니, 완벽히가 아니라 그냥 '잘' 수행되도록 만들기도 어렵다.

• C에선, Pointer가 Memory Block의 중간을 얼마든지 가리킬 수 있다.

  • 또한, Pointer와 Non-Pointer의 구분이 사실상 불가능하다.
    • 이게 가장 큰 이유이다.

• 하지만, 개선의 여지는 있다. 물론, 완벽한 개선은 아니지만.

  • 매 Allocation(Not only Heap, but also Data or Stack)마다, Allocated Block을 추적할 수 있도록 특정 (미리 마련한) Balanced Binary Tree의 Node를 Memory Block에 함께 저장한다. (Literally, 모든 Allocation에 대해 말이다)

    • 즉, Extra Space가 필요하긴 하다. 2Words가 필요하다. Left와 Right Child를 각각 기록하기 위해! 모든 Allocated Block에 대해서 말이다. ★★

    • 그 다음, Sweeping시 Allocated인지, 그리고 외부 Pointer인지를 확인하고, 그에 해당하면 Free하지 않는 것이다.

• 한편, 완벽하게 구현했다고 해도 Issue가 하나 더 있다.

  • Garbage Collector는 필연적으로 프로그램의 수행 속도를 늦춘다.

    • 구현이 복잡하기 때문

  • 그렇다면, Garbage Collector를 언제 동작시킬지에 대한 고민이 필요해지는 것이다. 매번 돌아가게 하면 속도가 너무 느려지기 때문이다.

  Dynamic Memory Allocation에 대한 학습은 여기까지이다. 다음 Chapter부터는 Linking에 대해 다뤄볼 것이다.

  금일 포스팅은 여기까지이다.