[TIL/크래프톤 정글] DAY 48

배재준·2025년 4월 26일

8기 TIL krafton jungle malloc week07 가상메모리 컴퓨터시스템

크래프톤 정글 - TIL

목록 보기

41/93

2025.04.26

TIL(TODAY I LEARN)

오늘한 내용 : CS - 가상메모리 9.9
WEEK07: 시스템 콜, 데이터 세그먼트, 메모리 단편화, sbrk/mmap

9.9 동적 메모리 할당

동적 메모리 할당의 필요성
- 런타임에 프로그램이 필요로 하는 메모리 크기를 미리 알 수 없을 때가 많다.
- 예) 사용자 입력 크기에 따라 배열 크기를 유연하게 결정해야 할 때
힙(heap)과 brk(“break”) 포인터
- 힙은 프로세스 가상 주소 공간에서 .bss(미초기화 데이터) 바로 위에서 시작해 위쪽(높은 주소)으로 확장
- 커널은 각 프로세스에 대해 brk 포인터를 유지하며, 이 포인터가 힙의 ‘끝’을 가리킨다
- 프로세스는 sbrk(incr) 또는 mmap/munmap 호출로 힙 크기를 늘이거나 줄일 수 있다
블록 단위 관리
- 힙은 여러 크기의 블록(block) 들로 구성된다.
  - 할당된 블록: 플리케이션이 사용 중인 영역
  - 자유 블록: 아직 할당되지 않아 곧바로 사용할 수 있는 영역
- 한 번 할당된 블록은 free(명시적 할당자)나 가비지 콜렉터(암시적 할당자)가 해제할 때까지 유지
명시적 vs. 암시적 할당자
- 명시적(explicit) 할당자:
  - 프로그래머가 malloc/free(C), new/delete(C++)로 직접 관리
- 암시적(implicit) 할당자 / 가비지 컬렉터:
  - 런타임이 더 이상 참조되지 않는 블록을 자동으로 해제(예: Java, ML, Lisp)

9.9.1 malloc과 free 함수

1. 인터페이스

#include <stdlib.h>
void *malloc(size_t size);
void  free(void *ptr);

malloc(size)
- 요청한 size 바이트 이상의 메모리 블록을 반환
- 반환 주소는 32비트 모드에서 8바이트, 64비트 모드에서 16바이트 경계에 정렬됨
- 실패 시 NULL 반환, errno에 ENOMEM 등 설정
- 초기화되지 않은(쓰레기) 상태의 메모리를 제공
- 제로 초기화가 필요하면 calloc 사용
- 기존 블록 크기 변경은 realloc 사용
free(ptr)
- malloc/calloc/realloc으로 받은 블록을 해제
- ptr이 유효하지 않으면(이미 해제했거나 다른 블록 포인터인 경우) 정의되지 않은 동작
- 반환값이 없으므로 잘못된 free는 런타임 오류를 일으킬 수 있음

2. 힙 확장 메커니즘

malloc 내부에서 더 큰 힙이 필요하면 커널에 sbrk 또는 mmap 호출
sbrk 함수
```
#include <unistd.h>
void *sbrk(intptr_t incr);
```
- 힙 끝을 incr 바이트만큼 늘리거나 줄임
- 성공 시 이전의 brk(힙 끝) 주소 반환, 실패 시 1 반환 및 errno = ENOMEM
- incr == 0일 때는 현재 brk 주소만 반환
mmap/munmap을 사용해 별도 가상 메모리 영역을 직접 매핑/해제할 수도 있음

9.9.2 왜 동적 메모리 할당인가?

프로그램 실행시키기 전까지 자료 구조의 크기를 알 수 없는 경우(입력된 정수 개수 n 만큼의 배열이 필요할 때)들이 있기 때문
- Malloc 호출 시점에 n을 알기 때문에 필요한 만큼만 메모리 확보

9.9.3 할당기 요구사항과 목표

1. 할당자가 지켜야 할 제약 조건

