malloc

오늘은 malloc이 무엇인지, 어떤 식으로 작동하는지, malloc과 동적 메모리 할당에 대해서 알아보도록 하자

1. 힙(Heap)이란?

운영체제 관점에서 메모리는 크게 4영역으로 나뉘어 있음:

1. Text: 실행 코드가 저장되는 영역
2. Data: 전역 변수, static 변수 등이 저장되는 영역
3. Stack: 함수 호출 시 생성되는 지역 변수, 매개변수 저장. LIFO 구조
4. Heap: 동적 메모리 할당 영역 → 우리가 malloc, free 할 때 쓰는 영역

• 힙은 프로그램 실행 중 런타임에 할당되는 메모리로, 크기가 정해지지 않고 필요할 때 요청해서 사용.
• 직접 메모리를 요청하고, 다 쓰고 나면 명시적으로 해제해야 함.

2. 왜 동적할당을 쓰는가 ?

메모리 크기를 실행 시간에 결정할 수 있음

• 컴파일 시점에는 데이터 크기를 모를 수 있음.
• 예를 들어, 사용자로부터 입력받는 리스트 크기나 파일로부터 읽을 데이터의 양은 미리 알 수 없음.
• 이런 경우 malloc이나 calloc을 사용해서 실행 중에 필요한 만큼 메모리를 확보할 수 있다!

int n;
scanf("%d", &n);               // 사용자 입력에 따라 크기 결정
int *arr = malloc(n * sizeof(int));

스택보다 더 큰 메모리를 사용할 수 있음

• 함수 내부에서 선언되는 배열 등은 스택(stack)에 저장됨 → 크기가 제한됨 (보통 수백 KB ~ 수 MB).
• 큰 데이터는 힙(heap)에 할당해서 사용해야 함.

int big_array[1000000]; // 스택 오버플로우 가능

⬇⬇⬇

int *big_array = malloc(1000000 * sizeof(int)); // 힙에서는 OK!

데이터 구조가 유연함 (리스트, 트리, 그래프 등)

• 연결 리스트, 트리 같은 동적 자료구조는 노드를 만들고 지우는 일이 많다.
• 이런 구조는 크기가 유동적이라 동적 메모리가 필수.

typedef struct Node {
    int val;
    struct Node *next;
} Node;

Node *head = malloc(sizeof(Node)); // 노드 하나 생성

메모리 재사용 및 관리 유리

• malloc과 free를 잘 활용하면 메모리를 절약해서 쓸 수 있음.
• 이건 특히 제한된 환경(임베디드, 시스템 프로그래밍 등)에서 매우 중요.

3. 할당기의 요구사항 및 목표

할당기는 다음 제약 조건들을 충족해야 한다:

1. 임의의 요청 순서 처리하기 : 어떤 순서로 malloc, free가 호출될지 모름.
2. 요청에 즉시 응답 : 할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬해야 함
3. 힙만 사용 : 확장성을 갖기 위해 할당기가 사용하는 비확장성 자료 구조들은 힙 자체에 저장되야 함
4. 블록 정렬하기 : 모든 데이터 타입을 저장할 수 있도록 정렬 조건을 만족해야 함.
5. 이미 할당된 블록을 수정하지 않기 : 할당기는 가용 블록을 조작하거나 변경할 수만 있다. 특히, 일단블록이 할당되면 이들을 수정하거나 이동하지 않는다. 그래서 할당된 블록들을 압축하는 것 같은 기법들은 허용 X

• 목표는 처리량(throughput)과 메모리 활용률(utilization)을 최대화하는 것

3-1. 묵시적 할당기 (Implicit Allocator)

• 사용자 입장에서는 명시적으로 메모리를 해제할 필요 없음.
• 즉, 메모리를 언제 해제할지 프로그래머가 명시하지 않고, 언어 런타임이 가비지 컬렉션(garbage collection)을 통해 자동으로 처리함.
• 예: Java, Python, Go, JavaScript 등 고수준 언어.

이 경우, 할당 자체는 new 같은 연산자로 요청하지만, 해제는 명시하지 않으므로 "묵시적"

