malloc

: 힙에서 사이즈 바이트 만큼 메모리를 "요청"해서 그 공간의 주소 (포인터)를 반환해주는 함수

프로그램이 힙에서 size바이트만큼 공간을 요청해서 빌려오는 함수
malloc()을 호출하면 그 공간의 시작 주소를 포인터로 반환해준다

int *p=malloc(100); //정수 25개의 공간 (4byte x 25)

int *arr = malloc(100 * sizeof(int)); // int 100개짜리 배열 할당

메모리는 아무주소나 주면 안된다

alignment에 따라

컴파일 모드	malloc이 주는 주소는?
32-bit (gcc -m32)	8의 배수 (ex. 0x08000008)
64-bit (기본)	16의 배수 (ex. 0x7ffe0010)

malloc의 실패

너무 큰 메모리를 요청했을 때 (가상 메모리 초과), 시스템 메모리가 부족할 때

NULL을 반환하고, errno에 에러 코드 저장

calloc

: 초기화된 메모리 요청

void *calloc(size_t num, size_t size);

모든 바이트 0으로 초기화
calloc(n,s)=malloc(n*s)+ 초기화 메모리

realloc

void realloc(void *ptr, size_t new_size);

이미 할당된 메모리의 크기변경 (기존 공간보다 더 크게 확장하고 싶을 때 사용)

free

void free(void *ptr)

malloc/calloc/realloc으로 얻은 메모리를 다 쓰고 나면 free(ptr)로 반납해야 해

반납하지 않으면 메모리 누수(memory leak) 발생
malloc 등으로 받은 포인터만 free해야 함
잘못된 주소나 이미 free한 주소를 free하면 → 오작동 (undefined behavior)

malloc 내부적으로 메모리를 어디서 가져오나?

sbrk()

#include <unistd.h>
void *sbrk(intprt_t incr);

현재 힙의 끝을 incr만큼 늘림
새로운 힙 영역을 만들고 이전 주소 반환
저수준 메모리 함수

왜 동적 메모리 할당?

정확한 데이터 크기를 실행 전에 모를 수 있기 때문

고정된 배열이라면 사용자마다 원하는 데이터 크기가 다를텐데 프로그램을 다시 컴파일 해야함

"처음에는 반찬 개수가 몇 개인지 모르니까, 나중에 알려주면 그때 맞는 크기의 도시락을 만들어주는 게 좋아!
그게 바로 동적 메모리 할당이야~ 🎒✨"

할당기가 꼭 지켜야할 규칙

1. 요청 순서는 예측 불가 : 어떤순서로 malloc/free가 올지 모르기에 유연한 사고
2. 즉시 반응: 요청이 들어오면 바로 처리
3. 힙사용: 할당기를 위한 자료구조도 힙 자체에 저장
4. 정렬 조건: 어떤 자료형도 담을 수 있도록 적절히 정렬된 주소를 반환해야함
5. 할당된 블록 건들지 말기 : 이미 쓰고 있는 블록은 수정 및 이동 불가(압축 불가)

목표

1. 처리 속도 Troughput
   단위 시간 당 처리할 수 있는 malloc/free횟수
   빠르게 하기 위해 : free블록 탐색 빠르게, malloc은 선형시간 free는 상수시간 정도로 만들수 있음

2. 메모리 효율성 Memory Utilization
   유한한 가상 메모리 공간을 최대한 아끼면서~
   모든 요청이 끝난 후 얼마나 유용한 데이터로 채워졌는지 평가

• 좋은 할당기는 속도와 공간 사이에서 균형이 중요

할당기 = 피자 가게 사장님이야 🍕
사람들이 랜덤하게 전화로 “피자 1개 주세요!” (malloc)
“이거 다시 가져갈게요!” (free) 를 외치고 있어

피자 가게 사장님의 어려움
어떤 손님이 언제 전화를 할지 모름 → 갑자기 3개 달라 했다가, 1개 취소하고 막 뒤죽박죽

바로 응답해야 함 → "지금 주세요!" 하니까, "기다리세요~" 이런 건 안 돼!

