힙 메모리 할당 (Heap Memory Allocation) 구현

본격적으로 힙 메모리 할당에 들어가기 전, 스택 메모리 할당과 힙 메모리 할당을 배열 선언으로 간단하게 비교해 보겠습니다.

 

배열 선언

스택(stack)과 힙(heap)은 다른 메모리 세그먼트(memory segment)입니다. 스택은 할당과 해제의 순서가 정해져 있지만 힙은 할당과 해제의 순서가 없거나 무작위입니다.

 

배열을 정적으로 선언하면, 컴파일 시점에 스택에 메모리를 할당합니다.

int arr[3];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;

함수가 끝나면 스택 프레임이 사라지고 arr 변수도 함께 소멸됩니다.

 

반면, 배열을 동적(malloc)으로 선언하면 런타임 시점에 힙영역에 메모리를 할당합니다.

int *arr = malloc(sizeof(int) * 3);
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;

함수가 끝나도 여전히 힙 메모리에 arr 데이터가 존재하고, arr을 가리키는 포인터가 스택 프레임에서 사라질 뿐입니다.

그래서 반드시 free 함수를 호출해서 힙 메모리를 반환해야 합니다.

 

💡만약 같은 포인터에 free를 두 번 적용하면?
Undefined Behavior(C 표준에서 "어떻게 될지 모르겠다"라고 선언한 동작. 컴파일러가 책임지지 않겠다는 뜻)가 발생합니다.
컴파일 오류보다 더 위험할 수도 있으며, 이유는 시스템마다 어떻게 동작할지 예측이 안되기 때문입니다.

예를 들어, 시스템에 따라서 다음과 같은 일들이 발생할 수 있습니다.
1. segmentation fault가 즉시 날 수도 있고
2. 에러를 뱉지 않지만 힙 관리 구조가 망가질 수도 있고
3. 데이터가 깨질 수도 있습니다.

 

 

힙 메모리의 데이터는 어떤 모습일까요?

힙블록 (Heap Block)

힙블록은 다음과 같이 구성됩니다.

• Header
  • Block Size (블록 크기): 헤더, 페이로드, 패딩의 사이즈를 합침. 항상 8의 배수
  • a/f (블록 할당 정보): 3비트로 블록 할당 여부 표시
• Payload: 사용자 데이터
• Padding: 8, 16 바이트 단위로 정렬을 쉽게 하기 위한 여분 공간

👀 용어 정리
bit (비트): 0 or 1
byte (바이트): 8bit
word: cpu가 한 번에 처리하는 단위. 4B(32bit) or 8B (64bit)
block (블록): 캐시나 메모리 전송의 최소 단위. 보통 32B ~ 64B

**하나의 블록에 여러 개의 워드가 들어갈 수 있습니다.

 

 

블록할당 방법

first fit

free list를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택합니다.

리스트 끝에 큰 가용 블록이 남아서 큰 블록을 찾는 경우 검색 시간이 늘어날 수 있습니다.

 

next fit

이전 검색이 종료된 지점에서 검색해서 크기가 맞는 첫 번째 가용 블록을 선택합니다.

이전 검색 후, 다음 검색에서 나머지 부분에서 찾는 게 가능성이 더 높다는 아이디어에서 나왔으며,

first fit보다 매우 빠르며 특히 작은 크기 블록이 리스트 앞부분에 모여있다면 특히 더 그런 성향을 보입니다.

 

best fit

모든 가용 블록을 검색해서 크기가 맞는 가장 작은 블록을 선택합니다.

first fit, next fit보다 좋은 메모리 이용도를 가지지만, 힙을 완전히 다 검색해야 합니다.

=> segregated free list를 사용하여 힙을 모두 검색하지 않도록 보완할 수 있습니다.

 

 

힙에 연속된 빈 블록이 없는데 연속된 블록을 할당해야 할 때는 어떻게 하나요?

이건 힙 외부 단편화와 관련된 문제입니다. 단편화는 힙을 제대로 이용하지 못하는 이유가 됩니다.

 

외부 단편화

전체로 보면 메모리 공간이 충분하지만 할당 요청을 만족시킬 단일한 가용블록이 없는 경우입니다.

8KB 연속된 공간이 할당되어야 하는 케이스

 

이 메모리 힙에 전체 가용 공간은 4 워드 + 4 워드로 총 8 워드가 남지만, 연속된 8 워드 공간이 없어 해당 크기의 블록을 할당할 수 없습니다. 

=> 인접한 빈블록을 병합을 하거나 sbrk()/mmap() 함수를 호출하여 힙 공간을 확장하여 추가 블록 할당할 수 있습니다.

 

내부 단편화

