Paging: OS는 가상 메모리를 어떻게 관리할까?
- 1. 페이징 기본 개념
- 2. 주소 변환 과정
- 3. 운영체제의 역할
- 4. 페이지 교체 (Page Replacement)
- 5. PintOS 관점 요약
- 6. 다단계 페이징을 쓰는 이유
- 7. 페이지 크기와 내부 단편화
- 8. 정리
페이징은 가상 주소와 물리 주소 사이에 간접층을 두어 각 프로세스에 독립적인 주소 공간을 제공한다. 주소 변환, CR3, PTE, TLB, 다단계 페이징까지 정리한다.
1. 페이징 기본 개념
| 용어 | 설명 |
|---|---|
| 페이지 (Page) | OS의 관리 단위인 고정 크기(보통 4KB)의 가상 메모리 블록 |
| 프레임 (Frame) | 물리 메모리에서 페이지와 1:1로 매핑되는 동일 크기 블록 |
| 페이지 테이블 (Page Table) | “가상 페이지 번호 → 물리 프레임 번호 + 접근 권한”을 저장하는 자료구조 |
| TLB (Translation Look-aside Buffer) | MMU 내부의 작은 캐시. 최근 주소 변환 결과를 보관해 속도를 높임 |
페이징은 가상 주소와 물리 주소 사이에 간접층을 삽입해, 각 프로세스가 독립적인 주소 공간을 갖게 하는 기술이다. 이를 통해 ① 보호(Protection), ② 공유(Sharing), ③ 공간 활용(세그먼트 단편화 제거)을 달성한다.
2. 주소 변환 과정
- 가상 주소(48bit)를 상위 9비트씩 잘라
PML4 → PDPT → PD → PT → Offset순으로 인덱싱한다 (x86-64 4-level 페이징) - MMU가 CR3 레지스터의 PML4 물리 주소를 읽어 다단계 테이블을 탐색한다
- 최종 PTE에서 PFN(프레임 번호) 와 권한 비트(R/W, U/S, P)를 읽는다
- 접근 허용이면 물리 주소 = PFN × 4KB + Offset
- 접근 위반이거나 P 비트 = 0이면 Page Fault 발생 → OS 개입
TLB가 히트하면 1~3단계가 생략되어 수십 ns 이내로 끝난다.
2-1. CR3 레지스터
CR3는 x86-64의 Control Register 3로, 현재 주소 공간의 PML4 물리 주소를 담는다.
| 비트 범위 | 이름 | 내용 |
|---|---|---|
| 63–52 | Reserved | CPU 모델별 확장 |
| 51–12 | PML4 물리 베이스 | 4KB 정렬된 최상위 테이블 주소 |
| 11–0 | PCID / 플래그 | Process-Context ID(0~4095) 및 제어 플래그 |
컨텍스트 스위칭 때 CR3를 바꾸면 MMU가 “새 주소 공간으로 바뀌었다”고 간주하며, 대부분의 TLB 엔트리가 자동 무효화된다. CR3의 역할을 정리하면 다음과 같다.
- 주소 공간 식별: 커널이 컨텍스트 스위칭 시 CR3를 새 값으로 로드한다. PCID가 이전과 다르면 TLB 엔트리가 ‘다른 주소 공간’으로 구분되어 대부분 유지되므로 TLB flush 비용이 줄어든다
- 전역(Global) 페이지: PTE의 G 비트를 1로 두면 CR3 변경에도 flush되지 않는다 (커널 코드·데이터용)
- Selective flush:
invlpg (addr)로 특정 페이지만 무효화한다. SMP 환경에서는 같은 주소 공간을 쓰는 다른 코어에도 IPI로 전파해야 한다
PintOS처럼 PCID를 쓰지 않는 단순 구현도, CR3를 재로드하면 “전체 TLB flush” 효과를 얻는다.
2-2. PTE의 R/W · U/S · P 비트
| 비트 | 이름 | 1일 때 | 0일 때 |
|---|---|---|---|
| R/W | 쓰기 권한 | 읽기 + 쓰기 허용 | 읽기 전용. write 시 폴트 |
| U/S | 특권 등급 | CPL 3(유저)도 접근 가능 | 커널(CPL 0~2)만 접근. 유저 접근 시 폴트 |
| P | 존재 여부 | 물리 프레임에 매핑됨 → 정상 접근 | 없음 → 접근 시 page fault |
CPL (Current Privilege Level)
CPL은 현재 실행 중인 명령어의 권한 레벨이다. 별도 레지스터가 아니라 CS 세그먼트의 하위 2비트가 CPL로 해석된다.
| Ring / CPL | 용도 | 유저 코드 진입 |
|---|---|---|
| 0 | 커널·하이퍼바이저·펌웨어 (최상위 권한) | ✗ |
| 1 | 일부 마이크로커널·드라이버 (거의 미사용) | ✗ |
| 2 | 특수 계층 (Windows NT 초기 등, 거의 미사용) | ✗ |
| 3 | 일반 사용자 애플리케이션 | ✓ |
페이징 권한 검사는 U/S 비트가 0이면 CPL 0~2만, R/W 비트가 0이면 (CPL 무관) 읽기만 허용한다. 시스템 콜(syscall, int 0x80)은 게이트를 통해 Ring 3 → Ring 0으로 권한을 상승한 뒤, 커널이 iretq로 돌아올 때 Ring 3로 복귀한다.
2-3. TLB 히트
CPU가 가상 주소를 던졌을 때 TLB에 그 VA→PA 매핑이 이미 있으면 히트(hit) 다. 이 경우 페이지 테이블을 걷지 않으므로 변환이 한두 사이클에 끝난다. 없으면 미스(miss) → 긴 4단계 페이지 테이블 워크가 수행된다.
| 레벨 | 커버 범위 | 페이지 크기 | 방식 |
|---|---|---|---|
| L1-DTLB | 데이터 변환 전용 | 4KB / 2MB | 64 엔트리, 4-way |
| L1-ITLB | 코드 변환 전용 | 4KB / 2MB | 128 엔트리, 4-way |
| STLB (L2) | Unified | 4KB / 2MB / 1GB | 1536 엔트리 이상 |
- 히트: 요청한 VPN이 TLB 태그에 있어 PFN을 즉시 반환
- 미스: MMU가 다단계 페이지 테이블 워크를 수행하며 메모리를 읽어야 해 수십~수백 ns 지연
- 멀티코어 일관성: PTE가 바뀌면 IPI(Inter-Processor Interrupt)로 다른 코어에 TLB flush를 요청해 무효화한다
체감상 L1 TLB 히트 ≈ 1~3 cycle, STLB 히트 ≈ 5~10 cycle, 미스 ≈ 수십 cycle이므로, TLB 친화적인(순차·지역성 높은) 메모리 접근이 성능에 큰 영향을 준다.
3. 운영체제의 역할
| 시점 | OS가 하는 일 |
|---|---|
| 프로세스 생성 | 새 페이지 테이블 구성, 코드/데이터 PTE를 “not-present”로 표기 |
| 페이지 폴트 | ⓐ 유효하나 매핑 없음 → Demand Paging(프레임 할당 → 디스크 로드 → PTE 갱신 → 재실행) / ⓑ 스택 확장 조건 위배·보호 위반 → Segmentation Fault |
| 메모리 부족 | 페이지 교체 알고리즘으로 victim 선정 → swap out → PTE 수정 |
| 컨텍스트 스위칭 | CR3에 새 프로세스의 PML4 물리 주소 기록, TLB flush |
TLB Flush
“페이지 테이블을 고쳤으니 캐시에 남은 옛 변환을 버려라”는 명령이다.
mov %cr3, ... / mov ..., %cr3: CR3 재로드로 전체(비-Global) TLB 무효화invlpg (addr): 지정 페이지 하나만 정밀 무효화
둘 다 커널 모드 전용이며, SMP 환경에서는 다른 CPU에도 IPI로 flush를 전파해야 한다.
4. 페이지 교체 (Page Replacement)
| 알고리즘 | 개요 | 장단점 |
|---|---|---|
| Optimal (OPT) | 가장 늦게 재참조될 페이지 제거 | 이론적 최적, 실현 불가 |
| LRU | 가장 오래 안 쓴 페이지 선택 | hit율 좋음, 구현 비용 높음 |
| Clock (2nd-chance) | 원형 큐 + reference bit로 LRU 근사 | 구현 간단, 성능 무난 |
PintOS Project 3에서는 Clock 변형으로 구현했다. (자세한 내용은 Page Replacement Policy 참고)
5. PintOS 관점 요약
| 구조체 / 함수 | 하는 일 |
|---|---|
struct page |
한 가상 페이지의 메타데이터(SPT key), 타입(anon/file), 프레임, dirty 등 |
| Supplemental Page Table (SPT) | 프로세스별 해시 맵/트리. spt_find_page(), spt_insert_page() |
vm_try_handle_fault() |
페이지 폴트 핸들러 진입점. 스택 성장·lazy loading 로직 포함 |
swap_in/out() |
스왑 디스크 I/O 실행. Clock victim이 anon이면 out, fault 시 in |
file_backed_initializer() |
mmap·lazy file load에 쓸 custom swap_in/out 등록 |
6. 다단계 페이징을 쓰는 이유
| 이유 | 설명 |
|---|---|
| 공간 절약 | 4-level 구조에서 사용된 테이블만 할당해 메모리 절약 |
| 보호 | 각 레벨 테이블을 4KB 페이지로 두고 U/S 비트로 커널이 관리 |
| 공유 | fork 시 상위 테이블을 copy-on-write로 공유 가능 |
7. 페이지 크기와 내부 단편화
- 페이지가 크면 → TLB miss 감소(+), 내부 단편화 증가(−), I/O 효율 향상(+)
- 현대 x86-64는 4KB 기본 + 2MB/1GB Huge Page 옵션을 제공한다
8. 정리
페이징은 프로세스마다 독립적·선형적인 주소 공간을 제공하면서, OS가 필요할 때만 물리 메모리·디스크를 할당하고, TLB와 다단계 페이지 테이블로 성능과 메모리 사용량을 균형 있게 최적화하는 메커니즘이다. PintOS에서 구현·조정하는 모든 VM 기능은 이 큰 틀 안에 위치한다.