임의의 요청 순서
- malloc/free 요청은 어떤 순서로든 올 수 있다.
- 각 free는 이전에 malloc된 블록이어야 하지만, 중첩·짝짓기 구조를 가정할 수 없다.
즉각 응답
- 요청이 들어오면 재정렬이나 지연 없이 바로 처리해야 한다.
힙 전용 사용
- 내부 자료구조(자유 리스트 등)도 모두 힙 메모리 내에 저장해야 확장성 확보.
정렬(alignment) 보장
- 모든 블록은 요구된 데이터 타입에 맞게 정렬되어야 한다.
할당 블록 불변
- 할당된 블록은 이동(compaction)이나 크기 변경 없이 고정된 위치에 있어야 한다.

2. 성능 목표

할당자는 위 제약을 지키면서 다음 두 가지 상충되는 목표를 최적화해야 한다.

처리량(Throughput) 최대화
- 단위 시간당 완료한 malloc+free 요청 수
- 예: 1초에 500번 malloc과 500번 free를 완료하면, 처리량은 1,000 ops/sec
- 처리량을 높이려면 평균 요청 처리 시간을 최소화해야 함
메모리 활용도(Utilization) 최대화
- 힙에 할당된 유효 데이터(payload) 대비 실제 확장된 힙 크기 비율

- 할당한 힙 중에 얼마나 데이터를 꽉 채워 사용했는가?

처리량(빠른 할당/해제)과 낭비되는 힙 공간(단편화)을 적절히 균형 맞추는 것이 성능 목표

9.9.4 단편화

1. 내부 단편화(Internal Fragmentation)

정의: 할당된 블록 크기(block size)가 실제로 사용되는 페이로드(payload)보다 클 때 발생하는 낭비
원인
- 최소 블록 크기, 정렬(alignment) 요구에 맞추기 위해 블록을 늘려야 할 때
- 예) 5워드 요청 → 6워드(패딩 포함)로 할당 → 1워드(4바이트) 낭비

2. 외부 단편화(External Fragmentation)

정의: 자유 블록들의 총합(aggregate free memory)은 충분하지만, 개별 자유 블록들이 흩어져 있어 연속된 요청을 만족시킬 수 없을 때 발생
원인
- 할당/해제 패턴에 따라 여러 크기의 자유 블록이 중구난방으로 남을 때
- 서로 인접한 자유 블록이 있지만 합쳐지지 않아 요청에 맞지 않는 경우
특징
- 정량화 어려움: 미래에 어떤 크기의 요청이 올지 모르므로 “단편화가 심하다”를 객관적으로 측정하기 어려움
- 동일한 자유 블록 분포라도, 이후 요청 패턴에 따라 단편화의 심각성이 달라짐

[allocated: 8][free: 4][allocated: 8][free: 4]
→ 총 8워드(free) 남음에도 8워드 연속 블록 없음 → 8워드 요청 실패

내부 단편화 = 할당된 블록 안에 남아 버린 “패딩” (32−30 = 2B)
외부 단편화 = 총 여유 공간은 충분해도, “연속된” 큰 블록이 없어서 요청을 못 채우는 상황

9.9.5 구현 이슈