3-2. 명시적 할당기 (Explicit Allocator)

• 메모리 할당과 해제를 프로그래머가 직접 관리해야 함.
• 예: C, C++에서 malloc/free, new/delete 사용.
• 실수로 free를 안 하면 메모리 누수(leak)가 발생하고, 잘못된 포인터를 해제하면 정의되지 않은 동작이 발생할 수 있음.

CS:APP에서의 묵시적/명시적 자유 리스트

구분	의미	관련 언어 예시
묵시적 할당기 (사용자 관점)	메모리 해제를 자동으로 수행 (GC 사용)	Java, Python, Go 등
명시적 할당기 (사용자 관점)	메모리 해제를 직접 수행	C, C++ 등
묵시적/명시적 자유 리스트 (할당기 내부)	자유 블록 연결 방식의 차이	C의 malloc 구현 방식에서 사용

4. malloc과 free 함수

• C 라이브러리의 malloc(size_t size) 함수는 힙에서 size 바이트의 메모리를 할당해주는 함수이며, 성공 시 해당 메모리의 포인터를 반환.
• free(void *ptr)는 이전에 malloc으로 할당받은 메모리를 해제.
• 이 함수들은 8 또는 16바이트 정렬(double-word aligned)을 유지.
• free는 왜 해야할까?

  더 이상 쓰지 않는 메모리를 다시 사용할 수 있도록 운영체제에 반환하기 위해

  • malloc으로 할당한 메모리는 자동으로 해제되지 않음.

  • 프로그램이 끝날 때까지 계속 남아 있어.

  • 그래서 명시적으로 free 해줘야 해.

    int *arr = malloc(100 * sizeof(int));
    // 사용 끝났으면
    free(arr); // 다시 사용할 수 있게 반환!

    메모리 누수(Memory Leak)를 방지하기 위해

  • malloc은 할 때마다 힙에서 메모리를 계속 소비해.

  • free를 안 하면 → 점점 힙이 커지고 → 결국 메모리 부족 발생! (특히 긴 시간 실행되는 프로그램에서 치명적)

  • OS가 "이 앱 메모리 너무 많이 씀!" 하면서 터뜨릴 수도 있어.

    for (int i = 0; i < 1000; i++) {
        int *temp = malloc(1000); // 계속 할당만 하고
        // free(temp); 안 하면? → 누수 발생!
    }

    재사용을 위해

  • free된 메모리는 다음 malloc 요청 시 재사용 가능.

  • 메모리를 아끼고 효율 높일 수 있음.

• free한 포인터를 재사용 한다면 벌어지는일…더보기

  • free(p)를 호출한 순간부터, 그 포인터 p가 가리키는 메모리는 해제되고 더 이상 유효하지 않은 상태가 됨.

  • 이후에 그 메모리 영역은 할당기 내부적으로 다른 목적으로 재사용될 수 있음.

  • p = 10 같은 접근을 하면 정의되지 않은 동작(Undefined Behavior) 이 발생. 즉, 어떤 일이 벌어질지 아무도 보장 못함.

    ---

    🔥 예시: 위험한 코드

    int *p = malloc(4 * sizeof(int));
    free(p);
    p[0] = 123;  // ❌ 매우 위험!

  • 이건 이미 반환된 메모리에 접근하는 것이므로 메모리 오류, 보안 취약점, 또는 운 좋게 조용히 작동할 수도 있지만 전혀 신뢰할 수 없음.

    ---

    🛡️ 안전하게 쓰는 법

    int *p = malloc(4 * sizeof(int));
    free(p);
    p = NULL;  // 💡 이제 p는 더 이상 잘못된 메모리를 가리키지 않음

  • free 후에 해당 포인터를 NULL로 초기화하는 건 매우 좋은 습관.

  • 나중에 잘못 접근하려 해도 p는 프로그램을 즉시 종료시켜 버그를 빨리 발견할 수 있게 해준다.

    즉, free한 포인터는 절대 재사용 ㄴㄴ.

    그 메모리 주소가 살아있는 것 같아도, 이제 니 메모리 아님

5. calloc

calloc(size_t nmemb, size_t size)

