malloc은 내부에서 어떻게 메모리를 관리할까

이전 글에서 malloc()이 실제로는 운영체제에서 매번 메모리를 받아오는 함수가 아니라,
이미 확보해둔 메모리를 나눠 쓰는 “관리자”라고 정리했다.

여기까지 보면 자연스럽게 다음 질문이 나온다.

그럼 그 메모리를 어떻게 나눠서 관리하는 걸까?

이걸 이해하려고 하면 한 번은 이런 오해를 한다.

“메모리는 그냥 쭉 이어진 공간이고, 필요한 만큼 잘라서 쓰면 되는 거 아닌가?”

실제로는 그렇게 단순하지 않다.

---

메모리는 “연속된 공간”이 아니라 “관리되는 조각”이다

프로그램 입장에서는 메모리가 하나의 큰 공간처럼 보인다.
하지만 malloc 내부에서는 그렇게 보지 않는다.

운영체제가 넘겨준 큰 메모리 덩어리를 이렇게 본다.

[--------- 하나의 큰 공간 ---------]

이걸 그대로 쓰는 게 아니라, 내부에서는 이렇게 쪼개서 관리한다.

[ chunk ][ chunk ][ chunk ][ chunk ]

여기서 chunk라는 건 그냥 “메모리 조각”이다.
그리고 중요한 건, 이 조각이 단순히 데이터만 담고 있는 게 아니라는 점이다.

각 chunk에는 이런 정보가 같이 붙어 있다.

• 이 블록의 크기
• 지금 사용 중인지
• 앞뒤 블록 상태

즉, 메모리는 그냥 바이트 배열이 아니라
관리 정보가 붙어 있는 구조체들의 집합에 가깝다.

---

free는 “삭제”가 아니라 “표시”다

이제 free를 보면 조금 다르게 보인다.

free(ptr);

이걸 처음 보면 이렇게 생각한다.

“메모리를 반납했다”

하지만 실제로는 그렇지 않다.

malloc 입장에서 free는

“이 블록 다시 써도 된다”

라는 표시일 뿐이다.

그래서 내부 상태는 이런 식이 된다.

[ 사용중 ][ free ][ 사용중 ][ free ]

여기서 중요한 건, 이 free 상태의 블록들을 어떻게 관리하느냐이다.

---

그래서 등장하는 게 bin이다

이제 진짜 핵심 구조가 나온다.

free된 블록들을 그냥 리스트로 들고 있으면 어떻게 될까?

[ 16B ][ 128B ][ 32B ][ 64B ][ 8B ]

여기서 malloc(32) 요청이 들어오면,
매번 전부 뒤져야 한다.

이건 당연히 느리다.

그래서 나온 아이디어가 이거다.

“크기별로 미리 나눠서 보관하자”

이게 bin이다.

---

내부에서는 이런 식이다

16B bin → [16][16][16]
32B bin → [32][32]
64B bin → [64][64][64]

이 상태에서 malloc(32)가 오면 어떻게 될까?

→ 그냥 32B bin에서 하나 꺼내면 끝이다.

그래서 malloc이 빠른 거다.

---

그런데 항상 딱 맞는 블록이 있는 건 아니다

여기서 현실적인 문제가 생긴다.

예를 들어 32B를 요청했는데,
32B bin이 비어 있고 64B만 남아 있다고 해보자.

이때 선택지는 두 개다.

1. 그냥 64B를 준다 (낭비)
2. 쪼갠다

대부분 allocator는 두 번째를 선택한다.

---

splitting — 큰 걸 쪼개서 쓴다

이게 splitting이다.

[ 64B free ]

이걸 이렇게 나눈다.

[ 32B 사용 ][ 32B free ]

이건 굉장히 자연스러운 선택이다.
필요한 만큼만 쓰고, 나머지는 다시 재사용하면 되니까.

그런데 이게 반복되면 어떤 일이 생길까?

---

메모리가 점점 조각난다

이런 상태를 상상해보자.

[ free ][ 사용 ][ free ][ 사용 ][ free ]

총 free 메모리는 충분하다.
그런데 연속된 큰 공간은 없다.

이 상태에서 큰 메모리를 요청하면 실패한다.

이게 fragmentation이다.

---

그래서 다시 합치는 과정이 필요하다

이걸 해결하려면 반대로 해야 한다.

“쪼갰으면 다시 합칠 수도 있어야 한다”

이게 coalescing이다.

---

예를 보면

[ 32B free ][ 32B free ]

이걸

[ 64B free ]

로 합친다.

이걸 통해 다시 큰 메모리를 만들 수 있다.

---

결국 malloc은 이걸 계속 반복한다

여기까지 보면 구조가 보인다.

malloc이 하는 일은 결국 이거다.

• 남아 있는 블록 중에서 적절한 걸 찾고
• 없으면 쪼개고(splitting)
• free되면 다시 합치고(coalescing)
• 가능한 한 재사용한다

즉,

메모리를 계속 “재구성”하면서 관리하는 시스템이다.

---

여기서 중요한 포인트 하나

이 구조를 이해하면 이상했던 것들이 설명된다.

---

왜 malloc은 대부분 빠를까

→ bin에서 바로 꺼내기 때문

---

왜 가끔 느려질까

→ 딱 맞는 블록이 없어서

• splitting
• coalescing
• 더 큰 탐색

이 발생하기 때문

---

왜 fragmentation이 문제일까

→ 메모리는 충분한데 “쓸 수 없는 상태”가 되기 때문

---

이제 다음 질문이 자연스럽게 나온다

여기까지 보면 한 가지 의문이 남는다.

malloc은 O(1)이라면서 왜 느려지는 순간이 있을까?

이건 단순히 알고리즘 문제가 아니라
실제 시스템 성능 문제로 이어진다.

---

한 줄 정리

malloc은 메모리를 단순히 나눠주는 게 아니라, chunk 단위로 쪼개고, bin으로 관리하고, 필요하면 다시 합치면서 계속 재구성하는 시스템이다.