가장 간단한 할당기는 커다란힙에서 주소(포인터)를 꺼내주는 것으로 구현 가능
위는 블록들을 하나도 재사용 하지 않음 → 메모리 이용도 낮음
실용적인 할당기들이 고려해야할 이슈
1. 가용(자유) 블록 구성: 어떤 식으로 힙 내의 free 블록들을 관리할 것인가
  - Implicit Free List (9.9.6)
    - 각 블록 헤더의 크기/할당 비트만으로 힙을 순회하며 자유 블록을 찾음
    - 구현 간단하지만, 탐색 비용이 힙의 블록 수에 비례하여 느림
  - Explicit Free List (9.9.13)
    - 자유 블록 몸체에 pred/succ 포인터를 저장하여 연결 리스트 관리
    - 자유 블록 수에 비례하는 빠른 탐색(First‐Fit 시 O(#free))
    - LIFO 순서 vs 주소 순서 등 삽입·삭제 정책에 따라 해제 비용·메모리 활용도가 달라짐
  - Segregated Lists(9.9.14)
    - 크기 구간별로 여러 리스트 유지 → 검색 범위 대폭 축소
2. 배치 정책: 새로 할당 요청이 들어왔을 때 어떤 가용 블록에 할당할 것인가 (9.9.7)
  - First Fit: 리스트 앞에서 첫 번째 맞는 블록 사용
  - Next Fit: 마지막 찾은 위치부터 탐색 시작
  - Best Fit: 모든 자유 블록을 스캔해 가장 작은 적합 블록 선택
  - 각 정책은 탐색 속도, 스플린터(splinter) 생성 경향, 단편화 특성에 차이를 보임
3. 블록 분할: 큰 free 블록에 작은 요청이 들어왔을 때, 남는 공간을 어떻게 처리할 것인가?
  - 전 블록 사용: 간단하지만 내부 단편화 심해짐
  - 블록 분할: 요청한 크기만큼 앞부분을 할당하고 나머지를 새로운 자유 블록으로 유지
    - 분할 후 남은 조각이 최소 블록 크기 이상일 때만 수행
    - 분할을 자주 하면 외부 단편화 발생 가능
4. 블록 병합: free가 호출되어 블록이 해제될 때 인접한 free 블록과 병합할 것인가?
  - 해제된 블록 주변의 자유 블록과 즉시 또는 지연 병합하여 “False Fragmentation” 방지
  - Immediate Coalescing
    - free 시 인접 블록과 바로 합병 → 항상 O(1) 비용
    - 그러나 반복적인 할당/해제 패턴에서 분할⇄병합 스래싱(thrashing) 유발 가능
  - Deferred Coalescing
    - 병합을 지연해 뒀다가, 예를 들어 할당 실패 시 전체 스캔하며 병합
    - 평상시 free는 빠르나, 병합 시점에 잠재적 O(n) 비용

9.9.6 묵시적(암시적) 가용 리스트(Implict Free Lists)

가장 간단한 자유 블록 관리 기법 : 힙 전체를 블록 단위로 순차 탐색

블록 포맷

[ 헤더(size | alloc) ]  ← 1워드(4B)
[ payload (할당된 경우) ]
[ padding? ]           ← alignment 충족용

헤더(1 word(4byte)): 전체 블록 크기(바이트)와 할당 상태 비트(LSB)를 저장
페이로드 : 데이터 (미할당 시 쓰레기 값)
패딩 : 가변적인 크기를 가짐
- 왜쓰지? → 1. 외부단편화 극복, 2. 정렬 요구사항 만족
풋터 없음: 이전 블록 정보를 알 수 없어 병합 시 루프 스캔 필요

힙 모양 예시

블록 크기는 항상 8의 배수

[size/alloc]
[unused: 크기=4]    ← sbrk가 반환한 주소를 8B 경계로 맞추기 위해 버린 4B 패딩
[  8/0 ]           ← 첫 번째 진짜 자유 블록 (8B, alloc=0)
[ 16/1 ]           ← p1 블록 (16B, alloc=1)
[ 32/0 ]           ← p3 블록 (32B, alloc=0)
[ 16/1 ]           ← p4 블록 (16B, alloc=1)
[  0/1 ]           ← 에필로그 헤더 (종료 표시)

장점: 헤더 하나만 쓰고, 병합·검색 코드는 아주 단순
단점:
- 빈 블록 찾기 비용이 힙의 블록 수에 비례(O(n))
- 해제해도 병합 안 돼서 빈 조각(fragment)만 늘어남

9.9.7 할당한 블록의 배치

1. First Fit

동작: 힙의 시작(프로로그 다음)부터 순차 탐색하여, 가장 먼저 size ≥ asize이면서 alloc=0인 블록을 선택
장점
- 평균 탐색 범위가 짧아 빠름
- 리스트 뒤쪽에 큰 블록이 온전히 남아 커다란 요청에 유리
단점
- 앞부분에 잘라진 작은 조각(스플린터)이 쌓여, 나중에 큰 요청 시 탐색 비용 증가
- 외부 단편화(front-end fragmentation) 경향

2. Next Fit

동작: “마지막으로 검색을 멈춘 위치”에서부터 다시 순차 탐색
장점
- Front의 작은 조각을 건너뛰어 First Fit보다 빠른 경우 있음
단점
- 리스트 뒷부분에 작은 조각이 많으면 원위치까지 돌아와야 해서 비효율
- 메모리 활용도(Utilization)가 First Fit보다 떨어질 수 있음

3. Best Fit

동작: 힙 전체를 스캔해, size ≥ asize인 블록 중 가장 작은 블록을 선택
장점
- 내부 단편화(internal fragmentation) 최소화
- 요청 크기와 최대한 근접한 블록 사용
단점
- 매번 전 범위 검색 → 탐색 비용 최악
- 작은 스플린터가 힙 곳곳에 흩어져 외부 단편화 심화

추가

단일 리스트의 한계를 넘어서려면, 후속 절의 “분리된 자유 리스트(Segregated Free Lists)”나 “버디 시스템(Buddy System)” 같은 기법을 도입해 탐색 범위를 줄이고 단편화를 완화할 수 있음.

9.9.8 가용(자유) 블록의 분할

1. 전체 블록 사용(Whole‐block Allocation)

방법: 찾은 자유 블록을 통째로 할당
장점: 구현 단순, 오버헤드·분기 로직 없음
단점: 블록 크기가 요청 크기보다 크면 내부 단편화(남는 공간 낭비) 심해짐

2. 블록 분할(Block Splitting)

방법: 자유 블록의 앞부분만 asize 만큼 할당하고, 나머지 뒷부분을 새로운 자유 블록으로 유지

9.9.9 추가적인 힙 메모리 획득하기

할당 요청을 만족시킬만한 자유 블록이 없으면, 할당자는 다음 두 가지를 시도.

인접 자유 블록 병합(Coalescing)
- 해제된 블록들을 즉시 합쳐 더 큰 자유 블록을 만든 뒤에 다시 find_fit을 시도할 수 있음.
힙 확장(Extend Heap)
- 이미 최대한 병합했는데도 요청을 맞출 블록이 없으면, 커널에 sbrk 함수를 호출해 힙을 더 늘려 달라고 요청함.

9.9.10 가용(자유) 블록 연결하기

할당된 블록을 해제해 자유 블록이 늘어나면, 인접한 자유 블록끼리 합쳐 주지 않으면 작은 조각들이 흩어져 false fragmentation가 발생

병합(coalescing) 정책

정책	설명	장점	단점
즉시 병합(Immediate)	`free` 시점에 항상 앞·뒤 인접 블록과 합쳐 버림	- 구현 간단- 병합 비용 O(1)	- 반복적 할당↔해제 패턴에서 분할⇄병합 스래싱 발생 가능
지연 병합(Deferred)	`free`는 간단히 표시만 하고, 나중에 (예: 할당 실패 시 전체 스캔) 일괄 병합	- 평소 `free`가 빠름	- 병합 시점에 O(n) 스캔 비용

9.9.11 경계 태그로 연결하기

풋터가 없으면 O(n) 탐색이 필요하지만, 경계 태그를 도입하면 상수 시간(O(1))에 앞뒤 블록을 모두 검사·합병할 수 있음.

경계 태그 아이디어

헤더(Header): 블록 시작에 “크기 + 할당 비트”
풋터(Footer): 블록 끝에 헤더를 그대로 복제
연결리스트 이전 이후 노드 다 표현한 것처럼

블록포인터bp를 해제한 뒤, 이전(prev_alloc)과 다음(next_alloc) 블록의 할당 비트를 확인해 네 가지 케이스별로 처리

Case	prev_alloc	next_alloc	동작
1	1	1	양쪽 모두 할당 중 → `bp`만 자유로 표시 (헤더·풋터 alloc=0)
2	1	0	다음 블록과 병합 → 헤더 크기 += next.size, 풋터 위치 → next
3	0	1	이전 블록과 병합 → 풋터 크기 += prev.size, 헤더 위치 → prev
4	0	0	양쪽과 모두 병합 → 헤더 위치 → prev, 풋터 위치 → next

9.9.12 종합 설계: 간단한 할당기의 구현

9.9.13 명시적 가용 리스트(Explicit Free List)

free 블록들만 골라 연결된 링크드 리스트로 관리해, 탐색·삽입·삭제 비용을 줄이는 기법

“자유 블록만 연결” → First‐Fit 탐색 비용을 O(#free) 로 단축

pred/succ 포인터를 자유 블록 몸체에 저장하여 헤더·풋터만으로 경계 정보를 유지

자유 블록 포인터 공간이 추가로 필요 → 최소 블록 크기 커짐, 내부 단편화 가능성 증가

자유 블록 리스트 관리법

| 정책 | 설명 | 장점 | 단점 |
| --- | --- | --- | --- |
| **LIFO(스택)** | 해제되는 블록을 리스트 맨 앞에 삽입 | `free` 시 O(1)– `coalesce` 후 바로 삽입 | 주소 분포 고려 안 함 → 단편화↑ |
| **주소 순(Address‐ordered)** | 블록 주소 순으로 리스트 유지 | 인접 블록 합병 시 삽입 위치 바로 결정– First‐Fit과 비슷한 활용도 | `free` 시 삽입 위치 찾으려 O(#free) 탐색 필요 |

9.9.14 분리 가용 리스트(Segregated Free Lists)

블록들을 크기 클래스의 집합들로 분리해 관리
두개의 기본 방법 소개 / 간단한 분리 저장장치, 분리 맞춤

Simple Segregated Storage

구성: 각 리스트에 고정 크기(size class의 최댓값) 블록만 보관
할당:
1. 요청 크기에 맞는 리스트에서 첫 블록을 꺼내 통째로 할당
2. 리스트가 비어 있으면, 운영체제에서 큰 청크(페이지 단위)를 받고 동일 크기 블록으로 잘라 채워 넣음
해제: 블록을 해당 크기대 리스트 앞에 삽입
장점:
- 할당·해제 모두 O(1)
- 분할·병합 전혀 없으므로 오버헤드 최소
단점:
- 내부 단편화 심함(항상 최대 크기만 할당)
- 외부 단편화 방어 불가(병합 안 함)
ex) {17~31} 이면 무조건 32 바이트로 다 할당

Segregated Fits

구성: 각 리스트는 해당 크기대에 속하는 가변 크기 블록을 보관
할당:
1. 요청 크기대 리스트에서 First-Fit 탐색
2. 없으면 더 큰 크기대 리스트로 이동
3. 블록을 할당 후 남은 조각은 적절한 리스트에 분할하여 삽입
해제: 블록을 병합한 뒤, 병합된 블록을 해당 리스트에 삽입
장점:
- 검색 범위 국소화 → 빠르면서도 내부 단편화 억제
- First-Fit만으로도 전체 best-fit에 근접하는 활용도
단점:
- 리스트 개수·크기대 정의 복잡
- 관리 오버헤드 다소 증가
ex)

Class 0: 1–16B  
Class 1: 17–32B  
Class 2: 33–64B  
…  
20B 할당 -> class 1로 감
1. 요청 크기대 리스트에서 **First-Fit** 탐색
-> 예를 들어 24B 있으면 거기 넣음

2. 블록을 할당 후 남은 조각은 적절한 리스트에 분할하여 삽입
-> 스플릿 여부 판단 24 - 20  = 4B
-> 4B가 최소 블록 크기(헤더+풋터+정렬 등 오버헤드)를 만족하면
-> 분할해서 4B 자유 블록을 만들어 class 0에 삽입
-> 그렇지 않으면, 24B 통째로 할당 -> 내부 단편화 발생

3. 없으면 더 큰 크기대 리스트로 이동
-> 다음 큰 class2로 이동해서 검색

버디 시스템(Buddy System)

특징: 크기대를 2^k 단위(2의 거듭제곱)로만 허용
할당:
1. 요청 크기를 2^k로 반올림
2. 그 크기 리스트에서 블록을 찾거나, 더 큰 블록을 반씩 쪼개며(split) 필요한 크기까지 분할
해제:
1. 블록의 “버디(buddy)”(주소가 1비트 차이)와 병합 가능하면 합치고,
2. 합쳐진 새 블록의 버디도 검사 → 재귀적 병합
장점:
- O(1) 할당·해제(병합)
- 메타데이터 단순
단점:
- 크기제약(2^k)으로 내부 단편화가 심할 수 있음

Simple Segregated: 고정 크기만, O(1) 빠르지만 단편화 심함
Segregated Fits: 가변 크기 + 분할·병합, 빠르면서도 단편화 억제
Buddy System: 2의 거듭제곱 크기대, O(1) 분할·병합, 내부 단편화 존재

배재준

^_^

이전 포스트

[TIL/크래프톤 정글] DAY 47

다음 포스트