창고(힙) 하나만 사용 가능 → 다른 창고 쓰지 말고, 가게 안에 있는 재료로만 해결해야 돼

피자 박스 크기는 정렬되어야 함 → 어떤 손님은 대왕피자, 어떤 손님은 미니피자
→ 그래서 모든 박스는 정해진 크기 기준에 맞게 줘야 돼

배달 나간 박스는 못 바꿈 → 손님한테 간 박스는 다시 열거나 합치면 안 돼!

사장님의 목표 2가지
빠르게 피자 배달 전화 오면 바로바로 피자 만들어서 보내야 함!
재료를 절약하며 사용 재료(메모리)가 한정되어 있으니까 아껴 써야 함
근데
빨리 배달하려고 막 포장하면 → 박스를 너무 크게 써서 재료 낭비
재료를 아끼려고 포장을 천천히 하면 → 손님 기다리게 해서 불만 생김

Fragmentation

메모리가 남아 있는데도, malloc 요청을 만족시킬 수 없는 상황

내부 단편화

int *x = malloc(5); // 요청은 5바이트

할당기는 최소 8바이트 단위로 할당한다고 가정하면:
→ 실제로는 8바이트를 줌 → 3바이트 낭비

즉, "받은 블록 내부에서 낭비되는 공간"

(내부 단편화= 상자 안의 빈 공간)

외부 단편화

재 힙에 이렇게 Free 블록이 있음:

[ Free 4B ] [ Used ] [ Free 4B ]

malloc(8)을 요청하면?
4 + 4 = 8바이트의 빈 공간이 있지만, 연속된 하나의 8바이트 블록이 없음!
→ 할당 실패 → 외부 단편화 발생!

"전체 빈 공간은 충분하지만, 쪼개져 있어서 못 쓰는 낭비"

"현재 상태"만 봐서는 문제가 있는지 없는지 알기 어려움

미래에 어떤 크기의 요청이 들어올지 모르기 때문
외부 단편화는 미래 요청 패턴까지 알아야 제대로 판단할 수 있음 → 현실적으로는 힘듦

(외부단편화: 냉장고에 상자를 넣을 공간이 없는 상황)

so what?

segmaention mapping + paging

할당기는 보통 큰 Free블록을 유지하려 한다
너무 쪼개진 블록은 안만들고자 하고 병함, 블록 정렬등의 기술로 큰 free블록을 만들려함

구현 이슈

• 단순한 할당기:
  힙을 그냥 큰 배열로 생각

포인터 p가 배열의 맨 앞에서 시작

malloc(size) → p를 size만큼 밀고, 이전 위치를 반환

free(ptr)은 아무 일도 안 함

-손님이 오면 → 피자 만들어줌
-빈 박스는 버림 (free는 무시!)

char heap[100000];
char *p = heap;

void *malloc(size_t size) {
  void *old_p = p;
  p += size;
  return old_p;
}

void free(void *ptr) {
  // 아무 것도 안 함
}

장점:
진짜 빠름 (거의 연산 몇 개로 끝남)

Throughput 최상

단점:
절대 재사용 안 함 → 메모리 낭비 극심

메모리 사용 효율이 최악

실제 프로그램에선 사용 불가능

고려사항

Free block organization: Free 블록들을 어떻게 저장하고 관리할까? (리스트, 트리 등)
→ 어떤 박스들이 비어있는지 메모장에 적어둬!

Placement: 새 요청이 들어왔을 때, 어느 Free 블록에 넣을까? (first-fit, best-fit 등)
→ 새 손님이 오면 어떤 박스를 줄까?
→ 너무 큰 박스를 주지 않게 고민해 (first-fit, best-fit)

Splitting: Free 블록이 너무 크면? → 일부만 잘라서 쓰고, 나머지는 다시 Free로 둘까?
박스가 너무 크면?
→ 필요한 만큼만 자르고, 나머지는 다시 적어둬

Coalescing: free()를 하면, 옆에 Free 블록과 합쳐서 큰 덩어리로 만들까? (→ 외부 단편화 줄이기)

빈 박스 두 개가 나란히 있으면?
→ 붙여서 하나의 큰 박스로 만들어둬!