C언어로 malloc(), free(), realloc()함수 구현하기
6주차에는 c언어로 동적할당 구현하는 것이 과제로 나왔다. Carnegie Mellon University의 Malloc Lab을 직접 구현할 수 있어서 뜻깊은 시간이였다.
6주차역시 5주차와 마찬가지로 C언어를 리눅스로 프로그래밍해야 하기 때문에 Ubuntu 18.04 LTS (x86_64)을 사용하였고 우분투를 도커를 이용해 실행하였다.
메모리가 free상태인 공간을 관리하기 위한 세 가지 주요 방법은 Implicit free list(암시적), Explicit free list(명시적), Segregated free list(분리가용)이 있다.
Implicit free list
- 암시적 목록 방식은 메모리 블록의 할당 및 해제 정보를 명시적으로 유지하지 않는다. 대신, 블록들은 메모리 공간 내에 순차적으로 배치되고, 할당되지 않은 블록들 사이에는 특정한 마커를 사용하여 구분한다.
- 할당된 블록을 찾기 위해서는 메모리를 순회하면서 블록들 사이의 구분 마커를 확인해야 한다.
- 암시적 목록 방식은 간단하고 구현하기 쉽지만, 메모리 관리 오버헤드가 높고 할당 및 해제 작업이 비효율적이다.
Explicit free list
- 명시적 목록 방식은 할당 및 해제된 메모리 블록의 정보를 명시적으로 유지한다. 각 블록은 연결 리스트의 형태로 구성되어 있으며, 각 블록은 할당 여부와 다음 블록을 가리키는 포인터를 포함한다.
- 명시적 목록 방식은 메모리 관리 오버헤드를 줄일 수 있고, 할당 및 해제 작업의 효율성을 높일 수 있다.
- 명시적 목록 방식은 추가적인 포인터를 유지해야 하므로 메모리 사용량이 증가하고, 리스트를 탐색하는 데 필요한 시간이 추가될 수 있습니다.
Segregated free list
- 분리가용 목록 방식은 명시적 목록의 확장으로, 메모리 블록을 크기에 따라 여러 개의 Class로 나눈다.
- 각 Class는 특정 크기 범위의 블록들을 관리하며, 각 Class는 명시적으로 유지된다.
- 분리가용 목록 방식은 메모리 할당 및 해제 작업을 빠르게 수행할 수 있으며, 적절한 크기의 블록을 찾기 위한 검색 시간을 줄일 수 있다.
- 분리가용 목록 방식은 메모리 내의 낭비를 줄일 수 있다.
그리고 메모리를 free된 공간에 할당하기위해 First-Fit, Next-Fit, Best-Fit, Worst-Fit을 이용하여 알맞은 공간을 찾을 수 있다.
First-Fit
- First-Fit 방법은 가장 먼저 맞는(첫 번째로 발견된) 충분한 크기의 가용 메모리 블록을 선택하여 할당한다.
- 메모리를 순차적으로 검색하며, 처음으로 발견된 충분한 크기의 블록을 사용한다.
- First-Fit 방법은 빠르고 간단하며 구현하기 쉽지만, 메모리 낭비가 발생할 수 있다.
Next-Fit
- Next-Fit 방법은 직전에 할당된 위치부터 탐색을 시작하여 가용 메모리 블록을 찾아 할당한다.
- 탐색을 직전 할당된 위치에서 재개하기 때문에, 이전에 사용한 메모리 영역 근처에 새로운 할당이 이루어질 가능성이 높다.
- First-Fit보다는 메모리 낭비가 적을 수 있으나, 여전히 메모리 낭비가 발생할 수 있다.
Best-Fit
- Best-Fit 방법은 사용 가능한 메모리 블록 중에서 요청한 크기와 가장 작게 차이나는 블록을 선택하여 할당한다.
- 모든 가용 블록을 검색하여 가장 작은 차이를 가지는 블록을 선택한다.
- Best-Fit 방법은 메모리를 최대한 효율적으로 사용할 수 있지만, 할당 작업에 필요한 탐색 시간이 더 오래 걸릴 수 있다.
Worst-Fit
- Worst-Fit 방법은 사용 가능한 메모리 블록 중에서 요청한 크기보다 큰 블록을 선택하여 할당한다.
- 모든 가용 블록을 검색하여 가장 큰 블록을 선택한다.
- Worst-Fit 방법은 메모리 낭비를 최소화할 수 있지만, 메모리 단편화를 유발할 가능성이 높고, 할당 작업에 필요한 탐색 시간이 길어질 수 있다.
우리팀은 각자 하고싶은 방식으로 구현을 하고 각자 이름으로 깃허브에 브랜치를 이름/구현방식으로 생성하여 마지막날에 제일 효율적인 코드를 팀 코드에 제출하였다.
나는 Explicit free list와 Worst-fit 방식으로 구현을 하였다.
이번 프로젝트를 통해 malloc함수의 실행과정에 대해 분석하는 경험을 통해 개발자의 길에 한발짝 다가간 느낌이였다.
c뿌리는 감자