글 목록으로 돌아가기

프로그래밍 언어 / C언어

동적 메모리 할당 basic 영상 요약

유튜브 영상 링크 🧠 동적 메모리 할당 (Dynamic Memory Allocation) 총정리 1. 개요 및 기본 개념 1.1. 동적 메모리 할당이란? 프로그램 실행 중(Runtime) 가상 메모리를 할당받는 방식입니다. 컴파일 타임에 크기를 알

임재환
임재환 2026년 4월 16일 · 3분 읽기 · 수정 2026년 4월 16일
동적 메모리 할당 basic 영상 요약

유튜브 영상 링크

🧠 동적 메모리 할당 (Dynamic Memory Allocation) 총정리

1. 개요 및 기본 개념

1.1. 동적 메모리 할당이란?

프로그램 실행 중(Runtime) 가상 메모리를 할당받는 방식입니다. 컴파일 타임에 크기를 알 수 없는 가변적인 데이터 구조를 다룰 때 필수적입니다.

  • 메모리 영역 (Heap): 동적 할당은 힙(Heap) 영역에서 이루어집니다.
    • 가상 주소 공간 내에 존재하며, 스택(Stack)과 반대 방향으로 성장합니다.
    • 시스템 포인터(BRK)에 의해 경계가 정해지며, 매우 큰 공간을 가질 수 있습니다.
  • 힙 내의 블록: 할당자는 힙을 가변 크기의 블록으로 관리하며, 각 블록은 할당(Allocated) 또는 자유(Free) 상태 중 하나입니다.

1.2. 할당자의 분류

구분 특징 대표 언어

명시적 할당자 개발자가 직접 malloc으로 할당하고 free로 해제 C, C++
암시적 할당자 가비지 컬렉터(GC)가 미사용 메모리를 자동 해제 Java, Python

1.3. C 언어 주요 함수

함수 역할 비고

malloc(size) 요청 크기 이상의 블록 포인터 반환 16-바이트 정렬 보장, 실패 시 NULL
free(ptr) 할당된 메모리 블록 해제 malloc/realloc으로 할당된 주소여야 함
realloc(ptr, size) 이미 할당된 영역의 크기 변경 기존 데이터 보존 시도
calloc(n, size) 메모리 할당 및 0으로 초기화 요소 개수와 크기를 인자로 받음
sbrk(incr) BRK 포인터를 이동시켜 힙 크기 조절 시스템 내부에서 주로 사용

1.4. 설계 가상 및 예시

  • 주소 지정: 단어(Word) 단위 주소 지정 가능.
  • 정렬(Alignment): 2단어(Double Word) 단위 정렬 (예시에서는 2-바이트 경계).
  • 시각화 규칙:
    • 🟩 녹색: 할당된 블록 (Allocated)
    • ⬜ 무색: 자유 블록 (Free)
  • 공간 낭비 예시: 정렬 경계 요구사항 때문에 할당 요청 사이에 사용하지 못하는 틈새 공간이 발생할 수 있습니다.

2. 제약 조건 및 성능 목표

2.1. 할당자의 제약 조건

할당자는 프로그램의 요청에 즉각 응답해야 하며, 메모리를 임의로 옮길 수 없습니다.

  1. 요청 제어 불가: 프로그램이 어떤 순서로 할당/해제를 요청할지 알 수 없음.
  2. 즉각 응답: 요청을 재정렬하거나 기다릴 수 없음.
  3. 정렬 준수: 아키텍처별 정렬 요구사항을 반드시 만족해야 함.
  4. 이동 불가(No Moving): 할당된 블록을 다른 위치로 옮길 수 없음 (free 시 위치를 알 수 없게 되기 때문).

2.2. 성능 목표 (Trade-off 관계)

  • 처리량 (Throughput): 단위 시간당 완료된 요청 수

$$ 10,000\ operations / 10\ sec = 1,000\ ops/sec $$

  • 최대 메모리 활용률 (Utilization): 힙을 얼마나 알뜰하게 사용하는가?
    • 낭비 요인: 패딩(Padding), 관리용 오버헤드(Header), 단편화.
  • $$ \frac{\max(\text{Payload 합계})}{\text{Current Heap Size}} $$

3. 메모리 단편화 (Fragmentation)

3.1. 내부 단편화 (Internal Fragmentation)

  • 원인: 요청한 크기보다 더 큰 블록이 할당될 때 발생 (정렬 패딩, 탐색 정책의 한계).
  • 특징: 할당된 블록 내부에 존재하므로 측정이 명확함.

3.2. 외부 단편화 (External Fragmentation)

  • 원인: 자유 공간의 총합은 충분하지만, 연속적이지 않고 조각나 있어 할당 요청을 수용하지 못하는 상태.
  • 특징: 미래의 요청 패턴에 따라 달라지므로 예측이 어려움.

4. 할당자 구현 시 고려 사항

4.1. 정보 저장 (Header)

  • free(ptr) 시 크기를 알기 위해 블록 시작점에 길이 필드(Length Field)를 저장합니다.
  • 이 필드에는 (페이로드 + 헤더) 크기가 포함되며, 하위 비트(LSB)를 사용하여 할당 여부를 표시합니다 (0: Free, 1: Allocated).

4.2. 자유 블록 관리 (Free List)

  1. 암시적 리스트 (Implicit List): 모든 블록(할당/자유)을 헤더 정보를 따라 순차 탐색. 구현이 간단하나 탐색이 느림(O(N)).
  2. 명시적 리스트 (Explicit List): 자유 블록들만 포인터로 연결. 할당된 블록을 건너뛰어 탐색이 빠름.
  3. 분리 자유 리스트 (Segregated List): 크기별로 리스트를 따로 관리하여 속도 향상.
  4. 균형 트리 (Balanced Tree): 크기순으로 정렬하여 최적의 핏(Best-fit)을 빠르게 탐색.

4.3. 블록 분할 (Splitting)

자유 블록이 요청보다 클 경우, 필요한 만큼만 할당하고 남은 공간을 새로운 자유 블록으로 쪼개어 단편화를 방지합니다.

4.4. 블록 병합 (Coalescing)

해제된 블록 주위에 다른 자유 블록이 있다면 하나로 합칩니다.

  • 경계 태그 (Boundary Tags): 각 블록의 끝에 푸터(Footer)를 두어 이전 블록의 정보를 즉시 확인합니다 (O(1)병합 가능).
  • 4가지 경우: (앞/뒤 상태에 따라) ①둘 다 할당됨 ②뒤만 자유 ③앞만 자유 ④둘 다 자유.
  • 시점: free 시 즉시 수행하거나(Immediate), 나중에 필요할 때 한꺼번에 수행(Deferred).

5. 할당 정책 요약

  • 배치 정책 (Placement):
    • First Fit: 첫 번째로 맞는 블록 선택.
    • Next Fit: 이전 탐색 종료 지점부터 시작.
    • Best Fit: 크기가 가장 딱 맞는 블록 선택 (메모리 효율 최상, 탐색 속도 최저).
  • 암시적 리스트의 한계: 구현은 쉬우나 할당 속도가 전체 블록 수에 비례하므로 실제 시스템에서는 다른 구조와 병행하여 사용됩니다.