Garbage Collection - 편집 역사

2025년 6월 19일 (목) 07:30에 Pinkgo님의 편집

2025-06-19T07:30:29Z

← 이전 판		2025년 6월 19일 (목) 07:30 판
16번째 줄:		16번째 줄:

	==Garbage Collector Basics==		==Garbage Collector Basics==
			[[파일:A garbage collector’s view of memory as a directed graph.png\|섬네일\|Figure 1. A garbage collector’s view of memory as a directed graph]]
	가비지 컬렉터는 메모리를 그림 figure 1과 같은 형태의 directed reachability graph로 간주한다. 이 그래프의 노드들은 루트 노드(root node) 집합과 힙 노드(heap node) 집합으로 나뉜다. 각 힙 노드는 힙에 있는 할당된 블록에 해당한다. 또한 간선 p → q는 블록 p의 어떤 위치가 블록 q의 어떤 위치를 가리킨다는 의미이다.		가비지 컬렉터는 메모리를 그림 figure 1과 같은 형태의 directed reachability graph로 간주한다. 이 그래프의 노드들은 루트 노드(root node) 집합과 힙 노드(heap node) 집합으로 나뉜다. 각 힙 노드는 힙에 있는 할당된 블록에 해당한다. 또한 간선 p → q는 블록 p의 어떤 위치가 블록 q의 어떤 위치를 가리킨다는 의미이다.

62번째 줄:		63번째 줄:
	Sweep 단계는 위에 나온 sweep 함수를 한 번 호출함으로써 수행된다. sweep() 함수는 힙 내의 모든 블록을 순회하면서, 가지비를 해제(free)한다.		Sweep 단계는 위에 나온 sweep 함수를 한 번 호출함으로써 수행된다. sweep() 함수는 힙 내의 모든 블록을 순회하면서, 가지비를 해제(free)한다.

	~~<syntaxhighlight lang~~=~~"c">~~		==Conservative Mark&Sweep for C Programs==
	~~</syntaxhighlight>~~		Mark & Sweep은 C 프로그램에서 가비지 컬렉션을 수행하기에 적절한 방법이다. 그 이유는 이 방식이 블록을 이동시키지 않기 때문이다. 하지만 그러나 C 언어는 isPtr 함수 구현에 있어 몇 가지 흥미로운 문제점을 가진다:
			# C는 메모리 위치에 타입 정보를 태깅(tagging)하지 않는다.
			#* 따라서, isPtr이 자신의 입력 인자 p가 포인터인지 아닌지를 확인할 명확한 방법이 없다.
			# 설령 p가 포인터임을 알더라도, isPtr이 p가 실제로 할당된 블록의 payload를 가리키는지 아닌지를 확인할 방법도 없다.
			후자의 문제에 대한 한 해결책은 할당된 블록들의 집합을 균형 이진 트리(balanced binary tree)로 유지하는 것이다. 이 트리는 다음과 같은 조건을 만족해야 한다:
			* 왼쪽 서브트리의 모든 블록들은 더 낮은 주소에 위치하고,
			* 오른쪽 서브트리의 모든 블록들은 더 높은 주소에 위치한다.
			[[파일:Left and right pointers in a balanced tree of allocated blocks.png\|섬네일\|Figure 2. Left and right pointers in a balanced tree of allocated blocks]]
			이 구조를 위해서는 figure 2와 같이 각 할당 블록의 헤더에 left와 right 필드가 추가되어야 한다. 이 필드들은 각각 다른 할당 블록의 헤더를 가리키는 포인터이다. isPtr(ptr p) 함수는 이 트리를 사용하여 할당된 블록들 중 p가 어디에 속하는지 이진 탐색(binary search)을 수행한다. 탐색 과정에서, 블록의 헤더에 있는 size 필드를 이용해 p가 해당 블록 범위 안에 속하는지를 판단한다.


	==각주==		==각주==

Pinkgo: /* Garbage Collector Basics */

2025-06-19T07:20:05Z

Garbage Collector Basics

@@ 16번째 줄: / 16번째 줄: @@
 ==Garbage Collector Basics==
