Malloc Lab
해당 글은 말록랩 실습과 리스트 종류, 배치 정책, 삽입 정책 등에 관한 내용을 다룹니다. 시간이 된다면 추후에 말록랩에 대한 개념을 정리해보겠습니다.
C 프로그램에서…
malloc은 메모리를 효과적으로 할당해주는 동적 할당을 해줍니다.
free는 그렇게 할당된 메모리를 해제해줍니다.
→ 앞으로 이러한 malloc을 직접 C언어로 구현해보면 됩니다.
직접 구현하기 전에 기본적인 리스트 종류와 배치 정책, 삽입 정책을 알아보겠습니다.
먼저, 정글에서 말록랩을 과제로 다운 받아실행을 해봅시다.
본인의 깃으로 클론한 다음에 깃 서버에 있는 리포지트리를 다운 받아 오면 로컬로 가지고오게 되고 그 파일을 열어보면 됩니다.
보통 도커를 통해 사용할 것입니다. 정글에서 설명한 기본적인 환경 세팅이 완료됐다는 가정하에 설명하겠습니다.
Malloc lab 실행해보기
실행하기 전에 해당 패키지들이 우분투에 설치되어 있어야합니다.
sudo apt update # package list update
sudo apt upgrade # upgrade packages
sudo apt install gcc make valgrind gdb # gcc, make 등 개발 환경 설치
sudo apt install gcc-multilib # 32-bit lib (WEEK06만 필요)
cd명령어를 통해 말록랩 폴더로 이동한다.make로 말록랩 파일을 만든다../mdriver를 통해 make로 만든 말록랩을 실행시킨다.(./mdriver -V사용시 테스트 케이스별 결과를 알 수 있다.)- 각각의 테스트 케이스(trace)에 따라 계산된 이용도(60) + 처리량(40)를 합해서 효율을 알려준다.(초기엔
out of memory로 뜬다) - 실행을 완료했으면 꼭 make clean을 통해 파일을 삭제해주자.
→ 위에 계산된 이용도와 처리량의 합을 최대치로 끌어 올리는 것이 이번 주 목표이다.
초기에는 우리가 앞으로 수정할 mm.c에 malloc을 구현하지 않았기 때문에 out of memory라고 뜰 것입니다.
malloc에 성능에 큰 영향을 주는 가용 블록 관리 방식(list 종류), 블록 배치 정책을 적절히 사용하여 높은 점수의 malloc을 구현해봅시다.
1. 가용 블록 관리 방식(list 종류)
1. Implicit Free List(암시적 가용 리스트)
- 모든 블록(할당된 블록 + 가용 블록)을 메모리에 일렬로 저장하는 방식.
- header에 블록이 사용 중(allocated)인지 여부를 기록해서 구분.
- 할당할 때 매번 전체 블록을 순차적으로 스캔해야 가용블럭 찾을 수 있다.
특징
- 탐색시간이 O(n)으로 성능이 별로다.
- 헤더만 있으면 되니, 구조가 단순하다.
예시) [헤더][데이터][헤더][데이터][헤더][데이터] (전부 이어져 있다.)
2. Explicit Free List(명시적 가용 리스트)
- 가용 블록만 따로 포인터로 연결해서 관리하는 방식.
- 각 가용 블록 내부에 선임자(Predecessor) 포인터, 후임자(Successor) 포인터가 있음. (이중 연결 리스트)
- 할당된 블록은 리스트에 포함되지 않는다.
특징
- 가용 블록끼리만 연결하니까 탐색 속도가 O(k)으로 훨씬 빠르다. (
k는 가용 블록 수) - 대신 메모리에 포인터 2개 추가 저장해야 하므로 약간 오버헤드 발생한다.
- 삽입/삭제가 빠르다.
예시) 가용 블록 A → 가용 블록 B → 가용 블록 C (포인터로 이어진다.)
3. Segregated Free List(분리 맞춤 리스트)
- 블록 크기별로 여러 개의 리스트를 따로 관리하는 방식.(16바이트/32바이트/64바이트 이하 리스트 별로)
- 새 블록을 요청할 때, 해당 크기 리스트만 빠르게 검색해서 할당할 수 있다.
특징
- 할당/해제 속도가 매우 빠름 (
O(1)에 가깝다) - 메모리 사용이 다소 비효율적일 수 있다 (리스트 수가 많아짐)
예시) [16B 이하 리스트][32B 이하 리스트] [64B 이하 리스트] … (각자 따로 포인터로 연결된 구조)
가용 블럭 관리 방식 요약표
| 리스트 종류 | 특징 | 장단점 |
|---|---|---|
| Implicit List | 전체 블록 순차 스캔 | 단순하지만 느림 |
| Explicit List | 가용 블록만 포인터로 연결 | 빠르지만 포인터 오버헤드 있음 |
| Segregated List | 크기별로 블록 분리 관리 | 매우 빠르지만 복잡하고 관리비용 큼 |
2. 배치 정책(Placement Policies)
malloc/free에서 자주 쓰이는 3가지 주요 배치 정책에 대해서 알아보겠습니다.
1. First Fit (최초 적합, 최초 검색)
가용 리스트를 앞에서부터 순차적으로 탐색해서 요청한 크기보다 크거나 같은 첫 번째 가용 블록에 할당하는 방법.
특징
- 탐색이 빠를 수도 있다. (운 좋으면 초반에 찾는다)
- 하지만 가용 블록들이 점점 쪼개져서 "단편화(fragmentation)" 문제가 생기기 쉽다.
예시) 블록 [10][30] [50] 있는데 25바이트 요청하면 30짜리 블록에 할당.
2. Best Fit (최적 적합, 최소 남김)
가용 리스트 전체를 스캔한 다음에 요청한 크기보다 크거나 같은 블록 중에서 "가장 작은 것"을 선택하는 방법.
특징
- 공간 낭비(외부 단편화)가 가장 적다. (블록을 가장 "딱 맞게" 쓴다)
- 하지만 전체를 다 검색해야 하니까 탐색 시간이 오래 걸릴 수 있다 (
O(n))
예시) 블록 [10][30] [50] 있을 때, 25바이트 요청하면 30짜리 선택. (30이 50보다 작으니까)
3. Next Fit (다음 적합, 순환 검색)
직전에 할당했던 가용 블록 이후부터 검색을 시작하는 방법. 리스트의 끝에 도달하면 처음부터 다시 순환해서 찾는다.
특징
- First Fit보다 살짝 빠를 수 있다 (항상 처음부터 다시 찾지 않기 때문이다)
- 하지만 단편화 문제는 First Fit과 비슷하다.
- "최근 사용 지역"을 피하기 때문에 약간 더 균등하게 메모리를 쓴다는 이론도 있다.
예시) 만약 직전에 블록 [10]을 썼다면, 다음에는 [30], [50] 순서로 탐색 시작.
배치 정책 요약표
| 배치 정책 | 탐색 방식 | 장점 | 단점 |
|---|---|---|---|
| First Fit | 처음부터 순차적으로 검색 | 빠를 수 있음 | 단편화 발생 가능 |
| Best Fit | 전체 검색 후 가장 작은 블록 선택 | 메모리 낭비 적음 | 탐색 오래 걸림 |
| Next Fit | 이전 탐색 위치 이후부터 검색 | 탐색 시간 줄어듦 | 단편화 문제 여전 |
3. 삽입 정책 (Insert Policies)
1. LIFO 삽입 (Last-In-First-Out)
특징
- 새로운 free 블록을 항상 리스트 맨 앞에 추가한다.
- 삽입이 빠르다. (리스트 포인터 몇 번만 바꾸면 됨)
- 하지만 주소 순서가 아니라서, 인접 블록을 찾기가 어렵다. → 병합할 때 별도 탐색 필요.
장점
- 삽입이 O(1) — 매우 빠르다.
- 구현이 간단하다.
단점
- 가용 리스트가 주소 순서대로 정렬되지 않음.
coalesce()때 블록 병합을 하려면 인접한 블록을 별도로 찾아야 함 → 성능 저하 위험
코드 예시
bp->succ = free_list_root;
if (free_list_root != NULL)
free_list_root->pred = bp;
bp->pred = NULL;
free_list_root = bp;2. 주소순 삽입 (Address-Ordered Insertion)
특징
- free 블록을 메모리 상의 주소 순서대로 삽입한다.
- 삽입할 때 삽입 위치를 찾기 위해 리스트를 쭉 검색해야 한다.
장점
- 가용 리스트가 메모리 주소 순서로 정렬돼 있음.
- coalescing이 매우 쉽다. (free_list 바로 앞뒤만 보면 인접 여부 알 수 있음)
- 단편화(fragmentation) 가 줄어드는 경향이 있음.
단점
- 삽입이 O(n) — (최악의 경우 전체 리스트 다 탐색해야 함)
- 구현이 약간 더 복잡함.
코드 예시(간단화)
void add_free_block(void *bp) {
void *p = free_list_root;
void *prev = NULL;
while (p != NULL && p < bp) {
prev = p;
p = GET_SUCC(p);
}
// bp를 prev와 p 사이에 삽입
if (prev == NULL) {
free_list_root = bp;
} else {
GET_SUCC(prev) = bp;
}
GET_PRED(bp) = prev;
GET_SUCC(bp) = p;
if (p != NULL)
GET_PRED(p) = bp;
}삽입 정책 요약표
| 구분 | LIFO 삽입 (Last-In-First-Out) | 주소순 삽입 (Address-Ordered) |
|---|---|---|
| 동작 | 새로 생긴 free 블록을 항상 리스트 맨 앞에 넣음 | free 블록을 메모리 주소 순서에 맞게 삽입 |
| 삽입 속도 | 아주 빠름 (O(1)) | 느림 (O(n), 주소 비교 필요) |
| 병합(Coalescing) | 복잡 (인접 블록 찾기 어려움) | 아주 쉽다 (리스트상에서 바로 앞/뒤 확인 가능) |
| 단편화(Fragmentation) | 증가할 가능성 있음 | 감소할 가능성 높음 |
| 구현 난이도 | 쉬움 | 약간 복잡 |
최적의 조합은?
위의 내용을 생각해보면 최적의 조합을 생각할 수 있다.
Malloc 구현 시 위에 서술된 가용 리스트 종류와 배치정책을 잘 조합하면, 메모리 성능과 단편화 문제를 해결한 조합을 만들 수 있다.
- 암시적 리스트 + First Fit = 느림
- 명시적 리스트 + Next Fit = 빠름
- 분리 맞춤 리스트 + Best Fit = 매우 빠르고 효율적 (최상)
