Dynamic Memory Allocation - 편집 역사

Pinkgo: /* Common Memory-Related Bugs in C Programs */

2025-06-19T08:02:31Z

Common Memory-Related Bugs in C Programs

Pinkgo: /* Garbage Collection */

2025-06-19T07:30:50Z

Garbage Collection

← 이전 판		2025년 6월 19일 (목) 07:30 판
174번째 줄:		174번째 줄:
	자세한 내용은 [[Garbage Collection]] 문서를 참조하십시오.		자세한 내용은 [[Garbage Collection]] 문서를 참조하십시오.

	~~<syntaxhighlight lang~~=~~"c">~~		==Common Memory-Related Bugs in C Programs==
	~~</syntaxhighlight>~~
	~~<syntaxhighlight lang~~=~~"c">~~
	~~</syntaxhighlight>~~
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	</syntaxhighlight>		</syntaxhighlight>

Pinkgo: /* Garbage Collection */

2025-06-19T06:25:08Z

Garbage Collection

← 이전 판		2025년 6월 19일 (목) 06:25 판
171번째 줄:		171번째 줄:
	이 방식의 장점은 로그 시간에 탐색 연산이 가능하므로, 처리량이 높게 뽑힌다는 점이다. 또한 메모리 활용이 높은데, 이는 해당 방식의 first-fit 탐색이 best-fit과 유사한 성능을 제공하기 때문이다. 만약 모든 크기에 대해 별도의 클래스를 제공한다면, best-fit과 일치하는 성능을 제공한다.		이 방식의 장점은 로그 시간에 탐색 연산이 가능하므로, 처리량이 높게 뽑힌다는 점이다. 또한 메모리 활용이 높은데, 이는 해당 방식의 first-fit 탐색이 best-fit과 유사한 성능을 제공하기 때문이다. 만약 모든 크기에 대해 별도의 클래스를 제공한다면, best-fit과 일치하는 성능을 제공한다.

	==Garbage Collection==		==[[Garbage Collection]]==
	자세한 내용은 [[Garbage Collection]] 문서를 참조하십시오.		자세한 내용은 [[Garbage Collection]] 문서를 참조하십시오.

Pinkgo: /* Explicit Free Lists */

2025-06-19T06:24:57Z

Explicit Free Lists

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

	==Explicit Free Lists==		==Explicit Free Lists==
			[[파일:Format of heap blocks that use doubly linked free lists.png\|대체글=Figure 9. Format of heap blocks that use doubly linked free lists\|가운데\|섬네일\|Figure 9. Format of heap blocks that use doubly linked free lists]]
	Implicit free list는 힙에 존재하는 전체 블록 수에 대해 선형 시간(linear)이 걸리기 때문에, 범용 할당기(general-purpose allocator)로는 적합하지 않다. 더 나은 접근법은, free 블록들을 어떤 형태의 명시적(explicit) 데이터 구조로 조직하는 것이다. 정의상, free 블록의 내부(body)는 프로그램에서 사용되지 않으므로, 포인터들을 그 내부에 저장할 수 있다. 예를 들어, 힙을 이중 연결 리스트(doubly linked list)로 구성할 수 있다. 이는 figure 9에 잘 나타나 있다.		Implicit free list는 힙에 존재하는 전체 블록 수에 대해 선형 시간(linear)이 걸리기 때문에, 범용 할당기(general-purpose allocator)로는 적합하지 않다. 더 나은 접근법은, free 블록들을 어떤 형태의 명시적(explicit) 데이터 구조로 조직하는 것이다. 정의상, free 블록의 내부(body)는 프로그램에서 사용되지 않으므로, 포인터들을 그 내부에 저장할 수 있다. 예를 들어, 힙을 이중 연결 리스트(doubly linked list)로 구성할 수 있다. 이는 figure 9에 잘 나타나 있다.

