🏎️[C] malloc-lab

이강욱·2022년 10월 31일

C 정글

🏎️ C

목록 보기

2/3

malloc

이번 과제는 malloc을 직접 구현하는 것.
좀 더 명확히는 malloc, free, realloc을 포함하는 동적 메모리 할당기를 만드는 것.

처음엔 책에 있는 코드를 그대로 타이핑 해보면서 이해했으나, 계속 이런 생각이 들었다.

그래서 이게 지금 뭘 하고 있는거지?

생각해보니 malloc이 안에서 어떻게 동작하는 지도 모르고 malloc을 따라 만들려고 했던 것.

그렇담 malloc이 무어냐. memory allocation.

C dynamic memory allocation refers to performing manual memory management for dynamic memory allocation in the C programming language via a group of functions in the C standard library, namely malloc, realloc, calloc and free.
- 출처 : https://en.wikipedia.org/wiki/C_dynamic_memory_allocation

malloc을 포함해 realloc, calloc, free는 C에서 메모리를 동적 할당 받을 수 있게 해주는 함수의 모음인 것.

구체적인 malloc의 내부 로직.

들어가기에 앞서, malloc이 heap 영역을 잡고 유지한다는 차원에서 이해를 돕기위해 pool이라는 단어를 사용했음을 알린다. 결국 같은 말이다.

malloc은 크기가 작은 할당요청에 대해서는 자신이 가진 pool(i.e. heap segment)에서 할당해주고, 크기가 큰 할당요청에 대해서는 pool이 아닌 memory mapping segment에서 할당해준다.
malloc 내에서는 두가지 syscall이 활용되는데, mmap과 sbrk가 그것이다.

sbrk는 malloc이 유지하고 있는(좀 더 정확히는 위에서 언급된 함수들로 이루어진 명시적 할당기에서 유지하고 있는) pool안에서 현재 할당요청에 대한 할당을 해줄 수 없는 상황이 왔을 때, pool의 size를 늘리기위해 사용된다.
sbrk에 원하는 incr를 전달해 호출하게 되면 가상메모리 상에서 heap segment의 끝 지점을 가리키는 program brk가 incr만큼 증가하고, 이는 곧 heap segment의 크기가 증가함을 의미한다. 또 이는 곧 malloc이 유지하는 pool의 크기가 증가함을 의미한다.
mmap은 크키가 큰 할당요청에 대해 memory mapping segment의 영역을 할당해 줄 때 사용된다. 원래 mmap은 '메모리 매핑'을 위해 사용되는 시스템 호출.

메모리 매핑이란, 어떤 가상메모리 영역을 디스크의 파일 내용으로 초기화할때 사용하는 시스템호출.

단, 지금 상황에서는 그저 할당 요청 크기에 맞는 가상메모리 영역을 얻으면 되는 것이므로, 특정 파일 내용이 들어가 있지 않은, 이 프로세스만이 사용 가능한 영역을 받으면 되겠다. 구체적인 내부 구현은 모르겠지만, mmap을 manual로 호출할 때 MAP_ANONYMOUS flag 와, MAP_PRIVATE flag를 주면, 메모리 영역 내부가 0으로 초기화 된, 이 프로세스만 사용 할 수 있는 영역을 얻을 수 있기에 이러한 방법을 사용했으리라 추측된다.

그렇담 왜 크기가 큰 할당 요청에 대해서는 heap의 영역이 아닌 memory mapping segment의 영역을 할당해줄까?
먼저, free를 통해서는 실제 메모리 공간의 반환이 이루어지지 않을 수도 있음을 알아야 한다. 앞서 말했듯 malloc은 자체적인 pool을 유지하면서 할당과 반환을 수행해주기 때문에, 일단 pool의 크기가 정해지면 그 크기 만큼은 해당 프로세스가 계속해서 점유하는 공간이 될 것이다.

이러한 상황에서, 크기가 제법 큰 영역을 pool안에 할당하고 반환한다면, 그리고 구현된 알고리즘의 특성상 그 영역을 활용하지 않게 된다면, 메모리의 낭비가 생길 것이다.

이를 방지하고자, 특정 threshold를 (glibc의 malloc 기준 128KB) 넘는 할당 요청에 대해서는 mmap을 통해 pool(heap segment) 바깥의 가상 메모리 영역에 공간을 할당해주고, free를 요청시 munmap을 통해 시스템에 실제 메모리 공간이 반환될 수 있도록 하는 것이다.

