[SW 정글] WEEK06 개발일지(동적 메모리 할당, Malloc Lab)
* C언어와 CS에 대해 배워가고 있는 단계입니다. 정리 목적으로 제 생각을 적은 부분이 많습니다. 틀린 부분이 있다면 댓글로 알려주시면 감사하겠습니다.
C언어를 공부한 지 일주일 만에 시작하게 된 Week06주 차 주제는 C언어에서 동적 메모리 할당(Dynamic Memory Allocation)을 할 때 사용하는 malloc함수를 직접 구현해보는 것이었다. 지난주에 RB Tree를 구현하며 malloc을 사용했는데, 그때 malloc 함수는 RB Tree 구조체(struct)와 노드 구조체를 저장할 공간을 할당받기 위해 사용되었다. 이번 포스팅에서는 동적 메모리 할당이 무엇인지, 그리고 대표적인 malloc의 구현 방식(정책, policy)은 어떤 것이 있는지 간단히 적어보도록 하겠다.
동적 메모리 할당은 왜 하는 걸까?
프로그램을 실행했을 때 우리가 선언한 변수들은 어떤 식으로든 메모리에 저장이 되어 있어야 한다. 그러나 프로그램에게 할당된 메모리는 유한한 자원이기 때문에 사용하지 않는 변수는 메모리에서 삭제되어야 한다. 따라서 프로그래머는 내가 선언할 변수가 (1) 함수 내부에서만 쓰이고 다른 곳에서는 사용될 필요가 없는지(지역 변수), (2) 프로그램이 실행되는 동안에는 계속 사용될 예정인지(전역 변수) (3) 프로그램이 실행되는 동안에는 계속 사용될 예정이지만 다른 함수, 프로그램에서의 변수 사용은 제한되어야 하는지(정적 변수), 그리고 (4) 특정 함수나 프로그램의 실행, 종료와는 상관없이 특정 경우에만 생성해 사용될 예정인지(동적 할당)를 고려해 코드를 작성해야 한다.
이때 (1) 지역 변수의 생성과 소멸은 해당 지역 변수가 속한 함수에 종속되며, 함수의 특성상 현재 실행 중인 함수는 스택(stack)에서 관리하기 편하므로 지역 변수와 함수는 메모리의 스택 영역에서 관리되며, 함수가 종료되면 지역 변수는 자동으로 사라지게 된다. 그리고 (2) 전역 변수와 (3) 정적 변수는 프로그램이 시작하면 종료될 때까지 생존해 있기 때문에 두 변수 모두 데이터 영역에서 관리된다. 지역, 정적, 전역 변수들은 프로그램이 실제로 실행되기 전인 컴파일 타임에 어떤 변수가 선언되는지 파악할 수 있기 때문에 데이터 영역과 스택 영역의 사이즈는 이때 결정되게 된다. 즉, 코드를 작성한 순간 할당해야 하는 메모리가 "정적(static)"으로 결정된다.
동적 메모리 할당(Dynamic Memory Allocation)
그와 달리 (4) 동적 할당의 경우는 내가 생성해야 하는 변수의 생성과 삭제가 특정 조건들에 종속되기 때문에 프로그램을 실행하지 않고서는 메모리가 얼마나 필요할지 알 수 없으며, 프로그램을 실행해보고 나서야(런타임) 알 수 있다. 또한 외부에서 프로그램을 어떻게 사용하느냐에 따라 변수를 생성하기 위한 조건을 만족하는 경우가 많을 수도 있고 적을 수도 있기 때문에 프로그램을 어떻게 사용하느냐에 따라 필요한 메모리의 양도 ''동적(dynamic)"으로 달라지게 된다.
지난주에 RB Tree에 대해 공부했으니 우리가 트리 자료구조를 만드는 코드를 짠다 치고 동적 메모리 할당에 대해 이해해보자. 우리는 트리를 생성하고, 노드를 삽입해주는 함수를 만들고 해당 함수가 있는 프로그램 파일을 이용해 그때그때 우리가 필요한 모양의 트리를 만들고 싶다고 치자. 프로그래머의 입장에서 노드를 삽입해주는 함수를 만든다 생각했을 때, 우리는 이 함수의 사용자가 노드를 몇 개나 만들지 알 수 없으며(이는 런타임 때 동적으로 결정될 것이다.) 사용자가 함수를 호출할 때마다 노드를 만들어 삽입해줘야 한다. 그렇기 때문에 생성한 노드 변수가 차지할 공간은 힙 영역에 동적 할당을 해줘야 하는 것이다.
동적 할당 해제(Free)와 메모리 누수
스택의 지역 변수가 차지하고 있는 메모리가 함수의 종료와 함께 자동으로 할당 해제되는 것과는 달리, 동적 할당된 변수는 사용이 완료된 경우(ex. 트리의 노드 삭제) 해당 변수가 차지하고 있는 메모리 영역의 할당을 해제(Free)해줘야 다음에 해당 메모리 영역을 사용할 수 있다. C언어의 경우 동적 할당된 변수를 더 이상 사용할 일이 없을 경우 해당 메모리 주소를 직접(명시적으로) free 시켜줘야 하는데, 이를 명시적 할당기(Explicit Allocator)라 한다. 반면, JAVA, Python 언어와 같이 사용이 끝난 변수의 메모리를 프로그램이 자동으로 수거해주는 프로그램을 garbage collector라 하며, 이를 묵시적 할당기(Implicit Allocator)라 부른다.
한편, 이미 사용이 끝난 동적 할당 변수를 free 시켜주지 않고 그냥 두게 되면 쓸모없는 변수가 메모리를 차지하게 되는데, 이를 메모리 누수(Memory Leakage)라 부른다. 메모리 누수가 심해지면 heap 메모리 영역이 가득 차 동적 할당을 할 수 없게 되고, 결국 프로그램이 강제로 종료되게 된다. 특히 서버 프로그램과 같이 장시간 동안 동작되는 프로그램에 메모리 누수가 발생하는 경우 심각한 문제를 일으킬 수 있다. 따라서 C언어를 작성할 땐 사용이 끝난 변수는 반드시 할당을 해제해줘야 한다.
malloc의 힙 메모리 할당 전략과 구현
malloc 함수
malloc은 size를 인자로 받아 힙 메모리 영역에서 size(Byte)만큼의 공간을 변수에 할당해주는 함수이다. 정확하게는 malloc함수가 인자로 받은 size만큼 힙 영역에 공간을 확보해주고 확보된 메모리의 시작 주소(포인터)를 리턴해준다.
malloc 함수의 메모리 할당 전략
Allocator(malloc 함수와 free함수)는 메모리 할당, 해제 요청에 대해 최대한 빠르고(Throughput), 공간 효율적(Space Utilization)으로 응답해줘야 한다. Allocator가 지켜야 하는 규칙은 아래와 같다.
- Allocator는 할당(allocate)과 반환(free) 요청에 대해 아무런 가정도 할 수 없다. 즉, 사용자가 어떤 사이즈의 블록(메모리 할당 단위)을 요청하거나 free 시키더라도 잘 대응할 수 있도록 설계해야 한다.
- Allocator는 할당과 반환 요청이 들어오면 즉시 처리해야 한다. 즉, 성능 향상을 위해 요청의 순서를 바꾸거나 미루는 일이 일어나서는 안 된다.
- 힙 영역의 메모리만 사용해야 한다.
- 블록을 나눌 때 정렬(alignment) 조건을 만족해야 한다.(여기서는 8바이트의 배수로 블록 사이즈를 align)
- Allocator는 가용 블록(할당되지 않은 블록)만 수정할 수 있으며, 이미 할당된 블록을 분할, 병합, 이동하는 행동을 해서는 안 된다.
이를 실현하기 위해 allocator를 구현하는 과정에서 힙 영역을 어떤 방법으로 할당해줄지 다양한 전략을 선택할 수 있는데, 선택한 전략에 따라 allocator의 성능이 달라지게 된다. 하지만 절대적으로 좋은 전략이 있는 것은 아니며 할당을 요청하는 사이즈가 크냐, 작냐 또는 범위가 넓냐 좁냐 등에 따라 좋은 전략이 바뀌게 된다. 따라서 상황에 따라 사용하는 allocator도 달라지게 된다. Allocator가 선택할 수 있는 전략의 요소는 아래와 같다.
1. Free list 구성 방식 : 가용 블록(할당되지 않은 블록)을 어떻게 관리할 것인가.(Free list는 가용 블록들만 모아놓은 리스트를 말한다)
- Implicit Free List : 가용 블록을 따로 관리하지 않는다. 따라서 할당 요청이 들어오면 힙 전체를 처음부터 탐색한다.
- Explicit Free List : 가용 블록을 링크드 리스트 자료구조로 관리한다. 따라서 할당 요청이 들어오면 가용 블록만 담겨 있는 free list에서 탐색한다.
- Segregated Free List : 블록의 사이즈에 따라 class를 나누어 class별로 free list(링크드 리스트)를 따로 관리한다. 따라서 할당 요청이 들어오면 요청이 들어온 사이즈에 맞는 class의 free list에서 탐색한다.
2. 배치 : 할당이 가능한 여러 개의 블록들 중에서 어떤 블록을 할당시킬 것인가.
- First fit : free list의 맨 처음부터 시작해 탐색을 시작해 가장 처음으로 찾은 블록을 할당
- Next fit : 이전에 할당되었던 블록의 다음부터 탐색을 시작해 가장 처음으로 찾은 블록을 할당
- Best fit : free list에 있는 블록들 중 할당 요청한 사이즈와 가장 가까운 블록을 할당
3. 분할 : 요청한 사이즈보다 큰 블록(넉넉한 블록)을 할당해줬을 때 블록의 남은 공간을 어떻게 할 것인가.
- 남은 공간을 쪼갠 뒤 활용하는 것이 무조건 좋을 것이라 생각할 수 있지만, 반드시 그런 것은 아니다. 예를 들어 힙 영역에 여유가 있거나 할당한 블록을 곧 free 시키는 경우가 많다면 쪼개지 않고 할당하는 편이 더 좋을 수 있다.
4. 연결(Coalesce) : free 된 블록의 앞 또는 뒤에 가용 블록이 있다면, 이 블록들을 연결할 것인가 아니면 그냥 둘 것인가.
위의 전략 요소들을 조합하여 Implicit free list, Explicit free list와 Segregated free list 중 Simple Segregated Storage 방식으로 allocator를 구현해보았다. 구현에 있어서 구체적인 요소들까지 다루면 포스팅이 너무 길어지므로 구현에 중요한 역할을 했던 CSAPP 교재의 그림과 구현 코드가 있는 Git Hub 링크를 첨부하며 마무리하겠다.
GitHub - GrilledSalmon/malloclab-jungle: 정글 Week06 malloc 만들깅
정글 Week06 malloc 만들깅. Contribute to GrilledSalmon/malloclab-jungle development by creating an account on GitHub.
github.com