161번째 줄:		162번째 줄:

	==Segregated Free Lists==		==Segregated Free Lists==
			[[파일:Each size class of blocks has its own free list.png\|섬네일\|Figure 10. Each ''size class'' of blocks has its own free list ]]
	Segregated Free List는 각기 다른 크기의 블록들을 별도의 리스트(free list)에 저장하는 방식이다. 이를 size class라고 부르며 figure 10에 잘 나타나 있다. 이때 작은 크기일수록 더 정밀하게 클래스 구분을 하며, 큰 크기일수록 두 배 단위(power-of-two)로 묶어 관리(예: 16–31, 32–63 등)한다.		Segregated Free List는 각기 다른 크기의 블록들을 별도의 리스트(free list)에 저장하는 방식이다. 이를 size class라고 부르며 figure 10에 잘 나타나 있다. 이때 작은 크기일수록 더 정밀하게 클래스 구분을 하며, 큰 크기일수록 두 배 단위(power-of-two)로 묶어 관리(예: 16–31, 32–63 등)한다.

	해당 방식에서는 malloc(n) 요청 시 크기 n보다 크거나 같은 클래스(m > n)을 찾는다. 해당 클래스에 대해 적절한 free 블록이 있으면 해당 블록을 사용한다. 이때 해당 블록을 쓰고 공간이 남으면 이를 split하여 남은 부분을 다른 free list로 보낼 수 있다. 만약 해당 클래스에 적절한 free 블록이 없다면, 다음으로 큰 사이즈의 클래스로 이동해 이를 반복한다. 만약 그래도 없다면, sbrk()로 OS에서 새로운 힙 메모리를 요청한다. 그리고 필요한 만큼 할당하고, 나머지는 가장 큰 클래스에 free 함수를 통해 넣는다.		해당 방식에서는 <code>malloc(n)</code> 요청 시 크기 n보다 크거나 같은 클래스(m > n)을 찾는다. 해당 클래스에 대해 적절한 free 블록이 있으면 해당 블록을 사용한다. 이때 해당 블록을 쓰고 공간이 남으면 이를 split하여 남은 부분을 다른 free list로 보낼 수 있다. 만약 해당 클래스에 적절한 free 블록이 없다면, 다음으로 큰 사이즈의 클래스로 이동해 이를 반복한다. 만약 그래도 없다면, <code>sbrk()</code>로 OS에서 새로운 힙 메모리를 요청한다. 그리고 필요한 만큼 할당하고, 나머지는 가장 큰 클래스에 free 함수를 통해 넣는다.

	블록을 해제할 때는 해제된 블록을 인접 블록과 병합(coalescing)한 뒤, 병합된 블록의 사이즈에 해당하는 클래스의 free list에 넣으면 된다.		블록을 해제할 때는 해제된 블록을 인접 블록과 병합(coalescing)한 뒤, 병합된 블록의 사이즈에 해당하는 클래스의 free list에 넣으면 된다.
169번째 줄:		171번째 줄:
	이 방식의 장점은 로그 시간에 탐색 연산이 가능하므로, 처리량이 높게 뽑힌다는 점이다. 또한 메모리 활용이 높은데, 이는 해당 방식의 first-fit 탐색이 best-fit과 유사한 성능을 제공하기 때문이다. 만약 모든 크기에 대해 별도의 클래스를 제공한다면, best-fit과 일치하는 성능을 제공한다.		이 방식의 장점은 로그 시간에 탐색 연산이 가능하므로, 처리량이 높게 뽑힌다는 점이다. 또한 메모리 활용이 높은데, 이는 해당 방식의 first-fit 탐색이 best-fit과 유사한 성능을 제공하기 때문이다. 만약 모든 크기에 대해 별도의 클래스를 제공한다면, best-fit과 일치하는 성능을 제공한다.

			==Garbage Collection==
			자세한 내용은 [[Garbage Collection]] 문서를 참조하십시오.

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

Pinkgo: /* Coalescing with Boundary Tags */

2025-06-19T06:20:54Z

Coalescing with Boundary Tags

@@ 152번째 줄: / 152번째 줄: @@
 경계 태그 기법은 단순하고 우아하며, 다양한 형태의 할당기와 free 리스트 조직에 일반적으로 적용 가능하다. 하지만 각 블록에 header와 footer를 모두 넣어야 하므로, 작은 블록을 많이 사용하는 애플리케이션에서는 메모리 오버헤드가 커질 수 있다는 단점이 있다. 이러한 단점을 극복하기 위해, 할당된 블록에는 footer를 생략할 수 있는 최적화 기법이 존재한다. 따라서, 현재 블록의 low-order bit 중 여분 비트 하나에 이전 블록의 할당 여부 비트를 저장하면, 할당된 블록에서는 footer 없이도 이전 블록 상태를 추론할 수 있다.
@@ 170번째 줄: / 186번째 줄: @@
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 ==각주==

Pinkgo: /* Coalescing Free Blocks */

2025-06-19T05:39:29Z

Coalescing Free Blocks

