09. adv_paging

  • Haram Lee
  • 2026-04-18
  • studies / 26-1 / operating-systems

Advanced Page Tables & TLB

Reading

  • 이 단원은 크게 두 부분으로 나뉜다.
    • Advanced Page Tables
    • TLB
  • 즉 paging 이후 남는 두 문제를 다룬다.
    • 공간 문제
      • page table이 너무 크다.
    • 시간 문제
      • address translation이 너무 느리다.

Linear Page Table

  • 가장 단순한 방식은 프로세스마다 선형 페이지 테이블 하나를 두는 것이다.
  • 하지만 이 방식은 page table이 너무 커진다.
  • 예를 들어 32-bit address space, 4KB page, 4B PTE라면 page table 하나가 4MB가 된다.
  • 프로세스 수가 많아지면 page table만으로도 상당한 메모리를 잡아먹는다.

Important observation of virtual address

  • 중요한 관찰은 프로세스의 virtual address space 대부분이 실제로는 비어 있다는 점이다.
  • 실제로는 code, heap, stack 같은 일부 영역만 valid하고, 나머지는 invalid entry가 대부분이다.
  • 즉 선형 페이지 테이블은 쓰이지 않는 엔트리까지 전부 저장하느라 메모리를 낭비한다.

Hybrid Approach: Paging and Segments

  • 첫 번째 절충안은 segmentation과 paging을 섞는 방식이다.
  • segmentation처럼 유효한 주소 공간만 segment로 나누고, 각 segment 내부는 paging처럼 고정 크기 page로 나눈다.
  • 즉 전체 virtual address space 하나에 giant page table을 두는 대신, segment별 page table을 두는 구조다.

Paging with Segmentation

  • 이 구조에서는 segment table이 각 segment의 page table 위치와 크기를 관리한다.
  • translation은 대략 다음 순서로 진행된다.
    • segment를 찾는다.
    • 그 segment의 page table을 찾는다.
    • 그 page table에서 page를 찾는다.
  • 선형 페이지 테이블보다 낭비는 줄지만, 구조는 더 복잡하다.

Summary: Paging with Segmentation

  • 장점
    • 선형 page table보다 메모리 사용량을 줄일 수 있다.
    • segment가 독립적으로 grow할 수 있다.
    • page 단위뿐 아니라 segment 단위 공유도 가능하다.
  • 단점
    • 큰 segment는 여전히 큰 page table을 가질 수 있다.
    • 각 segment의 page table은 연속적인 공간을 필요로 해서 외부 단편화 문제가 남는다.
  • 즉 개선은 되었지만, 완전한 해결책은 아니다.

Multi-level Page Table

  • 핵심 개선은 선형 페이지 테이블을 트리 구조처럼 여러 단계로 나누는 것이다.
  • page table 자체를 page 크기 단위로 쪼개고, 어떤 구간이 전부 invalid라면 그 하위 page table page는 아예 만들지 않는다.
  • 이를 위해 상위 구조인 page directory를 둔다.
  • 즉 필요한 부분의 page table만 실제로 할당하는 방식이다.

Virtual Address Translation

  • multi-level page table에서는 virtual address가 세 부분으로 나뉜다.
    • page directory index
    • page table index
    • page offset
  • 먼저 page directory에서 하위 page table을 찾고,
  • 그 다음 page table에서 PFN을 찾고,
  • 마지막으로 offset을 붙여 physical address를 만든다.

Two-level Page Tables

  • 2-level page table은 VPN을 두 부분으로 나눈다.
    • page directory index
    • page table index
  • 예를 들어 textbook example처럼
    • virtual address가 30bit이고
    • page size가 512B이면
    • offset은 9 bit다.
  • PTE가 4B라면 page table page 하나에 들어가는 엔트리 수는 512 / 4 = 128 = 2^7 개이므로 page table index는 7 bit가 된다.
  • 나머지 VPN 비트는 page directory index가 된다.

More Than Two Levels

  • page directory 자체도 크면 또 다시 나눌 수 있다.
  • 그래서 2-level이 끝이 아니라 3-level, 4-level로 확장될 수 있다.
  • 핵심 아이디어는 같다.
    • 한 번에 거대한 배열 하나를 두지 않고
    • 필요한 하위 테이블만 생성한다.