어쨌든 이 모든 이해를 통해 우리가 수행해야할 과제는,

나만의 명시적 할당기(malloc, free, realloc 을 포함하는)를 만드는 것. 구체적으로는 할당기가 갖고있는 pool을 관리하는 방법을 구현하는 것이 되겠다.

할당기가 해야하는 주된 업무는 요청 사이즈에 해당하는 블록을 찾아서 어플리케이션에게 전달해주고, 어플리케이션이 해당 블록을 반환하면 그 공간을 다시 재활용 하는 것.

블록을 찾는 방법을 단순하게 해서 시간을 빠르게 하면,
처리량(throughput)은 늘지만, 공간 활용도(space utilization)는 줄어든다.
반대로 블록을 정교하게 찾아서 공간을 효율적으로 잘 쓰면,
공간 활용도(space utilization)는 늘어나지만, 처리량(throughput)이 줄어들 것이다.

구현 이슈

pool을 관리하는 방법이라 함은,

적합한 free block list의 구조를 선택해 사용하고,
그 list에서 free block을 찾는 방법(알고리즘)을 잘 구현하는 것이다.

구체적으로 보자면 아래와 같다.

free block list의 구조

어떻게 free block들을 지속적으로 추적하는가?

free block list에는 implicit, explicit, segment list, buddy system이 있다.

implicit list : 각 블록의 헤더(와 푸터)에 그 블록의 할당여부가 저장되어 있을 뿐이다. 그래서 가용 블록들을 하나씩 보려면, 무조건 맨 처음 블록부터 퐁당퐁당 하나씩 보면서 그 블록이 free인지 allocated인지 확인해야 한다.
이 관점에서 보면 'free block list'라는건 존재하지 않는다(표면으로 드러나지 않는다). 단지 힙 안에 '묵시적으로' 숨어있는 것이다. 이런 식으로 free 블록을 찾아야 하기 때문에 implicit list라고 부른다.
explicit list : implicit과 다르게, free block 들이 서로 포인터를 통해 연결됨으로써 free block list가 명시적으로 존재하게 된다. 이중 연결 리스트로 구현할 수 있다.
명시적으로 리스트가 존재하기 때문에, 새롭게 발생된 free block을 list에 어떤 방식으로 삽입할 지 방법이 나뉠 수 있다 : LIFO(후입선출) 또는 free block의 address order. 전자는 반환이 빠르고 후자의 반환은 맞는 위치(주소순으로)를 확인해야 하기 때문에 시간이 걸린다. 뒤에서 설명될 first-fit의 방법을 사용한다고 하면, LIFO보다는 address order의 first-fit이 best-fit에 근접하는 좋은 메모리 이용도를 가짐. (best-fit이 가장 좋을테지만, 현실적으로 시간이 너무 오래 걸림. 따라서 first-fit을 사용하면서 list의 구성을 통해 best-fit에 근접해지려는 시도가 많음)
Segregated Lists (Segregated Fit) : 다수의 free block list를 크기 클래스로 나누어 유지하는데, 각 list의 blcok 크기는 그 list에 해당하는 크기 범위 안에 속한다. 분할이나 연결도 하지 않으면서 단지 free block을 크기별로 모아둠으로써 관리와 탐색을 용이하게 함.
빠르고 메모리 관리가 효율적인 방식. 어떠한 요청 크기에 대해 전체 힙이 아닌 해당 크기의 클래스 안(힙의 특정 부분)에서만 검색을 수행하기 때문에 빠른 검색시간.
또한 '해당 클래스'라는 말은 최대한 요청 크기와 비슷한 크기의 블록들 중에서 검색하는 것이므로 메모리 이용도도 나쁘지 않음.
buddy system : segregated fit 방법의 특별 케이스. 각 크기 크래스의 크기가 2의 제곱수이다. 만약 전체 heap size가 $2^m$ 이라면, 크기 클래스들의 크기는 $2^k$ ,where $0 \leq k \leq 2^m$
이다. 맨 처음에는 $2^m$ 크기의 블록 하나가 있고, 요청에 따라 해당 블록을 반으로 계속 쪼개면서 나누게된다. fit한 size의 블록이 생성되면 그 블록을 할당하고, 과정 중에 쪼개진 블록(buddy: 어떤 블록과 크기가 같은 짝꿍 블록)들은 다시 각각의 클래스로 들어가게 된다. 블록을 free할 때는 buddy가 free상태이면 연결하고, allocated buddy가 나올 때 까지 크기를 키워가며 이를 반복한다.
(Memory Partitioning 3: Buddy System).

