728x90
반응형
SMALL
메모리 관리 기법 정리
0 ) 용어 먼저
- 내부 단편화(Internal): 할당한 블록 내부에서 남는 공간이 낭비.
- 외부 단편화(External): 총 여유 공간은 충분하지만, 연속된 큰 블록이 없어 실패.
- 분할(Split)·병합(Coalescing): 큰 자유 블록을 쪼개거나, 인접 자유 블록을 합쳐 외부 단편화 완화.
- 압축(Compaction): 프로세스를 이동시켜 연속 공간을 만드는 작업(연속 메모리에서만 의미).
1 ) 연속 메모리 할당(Contiguous Allocation)
(A) 고정 분할(Fixed Partitioning)
- 메모리를 고정 크기로 나눠 미리 두는 방식.
- 장점: 관리 간단, 오버헤드 적음.
- 단점: 프로세스 크기와 딱 맞추기 어려워 내부 단편화 큼, 유연성 낮음.
(B) 가변 분할(Dynamic/Variable Partitioning)
- 요청 크기에 맞춰 그때그때 분할.
- 장점: 내부 단편화 ↓.
- 단점: 시간이 지나면 외부 단편화 ↑ → 주기적 병합/압축 필요.
- 여기서 쓰는 할당 전략이 First/Next/Best/Worst/Quick 등입니다.
2 ) 가변 분할의 대표 할당 전략
1) First Fit
- 첫 번째로 맞는(≥요청크기) 자유 블록에 할당. 자유 리스트는 주소순으로 두는 게 보통.
- 시간 빠름(앞에서 금방 찾음), 구현 간단.
- 단점: 앞쪽에 자잘한 조각들이 쌓여 외부 단편화가 선두에 집중.
2) Next Fit
- 직전에 탐색이 끝난 지점부터 순환 탐색(원형 리스트 느낌).
- 장점: 선두 쏠림 완화.
- 단점: First Fit보다 평균 탐색 길이가 약간 길어질 수 있음.
3) Best Fit
- 가장 작은 오버헤드(요청에 가장 근접한) 자유 블록 선택.
- 장점: 남는 공간 최소화 → 내부 단편화 감소 기대.
- 단점: 자투리 아주 작은 조각을 많이 만들어 오히려 외부 단편화 악화 가능, 탐색 비용 큼(사이즈 정렬·트리 필요).
4) Worst Fit
- 가장 큰 자유 블록에 할당(크게 쪼개라).
- 아이디어: 큰 조각을 쪼개면 남는 것도 쓸만한 큰 조각이 되길 기대.
- 현실: 성능은 보통 First/Best보다 안 좋은 편. 구현/탐색 비용도 큼.
5) Quick Fit (Segregated Free Lists)
- 자주 쓰는 크기 클래스별로 자유 리스트를 여러 개 유지(예: 32B, 64B, 128B…).
- 장점: 상수 시간에 가깝게 빠른 할당. 메모리 풀/캐시친화.
- 단점: 클래스 경계 때문에 내부 단편화 발생 가능, 빈도 변화에 민감(튜닝 필요).
6) Buddy System
- 자유 블록을 2의 거듭제곱 크기로 관리. 필요 크기 이상 가장 작은 2^k로 반복 분할. 해제 시 “버디(짝)”와 즉시 병합.
- 장점: split/merge가 매우 빠름, 외부 단편화 완화.
- 단점: 2^k 단위로 맞추다 보니 내부 단편화 최대 약 50%까지 발생 가능.
- 커널/런타임 할당기(페이지 프레임, 슬랩과 조합)에서 널리 사용.
요약 선택 가이드
빠르고 단순: First/Next
- 메모리 절약 시도: Best(하지만 파편화 역효과 주의)
- 보통 비추천: Worst
- 고성능/고빈도 할당: Quick Fit(분리 자유 리스트)
- 시스템·커널 친화: Buddy(+Slab)
3 ) 비연속 메모리 할당(Non-contiguous)
(A) 페이징(Paging)
- 물리 메모리를 고정 크기 프레임으로, 논리 주소공간을 같은 크기의 페이지로 분할해 매핑. 연속할 필요 없음.
- 장점: 외부 단편화 없음, 메모리 이용률↑.
- 단점: 마지막 페이지의 내부 단편화 가능, 페이지 테이블 오버헤드(TLB로 완화).
(B) 세그멘테이션(Segmentation)
- 코드/데이터/스택 등 의미 단위(세그먼트)로 나눔(크기 가변).
- 장점: 보호/공유에 유리, 논리 구조와 맞음.
- 단점: 외부 단편화 가능 → 압축 필요할 수 있음.
(C) 세그먼테이션 + 페이징 혼합
- 세그먼트를 다시 페이지로 나눠 장점 결합, 대형 OS 전형.
4 ) 예시로 보는 전략 차이
자유 블록: [100][500][200][300][600](단위 MB), 요청: 212MB
- First Fit: 500에서 할당 → 남음 [288]
- Best Fit: 300에서 할당 → 남음 [88] (아주 작은 조각 생성)
- Worst Fit: 600에서 할당 → 남음 [388]
- Buddy(2^k): 256 선택 후 212 사용 → 내부 낭비 ~44MB(여유는 빠른 병합/재사용 장점과 트레이드오프)
포인트: Best Fit은 남는 공간이 작아 보이지만, 이렇게 생성된 초소형 조각이 누적되면 오히려 할당 실패를 앞당길 수 있어요.
728x90
반응형
LIST