Multi-level Page Table: Intel x86

  • 실제 아키텍처도 multi-level page table을 쓴다.
  • x86_32에서는 보통 directory와 table을 거치는 2-level 구조를 생각할 수 있다.
  • x86_64는 훨씬 큰 address space를 다뤄야 하므로 더 많은 레벨을 사용한다.
  • 즉 multi-level page table은 단순 교과서용 아이디어가 아니라 현대 OS/CPU가 실제로 쓰는 구조다.

Summary: Multi-level Page Table

  • 장점
    • sparse address space를 효율적으로 지원한다.
    • page-table 공간이 실제 사용 주소 공간에 더 비례한다.
    • 각 page table이 보통 page 크기 안에 들어가서 관리가 쉽다.
    • 외부 단편화가 없다.
  • 단점
    • translation 과정에서 메모리 접근 횟수가 늘어난다.
    • 하드웨어 구조가 더 복잡해진다.
  • 즉 공간을 아끼는 대신 시간 비용이 커질 수 있다.

TLB

  • page table을 multi-level로 줄였더라도, address translation 자체는 여전히 느리다.
  • 이 문제를 해결하기 위해 TLB(Translation Lookaside Buffer) 를 둔다.
  • TLB는 MMU 안에 있는 작은 하드웨어 캐시로, 자주 쓰는 virtual-to-physical translation 결과를 저장한다.
  • 즉 page table 전체를 캐시하는 것이 아니라, 자주 쓰는 일부 translation만 빠르게 기억해 두는 구조다.

Address Translation Steps

  • paging에서 한 번의 memory reference는 생각보다 비싸다.
  • 대략 다음 순서가 필요하다.
    • VA에서 VPN을 뽑는다.
    • PTE 위치를 계산한다.
    • 메모리에서 PTE를 읽는다.
    • PFN을 뽑는다.
    • PA를 만든다.
    • 그 PA에서 실제 데이터를 읽는다.
  • 즉 data를 한 번 읽으려 해도, translation 때문에 page table 접근이 추가된다.

The Problem

  • linear page table은 memory lookup cost를 거의 2배로 만들 수 있다.
  • multi-level page table은 이 cost를 더 늘릴 수 있다.
  • 그래서 목표는 virtual address access를 physical address access에 가깝게 빠르게 만드는 것이다.
  • TLB는 바로 이 문제를 해결하기 위한 장치다.

Example: Accessing an Array

  • 배열을 순차적으로 접근하면 같은 page 안의 원소들을 연속해서 읽게 된다.
  • 이 경우 첫 접근은 TLB miss가 날 수 있지만, 같은 page 안의 다음 접근들은 TLB hit가 잘 난다.
  • 즉 TLB는 spatial locality 덕분에 효과를 낸다.
  • 슬라이드 예시에서는 여러 번의 배열 접근 중 일부만 miss이고 나머지는 hit가 된다.

Locality

  • TLB가 잘 동작하는 이유는 프로그램의 메모리 접근이 locality를 가지기 때문이다.
  • Temporal locality
    • 최근에 접근한 instruction이나 data는 곧 다시 접근될 가능성이 크다.
  • Spatial locality
    • 어떤 주소를 접근했다면 그 근처 주소도 곧 접근할 가능성이 크다.
  • 배열 순차 접근은 대표적인 spatial locality 예시다.

TLB Organization

  • TLB는 보통 적은 수의 entry를 가지는 작은 cache다.
  • entry 안에는 PFN만 있는 것이 아니라, translation에 필요한 PTE 정보 전체가 들어갈 수 있다.
  • 즉 TLB hit가 나면 page table까지 가지 않고도 PFN, valid 여부, protection 정보 등을 곧바로 얻을 수 있다.

Address Translation with TLB

  • address translation의 기본 흐름은 다음과 같다.
    • 먼저 TLB를 lookup한다.
    • TLB hit면 바로 PFN을 얻고 physical address를 만든다.
    • TLB miss면 page table 쪽으로 내려가서 translation을 다시 수행한다.
  • 즉 TLB는 page table 앞단에 놓인 translation cache다.