← 이전 판		2025년 6월 19일 (목) 05:39 판
116번째 줄:		116번째 줄:
	하지만 그렇지 않은 경우, 동적 메모리 할당기는 free 블록을 두 부분으로 분할한다. 첫 번째 부분은 할당된 블록이 되고, 나머지 부분은 새로운 free 블록이 된다. Figure 5는 Figure 3의 8워드짜리 free 블록을 어떻게 분할하는지에 대해 보여준다.		하지만 그렇지 않은 경우, 동적 메모리 할당기는 free 블록을 두 부분으로 분할한다. 첫 번째 부분은 할당된 블록이 되고, 나머지 부분은 새로운 free 블록이 된다. Figure 5는 Figure 3의 8워드짜리 free 블록을 어떻게 분할하는지에 대해 보여준다.

	== ~~Getting Additional Heap Memory~~ ==		==Coalescing Free Blocks==
			할당기가 할당된 블록을 해제(free)할 때, 그 새롭게 해제된 블록의 인접한 위치에 다른 free 블록이 존재할 수 있다. 이러한 인접한 free 블록들은 가짜 단편화(false fragmentation)라고 불리는 현상을 유발할 수 있다. 즉, 사용 가능한 free 메모리가 작고 쓸모없는 조각들로 쪼개져 있어서 실제로는 충분한 양의 메모리가 있음에도 불구하고, 요청을 만족시키지 못하는 상황이 발생하는 것이다.
			[[파일:An example of false fragmentation.png\|가운데\|섬네일\|500x500픽셀\|Figure 6. An example of false fragmentation]]
			Figure 6는 figure 5에서 할당된 블록을 해제한 후의 결과를 보여준다. 결과적으로, payload가 각각 3워드인 인접한 두 개의 free 블록이 생긴다. 이 경우, 만약 어떤 요청이 4워드 payload를 요구한다면, 전체 free 블록 크기는 충분하지만, 연속된 하나의 블록이 아니기 때문에 할당에 실패하게 된다. 이러한 false fragmentation을 방지하기 위해, 실용적인 동적 메모리 할당기라면 반드시 인접한 free 블록들을 병합(coalescing)해야 한다.

			이때 병합을 언제 수행할 지는 매우 중요한 질문이다. 할당기는 다음 중 하나를 선택할 수 있다:
			* 즉시 병합(immediate coalescing): 블록이 해제될 때마다 인접한 free 블록이 있다면 바로 병합한다.
			* 지연 병합(deferred coalescing): 병합을 나중 시점까지 미루고, 특정 조건이 충족될 때 한꺼번에 수행한다.
			** 예: 할당 요청이 실패했을 때 힙 전체를 스캔하여 모든 free 블록을 병합하는 방식이다.
			즉시 병합은 구현이 단순하고, 상수 시간 내에 수행할 수 있다. 하지만 어떤 요청 패턴에서는 thrashing이라 불리는 비효율이 생길 수 있다. 예를 들면 어떤 블록이 해제되어 병합된 직후, 다시 할당되면서 다시 분할되는 일이 반복되는 경우이다. 해당 문서에서는 즉시 병합(immediate coalescing)을 전제로 하지만, 현실에서는 지연 병합(deferred coalescing)을 선택하는 경우가 많다.

			===Coalescing with Boundary Tags===
			우리가 해제하려는 블록을 현재 블록(current block)이라고 하자. 그러면 현재 블록의 다음 블록(next block)을 병합하는 것은 직관적이고 효율적이다. 현재 블록의 헤더는 다음 블록의 헤더를 가리키므로, 그 헤더를 검사해 다음 블록이 free인지 여부를 확인할 수 있다. 만약 다음 블록이 free라면, 그 크기를 현재 블록의 크기에 더하면 되고, 이를 통해 상수 시간 내에 병합할 수 있다.

			하지만 이전 블록(previous block)을 병합은 더욱 까다롭다. 암시적 free 리스트에서는 각 블록에 헤더만 있으므로, 현재 블록에 도달할 때까지 리스트 전체를 순차적으로 탐색하며 이전 블록의 위치를 기억해야 한다. 즉, 암시적 free 리스트에서 free를 호출할 때, 필요한 시간은 힙 크기에 대해 선형 시간(linear time)이 된다.
			[[파일:Format of heap block that uses a boundary tag.png\|섬네일\|200x200픽셀\|Figure 7. Format of heap block that uses a boundary tag]]
			이러한 문제를 해결하기 위해서 도입된 기법이 경계 태그(boundary tags)이며, 이는 이전 블록과의 병합을 상수 시간에 수행할 수 있게 해준다. 해당 방식의 핵심적인 아이디어는 figure 7과 같이 각 블록의 끝 부분에 header의 복사본인 footer(경계 태그)를 추가하는 것이다. 이렇게 하면, 현재 블록 기준으로 한 워드 앞에 있는 footer를 확인하여 이전 블록의 시작 위치 및 상태(할당/비어있음)를 알 수 있다.

			할당기가 어떤 블록을 해제할 때, 발생 가능한 경우의 수는 다음 네 가지이다:
			# 이전 블록과 다음 블록이 모두 할당됨
			# [[파일:Coalescing with boundary tags.png\|섬네일\|622x622픽셀\|Figure 8. Coalescing with boundary tags]]이전 블록은 할당됨, 다음 블록은 free
			# 이전 블록은 free, 다음 블록은 할당됨
			# 이전 블록과 다음 블록이 모두 free
			Figure 8은 이 네 가지 경우 각각에서 어떻게 병합이 수행되는지 보여준다.
			* Case 1: 양쪽 블록이 모두 할당됨 → 병합 불가
			** 따라서, 현재 블록의 상태만 allocated → free로 변경
			* Case2: 현재 블록과 다음 블록을 병합
			** 현재 블록의 헤더와 다음 블록의 footer를 합쳐진 크기로 업데이트
			* Case3: 이전 블록과 현재 블록을 병합
			** 이전 블록의 헤더와 현재 블록의 footer를 합쳐진 크기로 업데이트
			* Case4: 이전, 현재, 다음 블록 모두 병합
			** 이전 블록의 헤더와 다음 블록의 footer를 세 블록 크기의 합으로 업데이트
			이 모든 경우에서 병합은 상수 시간에 수행된다.

			경계 태그 기법은 단순하고 우아하며, 다양한 형태의 할당기와 free 리스트 조직에 일반적으로 적용 가능하다. 하지만 각 블록에 header와 footer를 모두 넣어야 하므로, 작은 블록을 많이 사용하는 애플리케이션에서는 메모리 오버헤드가 커질 수 있다는 단점이 있다. 이러한 단점을 극복하기 위해, 할당된 블록에는 footer를 생략할 수 있는 최적화 기법이 존재한다. 따라서, 현재 블록의 low-order bit 중 여분 비트 하나에 이전 블록의 할당 여부 비트를 저장하면, 할당된 블록에서는 footer 없이도 이전 블록 상태를 추론할 수 있다.