-가비지 컬렉터는 메모리를 그림 9.49와 같은 형태의 directed reachability graph로 간주한다. 이 그래프의 노드들은 루트 노드(root node) 집합과 힙 노드(heap node) 집합으로 나뉜다. 각 힙 노드는 힙에 있는 할당된 블록에 해당한다. 또한 간선 p → q는 블록 p의 어떤 위치가 블록 q의 어떤 위치를 가리킨다는 의미이다.
+가비지 컬렉터는 메모리를 그림 figure 1과 같은 형태의 directed reachability graph로 간주한다. 이 그래프의 노드들은 루트 노드(root node) 집합과 힙 노드(heap node) 집합으로 나뉜다. 각 힙 노드는 힙에 있는 할당된 블록에 해당한다. 또한 간선 p → q는 블록 p의 어떤 위치가 블록 q의 어떤 위치를 가리킨다는 의미이다.
 어떤 루트 노드로부터 노드 p까지 가는 경로(directed path)가 존재한다면, 노드 p가 도달 가능(reachable)하다고 한다. 특정 시점에서, 도달 불가능한 노드들은 애플리케이션이 다시 사용할 수 없는 가비지에 해당한다. 가비지 컬렉터의 역할은 도달 가능성 그래프에 대한 어떤 표현을 유지하고, 주기적으로 도달 불가능한 노드들을 해제하고 자유 리스트로 되돌림으로써 이들을 회수하는 것이다.
 <syntaxhighlight lang="c">

Pinkgo: /* 개요 */

2025-06-19T06:54:49Z

개요

← 이전 판		2025년 6월 19일 (목) 06:54 판
2번째 줄:		2번째 줄:

	==개요==		==개요==
			C의 malloc 패키지와 같은 명시적 할당기(explicit allocator)를 사용할 경우, 애플리케이션은 malloc과 free 호출을 통해 힙 블록을 할당하고 해제한다. 어떤 블록이 더 이상 필요하지 않게 되었을 때 그 블록을 해제하는 책임은 애플리케이션에게 있다. 할당된 블록을 해제하지 않는 것은 흔한 프로그래밍 오류이다. 예를 들어, 다음과 같은 C 함수는 처리를 수행하는 동안 임시 저장 공간을 할당한다:
			<syntaxhighlight lang="c">
			void garbage() {
			int p = (int )Malloc(15213);
			return; /* 이 시점에서 배열 p는 가비지이다 */
			}
			</syntaxhighlight>
			p는 프로그램에서 더 이상 필요하지 않기 때문에 garbage가 반환되기 전에 해제되었어야 한다. 하지만 프로그래머는 그 블록을 해제하는 것을 잊어버렸다. 이 블록은 프로그램이 실행되는 동안 계속 할당된 상태로 남아 있게 되고, 이후의 할당 요청들을 처리할 수 있었던 힙 공간을 쓸모없이 점유하게 된다. 이러한 블록들을 가비지(garbage)라고 한다.

			가비지 컬렉터(garbage collector)는 프로그램이 더 이상 필요로 하지 않는 할당된 블록을 자동으로 해제하는 동적 저장소 할당기이다. 힙 저장소를 자동으로 회수하는 과정은 가비지 컬렉션(garbage collection)이라고 한다. 가비지 컬렉션을 지원하는 시스템에서는, 애플리케이션이 힙 블록을 명시적으로 할당은 하되, 결코 명시적으로 해제하지 않는다. C 프로그램의 문맥에서 보면, 애플리케이션은 malloc은 호출하지만 free는 호출하지 않는다. 대신, 가비지 컬렉터는 주기적으로 가비지 블록들을 식별한 후, 그 블록들을 다시 free list로 돌려놓기 위해 적절히 free를 호출한다.

			해당 문서에서는 Mark-and-Sweep 방식의 가비지 컬렉션에 대해 설명한다.

			==Garbage Collector Basics==
			가비지 컬렉터는 메모리를 그림 9.49와 같은 형태의 directed reachability graph로 간주한다. 이 그래프의 노드들은 루트 노드(root node) 집합과 힙 노드(heap node) 집합으로 나뉜다. 각 힙 노드는 힙에 있는 할당된 블록에 해당한다. 또한 간선 p → q는 블록 p의 어떤 위치가 블록 q의 어떤 위치를 가리킨다는 의미이다.

			어떤 루트 노드로부터 노드 p까지 가는 경로(directed path)가 존재한다면, 노드 p가 도달 가능(reachable)하다고 한다. 특정 시점에서, 도달 불가능한 노드들은 애플리케이션이 다시 사용할 수 없는 가비지에 해당한다. 가비지 컬렉터의 역할은 도달 가능성 그래프에 대한 어떤 표현을 유지하고, 주기적으로 도달 불가능한 노드들을 해제하고 자유 리스트로 되돌림으로써 이들을 회수하는 것이다.



			<syntaxhighlight lang="c">
			</syntaxhighlight>

	==각주==		==각주==

Pinkgo: 새 문서: 상위 문서: Dynamic Memory Allocation ==개요== ==각주==

2025-06-19T06:25:32Z

새 문서: 상위 문서: Dynamic Memory Allocation ==개요== ==각주==

새 문서

상위 문서: [[Dynamic Memory Allocation]]

==개요==

==각주==