• nmemb개의 요소 각각 size 바이트 크기의 메모리 블록을 할당하고, 0으로 초기화합니다.
• 사실상 malloc(nmemb * size)와 memset(ptr, 0, nmemb * size)를 합친 기능이에요.
• 예:

  int *arr = (int *)calloc(10, sizeof(int));  // 10개 정수 공간을 0으로 초기화

• 보통 구조체 배열이나 버퍼 초기화에 유용하게 쓰여요.

6. realloc (re-alloc)

• 이미 malloc/calloc 등으로 할당한 블록의 크기를 조정할 때 사용.
• 크기를 늘리면 새 공간은 초기화되지 않음.
• 크기를 줄이면 뒤쪽 데이터를 잘라냄.
• 내부적으로는 새 메모리를 할당하고 기존 데이터를 복사한 뒤, 이전 블록을 free하는 동작일 수도 있음.
• 예:

  int *arr = (int *)malloc(5 * sizeof(int));
  // ...
  arr = (int *)realloc(arr, 10 * sizeof(int));  // 더 큰 배열로 확장

⚠ realloc은 새 블록이 할당될 경우, 기존 포인터는 무효가 되니 반드시 반환값을 저장해야 함.

malloc, calloc, realloc 비교 요약

함수	기능	초기화 여부
malloc(size)	size 바이트 메모리 할당	❌ 초기화 안 됨
calloc(n, size)	n * size 바이트 메모리 할당	✅ 0으로 초기화
realloc(ptr, size)	ptr이 가리키는 블록의 크기 변경	❌ 새로 늘어난 부분은 초기화 안 됨

7. 단편화

• 메모리가 분할되고 할당과 해제가 반복되면서, 사용하지 못하는 빈 공간이 생기는 현상
• 성능과 자원 활용의 핵심 포인트

7-1. 내부 단편화 (Internal Fragmentation)

블록은 할당됐지만, 실제로는 일부만 사용되고 나머지는 낭비되는 경우

• 예: 17바이트 요청했는데, 24바이트 블록이 할당됨 → 7바이트 낭비

int *p = malloc(17); // 실제로는 8의 배수로 24바이트 할당될 수도 있음

7-2. 외부 단편화 (External Fragmentation)

메모리에는 충분한 여유 공간이 있음에도, 연속된 큰 블록이 없어서 할당이 안 되는 상황

• 예: 힙에 100바이트 여유가 있지만, 40, 30, 30으로 흩어져 있어 → 90바이트 요청하면 실패!

왜 중요한가 ?

이유	설명
메모리 낭비	전체 사용률이 떨어져 프로그램이 더 많은 메모리를 요구하게 됨
할당 실패	여유는 있지만 “연속된 공간”이 없어 메모리 할당에 실패할 수 있음
성능 저하	단편화가 심하면 할당/해제 작업 자체도 느려질 수 있음

단편화를 줄이는 방법

1. 적절한 블록 크기 정렬 (alignment)
2. 블록 병합 (coalescing) : 인접한 자유 블록을 합쳐서 큰 블록으로
3. 명시적 자유 리스트 사용 : 블록을 효율적으로 관리
4. 분리 자유 리스트 (segregated list) : 크기별로 따로 관리

할당기 구현 기법들

• 🔹 암시적 자유 리스트 (Implicit Free List) → 선형 탐색, 간단하지만 느림
  
• 🔹 명시적 자유 리스트 (Explicit Free List) → 포인터로 자유 블록 연결, 탐색 빠름
  
• 🔹 분리 자유 리스트 (Segregated Free List) → 크기별로 자유 블록 관리, 성능 우수
  

블록 배치 전략

• First Fit: 처음 맞는 거
• Next Fit: 이전 탐색 이후부터
• Best Fit: 가장 딱 맞는 거 (하지만 단편화 더 유발 가능성)

병합(Coalescing) 기법

• 인접한 자유 블록을 합쳐서 큰 블록 만들기
• 경계 태그(boundary tag) 기법으로 양쪽 블록 상태 추적 가능

다음 게시글에서는 malloc, free realloc을 각종 기법을 사용해서 구현해보겠다 !