할당된 블록이 요청 데이터보다 더 커서 낭비되는 부분이 생기는 경우입니다.

k번의 블록 할당 후 요청 패턴을 익혀 6 워드 크기로 블록을 잡으면,

이후에 더 작은 크기의 블록(3 워드, 4 워드)이 할당될 때 각각 3 워드와 2 워드 크기의 공간이 낭비됩니다.

=> 가변 크기 할당으로 공간 낭비를 줄일 수 있습니다.

 

외부 단편화가 내부 단편화보다 측정하기 어려운데, "과거 요청 패턴" + "할당기 구현" 뿐만 아니라 "미래의 요청 패턴"에도 의존하기 때문입니다. 

 

 

가용 블록 연결하기

할당된 블록을 반환할 때 false fragmentation을 유발할 수 있으며, 이는 작고 사용할 수 없는 가용 블록으로 메모리가 쪼개져 있는 경우 외부 단편화가 발생하는 상황입니다. coalescing이라는 연결 과정을 통해 인접 가용 블록을 통합할 수 있습니다.

 

연결 타이밍

• 즉시 연결: 할당기는 블록이 반환될 때마다 즉시 연결 할 수 있습니다. 간단하며 상수 시간 내에 수행되지만, 일부 요청 패턴에 대해 "연결하고 잠시 후에 분할되는 Thrashing"의 형태를 유발할 수 있습니다.
• 지연 연결: 일정 시간 후에 가용 블록을 연결하는 지연 연결  할 수 있습니다. 할당기는 일부 할당 요청이 실패할 때까지 기다렸다가, 전체 힙을 검색해서 모든 가용 블록을 연결합니다.

 

그렇다면 구체적으로 어떻게 블록들을 연결할까요?

현재 블록의 다음 블록은 현재 블록의 크기만큼 뒤에 있으므로 연결이 쉽습니다.

하지만 이전 블록을 연결할 때는 현재 블록에 도달할 때까지 전체 리스트를 검색해서 이전 블록의 위치를 찾는 문제가 있습니다.

 

경계태그

이 문제는 각 블록의 끝에 footer(경계 태그)를 추가해서 header를 복사하여 해결할 수 있습니다. 이제 현재 블록에서 1 워드 앞 주소로 이동하면, 이전 블록의 footer만 확인할 수 있고 이전 블록의 상태를 쉽게 알 수 있어서 연결이 빨라집니다.

블록은 낮은 주소 순서로 header(a/f -> block size) -> payload -> padding -> footer(a/f -> block size)로 메모리에 할당됩니다.

가장 낮은 주소는 header의 a/f, 가장 높은 주소는 footer의 block size입니다.

 

a/f는 allocated/free의 약자며 1이면 할당된 상태, 0이면 할당 가능한 가용 상태를 표현합니다.

 

 

할당기가 현재 블록을 반환(free)할 때, 고려할 경우의 수

 

 

 

case 1. 이전 블록과 다음 블록 모두 할당 상태

 

인접 블록의 병합 없이 현재 블록만 가용 상태(파란색 페이로드)로 변경됩니다.

 

 

 

 

 

 

 

 

 

 

case 2. 이전 블록은 할당, 다음 블록은 가용 상태

 

현재 블록과 다음 블록을 연결합니다. 통합된 블록은 가용상태로 변경됩니다.

현재 블록의 header와 다음 블록의 footer의 블록 크기는 현재 블록과 다음 블록 크기의 합이 됩니다.

 

 

 

 

 

 

 

 

case 3. 이전 블록은 가용, 다음 블록은 할당 상태

 

이전 블록과 현재 블록을 연결합니다. 통합된 블록은 가용상태로 변경됩니다.

이전 블록의 header와 현재 블록의 footer의 블록 크기는 이전 블록과 현재 블록 크기의 합이 됩니다.

 

 

 

 

 

 

 

 

 

 

case 4. 이전 블록과 다음 블록 모두 가용 상태

 

이전 블록과 현재 블록, 그리고 다음 블록을 연결합니다. 통합된 블록은 가용 상태로 변경됩니다.

이전 블록의 header와 다음 블록의 footer의 블록 크기는 이전 블록과 현재 블록, 그리고 다음 블록 크기의 합이 됩니다.

 

 

 

 

 

 

 

**만약, 작은 크기 블록이 많으면 header와 footer가 할당된 블록의 절반을 차지하는 메모리 오버헤드가 발생할 수 있습니다.

 

 

할당기 구현하기

묵시적 가용 리스트 (implicit free list)

모든 블록을 순차적으로 탐색하며 가용 블록을 찾습니다.

힙 전체를 리스트처럼 취급하여 모든 블록을 연결하며, free list는 1개입니다.

