늦어도 다시 한번 : Malloc Lab

두 번째 시리즈 시작이다.

저번 주에 했던 Malloc Lab 이야기다.

일단 팀은 너무 마음에 들었고(모든 팀이 마음에 들었다), 팀이 결성된 목요일에 아바티 CTO님이 오셔서 나태해진 나에게 채찍을 엄청 때리고 가셨다.

강연을 듣고 이번 주 우리 팀이 생각한 목표는 같았다. Malloc, 메모리 할당에 대해서 다시 보지 않아도 될 정도로 보고 가자! 그건 불가능했다..

일단은 책에 있는 내용을 구현하는 게 기본 틀이라서 책을 먼저 읽었다. 동적 메모리 할당(dynamic memory allocation) 이 어떤 것이고, 내부적으로 어떻게 구현되는지, 흐름을 한 번 짚어봤다.

간단히 설명하자면

사용자가 malloc() 호출 → 힙 관리자(heap manager) → 커널 시스템 콜

여기서 커널 시스템 콜이 두 가지로 나뉜다.

두 가지 방식의 차이는 용도와 관리 방식에 따라 다르다.

sbrk는 힙의 top 포인터를 단순히 증가시키는 방식이다. 그런데 만약 중간에 거대한 공간을 할당한다면 문제가 생긴다.

예)

4KB - 4KB - **4GB** - 4KB

나중에 4GB 공간을 free()하더라도, sbrk 포인터는 여전히 힙의 최상단을 가리키고 있어서 가운데에 커다란 ‘구멍(hole)’이 남는다.

재사용은 가능하지만, 커널에 반환이 불가능하기 때문에 결국 내부 단편화(internal fragmentation)가 발생하게 된다.

이를 해결하기 위해 블록을 분할(split)해서 사용하긴 하지만, 여전히 큰 공간이 남고, split 과정에서 오버헤드가 발생한다.

반면 mmap은 별도의 페이지 단위 메모리를 커널로부터 직접 할당받는다. free() 시 munmap()으로 즉시 커널에 반납할 수 있다. 즉, 내부 단편화 걱정은 줄지만, 대신 단점이 있다.

그래서 일반적으로 glibc 같은 실제 malloc 구현체도

작은 요청은 sbrk, 큰 요청은 mmap 으로 혼합해서 사용한다.

다시 돌아오면, 커널이 페이지를 확보하면 프로세스의 가상 주소 공간에 매핑하고, malloc의 내부 자료구조(가용 리스트, 헤더/푸터 등)를 업데이트한 다음 사용자에게 포인터를 리턴한다.

정처기 시험 보러 갈 때는 보자마자 포기했던 malloc이었는데… 지레 겁먹고 포기해버린 지난날이 밉다. 이렇게 재밌는 걸.

일단은 둘째 날까지 묵시적 가용 리스트(implicit free list) 로 동적 메모리 할당 구현을 끝냈다. 그다음은 명시적 가용 리스트(explicit free list) 로 넘어가야 하는데… 참 어려웠다.

세그폴트는 왜 이렇게 많이 나는 거고, 디버깅도 어떻게 해야 할지 모르겠고... 나란 사람은 왜 이렇게 게으르게 살았고, 전공 공부는 왜 안 했으며, 가진 건 왜 이렇게 없는지...

지난 생애에 대한 회한이 밀려오기 시작할 때쯤, 그냥 제미나이의 도움을 받기로 했다.

생각보다 단순한 문제였는데, 팻핑거 이슈로 인한 오타와 포인터를 잘못 꽂아 넣은 두 가지 함수가 문제였다. 이거 수정했으면 짜릿했을 것 같은데, 도파민 날려먹은 게 억울했다.

다음으로는 분리 가용 리스트의 구현이었다. 이때쯤이 아마 월요일 저녁이었던 것 같다. 슬슬 발표 준비도 시작해야 돼서 마음이 급했던 것 같다.

분리 가용 리스트는 크기별로 여러 개의 가용 리스트를 만들어 탐색 시간을 줄이는 방식이다. 예를 들어, 16B, 32B, 64B, 128B… 식으로 구간을 나누고, 요청 크기에 맞는 리스트에서만 탐색한다. 그래서 묵시적/명시적 리스트보다 훨씬 빠르다.

발표 주제는 분산 컴퓨팅 시스템에서 가상 메모리를 사용하는 방법이었다.

분산 시스템에서는 각 노드(컴퓨터)가 각각의 RAM을 가지고 있다. 그런데 마치 하나의 거대한 메모리처럼 동작해야 할 때가 있다.

예를 들어,

즉, 논리적 통합 메모리 공간을 구성하기 위해 가상 메모리 관리 기법(Virtual Memory Management)이 분산 환경에서도 쓰인다.

2분 안에 설명하기 힘들어서, 그냥 파이썬으로 시뮬레이터를 만들어 Streamlit 대시보드로 띄워 시연했다. 세부 내용은 궁금하면 따로 물어보셔요...

결국 마지막 날, 분리 가용 리스트 구현에는 성공했다. AI를 좀 덜 써보려고 내 TIL들이랑 구글링을 참고하면서 구현했는데, 그러면서 드는 생각이 있었다.

“코드 짜 달라고 하는 게 아니면, 그냥 TIL 보나, 구글링 하나, 스택 오버플로우 뒤지나, AI 쓰나 같은 거 아닌가…”

결국 지금은 검색을 대체한 구글 2.0처럼 AI를 쓰고 있다. 물론, 할루시네이션(환각 답변) 은 항상 체크해야겠지만.