Paging

in Blog / CS on 운영체제

OS가 가상 메모리를 어떻게 관리할까?

페이징(Paging) 기본 개념

용어설명
페이지(Page)OS가 관리 단위로 삼는 고정 크기(대게 4Kb)의 가상 메모리 블록
프레임(Frame)물리 메모리에서 페이지와 1 : 1로 매핑되는 동일 크기의 블록
페이지 테이블(Page Table)“가상 페이지 번호 → 물리 프레임 번호 + 접근 권한”을 저장하는 자료구조
TLB(Translation Look-aside Buffer)MMU 내부의 작은 캐시. 최근 주소 변환 결과를 보유해 속도를 높임

페이징은 “가상 주소 ↔ 물리 주소” 사이에 간접층을 삽입해 각 프로세스가 독립적인 주소 공간을 갖도록 만드는 기술이다. 이를 통해 ① 보호(Protection), ② 공유(Sharing), ③ 공간 활용(세그먼트 단편화 제거)이라는 세 가지 핵심 목표를 달성한다.

주소 변환(Translation) 과정

  1. 가상 주소(48 bit) : 상위 9 bit씩 네 번 잘라 PML4→PDPT→PD→PT→오프센 순으로 인덱싱(x86-64 4-level 페이징 구조)

  2. MMU가 CR3 레지스터에 있는 PML4 물리 주소를 읽어 다단계 테이블을 탐색

  3. 최종 PTE(Page Table Entry, PT에 존재)에서 PFN(프레임 번호)와 R/W(read only/writable), U/S(user/supervisor), P(present/not-present) 비트를 읽어

    • 접근 허용이면 물리 주소 = PFN x 4kb + 오프셋

    • 접근 위반 x P비트 = 0이면 Page Fault발생 → OS 개입

TLB가 히트하면 1 ~ 3 단계가 생략되어 수십 ns 이내로 끝납니다.

CR3 레지스터 (아직 이해 못함)

  • x86-64 Control Register 3

    • 상위 52비트 : 현재 주소 공간의 PML4 물리 주소

    • 하위 12비트 : PCID(프로세스-TLB 태그) 및 플래그로써 컨텍스트 스위칭 때 CR3를 바꾸면 MMU가 “새 주소 공간으로 바뀌었다”고 간주하며, 대부분의 TLB 엔트리가 자동으로 무효화됨

비트 범위이름내용
63-52Reserved(CPU 모델별 확장)
51-12PML4 물리베이스4KB 정렬된 주소(최상위 테이블)
11PCID-Enable(인텔)1 → PCID 지원 & PCID = 0 이면 “글로벌 flush”
11-0PCIDProcess-Context ID(0~4095)
TLB 태그로 붙어 “다른 PCID의 엔트리”는 그래도 남김

CR3의 역할 (아직 이해 못함)

  1. 주소 공간 식별자

    • 커널이 컨텍스트 스위칭 시 mov %cr3, %rax / mov %rax, %cr3로 새 값 로드

    • PCID ≠ 이전 값이면, TLB 엔트리가 ‘다른 주소 공간’으로 구분되어 대부분 유지 → TLB flush 비용 감소

  2. 전역(Global) 페이지

    • PTE에 G 비트를 1로 두면 CR3 변경에도 flush되지 않음 (커널 코드/데이터용)

  3. Selective flush

    • 특정 페이지만 무효화할 때 invlpg (addr)사용 → 해당 VPN + PCID 매칭 엔트리만 제거

    • SMP 환경에서 다른 코어도 동일 주소 공간이면, 스스로도 같은 명령을 실행해야 함(IPI 브로드캐스트)

PintOS처럼 PCID를 쓰지 않는 단순 구현도, CR3 재로드로 “전체 TLB flush” 효과를 얻음

PTE의 R-W / U-S / P 비트

비트이름값이 1일 때 의미값이 0일 때 의미
R/W (Read/Write)쓰기 권한읽기 + 쓰기 모두 허용읽기 전용. 사용자/커널이 write 하면 PF_W = 1 폴트
U/S (User/Supervisor)특권 등급CPL 3(유저)에서도 접근 가능CPL 0-2(커널)만 접근 가능 → 사용자 접근 시 PF_U = 1 폴트
P (Present)존재 여부해당 가상 페이지가 현재 물리 프레임에 매핑됨 → 정상 접근“없음”으로 표시 → 접근 시 페이지 폴트 발생

CPL(Current Privilege Level)

링(Ring)/CPL 값용도사용자 코드에서 진입 가능?
0커널·하이퍼바이저·펌웨어처럼 시스템의 최상위 권한✗
1일부 마이크로커널·드라이버(거의 사용 X)✗
2‘서비스 OS’(Windows NT 초기) 등 특수 계층(거의 사용 X)✗
3일반 사용자 애플리케이션✓

  • CPL은 현재 실행 중인 명령어의 권한 레벨이다.

  • CPU 레지스터에 따로 존재하지 않고 CS 세그먼트 하위 2비트가 CPL로 해석됨

  • 페이징 권한 검사 :

    • 페이지 엔트리 U/S 비트가 0이면 “Ring 0-2만, 즉 CPL 0~2만 접근 가능”

    • R/W 비트가 0이면, “읽기만 가능, 쓰기는 CPL에 관계없이 금지”

  • 시스템 콜(예 : syscall, int 0x80)은 게이트를 통해 Ring 3→Ring 0으로 ‘권한 상승’한 뒤, 커널이 iretq로 돌아올 때 Ring 3로 복귀한다.

