KAIST CS330 운영체제 및 실험 (Fall 2023, Prof. Youngjin Kwon) 교재: Operating Systems: Three Easy Pieces (OSTEP), Operating Systems: Principles and Practice (OSPP)
이전 글: [CS330] 4. 가상 메모리와 주소 변환
세그멘테이션의 한계
세그멘테이션은 메모리를 논리적인 단위로 나누어 관리하는 방식이지만, 치명적인 단점이 있다.
외부 단편화(External Fragmentation)
- 각 세그먼트는 가변 크기이기 때문에, 메모리에 빈 공간은 충분하지만 연속되지 않아서 할당할 수 없는 상황이 발생한다
- 세그먼트를 할당하고 해제하다 보면 물리 메모리에 작은 빈 공간들이 여기저기 흩어지게 된다
물리 메모리
┌─────────────┐
│ Segment A │
├─────────────┤
│ (빈 공간) │ ← 2KB 빈 공간
├─────────────┤
│ Segment B │
├─────────────┤
│ (빈 공간) │ ← 3KB 빈 공간
├─────────────┤
│ Segment C │
├─────────────┤
│ (빈 공간) │ ← 1KB 빈 공간
└─────────────┘
총 6KB의 빈 공간이 있지만, 5KB 세그먼트를 할당할 수 없다!
이 문제를 해결하기 위해 등장한 것이 **페이징(Paging)**이다.
페이징의 개념
페이징은 주소 공간을 고정 크기의 단위로 나누어 관리한다.
기본 용어
- 페이지(Page): 가상 주소 공간을 고정 크기로 나눈 단위 (보통 4KB)
- 프레임(Frame): 물리 메모리를 고정 크기로 나눈 단위 (페이지와 같은 크기)
- 페이지 테이블(Page Table): 페이지에서 프레임으로의 매핑 정보를 저장하는 자료구조
주소 변환 과정
가상 주소는 두 부분으로 나뉜다.
가상 주소 (Virtual Address)
┌──────────────────┬──────────────┐
│ VPN │ Offset │
└──────────────────┴──────────────┘
↓
Page Table 조회
↓
물리 주소 (Physical Address)
┌──────────────────┬──────────────┐
│ PFN │ Offset │
└──────────────────┴──────────────┘
- VPN (Virtual Page Number): 가상 페이지 번호, 페이지 테이블의 인덱스로 사용
- Offset: 페이지 내에서의 위치
- PFN (Physical Frame Number): 물리 프레임 번호
예시: 32비트 시스템, 4KB 페이지
- 가상 주소:
0x0004AFE - Offset은 12비트 (4KB = 2^12):
0xAFE - VPN은 20비트:
0x00004 - Page Table에서 VPN
0x00004를 조회하여 PFN0x4A6을 얻음 - 물리 주소:
0x46AFE
페이징의 장점
- 외부 단편화 없음: 고정 크기이므로 어떤 프레임이든 할당 가능
- 빠른 할당/해제: 비트맵이나 리스트로 간단히 관리
- 보호와 공유 용이: 페이지 단위로 권한 설정 가능
페이징의 단점
- 내부 단편화(Internal Fragmentation): 페이지 크기보다 작은 메모리 낭비
- 페이지 테이블 크기: 32비트 시스템에서 하나의 프로세스당 4MB 필요
- 메모리 접근 오버헤드: 주소 변환을 위해 추가적인 메모리 접근 필요
페이지 테이블
선형 페이지 테이블 (Linear Page Table)
가장 단순한 형태의 페이지 테이블은 배열 형태이다.
Page Table
┌─────┬─────────────────────────────────┐
│ VPN │ PTE (Entry) │
├─────┼─────────────────────────────────┤
│ 0 │ PFN: 0x03 | V:1 | R:1 | W:0 │
│ 1 │ PFN: 0x27 | V:1 | R:1 | W:1 │
│ 2 │ PFN: - | V:0 | R:0 | W:0 │
│ 3 │ PFN: 0xD0 | V:1 | R:1 | W:0 │
│ ... │ ... │
└─────┴─────────────────────────────────┘
PTBR (Page Table Base Register): 페이지 테이블의 시작 주소
PTE 구조 (x86 기준)
31 12 11 9 8 7 6 5 4 3 2 1 0
┌───────────────────────────────────────┬─────┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│ PFN (20 bits) │ G │P│P│D│A│P│P│U│R│P│
│ │ │A│C│ │ │W│W│/│/│ │
│ │ │T│D│ │ │T│T│S│W│ │
└───────────────────────────────────────┴─────┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
주요 비트 필드
- PFN: 물리 프레임 번호 (20비트)
- P (Present): 해당 페이지가 메모리에 있는지 (1) 또는 디스크에 있는지 (0)
- R/W (Read/Write): 읽기 전용(0) 또는 읽기/쓰기(1)
- U/S (User/Supervisor): 유저 모드(1) 또는 커널 모드(0)에서 접근 가능
- A (Accessed): 페이지가 접근되었는지
- D (Dirty): 페이지가 수정되었는지
페이지 테이블 크기 문제
32비트 주소 공간, 4KB 페이지를 사용하면:
- VPN 크기: 20비트 → 2^20 = 1,048,576개의 페이지
- PTE 크기: 4바이트
- 페이지 테이블 크기: 4MB
프로세스가 100개라면 400MB가 페이지 테이블에만 사용된다!
중요한 관찰: 대부분의 프로세스는 주소 공간 전체를 사용하지 않는다.
가상 주소 공간 (16KB, 1KB 페이지)
┌──────┬─────────────────┬──────────┐
│ code │ (사용 안 함) │ heap │
│ 0 │ 1 2 3 4 │ 5 │
├──────┴─────────────────┴──────────┤
│ (사용 안 함) │
│ ... │
├───────────────────────────────────┤
│ stack │
│ 15 │
└───────────────────────────────────┘
페이지 테이블에는 사용하지 않는 영역의 페이지도
모두 엔트리를 가지고 있어야 한다 (valid bit = 0)
Demand Paging
운영체제는 메모리를 페이지의 캐시로 사용한다.
기본 아이디어
- 필요할 때만 메모리에 적재: 모든 페이지를 처음부터 메모리에 올리지 않음
- 디스크를 백업 저장소로 사용: 사용하지 않는 페이지는 디스크로 내림 (스와핑)
- 프로세스에게 투명: 페이지의 이동은 프로세스가 알 필요 없음
Page Fault
Major Page Fault: Present bit가 0이고, 페이지가 디스크에 있는 경우
- CPU가 메모리 참조 시도
- MMU가 PTE를 확인하고 Present bit = 0 발견
- 페이지 폴트 예외 발생
- OS가 디스크에서 페이지를 읽어 빈 프레임에 적재
- 페이지 테이블 업데이트 (PFN 설정, Present bit = 1)
- 명령어 재실행
CPU
│
│ ① 메모리 접근
▼
Page Table ──② Page Fault──┐
┌────────┐ │
│ V=0 !! │ │
└────────┘ │
│
▼
커널 모드
│
③ 디스크에서 페이지 읽기
│
▼
Physical
Memory
┌──────┐
│ 빈 프레임 │
└──────┘
│
⑤ PTE 업데이트
│
⑥ 명령어 재실행
Minor Page Fault: 디스크 I/O 없이 해결 가능한 경우
- Lazy allocation: 스택/힙 페이지를 실제로 접근할 때 할당
- Copy-on-write: fork() 시 부모 페이지를 공유하다가 쓰기 시 복사
TLB (Translation Lookaside Buffer)
페이징의 가장 큰 문제는 주소 변환이 느리다는 것이다.
문제점
하나의 메모리 참조에 최소 2번의 메모리 접근이 필요하다.
- 페이지 테이블 접근 (VPN → PFN)
- 실제 데이터 접근 (PFN + Offset)
멀티레벨 페이지 테이블을 사용하면 더 많은 메모리 접근이 필요하다.
TLB의 역할
TLB는 자주 사용되는 주소 변환 정보를 캐시하는 하드웨어이다.
Virtual Address
│
▼
┌──────────┐
│ TLB │ ← 빠른 캐시
└──────────┘
│ │
TLB Hit │ │ TLB Miss
▼ ▼
Physical Page
Address Table
(메모리)
TLB 작동 방식
가상 주소: 0x0004AFE
│
▼
┌─────────────────────┐
│ VPN = 0x00004 조회 │
└─────────────────────┘
│
┌────┴────┐
│ │
TLB Hit TLB Miss
│ │
│ ▼
│ Page Table 접근
│ │
│ ▼
│ TLB 업데이트
│ │
└────┬────┘
│
▼
PFN = 0x4A6
│
▼
물리 주소: 0x46AFE
TLB 엔트리 구조
┌─────┬─────┬──────────────────────┐
│ VPN │ PFN │ Valid | R/W | U/S | D │
├─────┼─────┼──────────────────────┤
│ 0x4 │0x4A6│ 1 | 1 | 1 | 0 │
└─────┴─────┴──────────────────────┘
Spatial Locality 예시
배열을 순회할 때 TLB가 성능을 크게 향상시킨다.
int sum = 0;
for (int i = 0; i < 10; i++) {
sum += a[i];
}
VPN 배치 (4바이트 정수, 4KB 페이지)
┌────────┬────────┬────────┬────────┐
│ VPN 06 │ VPN 07 │ VPN 08 │ VPN 09 │
├────────┼────────┼────────┼────────┤
│ a[0] │ a[3] │ a[7] │ │
│ a[1] │ a[4] │ a[8] │ │
│ a[2] │ a[5] │ a[9] │ │
│ │ a[6] │ │ │
└────────┴────────┴────────┴────────┘
총 10번의 접근: 3번의 TLB Miss, 7번의 TLB Hit
→ TLB Hit Rate: 70%
Context Switch와 TLB
문제: 프로세스마다 페이지 테이블이 다르므로, 컨텍스트 스위치 시 TLB의 VPN → PFN 매핑이 무효화된다.
해결 방법 1: TLB Flush
- 컨텍스트 스위치 시 모든 TLB 엔트리를 무효화
- 간단하지만 성능 저하 발생
해결 방법 2: ASID (Address Space ID)
- TLB 엔트리에 프로세스 ID를 추가
- 프로세스를 구별할 수 있어 Flush 불필요
TLB with ASID
┌──────┬─────┬─────┬──────────┐
│ ASID │ VPN │ PFN │ flags │
├──────┼─────┼─────┼──────────┤
│ 10 │ 0x4 │0x4A6│ V=1 R/W=1│ ← Process A
│ 20 │ 0x4 │0x123│ V=1 R/W=1│ ← Process B
└──────┴─────┴─────┴──────────┘
Hardware-managed vs Software-managed TLB
Hardware-managed TLB (x86)
- TLB Miss 시 하드웨어가 자동으로 페이지 테이블을 탐색
- 페이지 테이블 형식이 고정되어 있음
- 빠르지만 유연성 떨어짐
Software-managed TLB (RISC-V, MIPS)
- TLB Miss 시 예외 발생, OS가 처리
- 페이지 테이블 형식을 자유롭게 구현 가능
- 유연하지만 소프트웨어 오버헤드
멀티레벨 페이지 테이블
선형 페이지 테이블의 문제
32비트 주소 공간, 4KB 페이지, 4바이트 PTE 사용 시:
- 프로세스당 4MB의 페이지 테이블 필요
- 대부분의 엔트리는 invalid (valid bit = 0)
핵심 아이디어: 사용하지 않는 영역의 페이지 테이블은 할당하지 않자!
2단계 페이지 테이블
페이지 테이블을 페이지 크기로 쪼개고, **페이지 디렉토리(Page Directory)**로 관리한다.
Virtual Address
┌───────────────┬───────────────┬──────────┐
│ Outer Page # │Secondary Page#│ Offset │
└───────────────┴───────────────┴──────────┘
│ │
│ │
▼ │
Page Directory │
┌──────────┐ │
│ Valid PFN│ │
├──────────┤ │
│ Valid PFN├────────┼───┐
├──────────┤ │ │
│Invalid -│ │ │
├──────────┤ │ │
│ Valid PFN│ │ │
└──────────┘ │ │
│ │
▼ ▼
Page Table Page
┌──────────┐
│ Valid PFN├──→ Frame
├──────────┤
│ Valid PFN├──→ Frame
├──────────┤
│Invalid -│
└──────────┘
장점
- 공간 절약: 사용하지 않는 영역의 페이지 테이블 페이지를 할당하지 않음
- 페이지 크기 단위: 페이지 테이블 자체도 페이지 단위로 관리
- 스와핑 가능: 사용하지 않는 페이지 테이블 페이지를 디스크로 내릴 수 있음
단점
- 복잡도 증가: 주소 변환이 복잡해짐
- 메모리 접근 증가: TLB Miss 시 여러 번의 메모리 접근 필요
- 시간-공간 트레이드오프: 공간은 절약하지만 시간은 더 걸림
x86_32 예시
32비트 주소, 4KB 페이지, 4바이트 PTE:
- Offset: 12비트 (4KB = 2^12)
- 페이지당 1024개의 PTE (4KB / 4B = 1024 = 2^10)
- Page Table Index: 10비트
- Page Directory Index: 10비트
31 22 21 12 11 0
┌────────────┬────────────┬───────────┐
│ Dir (10) │Table (10) │Offset (12)│
└────────────┴────────────┴───────────┘
CR3 → Page Directory → Page Table → Physical Frame
x86_64 예시
48비트 “linear” 주소, 4KB 페이지 → 4단계 페이지 테이블
- PML4 (Page Map Level 4) → PDPT → PD → PT → Frame
47 39 38 30 29 21 20 12 11 0
┌────────┬────────┬────────┬────────┬─────┐
│ PML4 │ PDPT │ PD │ PT │ Ofs │
│ (9) │ (9) │ (9) │ (9) │(12) │
└────────┴────────┴────────┴────────┴─────┘
Inverted Page Table
멀티레벨 페이지 테이블과 반대 방향의 접근: 물리 메모리 중심으로 설계한다.
아이디어
프로세스마다 페이지 테이블을 가지는 대신, 시스템 전체에 하나의 페이지 테이블을 둔다.
전통적 페이지 테이블: VPN → PFN (프로세스마다)
Inverted 페이지 테이블: PFN → (PID, VPN) (시스템 전체)
장단점
장점
- 페이지 테이블 크기가 물리 메모리 크기에 비례 (가상 주소 공간 크기 무관)
- 64비트 시스템에서 유리
단점
- 주소 변환이 복잡함 (해시 테이블 사용)
- 공유 메모리 구현이 어려움
정리
페이징은 고정 크기 단위로 메모리를 관리하여 외부 단편화를 해결한다. 하지만 페이지 테이블의 크기와 주소 변환 속도라는 새로운 문제를 만들었다.
운영체제는 이러한 문제를 해결하기 위해:
- TLB로 주소 변환 속도를 높인다
- 멀티레벨 페이지 테이블로 공간을 절약한다
- Demand Paging으로 필요한 페이지만 메모리에 유지한다
다음 글에서는 메모리가 부족할 때 어떤 페이지를 디스크로 내보낼지 결정하는 페이지 교체 정책에 대해 알아본다.