동적 메모리 할당(Dynamic Allocation)이란?

서론

C언어를 공부하다보면 malloc(), calloc(), realloc()이라는 함수를 사용하여 동적 메모리 할당을 합니다. 그럼 동적 메모리 할당은 무엇이며 어떻게 이루어지는 걸까요? '동적 메모리 할당'이란 프로그램 실행 중에 필요한 메모리를 힙(heap, 보통은)에 할당하는 것입니다.

📝 그렇다면 힙이란 무엇인가?

힙은 가상 주소 공간(virtual address space)에서 데이터 영역(data segment)과 코드 영역(code segment) 사이의 영역으로 동적으로 할당된 데이터를 저장하는 영역입니다.
* 힙의 꼭대기를 brk ptr라고 합니다.

🤔 그럼 동적 메모리 할당이 왜 필요한 것인가?

가장 중요한 이유는 종종 프로그램을 실제 실행시키기 전에는 자료 구조의 크기를 알 수 없는 경우들이 있기 때문이다.
1. 필요한 만큼의 메모리만 할당하고, 더 이상 필요하지 않은 메모리는 해제할 수 있습니다. 이로써 프로그램이 불필요한게 많은 메모리를 사용하는 것을 방지할 수 있습니다. 만약 배열의 크기를 모른다면 MAXN값으로 정할 수 있습니다. 하지만 너무 작은 값이 들어오게 되면 내부 단편화가 일어나게 됩니다.
2. 동적 메모리 할당은 큰 블록을 작은 조각으로 나누어 메모리를 효율적으로 사용할 수 있습니다. 이를 통해 메모리 할당 및 해제의 오버헤드를 최소화하고 프로그램의 성능을 향상시킬 수 있습니다.

🤪 함수 설명

void *malloc(size_t size)

: 메모리 할당

• 리턴값: 최소 size 바이트를 갖는 메모리 블록의 포인터
  * 주소는 32bit에서 항상 8의 배수, 64bit에서 항상 16의 배수입니다.
• 문제시 리턴값: NULL
  * errno를 ENOMEM으로 설정합니다.

void *sbrk(int ptr_t incr)

: 커널의 btk ptr(힙의 꼭대기)에 incr을 더해서 힙의 크기 조정
* incr: 늘리거나 줄일 크기

• 리턴값: 이전 brk의 값
• 문제시 리턴값: -1
  * errno를 ENOMEM으로 설정합니다.

void free(void *ptr)

: 할당된 메모리 해제
* ptr: 할당된 블록의 시작

😬 할당기의 조건

• 임의의 요청 순서 처리하기
• 요청에 즉시 응답하기
• 힙만 사용하기
• 블록 정렬하기(정렬 요건)
• 할당된 블록을 수정하지 않기

🥅 할당기의 목표

• 처리량(단위 시간당 완료된느 요청 수) 극대화하기
• 메모리 이용도 최대화하기

🧩 단편화(Fragmentation)

왜 발생하는가? 가용 메모리가 할당 요청을 만족할 수 없을 때

• 내부 단편화: 할당된 블록이 데이터 자체보다 더 클 때
• 외부 단편화: 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용 블록은 없을 때

외부 단편화는 미래의 요청 패턴에 달려 있기 때문에 측정하기 더 어렵고 예측이 불가능하다. 예를 들어 위의 그림에서 할당 요청이 1의 크기이면 외부 단편화가 일어나지 않고, 2 이상일 때 외부 단편화가 일어난다. 그렇기 때문에 할당기는 많은 수의 더 작은 가용 블록보다는 더 적은 수의 더 큰 가용 블록을 유지하려 한다.

---

😆 실용적인 할당기

(가용 블록 구성) 어떻게 가용 블록을 지속적으로 추적할 것인가?

• 묵시적 가용 리스트(implicit)
  👍🏻 장점: 단순성
  👎🏻 단점: 가용 리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례합니다. (전체를 탐색해야 하기 때문)
• 명시적 가용 리스트(explicit)
• 분리 가용 리스트(segregated)
• 버디 시스템(buddy system)

(배치) 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?

• first-fit
  : 처음부터 탐색하고 크기가 맞는 첫 가용 블록을 선택합니다.
  👍🏻 장점: 리스트의 끝 부분에 큰 가용 블록을 갖게 되는 경향이 있습니다.
  👎🏻 단점: 리스트의 앞 쪽에 작은 가용 블록 조각을 남겨두는 경향이 있습니다. 그렇기 때문에 더 큰 블록을 찾는 데 시간이 증가합니다.
• next-fit
  : 이전 탐색이 종료된 시점부터 탐색합니다.
• best-fit
  : 모든 가용 블록을 검사해서, 크기에 맞는 가용 블록 중 가장 작은 블록을 찾습니다.
  👍🏻 장점: 가장 크기에 맞는 블록을 찾기 때문에 메모리 활용도가 높습니다.

(분할) 새롭게 할당된 블록을 배치 후, 가용 블록의 나머지 부분들로 무엇을 할 것인가?

• 가용 블록 전체 할당
• 둘로 나눠 할당

(연결) 방금 반환된 블록으로 무엇을 할 것인가?

언제?

• 즉시 연결
  : 블록이 해제될 때 인접 블록 합치기
• 지연 연결
  : 나중에 합치기

출처

• <Computer Systems: A Programmers Perspective> Section 9.9 - Randal Bryant
• 이서현의 Notability(비공개)