[CS:APP/C언어] Malloc Lab 사전 지식: 힙, 가용 리스트, 병합, 파편화
2024년 04월 15일 00시 57분 27초에 업로드 된 글입니다.작성자: kugorang728x90TL;DR (세 줄 요약)
- Malloc Lab은
malloc,free,realloc을 직접 구현하는 과제입니다. 이 글은 구현을 시작하기 전에 알아야 하는 사전 지식을 정리합니다. - 힙은
sbrk로 늘립니다. 블록마다 크기와 사용 여부를 적은 헤더를 두고, 비어 있는 블록(가용 블록)은 리스트로 관리합니다. 할당 정책(First Fit, Best Fit 등)과 병합(Coalescing)이 파편화와 처리 속도에 영향을 줍니다. - 과제는 사용률(힙을 얼마나 낭비 없이 썼는가)과 처리량(1초에 요청을 몇 번 처리했는가)을 함께 봅니다. 두 값은 한쪽을 올리면 다른 쪽이 내려가기 쉬우므로 둘을 함께 확인해야 합니다.
이 글은 크래프톤 정글 4기에서 Malloc Lab을 구현하기 전에 정리한 사전 지식입니다. Malloc Lab은 CS:APP(Computer Systems: A Programmer's Perspective) 교재에 딸린 실습 과제입니다. 관련 용어를 정의와 동작 위주로 설명합니다.

그림. DALL·E 3로 만든 CS:APP Malloc Lab 사전 지식 글의 대표 그림 1. 가상 메모리와 페이징은 무엇인가요?
가상 메모리는 각 프로그램이 실제 물리 메모리보다 큰 주소 공간을 혼자 쓰는 것처럼 보이게 하는 기술입니다. 물리 메모리는 컴퓨터에 실제로 꽂혀 있는 메모리(RAM)입니다. 운영체제는 프로그램에 필요한 부분만 물리 메모리에 올리고 나머지는 디스크에 둡니다. 그래서 프로그램은 실제 메모리보다 많은 데이터를 다룰 수 있습니다.
페이징은 어떻게 동작하나요?
가상 주소 공간을 같은 크기의 조각으로 나눈 것을 페이지라고 부릅니다. 페이지 단위로 메모리를 관리하는 방식을 페이징이라고 부릅니다.
- CPU가 가상 주소로 메모리에 접근합니다.
- 메모리 관리 장치(MMU)가 페이지 테이블을 봅니다. 페이지 테이블은 가상 주소의 페이지가 물리 메모리의 어디에 있는지 적어 둔 표입니다.
- 그 페이지가 물리 메모리에 있으면 바로 접근합니다.
- 물리 메모리에 없으면 페이지 폴트가 발생합니다. 페이지 폴트는 CPU가 "이 페이지가 메모리에 없다"고 운영체제에 알리는 일입니다. 운영체제는 디스크에서 그 페이지를 가져와 물리 메모리에 올립니다.
페이징은 왜 필요한가요?
- 메모리 절약: 모든 코드와 데이터를 올리지 않고 필요한 페이지만 올립니다.
- 독립성: 프로그램마다 별도의 주소 공간을 가집니다. 그래서 한 프로그램의 오류가 다른 프로그램에 번지지 않습니다.
- 보안: 다른 프로그램의 메모리에 접근하지 못하게 막을 수 있습니다.
교체 알고리즘과 스레싱은 무엇인가요?
물리 메모리가 가득 차면 어떤 페이지를 디스크로 보낼지 정해야 합니다. 이것을 정하는 방법을 페이지 교체 알고리즘이라고 부릅니다. 가장 오랫동안 쓰이지 않은 페이지를 보내는 LRU(Least Recently Used)가 대표적입니다.
페이지를 너무 자주 옮기면 실제 작업보다 페이지를 옮기는 데 시간을 더 쓰게 됩니다. 이 상태를 스레싱(thrashing)이라고 부릅니다.
2. 동적 메모리 할당과 힙은 무엇인가요?
프로그램이 실행 중에 필요한 만큼 메모리를 요청하고 다 쓰면 돌려주는 것을 동적 메모리 할당이라고 부릅니다. 이때 쓰는 공간이 힙(heap)입니다. 힙은 시작 주소에서 높은 주소 쪽으로 자랍니다.
sbrk와 mmap은 무엇인가요?
함수 하는 일 sbrk프로그램의 힙 끝 주소를 늘리거나 줄입니다. 커널(운영체제의 핵심 부분)에 "힙을 n바이트 늘려 달라"고 요청하는 함수입니다. mmap파일이나 장치를 프로세스의 주소 공간에 연결합니다. 큰 메모리를 힙이 아닌 별도 영역에 받을 때도 씁니다. malloc과 free는 무슨 일을 하나요?
void *malloc(size_t size); void free(void *ptr); void *realloc(void *ptr, size_t size); // 크기 변경, 필요하면 복사malloc(size): size바이트 이상을 담을 수 있는 블록을 찾아 그 시작 주소를 돌려줍니다. 블록은 힙을 나눈 조각 하나입니다.free(ptr):malloc이 돌려준 주소를 받아, 그 블록을 다시 쓸 수 있다고 표시합니다.realloc(ptr, size): 이미 받은 블록의 크기를 size바이트로 바꿉니다. 제자리에서 바꿀 수 없으면 새 블록을 받아 내용을 복사합니다.
free는 보통 메모리를 커널에 바로 돌려주지 않습니다. 다음malloc이 그 자리를 다시 쓸 수 있게 가용 블록 목록에 넣습니다.3. 메모리 누수와 파편화는 무엇인가요?
다 쓴 블록을
free하지 않으면 그 블록은 다시 쓸 수 없습니다. 이런 블록이 쌓이면 프로그램이 쓸 수 있는 메모리가 줄어듭니다. 이것을 메모리 누수라고 부릅니다.파편화는 빈 공간이 있는데도 쓰지 못하는 현상입니다. 두 가지가 있습니다.
종류 뜻 예 내부 파편화 할당한 블록 안에서 요청한 데이터에 쓰이지 않는 공간입니다. 100바이트를 요청했는데 정렬과 헤더 때문에 112바이트 블록을 주면, 12바이트는 요청한 데이터에 쓰이지 않습니다. 외부 파편화 빈 공간의 총합은 충분한데 여러 조각으로 흩어져 있어 큰 블록을 만들 수 없는 상태입니다. 500바이트 빈 공간 두 개가 서로 떨어져 있으면 1000바이트 요청을 처리할 수 없습니다. 정렬은 블록의 시작 주소와 크기를 8이나 16 같은 정해진 수의 배수로 맞추는 것입니다.
4. 파편화는 어떻게 줄이나요?
병합(Coalescing)과 경계 태그는 무엇인가요?
free한 블록의 바로 앞이나 바로 뒤 블록이 비어 있으면, 이웃한 빈 블록을 하나로 합쳐 큰 블록을 만듭니다. 이것을 병합이라고 부릅니다.병합하려면 앞뒤 블록이 비어 있는지 빠르게 확인해야 합니다. 그래서 블록마다 다음 두 가지를 둡니다.
- 헤더: 블록의 맨 앞에 크기와 사용 여부를 적습니다.
- 푸터: 블록의 맨 뒤에 헤더와 같은 값을 적습니다.
이 두 값을 경계 태그라고 부릅니다. 현재 블록의 바로 앞에는 앞 블록의 푸터가 있습니다. 그 푸터를 읽으면 앞 블록의 크기와 사용 여부를 바로 알 수 있습니다. 그래서 블록이 몇 개든 병합에 걸리는 시간이 일정합니다. 이것을 O(1)이라고 적습니다.
// 블록 헤더: 크기(하위 비트 제외) + 할당 비트 #define SIZE_MASK ~0x7 #define ALLOC 0x1 size_t header = *(size_t *)block; // 크기와 할당 여부 size_t size = header & SIZE_MASK; int allocated = header & ALLOC;- 블록 크기는 정렬 때문에 8의 배수입니다. 8의 배수는 2진수로 적으면 맨 아래 3비트가 항상 0입니다. 그래서 이 3비트에 다른 정보를 넣을 수 있습니다.
ALLOC 0x1: 맨 아래 1비트를 할당 여부로 씁니다. 1이면 사용 중이고 0이면 비어 있습니다.SIZE_MASK ~0x7: 맨 아래 3비트를 0으로 지우는 값입니다.header & SIZE_MASK: 헤더에서 크기만 꺼냅니다.header & ALLOC: 헤더에서 할당 여부만 꺼냅니다.
가용 리스트에는 어떤 종류가 있나요?
가용 리스트는 비어 있는 블록을 찾아갈 수 있게 이어 둔 목록입니다.
종류 방법 특징 묵시적 가용 리스트 (Implicit) 모든 블록을 앞에서부터 차례로 따라가며 쓸 수 있는 블록을 찾습니다. 헤더에 크기가 있으므로 다음 블록의 위치를 계산할 수 있습니다. 구현이 단순합니다. 찾는 시간이 전체 블록 수에 비례합니다. 명시적 가용 리스트 (Explicit) 비어 있는 블록끼리만 포인터로 연결합니다. 찾는 범위가 빈 블록으로 줄어 빠릅니다. 할당과 해제 때 포인터를 고쳐야 합니다. 분리 가용 리스트 (Segregated) 크기별로 리스트를 여러 개 두고, 요청한 크기에 맞는 리스트부터 찾습니다. GNU C 라이브러리의 malloc같은 실제 할당기가 쓰는 방식입니다.할당 정책에는 무엇이 있나요?
할당 정책은 여러 가용 블록 중 어느 것을 줄지 정하는 규칙입니다.
정책 방법 특징 First Fit 앞에서부터 찾아 처음 만난 충분히 큰 블록을 줍니다. 빠릅니다. 리스트 앞쪽에 작은 조각이 쌓입니다. Next Fit 지난번에 할당한 위치부터 찾습니다. 앞쪽에 조각이 몰리는 것을 줄입니다. Best Fit 요청을 담을 수 있는 블록 중 남는 공간이 가장 작은 블록을 줍니다. 낭비가 적습니다. 끝까지 찾아야 해서 느리고, 아주 작은 조각이 생깁니다. Worst Fit 가장 큰 블록을 줍니다. 남는 공간이 커서 다시 쓸 수 있습니다. 큰 블록이 빨리 없어집니다. 5. Malloc Lab은 무엇을 요구하나요?
과제는 두 가지 값을 함께 봅니다.
지표 뜻 올리는 방법 사용률 힙 전체 크기 중 프로그램이 요청해서 실제로 쓴 바이트의 비율입니다. 헤더 크기와 정렬로 생기는 낭비를 줄입니다. 처리량 1초 동안 처리한 malloc과free요청의 횟수입니다.가용 리스트를 잘 관리해 블록을 찾는 시간을 줄입니다. 두 값은 한쪽을 올리면 다른 쪽이 내려가기 쉽습니다. 예를 들어 Best Fit은 낭비를 줄이지만 찾는 시간이 깁니다. 점수는 두 값을 함께 계산합니다. 그래서 한쪽만 좋게 만든 구현은 높은 점수를 받기 어렵습니다.
코드를 고친 뒤에는 반드시 과제에 들어 있는 채점 프로그램(드라이버)을 돌려 두 값을 확인해야 합니다. 코드 수정, 측정, 실제 채점은 각각 다른 단계입니다.
6. 함께 알면 좋은 개념은 무엇인가요?
개념 뜻 가비지 컬렉션 더 이상 참조되지 않는 메모리를 자동으로 회수하는 기능입니다. C 언어에는 없고 Java와 C#에 있습니다. 메모리 풀 같은 크기의 블록을 미리 여러 개 잡아 두고, 요청이 오면 거기서 꺼내 씁니다. 할당 시간과 내부 파편화를 줄입니다. 컴팩션 흩어진 블록을 한쪽으로 모아 크고 연속된 빈 공간을 만듭니다. 블록의 주소가 바뀌므로, 주소를 포인터로 직접 들고 있는 C 언어에서는 쓰기 어렵습니다. 이 개념들만으로 Malloc Lab이 바로 풀리지는 않습니다. 하지만 헤더, 가용 리스트, 병합, 두 지표의 관계를 알고 시작하면 시행착오가 줄어듭니다. 같은 과제를 하는 분께 도움이 되면 좋겠습니다.
자주 묻는 질문 (FAQ)
Q1. free를 하면 메모리가 운영체제로 돌아가나요?
대부분은 아닙니다.
free는 그 블록을 가용 리스트에 넣어 다음malloc이 다시 쓸 수 있게 표시합니다. 힙의 끝부분이 충분히 비면sbrk로 힙을 줄일 수 있습니다. 하지만 Malloc Lab에서는 힙을 줄이지 않는 구현이 일반적입니다.Q2. 경계 태그는 왜 앞뒤에 둘 다 두나요?
다음 블록으로 갈 때는 현재 블록의 주소에 헤더에 적힌 크기를 더하면 됩니다. 하지만 이전 블록으로 갈 때는 이전 블록의 크기를 알아야 하는데, 헤더만으로는 알 수 없습니다. 푸터에 같은 크기를 적어 두면 현재 블록 바로 앞에서 이전 블록의 크기를 읽을 수 있습니다. 그래서 이전 블록으로 O(1)에 이동해 병합할 수 있습니다.
Q3. 사용률과 처리량 중 무엇을 먼저 올려야 하나요?
점수는 두 값을 함께 계산하므로 한쪽만 올려서는 높은 점수를 받기 어렵습니다. 보통은 헤더와 정렬을 먼저 정해 사용률의 기본 수준을 만듭니다. 그다음 가용 리스트 구조를 개선해 처리량을 올리는 순서가 안전합니다.
수정 안내
이 글은 2026년 11월 21일에 다시 썼습니다. 이전 판에서 "디스크에서 페이지를 가져오는 과정"을 페이지 폴트라고 적은 것을 "페이지가 메모리에 없을 때 CPU가 운영체제에 알리는 일"로 고쳤습니다. 병합 조건을 "앞뒤가 모두 비어 있으면"에서 "앞이나 뒤가 비어 있으면"으로 고쳤습니다. 묵시적 가용 리스트에서 다음 블록으로 이동할 수 있는 이유를 "헤더에 사용 여부가 있어서"에서 "헤더에 크기가 있어서"로 고쳤습니다. "한쪽만 좋게 만든 구현은 점수가 오르지 않는다"는 표현은 "높은 점수를 받기 어렵다"로 고쳤습니다. 5번 항목에서 본문이 코드 블록 안에 들어가 있던 형식 오류를 바로잡았습니다.
참고 자료
같은 주제의 다른 글: [PintOS/운영체제] Project 1 Threads 개념 정리: 스케줄링·동기화·MLFQS, [게임 인프라] 게임 운영체제(OS) 비교: 콘솔, PC, 모바일은 무엇이 다른가
728x90728x90'시스템 & 인프라 > PintOS & CS' 카테고리의 다른 글
[게임 인프라] 게임 운영체제(OS) 비교: 콘솔, PC, 모바일은 무엇이 다른가 (1) 2025.04.13 [데이터베이스] DB 인덱스(Index) 핵심 원리: B-Tree 구조와 검색 성능 최적화 (2) 2025.01.16 [PintOS/운영체제] Project 1 Threads 개념 정리: 스케줄링·동기화·MLFQS (4) 2024.03.17 다음글이 없습니다.이전글이 없습니다.댓글- Malloc Lab은