Pinkgo: /* Implicit Free Lists */

2025-06-19T05:14:16Z

Implicit Free Lists

@@ 83번째 줄: / 83번째 줄: @@
 ==Implicit Free Lists==
-모든 실용적인 할당기는 블록 경계를 구분하고 할당된 블록과 비어 있는 블록을 구분할 수 있도록 하는 자료구조를 필요로 한다. 이때 대부분의 할당기는 이 정보를 블록 내부에 직접 포함시킨다.
+[[파일:Format of a simple heap block.png|섬네일|400x400픽셀|Figure 3. Format of a simple heap block]]
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">
 </syntaxhighlight>
@@ 103번째 줄: / 136번째 줄: @@
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 ==각주==

Pinkgo: /* Fragmentation */

2025-06-19T04:31:17Z

Fragmentation

@@ 57번째 줄: / 57번째 줄: @@
 == Fragmentation ==
 <syntaxhighlight lang="c">
 </syntaxhighlight>
@@ 75번째 줄: / 103번째 줄: @@
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 ==각주==

Pinkgo: /* Allocator Requirements and Goals */

2025-06-19T04:11:57Z

Allocator Requirements and Goals

@@ 38번째 줄: / 38번째 줄: @@
 ==Allocator Requirements and Goals==
 <syntaxhighlight lang="c">
 </syntaxhighlight>
@@ 57번째 줄: / 75번째 줄: @@
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 ==각주==

Pinkgo: /* The malloc and free Functions */

2025-06-19T03:58:13Z

The malloc and free Functions

← 이전 판		2025년 6월 19일 (목) 03:58 판
15번째 줄:		15번째 줄:
	하지만, 해당 문서에서는 명시적 할당기의 설계와 구현에 대해 논의한다. 또한 앞으로 word 사이즈는 int를 기준으로 하고, 바이트가 아닌, 워드 단위로 주소를 사용한다고 가정한다.		하지만, 해당 문서에서는 명시적 할당기의 설계와 구현에 대해 논의한다. 또한 앞으로 word 사이즈는 int를 기준으로 하고, 바이트가 아닌, 워드 단위로 주소를 사용한다고 가정한다.

	===The malloc and free Functions===		==The malloc and free Functions==
	C 표준 라이브러리는 malloc 패키지로 알려진 명시적 할당기를 제공한다. 프로그램은 malloc 함수를 호출하여 힙에서 블록을 할당한다:		C 표준 라이브러리는 malloc 패키지로 알려진 명시적 할당기를 제공한다. 프로그램은 malloc 함수를 호출하여 힙에서 블록을 할당한다:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">