KAIST CS330 운영체제 및 실험 (Fall 2023, Prof. Youngjin Kwon) 교재: Operating Systems: Three Easy Pieces (OSTEP), Operating Systems: Principles and Practice (OSPP)
이전 글: [CS330] 4. 가상 메모리와 주소 변환
세그멘테이션의 한계
세그멘테이션은 메모리를 논리적인 단위로 나누어 관리하지만, 치명적인 외부 단편화(External Fragmentation) 문제가 있다. 각 세그먼트는 가변 크기이기 때문에, 빈 공간은 충분하지만 연속되지 않아 할당할 수 없는 상황이 발생한다. 이를 해결하기 위해 등장한 것이 **페이징(Paging)**이다.
페이징의 개념
페이징은 주소 공간을 고정 크기의 단위로 나누어 관리한다.
기본 용어
- 페이지(Page): 가상 주소 공간을 고정 크기로 나눈 단위 (보통 4KB)
- 프레임(Frame): 물리 메모리를 고정 크기로 나눈 단위 (페이지와 같은 크기)
- 페이지 테이블(Page Table): 페이지에서 프레임으로의 매핑 정보를 저장하는 자료구조
주소 변환 과정
가상 주소는 **VPN (Virtual Page Number)**과 Offset으로 나뉘고, 페이지 테이블 조회를 통해 VPN을 **PFN (Physical Frame Number)**으로 변환한다.
가상 주소: 0x0004AFE (32비트, 4KB 페이지)
┌──────────────────┬──────────────┐
│ VPN: 0x00004 │ Offset: 0xAFE│
└──────────────────┴──────────────┘
↓ Page Table 조회
┌──────────────────┬──────────────┐
│ PFN: 0x4A6 │ Offset: 0xAFE│
└──────────────────┴──────────────┘
물리 주소: 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 페이지 사용 시 프로세스당 4MB의 페이지 테이블이 필요하다 (2^20개 엔트리 × 4바이트). 프로세스가 100개라면 400MB가 페이지 테이블에만 사용된다!
중요한 관찰: 대부분의 프로세스는 주소 공간 전체를 사용하지 않지만, 선형 페이지 테이블은 사용하지 않는 영역에도 엔트리를 가져야 한다 (valid bit = 0).
Demand Paging
운영체제는 메모리를 페이지의 캐시로 사용한다.
기본 아이디어
- 필요할 때만 메모리에 적재: 모든 페이지를 처음부터 메모리에 올리지 않음
- 디스크를 백업 저장소로 사용: 사용하지 않는 페이지는 디스크로 내림 (스와핑)
- 프로세스에게 투명: 페이지의 이동은 프로세스가 알 필요 없음
Page Fault
Major Page Fault: Present bit가 0이고 페이지가 디스크에 있는 경우
- MMU가 PTE 확인 → Present bit = 0 발견
- 페이지 폴트 예외 발생
- OS가 디스크에서 페이지를 읽어 빈 프레임에 적재
- 페이지 테이블 업데이트 후 명령어 재실행
Minor Page Fault: 디스크 I/O 없이 해결
- Lazy allocation: 스택/힙 페이지를 실제 접근 시 할당
- Copy-on-write: fork() 시 부모 페이지 공유 후 쓰기 시 복사
TLB (Translation Lookaside Buffer)
페이징의 가장 큰 문제는 주소 변환이 느리다는 것이다.
문제점과 해결
하나의 메모리 참조에 최소 2번의 메모리 접근이 필요하다 (페이지 테이블 접근 + 실제 데이터 접근). TLB는 자주 사용되는 주소 변환 정보를 캐시하는 하드웨어로 이 문제를 해결한다.
TLB 작동 방식
VPN으로 TLB를 조회한다. Hit이면 즉시 PFN을 얻고, Miss이면 페이지 테이블을 접근하여 TLB를 업데이트한 후 PFN을 얻는다.
TLB 엔트리 구조
┌─────┬─────┬──────────────────────┐
│ VPN │ PFN │ Valid | R/W | U/S | D │
├─────┼─────┼──────────────────────┤
│ 0x4 │0x4A6│ 1 | 1 | 1 | 0 │
└─────┴─────┴──────────────────────┘
Spatial Locality 예시
배열을 순회할 때 같은 페이지 내의 원소들은 TLB Hit을 일으킨다. 예를 들어 10개 원소 접근 시 3번의 Miss, 7번의 Hit로 70% Hit Rate를 달성할 수 있다.
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가 처리. 유연하지만 소프트웨어 오버헤드 존재.
멀티레벨 페이지 테이블
선형 페이지 테이블의 문제
프로세스당 4MB의 페이지 테이블이 필요하지만, 대부분의 엔트리는 invalid이다. 핵심 아이디어: 사용하지 않는 영역의 페이지 테이블은 할당하지 않자!
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 예시
x86_32: 32비트 주소를 Dir(10) + Table(10) + Offset(12)로 분할. CR3 → Page Directory → Page Table → Physical Frame 순서로 변환.
x86_64: 48비트 주소, 4단계 페이지 테이블 (PML4 → PDPT → PD → PT → Frame). 각 레벨은 9비트씩 사용.
Inverted Page Table
멀티레벨 페이지 테이블과 반대 접근: 프로세스마다 페이지 테이블을 가지지 않고, 시스템 전체에 하나의 페이지 테이블을 둔다. 전통적 방식이 VPN → PFN 매핑이라면, Inverted는 PFN → (PID, VPN) 매핑이다.
장점: 페이지 테이블 크기가 물리 메모리 크기에 비례 (64비트 시스템에서 유리).
단점: 주소 변환이 복잡하고 (해시 테이블 사용), 공유 메모리 구현이 어렵다.
정리
페이징은 고정 크기 단위로 메모리를 관리하여 외부 단편화를 해결한다. 하지만 페이지 테이블의 크기와 주소 변환 속도라는 새로운 문제를 만들었다.
운영체제는 이러한 문제를 해결하기 위해:
- TLB로 주소 변환 속도를 높인다
- 멀티레벨 페이지 테이블로 공간을 절약한다
- Demand Paging으로 필요한 페이지만 메모리에 유지한다
다음 글에서는 메모리가 부족할 때 어떤 페이지를 디스크로 내보낼지 결정하는 페이지 교체 정책에 대해 알아본다.