TLB 히트란?

CPU가 가상주소를 던졌을 때 TLB(주소 변환 캐시) 안에 그 VA→PA 매핑이 이미 들어 있으면 히트(hit)라고 부릅니다. 이 경우 MMU가 페이지 테이블을 전혀 걷지 않아도 되므로 변환이 한두 사이클 안에 끝납니다. 반대로 없으면 미스(miss) → 긴 ‘4-단계 페이지 테이블 워크’가 수행됩니다.

TLB 히트 깊게

레벨커버 범위페이지 크기방식
L1-DTLB데이터 변환 전용4KB / 2MB64 엔트리, 4-way set-assoc
L1-ITLB코드 변환 전용4KB / 2MB128 엔트리, 4-way
STLB(L2)Unified4KB / 2MB / 1GB1536 엔트리 이상

  • 히트(Hit) → “요청한 가상주소의 상위 n비트(=VPN)가 TLB태그에 이미 존재하여, 물리 프레임 번호(PFN)를 즉시 반환할 수 있었다”는 뜻

  • 미스(miss) → MMU가 다단계 페이지 테이블 워크를 수행하면서 메모리를 실제로 읽어야 하므로 수십~수백 ns 추가 지연이 발생

  • 멀티코어에서의 일관성 : 같은 물리 페이지를 서로 다른 CPU가 매핑 바꿀 수 있으므로, PTE가 변하면 IPI(Inter-Processor Interrupt)로 다른 코어에 “TLB flush 요청”을 보내 반드시 무효화하게 한다.

체감적으로 L1 TLB 히트는 ≒ 1-3 cycle, STLB 히트는 ≒ 5-10 cycle, 미스는 수십 cycle이기 때문에 “TLB 친화적인(=순차·지역성 높은) 메모리 접근”이 성능에 큰 영향을 줍니다.

운영체제의 역할

시점OS가 수행하는 일
프로세스 생성새 페이지 테이블 구성, 코드/데이터 영역 PTE를 “not-present”로 표기
페이지 폴트ⓐ 유효 but 매핑 없음 → Demand Paging
- 여유 프레임 할당
- 디스크에서 해당 페이지 로드
- PTE 업데이트, 다시 실행
ⓑ 스택 자동 확장 조건 위배, 보호 위반 → Segmentation Fault
메모리 부족페이지 교체 알고리즘으로 Victim 선정, → 디스크 스왑 아웃 → PTE 수정
컨텍스트 스위칭CR3에 새 프로세스 PML4 물리 주소 기록, TLB flush

TLB Flush

“페이지 테이블을 고쳤으니 캐시에 남은 옛 변환을 버려라”는 명령입니다.

대표 방법 :

  • mov %cr3, %rax / mov %rax, %cr3 - CR3를 재로드 해 전체(비-Global) TLB 무효화

  • invlpg (addr) - 지정 페이지 하나만 정밀 무효화

둘 다 커널 모드에서만 가능하며, SMP 환경에선 다른 CPU에도 IPI로 flush를 전파해야 함

페이지 교체(Page Replacement)

알고리즘개요장단점
Optimal(OPT)“앞으로 가장 늦게 재참조될 페이지” 제거이론적 최적 · 실현 불가
LRU최근에 가장 오래 안 쓴 페이지 선택좋은 hit 을, 구현 비용 높음
Clock(2nd-chance)원형 큐 + reference bit로 LRU 근사구현 간단, 성능 무난

기존에 올렸던 PintOS Project3에서는 Clock 변형으로 구현하였다.

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 등록

다단계 페이징을 쓰는 이유

  1. 공간 절약 - 4KB(212) 페이지 x 220 → 4GB 주소 공간. 다단계(4-level)면 “사용된 테이블만” 할당

  2. 보호 - 각 레벨 테이블을 4KB 페이지로 두고 U/S 비트 = 0으로 하면 커널이 관리

  3. 공유 - 부모-자식 fork시 상위 N개 테이블을 copy-on-write 방식으로 공유 가능(메모리 절약)

페이지 크기와 내부 단편화

  • 페이지 크기가 크면 → TLB miss 감소(+), 내부 단편화(-), I/O 효율(+)

  • 현대 x86-64는 4KB 기본 + 2MB/1GB Huge Page 옵션 제공

정리

페이징은 프로세스마다 독립적/선형적인 주소 공간을 제공하면서, OS가 필요한 때만 물리 메모리/디스크를 할당하고 TLB/다단계 페이지 테이블로 성능과 메모리 사용량을 균형있게 최적화하는 메커니즘입니다. PintOS 프로젝트에서 구현·조정하는 모든 VM 기능들은 이 큰 틀 안에 위치합니다.

© 2022 JeongHwan Yun.