• 블록 구성: [Header][Payload][Padding][Footer]
  • free/alloc 여부는 Header와 Footer에서 확인 가능
• 더미 블록: 정렬(Alignment)과 연결(Coalescing) 시 별도로 예외 처리를 하지 않기 위해 필수적으로 사용
  • 첫 번째 블록: Prologue block
  • 마지막 블록: Epilogue block

동적 할당(malloc)

first-fit 또는 next-fit 또는 best-fit 방식으로 순회하며 가용 블록을 찾아 할당합니다.

만약 찾지 못하면, sbrk() 또는 mmap() 시스템 콜을 통해 힙 영역을 확장하여 가용 블록을 할당합니다.

해당 블록의 Header와 Footer의 가용 상태를 1(allocated)로 업데이트합니다.

 

반환(free)

블록의 Header와 Footer의 가용 상태를 0(free)으로 업데이트합니다.

만약, 인접 블록의 가용 상태가 0이면 연결(coalescing)을 수행합니다.

---

💡 잠깐! 힙을 확장하면 메모리에서 어떤 일이 벌어질까요?

힙을 확장하면 OS는 페이지 테이블에 PTE를 생성하지만 프레임 번호는 비워두고 논리 주소만 확보해요.

추후에 실제로 새 힙 영역을 처음 읽거나(read) 쓰면(write) 페이지 폴트(page fault)가 발생합니다.

커널(kernel)은 이 시점에 물리 메모리에 프레임을 할당하고, 물리 주소를 PTE에 갱신합니다.

 

• Heap start: 힙 영역의 시작 주소
• Heap end(brk): 힙 영역의 끝 주소
• Heap end 이후 주소: 힙 영역이 아니기 때문에 블록을 할당 불가
• 힙 영역 확장: Heap end(brk)가 할당 크기만큼 이동하여, 추가 힙 영역을 확보

** 페이지 (Page)
OS는 페이지 단위로 가상메모리를 관리합니다.
즉, 페이지는 가상 주소 공간을 일정한 크기로 균등하게 나눠 놓은 구획선(boundary)입니다.
정리하면, 힙 메모리 확장은 가상메모리를 추가로 할당받는 것이고, 새로운 페이지가 페이지 테이블에 추가됩니다.

 

---

 

명시적 가용 리스트 (explicit free list)

가용(free) 블록들끼리만 연결 리스트(linked list)로 연결하고 탐색하며 가용 블록을 찾습니다.

연결 리스트인 free list는 free 블록들만 연결하며, 1개입니다. 메모리 내 블록 배열과 free list는 별개입니다.

• 블록 구성: [Header][[Pred pointer][Succ pointer] / [Payload]][Padding][Footer]
  • Pred(prev)와 Succ(next) 포인터가 추가되어, 가용 블록들을 이중 연결리스트로 연결
  • free 블록일 경우, Pred와 Succ 포인터로, allocated 블록일 경우 Payload로 사용

동적 할당(malloc)

first-fit 또는 next-fit 또는 best-fit 방식으로 free list를 순회하며 가용 블록을 탐색합니다.

적합한 free 블록을 찾으면, 필요한 크기만큼 블록을 분할하고 할당된 블록은 free list에서 제외합니다.

필요 없는 나머지 부분은 다시 free list에 연결합니다.

만약 찾지 못하면, sbrk() 또는 mmap() 시스템 콜을 통해 힙 영역을 확장하여 가용 블록을 할당합니다.

해당 블록의 Header와 Footer의 가용 상태를 1(allocated)로 업데이트합니다.

 

반환(free)

블록의 Header와 Footer의 가용 상태를 0(free)으로 업데이트합니다.

만약, 메모리상 인접한 블록의 가용 상태가 0이면 연결(coalescing)을 수행합니다.

---

 

분리 가용 리스트 (segregated free list)

explicit free list의 확장 버전으로, 블록 크기별로 여러 개의 bin(free list)을 구성합니다.

• list[0]: 1–31B
• list[1]: 32–63B
• list[2]: 64–127B
• list[3]: 128B-255B
• ...
• list[k]: >4096B

블록 요청 시 크기에 맞는 bin을 검색합니다.

크기 별로 묶는 이유는 free list가 1개뿐이면 다양한 크기의 블록이 섞여서 탐색에 비효율이 생기기 때문입니다.

 

 

• 블록 구성: [Header][[Pred pointer][Succ pointer] / [Payload]][Padding][Footer]
  • Pred(prev)와 Succ(next) 포인터가 추가되어, 가용 블록들을 이중 연결리스트로 연결
  • free 블록일 경우, Pred와 Succ 포인터로, allocated 블록일 경우 Payload로 사용