free block 선택 방법

할당 요청에 적합한 free block을 어떤 방식으로 선택할 것인가?

first fit : free block list를 처음부터 검색해서 크기가 맞는 첫 번째 free block을 선택
next fit : first fit과 유사하나, 검색 시작 지점이 이전 검색이 종료된 지점.
best fit : free block list에 있는 모든 free block을 검사해 크기가 가장 딱 맞는 free block을 선택

분할 (splitting)

free block에서 요청된 size만큼을 뺀 나머지의 블록 영역을 다시 free block으로 만들 것인가?

상관 없이 그냥 선택된 free block 전체를 사용.
(가능하다면) 나머지 부분을 새로운 free blcok으로 재생. -> 과제에서 사용하는 방법

연결 (coalescing)

방금 반환된 free block을 인접한 free block들과 합쳐 하나의 더 큰 free blcok으로 만들 것인가?

즉시 연결 : free block이 반환될 때 마다 즉시 연결. 쓰래싱(연결 후 잠시 뒤 바로 분할됨) 발생 가능. -> 과제에서 사용하는 방법
지연 연결 : 일정 시간 후에 연결. e.g. 어떤 할당 요청이 실패할 때까지 연결하지 않고 있다가, 실패하는 요청이 생기면 그 때 전체 힙을 검색해 모든 가능한 연결을 수행.

사실 이런 모든 노력들을 해야하는 이유는 어플리케이션이 명시적으로 free를 요청하기 때문 (명시적 할당기). 각 요청에 적합한 빈 공간을 탐색하고 할당하는 과정과 그 구조를 구현하는 것이 복잡한 것.
free를 묵시적으로 하기로 약속 한다면, 즉 어플리케이션은 무조건 할당만 받고, 할당 받은 공간 중 더이상 쓰이지 않을 공간들을 할당기 측에서 판단해 임의로 free해줄 수 있다면 공간 관리가 매우 유용해질 것. 단 이 경우에는 할당해준 공간 중 더 이상 쓰이지 않을 할당 공간을 판단하는 기준과 그 구현이 복잡해질 것이다.

배경지식

가상메모리

프로세스들은 서로 cpu와 메인메모리를 다른 프로세스들과 공유한다.
이러한 상황에서 메모리를 보다 효율적이고 더 적은 에러를 갖도록 관리하기 위해 가상메모리(Virtual Memory)라는 메인메모리에 대한 추상화를 이용한다. 이러한 추상화를 통해 프로세스 하나는 자신이 메인메모리 전체를 사용한다고 가정하면서 실행될 수 있다.

가상 메모리를 통해 다음의 세가지 기능을 얻을 수 있다.

메인메모리를 디스크에 대한 캐시로 취급해, 메인 메모리 내 활성화 영역만 유지하면서 필요할 때만 디스크와 메모리 간의 데이터 전송이 이루어지도록 한다.
각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다.
각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다.

데이터 세그먼트

프로그램이 사용하는(자기 자신이 메모리에 올려지는 것 포함) 메모리 공간을 각 용도에 맞게 세그먼트(영역)으로 나눠서 구조화 한 것.

code segment (text segment)
실행가능한 명령어(executable code)가 저장된다. 보통 read-only이고, 사이즈가 정해져있다.
data segment (initialized)
초기화된 static 변수들(e.g. global variables, local static variables)을 포함한다.
BSS segment (Block Started by Symbol)
초기화되지 않은 static 변수들을 포함한다.
이 세그먼트의 데이터들은 프로그램의 실행과 함께 커널에 의해 0으로 초기화된다.
Stack
스택 영역은 LIFO 구조를 가지는 프로그램 스택을 포함한다.
호출된 함수의 지역변수, 함수 수행 이후에 리턴할 주소와 레지스터 상태 값 등의 정보가 저장된다.
Heap
동적 메모리 할당이 수행되는 세그먼트 공간.