가상 메모리
가상 메모리¶
개요¶
가상 메모리(Virtual Memory)는 프로그램에게 연속적이고 독립적인 주소 공간을 제공하며, 물리 메모리보다 큰 프로그램도 실행할 수 있게 해주는 핵심 기술입니다. 이 레슨에서는 가상 메모리의 개념, 페이지 테이블, TLB, 페이지 폴트 처리 등을 학습합니다.
난이도: ⭐⭐⭐⭐
선수 지식: 메모리 계층 구조, 캐시 메모리
목차¶
- 가상 메모리의 필요성
- 주소 공간
- 페이지와 페이지 프레임
- 페이지 테이블
- TLB (Translation Lookaside Buffer)
- 페이지 폴트와 페이지 교체
- 페이지 교체 알고리즘
- 고급 주제
- 연습 문제
1. 가상 메모리의 필요성¶
1.1 가상 메모리 이전의 문제점¶
문제 1: 메모리 용량 제한
┌─────────────────────────────────────────────────────────────┐
│ 프로그램 A: 2GB 필요 │
│ 물리 메모리: 1GB │
│ │
│ → 프로그램 A를 실행할 수 없음! │
└─────────────────────────────────────────────────────────────┘
문제 2: 메모리 단편화
┌─────────────────────────────────────────────────────────────┐
│ 물리 메모리 상태: │
│ ┌──────┬──────┬──────┬──────┬──────┬──────┬──────┐ │
│ │ 사용 │ 빈틈 │ 사용 │ 빈틈 │ 사용 │ 빈틈 │ 사용 │ │
│ │ 100M │ 50M │ 200M │ 30M │ 100M │ 70M │ 150M │ │
│ └──────┴──────┴──────┴──────┴──────┴──────┴──────┘ │
│ │
│ 총 빈 공간: 150MB, 하지만 100MB 연속 공간 없음 │
│ → 100MB 프로그램 로드 불가 (외부 단편화) │
└─────────────────────────────────────────────────────────────┘
문제 3: 메모리 보호 부재
┌─────────────────────────────────────────────────────────────┐
│ 프로그램 A가 프로그램 B의 메모리 영역 접근 가능 │
│ → 보안 취약점, 시스템 불안정 │
└─────────────────────────────────────────────────────────────┘
문제 4: 재배치 문제
┌─────────────────────────────────────────────────────────────┐
│ 프로그램이 특정 주소에서 실행되도록 컴파일됨 │
│ → 해당 주소가 사용 중이면 실행 불가 │
│ → 프로그램마다 다른 주소로 재컴파일 필요 │
└─────────────────────────────────────────────────────────────┘
1.2 가상 메모리의 해결책¶
┌─────────────────────────────────────────────────────────────┐
│ 가상 메모리 시스템 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 프로그램 A 프로그램 B 프로그램 C │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ Virtual │ │ Virtual │ │ Virtual │ │
│ │ Address │ │ Address │ │ Address │ │
│ │ Space │ │ Space │ │ Space │ │
│ │ 0~4GB │ │ 0~4GB │ │ 0~4GB │ │
│ └────┬────┘ └────┬────┘ └────┬────┘ │
│ │ │ │ │
│ └────────────────┼────────────────┘ │
│ │ │
│ ┌─────────┴─────────┐ │
│ │ MMU (Memory │ │
│ │ Management Unit) │ │
│ │ 가상→물리 변환 │ │
│ └─────────┬─────────┘ │
│ │ │
│ ┌─────────┴─────────┐ │
│ │ Physical Memory │ │
│ │ (1GB 등) │ │
│ └─────────┬─────────┘ │
│ │ │
│ ┌─────────┴─────────┐ │
│ │ Disk (Swap) │ │
│ │ (수백 GB) │ │
│ └───────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
가상 메모리의 장점:
1. 용량 확장: 디스크를 메모리 확장으로 사용
2. 메모리 보호: 각 프로세스가 독립된 주소 공간
3. 메모리 공유: 여러 프로세스가 같은 물리 페이지 공유 가능
4. 단편화 해결: 비연속적 물리 메모리를 연속적으로 보이게
5. 재배치 투명성: 모든 프로그램이 같은 가상 주소에서 시작
2. 주소 공간¶
2.1 가상 주소 vs 물리 주소¶
가상 주소 (Virtual Address):
- 프로그램이 사용하는 주소
- CPU가 생성하는 주소
- 프로세스마다 독립적인 공간
물리 주소 (Physical Address):
- 실제 메모리 하드웨어의 주소
- DRAM 칩에 접근하는 주소
- 시스템 전체에서 유일
┌─────────────────────────────────────────────────────────────┐
│ │
│ 프로세스 A 프로세스 B 물리 메모리 │
│ 가상 주소 공간 가상 주소 공간 │
│ │
│ 0x00000000 0x00000000 0x00000000 │
│ ┌───────────┐ ┌───────────┐ ┌───────────┐ │
│ │ Code │─────▶│ Code │──┐ │ Frame 0 │ │
│ ├───────────┤ ├───────────┤ │ ├───────────┤ │
│ │ Data │───┐ │ Data │──┼──▶│ Frame 1 │ │
│ ├───────────┤ │ ├───────────┤ │ ├───────────┤ │
│ │ Heap │ └─▶│ Heap │──┼──▶│ Frame 2 │ │
│ ├───────────┤ ├───────────┤ │ ├───────────┤ │
│ │ ↓ │ │ ↓ │ └──▶│ Frame 3 │ │
│ │ │ │ │ ├───────────┤ │
│ │ ↑ │ │ ↑ │ │ Frame 4 │ │
│ ├───────────┤ ├───────────┤ ├───────────┤ │
│ │ Stack │──────│ Stack │─────▶│ Frame 5 │ │
│ └───────────┘ └───────────┘ └───────────┘ │
│ 0xFFFFFFFF 0xFFFFFFFF (실제 크기) │
│ │
│ 같은 가상 주소 0x1000이 다른 물리 주소로 매핑될 수 있음 │
│ │
└─────────────────────────────────────────────────────────────┘
2.2 주소 공간 크기¶
32비트 시스템:
- 가상 주소 공간: 2^32 = 4GB
- 물리 메모리: 실제 장착된 용량 (예: 4GB)
64비트 시스템:
- 이론적 가상 공간: 2^64 = 16 엑사바이트
- 실제 구현 (x86-64):
- 48비트 사용: 256TB 가상 공간
- 물리 주소: 52비트까지 지원 (4PB)
┌─────────────────────────────────────────────────────────────┐
│ x86-64 가상 주소 공간 레이아웃 (48비트) │
├─────────────────────────────────────────────────────────────┤
│ │
│ 0xFFFF_FFFF_FFFF_FFFF ┌───────────────────┐ │
│ │ Kernel Space │ │
│ │ (상위 절반) │ │
│ 0xFFFF_8000_0000_0000 ├───────────────────┤ │
│ │ │ │
│ │ Non-Canonical │ ← 사용 불가 │
│ │ (hole) │ │
│ │ │ │
│ 0x0000_7FFF_FFFF_FFFF ├───────────────────┤ │
│ │ User Space │ │
│ │ (하위 절반) │ │
│ 0x0000_0000_0000_0000 └───────────────────┘ │
│ │
│ 각각 128TB씩 사용 가능 │
│ │
└─────────────────────────────────────────────────────────────┘
3. 페이지와 페이지 프레임¶
3.1 페이징 개념¶
페이지 (Page):
- 가상 주소 공간을 고정 크기로 나눈 단위
- 일반적으로 4KB (4096 bytes)
- 가상 메모리의 관리 단위
페이지 프레임 (Frame):
- 물리 메모리를 같은 크기로 나눈 단위
- 페이지와 동일한 크기
- 물리 메모리의 관리 단위
┌─────────────────────────────────────────────────────────────┐
│ │
│ 가상 주소 공간 물리 메모리 │
│ │
│ ┌─────────────┐ ┌─────────────┐ │
│ │ Page 0 │──────────▶│ Frame 3 │ │
│ ├─────────────┤ ├─────────────┤ │
│ │ Page 1 │──────┐ │ Frame 0 │ │
│ ├─────────────┤ │ ├─────────────┤ │
│ │ Page 2 │ └───▶│ Frame 1 │ │
│ ├─────────────┤ ├─────────────┤ │
│ │ Page 3 │──────────▶│ Frame 4 │ │
│ ├─────────────┤ ├─────────────┤ │
│ │ Page 4 │─ (Disk) │ Frame 2 │◀─ 다른 프로세스│
│ ├─────────────┤ ├─────────────┤ │
│ │ Page 5 │──────────▶│ Frame 5 │ │
│ └─────────────┘ └─────────────┘ │
│ │
│ - Page와 Frame 크기 동일 (4KB) │
│ - 매핑은 임의적 (비연속 가능) │
│ - 일부 페이지는 디스크에 있을 수 있음 │
│ │
└─────────────────────────────────────────────────────────────┘
3.2 페이지 크기¶
일반적인 페이지 크기:
- 4KB (2^12): 가장 일반적
- 2MB (2^21): Large Page (Huge Page)
- 1GB (2^30): Gigantic Page
┌─────────────────────────────────────────────────────────────┐
│ 페이지 크기 트레이드오프 │
├────────────────┬───────────────────┬────────────────────────┤
│ │ 작은 페이지 (4KB)│ 큰 페이지 (2MB) │
├────────────────┼───────────────────┼────────────────────────┤
│ 내부 단편화 │ 적음 │ 많음 │
├────────────────┼───────────────────┼────────────────────────┤
│ 페이지 테이블 │ 큼 │ 작음 │
├────────────────┼───────────────────┼────────────────────────┤
│ TLB 커버리지 │ 작음 │ 큼 │
├────────────────┼───────────────────┼────────────────────────┤
│ 디스크 전송 │ 비효율적 │ 효율적 │
├────────────────┼───────────────────┼────────────────────────┤
│ 적합한 경우 │ 일반 프로그램 │ 대용량 메모리 앱 │
└────────────────┴───────────────────┴────────────────────────┘
내부 단편화 예시:
- 프로세스가 4097 바이트 필요
- 4KB 페이지: 2페이지 필요 (8KB), 낭비 약 4KB
- 2MB 페이지: 1페이지 필요 (2MB), 낭비 약 2MB
3.3 가상 주소 분해¶
4KB 페이지, 32비트 가상 주소:
┌─────────────────────────────────────────────────────────────┐
│ 31 12 11 0 │
│ ├────────────────────────────────┼────────────────────────┤│
│ │ Virtual Page Number (VPN) │ Page Offset ││
│ │ (20 bits) │ (12 bits) ││
│ └────────────────────────────────┴────────────────────────┘│
└─────────────────────────────────────────────────────────────┘
Page Offset: 12비트 = 4KB 페이지 내 위치 (0-4095)
VPN: 20비트 = 2^20 = 약 100만 개의 가상 페이지
예시: 가상 주소 0x12345678
- VPN = 0x12345 (상위 20비트)
- Offset = 0x678 (하위 12비트)
변환 후 물리 주소:
- 페이지 테이블에서 VPN 0x12345 → PFN 0x00ABC
- 물리 주소 = 0x00ABC000 + 0x678 = 0x00ABC678
┌─────────────────────────────────────────────────────────────┐
│ │
│ 가상 주소: 0x12345 │ 0x678 │
│ (VPN) │ (Offset) │
│ ↓ │
│ [Page Table] │
│ ↓ │
│ 물리 주소: 0x00ABC │ 0x678 │
│ (PFN) │ (Offset) ← 그대로 복사 │
│ │
└─────────────────────────────────────────────────────────────┘
4. 페이지 테이블¶
4.1 단일 레벨 페이지 테이블¶
구조:
┌─────────────────────────────────────────────────────────────┐
│ Page Table │
├──────┬───────┬───────┬───────┬──────────────────────────────┤
│Index │ Valid │ PFN │ Prot │ Other Flags │
├──────┼───────┼───────┼───────┼──────────────────────────────┤
│ 0 │ 1 │ 0x003 │ RW │ Present, Dirty │
│ 1 │ 1 │ 0x001 │ R │ Present │
│ 2 │ 0 │ - │ - │ Not Present (Disk) │
│ 3 │ 1 │ 0x004 │ RW │ Present │
│ 4 │ 1 │ 0x002 │ RWX │ Present │
│ ... │ ... │ ... │ ... │ ... │
└──────┴───────┴───────┴───────┴──────────────────────────────┘
Page Table Entry (PTE) 구조 (x86, 32비트):
┌─────────────────────────────────────────────────────────────┐
│ 31 12 11 9 8 7 6 5 4 3 2 1 0│
│ ├────────────────┼────────┼────┼───┼───┼───┼───┼───┼──┼──┼──┤│
│ │ Page Frame │Reserved│ G │PAT│ D │ A │PCD│PWT│U │W │P ││
│ │ Number │ │ │ │ │ │ │ │/S│/R│ ││
│ └────────────────┴────────┴────┴───┴───┴───┴───┴───┴──┴──┴──┘│
└─────────────────────────────────────────────────────────────┘
P (Present): 페이지가 물리 메모리에 있음
W/R: 쓰기 가능 (1) / 읽기 전용 (0)
U/S: 사용자 접근 가능 (1) / 커널만 (0)
A (Accessed): 접근됨 (읽기 또는 쓰기)
D (Dirty): 수정됨 (쓰기)
문제점: 메모리 낭비
- 32비트 주소, 4KB 페이지: 2^20 = 1M 엔트리
- 엔트리당 4바이트: 4MB 페이지 테이블/프로세스
- 대부분의 공간이 사용되지 않아도 전체 테이블 필요
4.2 다단계 페이지 테이블¶
2단계 페이지 테이블 (32비트, 4KB 페이지):
┌─────────────────────────────────────────────────────────────┐
│ 31 22 21 12 11 0 │
│ ├──────────────────┼──────────────────┼──────────────────┤ │
│ │ Page Dir Index │ Page Table Index │ Page Offset │ │
│ │ (10 bits) │ (10 bits) │ (12 bits) │ │
│ └──────────────────┴──────────────────┴──────────────────┘ │
└─────────────────────────────────────────────────────────────┘
변환 과정:
┌─────────────────────────────────────────────────────────────┐
│ │
│ Virtual Address: [Dir Index | Table Index | Offset] │
│ │ │ │ │
│ ▼ │ │ │
│ ┌─────────────────────────────┐ │ │ │
│ │ Page Directory (4KB) │ │ │ │
│ │ 1024 entries × 4B │ │ │ │
│ │ ┌─────────────────────┐ │ │ │ │
│ │ │ Entry 0 → PT0 │ │ │ │ │
│ │ │ Entry 1 → PT1 │ │ │ │ │
│ │ │ Entry 2 → null │←── 미사용 영역은 테이블 없음 │
│ │ │ ... │ │ │ │ │
│ │ │ Entry N → PTN │────┼───┘ │ │
│ │ └─────────────────────┘ │ │ │
│ └─────────────────────────────┘ │ │
│ │ │ │
│ ▼ │ │
│ ┌─────────────────────────────┐ │ │
│ │ Page Table N (4KB) │ │ │
│ │ 1024 entries × 4B │ │ │
│ │ ┌─────────────────────┐ │ │ │
│ │ │ Entry 0 → Frame X │ │ │ │
│ │ │ Entry M → Frame Y │────┼──────────────┘ │
│ │ │ ... │ │ │
│ │ └─────────────────────┘ │ │ │
│ └─────────────────────────────┘ │ │
│ │ │ │
│ ▼ │ │
│ Physical Frame Y + Offset = Physical Address │
│ │
└─────────────────────────────────────────────────────────────┘
장점:
- 사용하지 않는 영역은 페이지 테이블 할당 안 함
- 대부분의 가상 공간이 비어있으면 큰 절약
4.3 4단계 페이지 테이블 (x86-64)¶
64비트 시스템의 4단계 페이지 테이블:
┌─────────────────────────────────────────────────────────────┐
│ 63 48 47 39 38 30 29 21 20 12 11 0 │
│ ├──────┼────────┼────────┼────────┼────────┼────────────┤ │
│ │ Sign │ PML4 │ PDPT │ PD │ PT │ Offset │ │
│ │ Ext │(9bits) │(9bits) │(9bits) │(9bits) │ (12bits) │ │
│ └──────┴────────┴────────┴────────┴────────┴────────────┘ │
└─────────────────────────────────────────────────────────────┘
PML4: Page Map Level 4
PDPT: Page Directory Pointer Table
PD: Page Directory
PT: Page Table
변환 과정:
┌─────────────────────────────────────────────────────────────┐
│ │
│ CR3 Register │
│ │ │
│ ▼ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ PML4 │─────▶│ PDPT │─────▶│ PD │ │
│ │ (512E) │ │ (512E) │ │ (512E) │ │
│ └─────────┘ └─────────┘ └─────────┘ │
│ │ │
│ ▼ │
│ ┌─────────┐ │
│ │ PT │ │
│ │ (512E) │ │
│ └────┬────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ Physical Frame │ │
│ │ + Offset │ │
│ └─────────────────┘ │
│ │
│ 각 레벨: 512 엔트리 × 8바이트 = 4KB │
│ 최대 4번의 메모리 접근 (TLB 미스 시) │
│ │
└─────────────────────────────────────────────────────────────┘
4.4 역 페이지 테이블 (Inverted Page Table)¶
기존 페이지 테이블:
- 가상 페이지 수만큼 엔트리 필요
- 프로세스마다 별도 테이블
역 페이지 테이블:
- 물리 프레임 수만큼 엔트리
- 시스템에 하나만 존재
┌─────────────────────────────────────────────────────────────┐
│ Inverted Page Table │
├───────┬────────┬──────────────┬─────────────────────────────┤
│ Frame │ PID │ VPN │ Chain │
├───────┼────────┼──────────────┼─────────────────────────────┤
│ 0 │ 42 │ 0x12345 │ null │
│ 1 │ 17 │ 0x00ABC │ → 5 │
│ 2 │ 42 │ 0x67890 │ null │
│ 3 │ 25 │ 0x11111 │ null │
│ 4 │ 17 │ 0x00DEF │ null │
│ 5 │ 33 │ 0x00ABC │ null (hash chain) │
│ ... │ ... │ ... │ ... │
└───────┴────────┴──────────────┴─────────────────────────────┘
검색: (PID, VPN) 해시하여 테이블 검색
- 해시 충돌 시 체인 따라감
- 장점: 메모리 절약 (물리 메모리 비례)
- 단점: 검색 시간 (해시 + 체인)
5. TLB (Translation Lookaside Buffer)¶
5.1 TLB의 필요성¶
페이지 테이블 접근 오버헤드:
- 4단계 페이지 테이블: 4번의 추가 메모리 접근
- 실제 데이터 접근 전에 4번의 테이블 조회
┌─────────────────────────────────────────────────────────────┐
│ TLB 없이 메모리 접근: │
│ │
│ 1. PML4 접근 (메모리) │
│ 2. PDPT 접근 (메모리) │
│ 3. PD 접근 (메모리) │
│ 4. PT 접근 (메모리) │
│ 5. 실제 데이터 접근 (메모리) │
│ │
│ 총 5번의 메모리 접근! (400+ 사이클) │
│ │
│ TLB 히트 시: │
│ 1. TLB 조회 (~1 사이클) │
│ 2. 실제 데이터 접근 (메모리) │
│ │
│ 총 ~100 사이클 (TLB 조회 + 메모리) │
└─────────────────────────────────────────────────────────────┘
5.2 TLB 구조¶
TLB (Translation Lookaside Buffer):
- 최근 변환 결과를 캐싱
- 완전 연관 또는 집합 연관 구조
- 매우 작음 (32-1024 엔트리)
- 매우 빠름 (~1 사이클)
┌─────────────────────────────────────────────────────────────┐
│ TLB │
├──────┬───────┬──────────┬──────────┬────────────────────────┤
│ ASID │ Valid │ VPN │ PFN │ Permissions │
├──────┼───────┼──────────┼──────────┼────────────────────────┤
│ 42 │ 1 │ 0x12345 │ 0x00ABC │ R/W, User │
│ 42 │ 1 │ 0x12346 │ 0x00ABD │ R/W, User │
│ 17 │ 1 │ 0x00100 │ 0x00300 │ R, User │
│ 42 │ 1 │ 0x7FFFF │ 0x00123 │ R/W, User │
│ 17 │ 1 │ 0x00200 │ 0x00400 │ R/W/X, User │
│ ... │ ... │ ... │ ... │ ... │
└──────┴───────┴──────────┴──────────┴────────────────────────┘
ASID (Address Space ID):
- 프로세스 구분
- 컨텍스트 스위치 시 TLB 플러시 방지
5.3 TLB 동작¶
주소 변환 과정:
┌─────────────────────────────────────────────────────────────┐
│ │
│ CPU가 가상 주소 생성 │
│ │ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ TLB 조회 │ ← 병렬로 수행 (VPN 추출 & TLB 검색) │
│ └────────┬────────┘ │
│ │ │
│ ┌─────┴─────┐ │
│ │ │ │
│ Hit? Miss │
│ │ │ │
│ ▼ ▼ │
│ ┌──────┐ ┌─────────────────────────────────────┐ │
│ │ PFN │ │ Page Table Walk │ │
│ │ 획득 │ │ (HW 또는 SW로 수행) │ │
│ └──┬───┘ │ 1. PML4 접근 │ │
│ │ │ 2. PDPT 접근 │ │
│ │ │ 3. PD 접근 │ │
│ │ │ 4. PT 접근 │ │
│ │ │ 5. TLB에 결과 저장 │ │
│ │ └───────────────┬─────────────────────┘ │
│ │ │ │
│ └───────────┬───────────┘ │
│ │ │
│ ▼ │
│ 물리 주소 = PFN + Offset │
│ │ │
│ ▼ │
│ 캐시/메모리 접근 │
│ │
└─────────────────────────────────────────────────────────────┘
5.4 TLB 성능¶
TLB 히트율과 AMAT:
일반적인 TLB 히트율: 99% 이상
AMAT 계산:
AMAT = TLB_Hit_Rate × (TLB_Time + Mem_Time) +
TLB_Miss_Rate × (TLB_Time + Walk_Time + Mem_Time)
예시:
- TLB 접근: 1 사이클
- 페이지 워크: 100 사이클 (4번 메모리 접근)
- 메모리 접근: 100 사이클
- TLB 히트율: 99%
TLB 히트: 1 + 100 = 101 사이클
TLB 미스: 1 + 100 + 100 = 201 사이클
AMAT = 0.99 × 101 + 0.01 × 201
= 99.99 + 2.01
= 102 사이클
TLB 없이: 500 사이클 (5번 메모리 접근)
→ TLB로 약 5배 성능 향상
TLB 커버리지:
- 64 엔트리 TLB, 4KB 페이지: 256KB
- 64 엔트리 TLB, 2MB 페이지: 128MB
- 큰 페이지 사용 시 TLB 효율 증가
6. 페이지 폴트와 페이지 교체¶
6.1 페이지 폴트¶
정의: 접근하려는 페이지가 물리 메모리에 없는 상황
페이지 폴트 원인:
1. 페이지가 디스크에 있음 (스왑 아웃됨)
2. 아직 할당되지 않은 주소 접근
3. 권한 위반 (읽기 전용 페이지에 쓰기 등)
┌─────────────────────────────────────────────────────────────┐
│ Page Fault 처리 과정 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1. CPU가 가상 주소 접근 │
│ │ │
│ ▼ │
│ 2. MMU가 PTE 확인: Present = 0 │
│ │ │
│ ▼ │
│ 3. Page Fault Exception 발생 │
│ │ │
│ ▼ │
│ 4. OS Page Fault Handler 실행 │
│ │ │
│ ┌─────┴─────────────────────────────────┐ │
│ │ │ │
│ ▼ ▼ │
│ 유효한 접근? 무효한 접근 │
│ │ │ │
│ ▼ ▼ │
│ 5. 빈 프레임 찾기 SIGSEGV 발생 │
│ (없으면 페이지 교체) (프로세스 종료) │
│ │ │
│ ▼ │
│ 6. 디스크에서 페이지 읽기 (~10ms) │
│ │ │
│ ▼ │
│ 7. 페이지 테이블 갱신 (Present = 1) │
│ │ │
│ ▼ │
│ 8. 명령어 재실행 │
│ │
└─────────────────────────────────────────────────────────────┘
6.2 페이지 폴트 비용¶
페이지 폴트 시간:
- 디스크 읽기: ~10ms (HDD) 또는 ~0.1ms (SSD)
- CPU 클럭: 3GHz = 0.33ns/사이클
사이클 수:
- HDD: 10ms / 0.33ns = 30,000,000 사이클
- SSD: 0.1ms / 0.33ns = 300,000 사이클
일반 메모리 접근: ~100 사이클
성능 영향 계산:
페이지 폴트율 p에 대해:
EAT = (1-p) × 100ns + p × 10ms
= 100ns + p × 10,000,000ns
허용 가능한 성능 저하를 10%로 제한하면:
110ns ≥ 100ns + p × 10,000,000ns
p ≤ 0.000001 (백만 번에 한 번)
→ 페이지 폴트율은 매우 낮아야 함!
6.3 Demand Paging vs Prepaging¶
Demand Paging:
- 필요할 때만 페이지 로드
- 초기에는 메모리 사용 적음
- 처음 접근 시 페이지 폴트 발생
┌─────────────────────────────────────────────────────────────┐
│ 프로세스 시작 시: │
│ - 코드 페이지 로드 안 됨 │
│ - 첫 명령어 실행 시 페이지 폴트 │
│ - 필요한 페이지만 로드 │
└─────────────────────────────────────────────────────────────┘
Prepaging:
- 관련 페이지들을 미리 로드
- 초기 페이지 폴트 감소
- 사용 안 될 페이지도 로드할 수 있음
┌─────────────────────────────────────────────────────────────┐
│ 프로세스 시작 시: │
│ - Working Set 예측하여 미리 로드 │
│ - 코드 영역 전체 또는 일부 프리로드 │
│ - 초기 페이지 폴트 감소 │
└─────────────────────────────────────────────────────────────┘
7. 페이지 교체 알고리즘¶
7.1 FIFO (First-In, First-Out)¶
원리: 가장 먼저 들어온 페이지를 교체
예시: 3 프레임, 접근 순서 1,2,3,4,1,2,5,1,2,3,4,5
┌────┬─────────┬─────────┬─────────┬───────┐
│접근│ Frame 0 │ Frame 1 │ Frame 2 │ 결과 │
├────┼─────────┼─────────┼─────────┼───────┤
│ 1 │ 1 │ - │ - │ Miss │
│ 2 │ 1 │ 2 │ - │ Miss │
│ 3 │ 1 │ 2 │ 3 │ Miss │
│ 4 │ 4 │ 2 │ 3 │ Miss │ ← 1 교체
│ 1 │ 4 │ 1 │ 3 │ Miss │ ← 2 교체
│ 2 │ 4 │ 1 │ 2 │ Miss │ ← 3 교체
│ 5 │ 5 │ 1 │ 2 │ Miss │ ← 4 교체
│ 1 │ 5 │ 1 │ 2 │ Hit │
│ 2 │ 5 │ 1 │ 2 │ Hit │
│ 3 │ 3 │ 1 │ 2 │ Miss │ ← 5 교체
│ 4 │ 3 │ 4 │ 2 │ Miss │ ← 1 교체
│ 5 │ 3 │ 4 │ 5 │ Miss │ ← 2 교체
└────┴─────────┴─────────┴─────────┴───────┘
총 미스: 10회, 히트: 2회
Belady's Anomaly:
- FIFO에서 프레임 수 증가 시 미스율 증가 가능
- 비직관적 현상
7.2 Optimal (OPT)¶
원리: 가장 오래 사용되지 않을 페이지를 교체
예시: 3 프레임, 접근 순서 1,2,3,4,1,2,5,1,2,3,4,5
┌────┬─────────┬─────────┬─────────┬───────┬────────────────┐
│접근│ Frame 0 │ Frame 1 │ Frame 2 │ 결과 │ 미래 참조 │
├────┼─────────┼─────────┼─────────┼───────┼────────────────┤
│ 1 │ 1 │ - │ - │ Miss │ │
│ 2 │ 1 │ 2 │ - │ Miss │ │
│ 3 │ 1 │ 2 │ 3 │ Miss │ │
│ 4 │ 1 │ 2 │ 4 │ Miss │ 3 가장 늦게 사용│
│ 1 │ 1 │ 2 │ 4 │ Hit │ │
│ 2 │ 1 │ 2 │ 4 │ Hit │ │
│ 5 │ 1 │ 2 │ 5 │ Miss │ 4 다시 안 사용 │
│ 1 │ 1 │ 2 │ 5 │ Hit │ │
│ 2 │ 1 │ 2 │ 5 │ Hit │ │
│ 3 │ 1 │ 2 │ 3 │ Miss │ 5 가장 늦게 │
│ 4 │ 1 │ 4 │ 3 │ Miss │ 2 가장 늦게 │
│ 5 │ 1 │ 4 │ 5 │ Miss │ 3 다시 안 사용 │
└────┴─────────┴─────────┴─────────┴───────┴────────────────┘
총 미스: 8회, 히트: 4회
최적이지만 구현 불가능 (미래 예측 필요)
→ 비교 기준으로만 사용
7.3 LRU (Least Recently Used)¶
원리: 가장 오래 전에 사용된 페이지를 교체
예시: 3 프레임, 접근 순서 1,2,3,4,1,2,5,1,2,3,4,5
┌────┬─────────┬─────────┬─────────┬───────┬────────────────┐
│접근│ Frame 0 │ Frame 1 │ Frame 2 │ 결과 │ LRU 순서 │
├────┼─────────┼─────────┼─────────┼───────┼────────────────┤
│ 1 │ 1 │ - │ - │ Miss │ 1 │
│ 2 │ 1 │ 2 │ - │ Miss │ 1,2 │
│ 3 │ 1 │ 2 │ 3 │ Miss │ 1,2,3 │
│ 4 │ 4 │ 2 │ 3 │ Miss │ 2,3,4 (1 교체)│
│ 1 │ 4 │ 1 │ 3 │ Miss │ 3,4,1 (2 교체)│
│ 2 │ 4 │ 1 │ 2 │ Miss │ 4,1,2 (3 교체)│
│ 5 │ 5 │ 1 │ 2 │ Miss │ 1,2,5 (4 교체)│
│ 1 │ 5 │ 1 │ 2 │ Hit │ 2,5,1 │
│ 2 │ 5 │ 1 │ 2 │ Hit │ 5,1,2 │
│ 3 │ 3 │ 1 │ 2 │ Miss │ 1,2,3 (5 교체)│
│ 4 │ 3 │ 4 │ 2 │ Miss │ 2,3,4 (1 교체)│
│ 5 │ 3 │ 4 │ 5 │ Miss │ 3,4,5 (2 교체)│
└────┴─────────┴─────────┴─────────┴───────┴────────────────┘
총 미스: 10회, 히트: 2회
구현 방법:
1. 타임스탬프: 각 페이지에 마지막 접근 시간 기록
2. 스택: 접근 시 페이지를 스택 top으로 이동
3. 근사 LRU: Clock 알고리즘 등
7.4 Clock Algorithm (Second Chance)¶
원리: FIFO + Reference Bit로 LRU 근사
┌─────────────────────────────────────────────────────────────┐
│ │
│ Clock Hand (시계 바늘) │
│ ↓ │
│ ┌────────┐ │
│ │Page 0 │ │
│ │ R=0 │ ← R=0이면 교체 │
│ ┌──┴────────┴──┐ │
│ │ │ │
│ ┌───┴───┐ ┌───┴───┐ │
│ │Page 3 │ │Page 1 │ │
│ │ R=1 │ │ R=1 │ ← R=1이면 R=0으로 바꾸고 통과 │
│ └───┬───┘ └───┬───┘ │
│ │ │ │
│ └──┬────────┬──┘ │
│ │Page 2 │ │
│ │ R=1 │ │
│ └────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
알고리즘:
1. 시계 바늘이 가리키는 페이지 확인
2. R=0이면 해당 페이지 교체
3. R=1이면 R=0으로 설정하고 다음 페이지로 이동
4. 모든 페이지가 R=1이면 한 바퀴 돌아 R=0인 페이지 교체
Enhanced Clock (NRU):
- Modified(M) 비트 추가
- 우선순위: (R=0,M=0) > (R=0,M=1) > (R=1,M=0) > (R=1,M=1)
- 수정된 페이지는 디스크 쓰기 필요하므로 후순위
7.5 알고리즘 비교¶
┌────────────────┬──────────────────┬─────────────────────────┐
│ 알고리즘 │ 장점 │ 단점 │
├────────────────┼──────────────────┼─────────────────────────┤
│ FIFO │ 구현 간단 │ Belady's Anomaly │
│ │ │ 성능 불안정 │
├────────────────┼──────────────────┼─────────────────────────┤
│ Optimal │ 최적 성능 │ 구현 불가능 (미래 예측) │
│ │ 비교 기준 │ │
├────────────────┼──────────────────┼─────────────────────────┤
│ LRU │ 좋은 성능 │ 구현 비용 높음 │
│ │ Stack property │ 하드웨어 지원 필요 │
├────────────────┼──────────────────┼─────────────────────────┤
│ Clock │ 효율적 근사 │ LRU보다 약간 낮은 성능 │
│ │ 구현 용이 │ │
├────────────────┼──────────────────┼─────────────────────────┤
│ Working Set │ 스래싱 방지 │ 파라미터 설정 어려움 │
│ │ 적응적 │ │
└────────────────┴──────────────────┴─────────────────────────┘
8. 고급 주제¶
8.1 Copy-on-Write (COW)¶
원리: fork() 시 페이지를 복사하지 않고 공유
┌─────────────────────────────────────────────────────────────┐
│ Copy-on-Write │
├─────────────────────────────────────────────────────────────┤
│ │
│ fork() 직후: │
│ Parent Child │
│ ┌─────────┐ ┌─────────┐ │
│ │ Page 0 │──────┬────│ Page 0 │ │
│ │ (R/O) │ │ │ (R/O) │ │
│ ├─────────┤ │ ├─────────┤ │
│ │ Page 1 │──┐ │ ┌──│ Page 1 │ │
│ │ (R/O) │ │ │ │ │ (R/O) │ │
│ └─────────┘ │ │ │ └─────────┘ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌─────┐ │
│ │ │Frame│ Physical Memory │
│ │ │ A │ (공유) │
│ │ └─────┘ │
│ │ ▲ │
│ └───┘ │
│ │
│ Child가 Page 1에 쓰기 시도: │
│ ┌─────────┐ ┌─────────┐ │
│ │ Page 1 │ │ Page 1 │ │
│ │ (R/W) │ │ (R/W) │ │
│ └────┬────┘ └────┬────┘ │
│ │ │ │
│ ▼ ▼ │
│ ┌─────────┐ ┌─────────┐ │
│ │ Frame A │ │ Frame B │ ← 복사본 생성 │
│ │(원본 유지)│ │(수정된 내용)│ │
│ └─────────┘ └─────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
장점:
- fork() 빠름 (복사 지연)
- 메모리 절약 (읽기만 하면 공유 유지)
- exec() 시 모든 페이지 버려지므로 효율적
8.2 메모리 맵 파일 (mmap)¶
원리: 파일을 가상 주소 공간에 직접 매핑
┌─────────────────────────────────────────────────────────────┐
│ │
│ 프로세스 가상 주소 공간 디스크 파일 │
│ │
│ 0x40000000 ┌────────────┐ ┌────────────┐ │
│ │ │ │ │ │
│ │ Mapped │◀═══▶│ File │ │
│ │ Region │ │ Content │ │
│ │ │ │ │ │
│ 0x40100000 └────────────┘ └────────────┘ │
│ │
│ 접근 방식: │
│ - 파일 내용을 메모리처럼 접근 (포인터 사용) │
│ - 페이지 폴트 시 파일에서 자동 로드 │
│ - 수정 시 자동으로 파일에 반영 (또는 명시적 msync) │
│ │
└─────────────────────────────────────────────────────────────┘
용도:
- 대용량 파일 처리
- 프로세스 간 공유 메모리
- 동적 라이브러리 로딩
8.3 Huge Pages¶
일반 페이지 vs Huge Page:
일반 페이지 (4KB):
- 2MB 메모리 = 512 페이지
- 512 TLB 엔트리 필요 (TLB 압박)
- 페이지 테이블 오버헤드 큼
Huge Page (2MB):
- 2MB 메모리 = 1 페이지
- 1 TLB 엔트리만 필요
- TLB 커버리지 증가
┌─────────────────────────────────────────────────────────────┐
│ TLB 커버리지 비교 (64 TLB 엔트리): │
│ │
│ 4KB 페이지: 64 × 4KB = 256KB │
│ 2MB 페이지: 64 × 2MB = 128MB │
│ 1GB 페이지: 64 × 1GB = 64GB │
│ │
│ 데이터베이스, 가상화 등 대용량 메모리 사용 시 큰 효과 │
└─────────────────────────────────────────────────────────────┘
Linux에서 사용:
# 시스템 설정
echo 1024 > /proc/sys/vm/nr_hugepages
# 프로그램에서
mmap(..., MAP_HUGETLB, ...);
9. 연습 문제¶
기초 문제¶
-
가상 메모리의 주요 장점 3가지는?
-
32비트 시스템, 4KB 페이지에서 가상 주소 0x12345ABC의:
- VPN은?
-
Offset은?
-
TLB의 역할과 필요성을 설명하시오.
중급 문제¶
-
다음 접근 순서에서 FIFO, LRU 알고리즘의 미스 횟수를 구하시오: (3 프레임, 접근: 7,0,1,2,0,3,0,4,2,3)
-
2단계 페이지 테이블에서 TLB 미스 시 메모리 접근 횟수는?
-
Copy-on-Write의 동작 원리와 장점을 설명하시오.
심화 문제¶
-
64비트 시스템에서 4단계 페이지 테이블을 사용하는 이유는?
-
다음 상황에서 Effective Access Time을 계산하시오:
- TLB 히트 시간: 10ns
- TLB 히트율: 98%
- 페이지 테이블 워크: 200ns (4번 메모리 접근)
- 메모리 접근: 100ns
- 페이지 폴트율: 0.001%
-
페이지 폴트 처리: 10ms
-
Working Set 모델이 스래싱을 방지하는 원리를 설명하시오.
정답
1. 가상 메모리 장점: - 물리 메모리보다 큰 프로그램 실행 가능 - 메모리 보호 (프로세스 격리) - 메모리 공유 (라이브러리 등) - 단편화 해결 - 재배치 투명성 2. 주소 분해 (0x12345ABC): - VPN = 0x12345 (상위 20비트) - Offset = 0xABC (하위 12비트) 3. TLB 역할: - 가상-물리 주소 변환 결과 캐싱 - 페이지 테이블 접근 오버헤드 감소 - 필요성: 4단계 테이블 = 4번 추가 메모리 접근을 1사이클로 단축 4. 미스 횟수: FIFO: 7,0,1,2,0,3,0,4,2,3 - Miss: 7,0,1 (초기 로드) - Miss: 2 (7 교체) - Hit: 0 - Miss: 3 (0 교체, wait 0 was just hit... 재계산) 실제 계산: [7,-,-] → [7,0,-] → [7,0,1] → [2,0,1] → Hit → [2,3,1] → [2,3,0] → [4,3,0] → [4,2,0] → [4,2,3] FIFO: 9 Miss, 1 Hit LRU: [7,-,-] → [7,0,-] → [7,0,1] → [2,0,1] → Hit(0) → [2,0,3] → Hit(0) → [4,0,3] → [4,0,2] → [4,3,2] LRU: 8 Miss, 2 Hit 5. 2단계 페이지 테이블 TLB 미스 시: - Page Directory 접근: 1회 - Page Table 접근: 1회 - 실제 데이터 접근: 1회 - 총 3번 메모리 접근 6. Copy-on-Write: - 원리: fork() 시 페이지 테이블만 복사하고 실제 페이지는 공유, 쓰기 시 복사 - 장점: fork() 빠름, 메모리 절약, exec() 시 효율적 7. 4단계 페이지 테이블 이유: - 64비트 주소 공간이 너무 큼 - 단일 레벨: 2^52 / 4KB × 8B = 수 PB 테이블 - 다단계: 사용하는 영역만 테이블 할당하여 메모리 절약 8. EAT 계산: TLB 히트: 10ns + 100ns = 110ns TLB 미스: 10ns + 200ns + 100ns = 310ns 페이지 폴트: 10ms = 10,000,000ns EAT = 0.98 × 0.99999 × 110 + 0.02 × 0.99999 × 310 + 0.00001 × 10,000,000 = 107.78 + 6.20 + 100 ≈ 214ns 9. Working Set 모델: - 프로세스의 Working Set 크기 추적 - 물리 메모리 < 모든 프로세스의 Working Set 합이면 - 일부 프로세스 스왑 아웃하여 다른 프로세스에 충분한 메모리 제공 - 각 프로세스가 Working Set만큼의 프레임을 보장받아 스래싱 방지다음 단계¶
- 17_IO_Systems.md - I/O 시스템, 인터럽트, DMA
참고 자료¶
- Operating System Concepts (Silberschatz et al.)
- Computer Architecture: A Quantitative Approach (Hennessy & Patterson)
- Intel Software Developer's Manual - Paging
- Linux Kernel Documentation - Memory Management