• 리스트 배열 구성
  • list[0] head → [Free(4)] → [Free(4)] ->tail
  • list[1] head → [Free(46)] ->tail
  • list[2] head → [Free(96)] ->tail
  • ...

동적 할당(malloc)

요청 크기에 따라 bin을 탐색합니다. 만약 요청 크기가 훨씬 크면 힙을 확장합니다.

적절한 free list를 찾으면 first-fit 또는 next-fit 또는 best-fit 방식으로 free list를 순회하며 가용 블록을 탐색합니다.

적합한 free 블록을 찾으면, 필요한 크기만큼 블록을 분할하고 할당된 블록은 free list에서 제외합니다.

필요 없는 나머지 부분은 다시 free list에 연결합니다.

만약 찾지 못하면, sbrk() 또는 mmap() 시스템 콜을 통해 힙 영역을 확장하여 가용 블록을 할당합니다.

해당 블록의 Header와 Footer의 가용 상태를 1(allocated)로 업데이트합니다.

 

반환(free)

블록의 Header와 Footer의 가용 상태를 0(free)으로 업데이트합니다.

만약, 메모리상 인접한 블록의 가용 상태가 0이면 연결(coalescing)을 수행합니다.

반환된 블록 크기에 따라 해당되는 bin에 연결합니다.

 

---

 

버디 시스템 (buddy system)

메모리 관리의 다른 철학을 엿볼 수 있는 방법입니다.

분리 가용 리스트가 최적화 기법을 보여준다면, 버디 시스템은 2^k로 관리를 하고, 병합을 단순화하는 방법을 제안합니다.

 

2^k 크기별 free list를 두고, 블록 요청이 들어오면 적절한 크기의 free list를 찾아서 필요한 크기에 가장 가까운 2^k 단위 블록을 찾거나 쪼개어 할당합니다. 메모리를 반으로 쪼개거나(split), 다시 짝을 찾아 합치기(coalesce)를 반복합니다.

 

 

동적 할당(malloc)

요청이 들어오면, 2의 배수 단위로 요청 블록 크기에 최대한 근접하게 메모리를 분할합니다.

블록을 찾으면 할당 순서는 왼쪽 버디(낮은 주소)에 먼저 할당합니다.

만약 가용 리스트의 크기가 1024k인데 2000k 요청이 들어오면 OS에 새로운 힙 영역을 요청합니다.

 

반환(free)

메모리를 해제하면 인접해 있는 가용 블록들을 모두 병합합니다.

 

**버디 시스템 알고리즘을 사용해서 malloc을 구현하면, 내부 단편화 심해져서 분리 가용 리스트보다 느리고 비효율적입니다.

 

 

가비지 컬렉션 (gc)

더 이상 필요하지 않은 할당된 블록들은 반드시 반환해야 합니다.

 

gc는 더 이상 사용하지 않는 블록들을 자동으로 반환하는 동적 저장장치 할당기입니다. 주기적으로 가비지 블록을 식별하고 가용 리스트로 돌려주기 위해 적절하게 free를 호출합니다.

 

Mark&Sweep 알고리즘

 

• mark: 루트 노드들이 도달 가능한 할당된 하위 노드들을 표시
• sweep: 표시가 없는 블록을 반환

루트 노드를 시작으로 연결된 블록들로 이동(DFS/BFS)하며 mark를 하고, 힙 전체를 순회하며 mark가 없는 가용 리스트의 블록들을 반환합니다.

 

보수적이라는 의미

값이 포인터처럼 보이면 포인터라 가정하고 해제하지 않습니다. 그래서 안전하지만 회수 효율이 좋지 않습니다.

이유는 포인터라고 알려주는 메타데이터가 c언어에 없기 때문입니다.

int *p = malloc(sizeof(int));
*p = 42;

long x = (long)p;     // 포인터를 숫자로 저장
long y = x + 8;       // 주소 비슷한 값

printf("%p", (void*)y); // 이건 그냥 숫자일 수도 있음

x, y 가 진짜 포인터인지 그냥 숫자인지 모르죠.

 

실제로 메모리를 까보면, 루트를 직접 스택/전역 메모리에서 스캔해야 하는데, 스택 프레임 안을 보면 그저 비트들의 집합일 뿐입니다.

스택:
0x7ffd1234:  0x0040abcd
0x7ffd1238:  0x0000000a
0x7ffd123c:  0x00000001

보시는 바와 같이 뭐가 포인터이고 그냥 숫자인지 알 수 없습니다.

그래서 GC가 스택을 훑을 때 "값이 힙 영역의 주소 범위 안이면, 포인터라 가정"하게 됩니다.

 

 

 

출처

Computer Systems: A Programmer's Perspective 9.9(동적메모리 할당), 9.10(gc)