Handling TLB Misses

  • TLB miss 처리 방식은 두 가지가 있다.
  • Software-managed TLB
    • miss가 나면 CPU가 trap을 발생시키고 OS가 page table을 보고 TLB를 채운다.
  • Hardware-managed TLB
    • CPU가 직접 page table walk를 해서 TLB를 채운다.
  • 즉 miss 처리 주체가 OS인지 하드웨어인지가 아키텍처에 따라 다르다.

TLB on Context Switches

  • context switch가 나면 이전 프로세스용 TLB entry가 남아 있을 수 있다.
  • 가장 단순한 방법은 switch 때마다 TLB flush를 하는 것이다.
  • 하지만 그러면 새 프로세스가 실행될 때 TLB가 텅 비어서 성능이 나빠진다.
  • 이를 줄이기 위해 ASID(Address Space ID) 같은 태그를 사용하기도 한다.
  • ASID를 쓰면 서로 다른 프로세스의 같은 VPN도 TLB 안에서 구분할 수 있다.

TLB on Multi-core

  • multi-core에서는 더 복잡한 문제가 생긴다.
  • 한 코어에서 page table을 바꿨더라도, 다른 코어의 TLB에는 옛 entry가 남아 있을 수 있다.
  • 그래서 OS는 필요할 때 다른 코어들에게 invalidate를 요청하는 TLB shootdown을 해야 한다.
  • 즉 TLB coherence는 cache coherence와는 또 다른 관리 문제를 만든다.

Load Example

  • 정상적인 load의 common case는 다음과 같다.
    • CPU가 virtual address로 load를 시도한다.
    • TLB hit가 난다.
    • protection을 확인한다.
    • PFN과 offset으로 physical address를 만든다.
    • 그 physical address에서 data를 읽는다.
  • 즉 가장 빠른 경우는 TLB hit + no fault다.

Load: On TLB Miss

  • TLB miss는 TLB에 translation entry가 없을 뿐이라는 뜻이다.
  • 이 경우
    • hardware-managed면 MMU가 page table을 본다.
    • software-managed면 OS가 trap을 받아 처리한다.
  • 그 뒤 TLB를 채우고 instruction을 다시 수행한다.
  • 중요한 점은 TLB miss와 page fault는 다르다는 것이다.

Load: On Page Faults

  • page fault는 translation이 아예 invalid하거나, page가 physical memory에 없을 때 발생한다.
  • 경우는 크게 나눠서 볼 수 있다.
    • protection violation
      • 허용되지 않은 접근이다.
    • invalid page
      • 애초에 process address space에 없는 page다.
    • not-present but valid
      • page는 유효하지만 지금 memory에 없어서 disk에서 가져와야 한다.
  • 즉 page fault는 단순 miss보다 더 큰 사건이다.

Integrating VM and Cache

  • TLB 뒤로는 cache와 virtual memory의 관계가 나온다.
  • physical-addressed cache는 단순하지만 translation 이후에야 접근할 수 있어서 느릴 수 있다.
  • 반대로 virtual-addressed cache는 translation 전에 접근할 수 있어 빨라 보이지만 homonym, synonym 같은 문제를 일으킬 수 있다.
  • 그래서 실제 시스템은 이 둘 사이에서 절충된 구조를 사용한다.

TLB Summary

  • 이 단원의 핵심은 두 줄로 정리할 수 있다.
    • page table이 너무 크다
      • → multi-level page table로 줄인다.
    • address translation이 너무 느리다
      • → TLB로 빠르게 만든다.
  • 즉 9단원은 paging 이후 남는 공간 오버헤드와 시간 오버헤드를 해결하는 단원이다.

마지막 정리

  • 선형 페이지 테이블은 구현은 단순하지만 메모리 낭비가 크다.
  • 이를 줄이기 위해 paged segmentation, multi-level page table 같은 구조가 등장한다.
  • 하지만 page table이 작아져도 translation cost 자체는 여전히 크다.
  • 그래서 MMU 안에 TLB를 두어 자주 쓰는 translation을 캐시한다.
  • 결국 이 단원은 paging을 현실적인 구조로 만들기 위해 필요한 개선들을 다룬다고 볼 수 있다.
Discussion