[CS] 메모리 단편화
메모리 단편화와 운영체제의 메모리 관리 전략
운영체제는 사용자 프로그램과 커널 간의 자원 충돌을 방지하고, 메모리를 효율적으로 할당하기 위해 다양한 메모리 관리 전략을 사용합니다. 특히 단편화 문제는 메모리 낭비를 초래할 수 있기 때문에 주요 해결 과제 중 하나입니다.
1. 메모리 단편화 개념
1-1. 내부 단편화 (Internal Fragmentation)
정의
할당된 블록 내부의 남는 공간 (사용자가 요청한 크기보다 큰 블록이 할당될 때 발생)
원인
고정 크기 블록 할당 방식에서 발생
예시
요청 50KB, 할당 64KB → 14KB 낭비
해결 방법
- 더 작은 블록 단위 사용
- 동적 메모리 할당 기법 사용 (
malloc,new) - 슬랩 할당자 사용
1-2. 외부 단편화 (External Fragmentation)
정의
사용하지 않는 메모리 조각들이 흩어져 있어 큰 연속 공간을 확보하지 못하는 상황
원인
가변 크기 블록의 동적 할당과 해제 반복
예시
전체 여유 공간은 충분하지만 연속되지 않아 큰 블록을 할당하지 못함
해결 방법
- 메모리 압축(compaction)
- 페이징(Paging) 기법 사용
- 베스트 핏 / 퍼스트 핏 / 워스트 핏 전략 사용
2. 운영체제의 메모리 관리 전략
2-1. 페이징 (Paging)
개념
메모리를 고정 크기 블록으로 나눠서 가상 메모리와 물리 메모리 간의 연속성 문제를 해결하는 기법
구성 요소
- 페이지(Page): 가상 주소 공간의 단위 (예: 4KB)
- 프레임(Frame): 물리 메모리의 동일 크기 단위
- 페이지 테이블: 페이지와 프레임을 매핑하는 자료구조
장점
- 외부 단편화 없음
- 가상 메모리 구현 용이
- 프로세스 간 메모리 보호 가능
단점
- 내부 단편화 가능
- 페이지 테이블 접근 시 오버헤드 발생 (→ TLB로 보완)
페이징 주소 변환 과정
- 가상 주소 = 페이지 번호 + 페이지 오프셋
- 페이지 번호를 페이지 테이블에서 조회 → 프레임 번호 획득
- 프레임 번호 + 오프셋 = 실제 물리 주소
TLB (Translation Lookaside Buffer)
- 페이지 테이블 접근 속도를 높이기 위한 캐시
- 최근 참조한 페이지 정보를 저장 → 주소 변환 성능 향상
계층적 페이지 테이블 (Multi-level Paging)
- 2단계 이상 구조로 구성된 페이지 테이블
- 큰 가상 주소 공간을 트리 구조로 관리 → 메모리 공간 절약
역방향 페이지 테이블 (Inverted Page Table)
- 물리 프레임 기준으로 가상 주소를 매핑
- 공간 절약에 유리하나 검색 속도는 느림 (→ 해시로 보완)
페이지 폴트 (Page Fault)
정의: 필요한 페이지가 메모리에 없을 때 발생하는 인터럽트
처리 절차
- 디스크에서 해당 페이지 읽기
- 물리 메모리에 로드
- 페이지 테이블 업데이트 후 재실행
종류
- Major Page Fault: 디스크 접근 필요
- Minor Page Fault: 디스크 접근 없이 재매핑만 수행
페이지 교체 알고리즘 (Page Replacement Algorithm)
- 페이지 폴트 시 기존 페이지를 교체하여 새로운 페이지를 로드
대표 알고리즘
- FIFO: 가장 오래된 페이지 제거
- LRU: 가장 오랫동안 사용되지 않은 페이지 제거
- Clock: 원형 포인터 기반 LRU 근사
페이지 교체 알고리즘 비교: Clock vs LRU vs FIFO
| 알고리즘 | 핵심 아이디어 | 구현 방식 | 장점 | 단점 |
|---|---|---|---|---|
| Clock | 최근 참조된 페이지를 피하면서 교체 | 참조 비트와 시계 바늘 사용 | 근사 LRU, 구현 간단 | 전부 순회할 수도 있음 |
| LRU (Least Recently Used) | 가장 오래 사용하지 않은 페이지 교체 | 정확한 시간 추적 필요 | 최적에 가까운 성능 | 구현 복잡, 비용 높음 |
| FIFO (First In First Out) | 가장 먼저 들어온 페이지 제거 | 큐로 구현 | 구현 매우 단순 | 최근에 자주 쓰인 페이지도 제거 가능 (Belady’s anomaly) |
정리:
2-2. 세그멘테이션 (Segmentation)
개념
메모리를 코드, 데이터, 스택 등 논리적인 단위(세그먼트)로 나누어 할당
특징
- 세그먼트마다 크기 가변적
- 논리적 구조에 따라 메모리 배치 가능
단점
- 외부 단편화 발생 가능
- 메모리 압축 필요 시 성능 저하
2-3. 페이징 + 세그멘테이션
개념
- 각 세그먼트를 다시 페이지로 나눔
- 세그먼트 구조의 논리성과 페이징의 효율성을 결합한 구조
2-4. 버디 시스템 (Buddy System)
개념
메모리를 2의 거듭제곱 단위로 관리하며, 필요한 크기의 블록으로 분할하여 할당하고, 인접 블록은 병합 가능
장점
- 빠른 할당 및 해제
- 블록 병합 가능성
단점
- 실제 필요한 크기보다 더 큰 블록 할당 시 낭비 발생
2-5. 슬랩 할당자 (Slab Allocator)
개념
자주 사용하는 커널 객체를 위한 캐시 메모리 풀 시스템
특징
- 객체 생성과 삭제가 매우 빠름
- 커널 메모리 최적화에 효과적
2-6. 스와핑 (Swapping)
개념
- 실행 중인 프로세스의 메모리 일부 또는 전체를 디스크로 내보내고, 필요 시 다시 불러오는 기법
용도
- 메모리가 부족할 때 유휴 프로세스를 디스크로 이동시켜 공간 확보
단점
- 속도 느림 (디스크 I/O 필요)
- 성능 저하
3. 요약 정리
단편화 요약
- 내부 단편화: 고정 크기 블록 내 낭비 공간 → 슬랩, 동적 할당으로 해결
- 외부 단편화: 메모리 사이사이 사용 불가 공간 → 페이징, 압축으로 해결
주요 기법 요약
| 기법 | 특징 | 장단점 | |——|——|——–| | 페이징 | 고정 크기 블록, 주소 매핑 | 외부 단편화 해결, 내부 단편화 가능성 있음 | | 세그멘테이션 | 논리 단위로 분할 | 외부 단편화 발생 가능, 논리 구조 반영 용이 | | 페이징+세그멘테이션 | 세그먼트 내 페이지 사용 | 구조 + 효율 결합, 복잡도 증가 | | 버디 시스템 | 2의 거듭제곱 블록 | 병합/분할 빠름, 낭비 가능성 있음 | | 슬랩 | 커널 객체 캐시 | 빠른 할당, 캐시 오버헤드 있음 | | 스와핑 | 디스크로 메모리 이동 | 공간 확보 가능, 성능 저하 발생 |