Translation Buffer, Advanced Page Table

December 4, 2025 8 분 소요

이번 포스트는 OS의 Tranlstaion Lookaside Buffer와 Advanced Page Tables 에 대해 다룬다.

Translation Lookaside Buffer

TLB

MMU (Memory Management Unit)안에 있는 고속 캐시
목적 : 가장 자주 사용되는 VA -> PA (virtual -> physical) 변환 정보를 빠르게 제공
- 페이지 테이블 전체를 매번 메모리에 읽지 않도록 하기 위한 하드웨어 캐시 역할
구조

CPU → Logical Address 생성
      ↓
     MMU
        ↳ TLB Lookup
           ● Hit → 바로 Physical Address 반환
           ● Miss → Page Table 접근 후 변환을 찾고, TLB에 저장
      ↓
Physical Memory 접근

우선 TLB에서 변환을 찾는다.

있으면 (TLB Hit) : page table 접근 없이 즉시 물로 주소를 획득한다.
없으면 (TLB Miss) : MMU가 페이지 테이블을 메모리에서 읽어 PFN을 얻고, 그 결과를 TLB에 넣고 다시 instruction을 재실행

TLB는 캐시의 캐시 같은 역할

TLB 기본 알고리즘

Virtual Page Number 추출
- 가상주소 상위 비트 구간을 VPN으로 사용
- page table indexing 용도

VPN = (VirtualAddress & VPN_MASK) >> SHIFT

TLB Lookup
- TLB 내부에 VPN과 동일한 entry 가 있는지 검색

(Success, TlbEntry) = TLB_Lookup(VPN)

TLB Hit 처리
- 보호 비트 (읽기/쓰기/실행)가 허용되면 정상 접근
- PFN (page frame number)을 가져와 offset 과 합쳐 물리 주소 생성

if(Success){
    if(CanAccess(TlbEntry.ProtectBit)){
        offset = VirtualAddress & OFFSET_MASK;
        PhysAddr = (TlbEntry.PFN << SHIFT) | offset;
        AccessMemory(PhysAddr);
    }
    else RaiseException(PROTECTION_ERROR);
}

아래는 TLB Miss 처리

한 번은 반드시 페이지 테이블 액세스가 필요

이후 같은 주소 접근 시 TLB Hit로 빠르게 처리

TLB Table Entry 위치 계산
- Page Table Base Register (PTBR)는 page table의 시작 주소를 나타냄
- VPN을 인덱스로 하여 PTE로 주소를 계산

PTEAddr = PTBR + (VPN * sizeof(PTE))

Page Table Access
- Valid bit = 0
- VPN이 유효하지 않다. -> Segmentation Fault

PTE = AccessMemory(PTEAddr)
if(PTE.Valid == False)
    RaiseException(SEGFAULT)

새로운 변환을 TLB에 삽입
- 방금 얻은 변환 (VPN -> PFN)을 TLB에 저장
- instruction 재실행 (이제 TLB Hit 발생)

Locality

TLB가 잘 작동할 수 있는 이유 = 프로그램의 지역성 (Locality) 때문

Temporal Locality (시간 지역성)

최근에 접근한 페이지는 곧 다시 접근할 확률이 높다.
- 예: 같은 변수 반복 참조, 반복문 내 변수

Spatial Locality (공간 지역성)

주소 x를 접근했다면, 근처 주소도 곧 접근 가능성이 높다.
- 예 : 배열 순차 접근 a[i], a[i + 1]

Who handles TLB Miss?

TLB miss 발생하면 누가 처리하는지는 CPU 아키텍처에 따라 다르다.

CISC

Intel x86 (하드웨어-managed TLB)
TLB miss 시 CPU 하드웨어가 직접 page table walk 수행
CPU가 메모리에서 page table 찾아보고 PFN 가져와서 TLB 갱신

과정

TLB miss
하드웨어가 page table에서 PTE를 읽음
TLB 업데이트
Instruction 재실행

OS 의 개입이 거의 없다. (성능이 높음)

CPU가 메모리에서 page table을 직접 찾아보고 PFN에서 가져와서 TLB를 갱신

RISC

ARM, MIPS 등 (소프트웨어-managed TLB)
TLB Miss 시 hardware는 trap만 발생
실제 페이지 테이블 lookup은 OS 코드 (trap handler)가 수행

과정

TLB Miss
하드웨어가 TLB_Miss Exception 발생
OS Trap Handler 발생
OS가 Page Table Lookup 수행
TLB에 넣고 instruction을 재실행

장점 : 하드웨어가 간단

단점 : OS trap -> context swtich 성능 저하

코드 구현

VPN = Extract(VirtualAddress)

(Success, Entry) = TLB_Lookup(VPN)

if (Success == TRUE) {        // TLB Hit
    if (AccessAllowed(Entry.ProtectBits)) {
        offset = VA & OFFSET_MASK
        PA = (Entry.PFN << SHIFT) | offset
        AccessMemory(PA)
    } else {
        RaiseException(PROTECTION_FAULT)
    }
}

이 중에서

else {       // TLB Miss
    RaiseException(TLB_MISS)
}

TLB Miss를 OS에 넘기는 것 = ARM/RISC 스타일

OS trap Handler에서 할 일:

Page Table에서 PTE 찾음.
권한 체크
유효하지 않으면 segfault
유효하면 해당 VPN -> PFN 을 TLB에 넣음
faulting instruction retry

TLB Entry

TLB는 Fully Associative 방식으로 관리된다.
- 어떤 번역 (translation)도 TLB 의 어느 위치에나 저장될 수 있다.
- 하드웨어가 모든 엔트리를 병렬 탐색하여 원하는 VPN을 찾는다.

구성 요소

VPN (Virtual Page Number) : 가상 페이지 번호
PFN (Page Frame Number) : 실제 물리 프레임 번호
Other Bits
- valid bit
- protection bits
- dirty bits
- address-space identifier (ASID) 등

Issue : Context Switching

프로세스가 전환할 때,
- TLB에 남아있는 이전 프로세스의 엔트리 때문에
- 잘못된 PFN을 사용하여 메모리를 접근할 위험이 있다.

TLB는 VPN만 보고 찾기 때문에, 동일 VPN을 가진 다른 프로세스의 엔트리를 구분을 못한다.

TLB의 엔트리로만 어떤 프로세스의 번역인지 판별이 불가능

해결 방법 : ASID

ASID (Address Space Identifier)

TLB 엔트리에 ASID 필드를 추가하여 같은 VPN이라도 프로세스별로 구분이 가능하게 한다.
장점 :
- Context switching 시 TLB Flush 를 완전히 할 필요가 없다.
- 같은 번호의 VPN이라도 프로세스마다 따로 관리된다.

Another Case

두 프로세스가 페이지를 공유하는 경우

서로 다른 프로세스라도 같은 물리 페이지(PFN)을 공유할 수 있다.
VPN이 다르지만 PFN이 동일한 상황
- 페이지 공유는 물리 메모리 사용량을 줄이는 장점이 있어서 사용

LRU (Least Recently Used)

TLB가 꽉 찼을 때 가장 오랫동안 사용되지 않은 엔트리부터 교체
Locality (시간, 공간 지역성)를 활용하는 정책

LRU

실제 TLB 엔트리의 구성 (64-bit)

필드	역할
19-bit VPN	가상 페이지 번호
24-bit PFN	물리 페이지 번호 (64GB 주소공간 지원)
Global bit (G)	여러 프로세스가 공유하는 페이지 표시
ASID	TLB 항목의 소유 프로세스를 구분
Coherence bit (C)	캐시 일관성(캐시 전략) 관련 설정
Dirty bit (D)	페이지가 수정되었는지 여부(Write-back에 사용)
Valid bit (V)	TLB 엔트리가 유효한지 여부

실제 시스템의 TLB는 매우 다양한 메타데이터를 포함

이 비트들 덕분에 TLB는 보안, 공유, 캐싱, 변경 여부까지 모두 관리가 가능

Advanced Page Table

Paging : Linear Tables

모든 프로세스는 자신만의 페이지 테이블을 가진다.
32-bit 주소 공간, 4KB 페이지, PTE 4바이트라고 가정하면:
- 페이지 개수 = 2^20 = 약 100만개
- 페이지 테이블 크기 = 4MB
문제점
- 각 프로세스마다 페이지 테이블이 4MB나 필요하다
- 프로세스 100개면 페이지 테이블만 400MB -> 너무 크다.
- 물리 메모리를 낭비한다.

Smaller Tables

시도 : 페이지 크기를 키우자 (4KB -> 16KB)

페이지 개수가 줄어들어 페이지 테이블도 줄어든다.
- 새 페이지 개수 = 2^18 = 약 26만개
- 페이지 테이블 크기 = 1MB
장점 : 페이지 테이블 사이즈가 4MB -> 1MB로 감소되면서 메모리 절약
문제점
- 내부 단편화 (internal fragmentation) 발생이 커진다.
- 1KB만 사용해도 16KB 페이지 하나 전체를 차지해야 함.
- 작은 메모리 요청이 큰 페이지를 낭비시키는 구조

Single Page Table Problem

상황

16KB 가상 주소 공간, 페이지 크기 1KB -> 총 16개의 VPN (0~15)
프로세스는 code/heap/stack 등 특정 페이지만 실제 물리 메모리와 매핑됨.

문제

전체 페이지 테이블 (16개 엔트리)을 만들어야 한다.
하지만 실제 사용하는 페이지(매핑된 페이지)는 몇 개뿐
나머지 엔트리는 다음과 같이 invalid

즉, unused entries 가 대부분을 차지한다.

메모리 사용량이 불필욯아게 커짐. (페이지 테이블의 대부분이 낭비됨)

Hybrid Approach : Paging and Segments

아이디어 : 프로세스의 가상 주소 공간은 보통 여러 ‘segment’로 나뉜다.

예:

code segment (01)
heap segment (10)
stack segment (11)

각 세그먼트마다 필요한 만큼만 page table을 따로 만든다.

가상 주소 구성

Bits	의미
31–30	Segment Number (SN)
29–12	VPN (세그먼트 내부 페이지 번호)
11–0	Offset

장점

각 세그먼트에 대해 작고 필요한 만큼만 페이지 테이블 생성
불필요한 Huge linear page table 생성 X
메모리 절약 효과가 크다.

TLB Miss on Hybrid Approach

TLB miss가 발생하면, HW는 다음 단계를 수행한다.

1. SN 추출

SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT

가상 주소의 상위 2비트를 보고 어떤 segment인지 판단
- 예: 01=code , 10 = heap, 11 = stack

2. VPN 추출

VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT

3. 해당 Segment Page Table에서 PTE 주소 생성

AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

여기서 Base[SN] = ‘해당 세그먼트 page table의 시작 물리 주소’

Problem of Hybrid Approach

Heap 문제

예를 들어 heap 세그먼트의 크기를 아주 크게 잡았는데, 실제로는 몇 페이지만 사용하는 경우
이 세그먼트에 대해 페이지 테이블 하나를 만들면
- 사용하지 않는 가상 페이지들에 대해서도 페이지 테이블 엔트리가 존재한다.
- 대부분이 valid = 0 인 무효 엔트리인데도 메모리를 차지한다.
즉 세그먼트 단위로 페이지 테이블을 쪼갰지만, 세그먼트 안에서의 희소성 (sparsity) 문제 때문에 여전히 페이지 테이블 낭비가 크다.

외부 단편화 (external fragmentation) 재발

세그먼트 방식이 들어오면, 각 세그먼트를 위한 페이지 테이블 자체가 물리 메모리에서 연속적인 공간을 필요로 할 수 있다.
세그먼트 크기가 커지고 쪼개졌다 늘어났다 하면, 물리 메모리 안에 조각난 빈 공간들이 생기게 되고, 이것이 외부 단편화이다.

Multi-level Page Tables

기존 1차원 배열인 페이지 테이블 -> 다단계 (트리 비슷한 구조로 변경)
페이지 테이블 전체를 여러 개의 페이지 단위 조각으로 나눈다.
- 각각의 조각은 페이지 테이블의 한 페이지라고 생각하면 된다.
Invalid 엔트리만 있는 페이지는 아예 안 만든다.
- 전부 invalid인 엔트리가 있으면, 그 페이지 자체를 물리 메모리에 할당하지 않는다.
- 사용하지 않는 가상영역에 대한 테이블 페이지는 아예 생성하지 않아서 메모리 절약이 가능
Page Directory
- 어떤 페이지 테이블 조각이 존재하는지 안하는지를 추적하는 역할
- 각 페이지에 대한 포인터 + 유효 비트를 가진 상위 테이블

Advantage

사용한 주소 공간에 비례해서만 페이지 테이블 공간 사용
- 프로세스가 실제로 사용하는 가상 주소 범위에 해당하는 부분의 PTE 페이지만 존재
- sparse 가상 주소 공간에서 특히 장점
  - code, stack, heap 사이에 큰 빈 구간이 있어도 그 구간에 대한 페이지 테이블 페이지는 생성하지 않음.
OS가 필요할 때마다 다음 빈 페이지를 가져다 씀
- 새로운 영역 (ex : 힙 확장, 스택 성장)을 위해 페이지 테이블이 필요해지면, OS가 다음 빈 물리 페이지를 할당해서 새 페이지 테이블 페이지로 쓰면 된다.
- On-demand로 페이지 테이블 확장이 가능함.

Disadvantage

Time-sapce trade-off
- 공간은 절약했지만, 주소 변환 과정이 더 복잡함.
- 따라서 추가적인 메모리 참조 횟수 때문에 성능을 어느정도 희생하게 됨.
Complexity
- 하드웨어 (MMU) 와 OS 코드가 더 복잡해짐.
- 페이지 디렉터리 / tree 인덱싱 계산
- TLB 미스 처리 시 여러 단계 테이블을 따라가야 함
- 구현 난이도 증가

Page Directory

Page Directory는 Page Table의 각 페이지당 1개의 엔트리를 가진다.
각 엔트리는 PDE (Page Directory Entry)라고 부른다.
- valid bit : 해당 페이지 테이블 페이지가 실제 메모리에 존재하는지
- PFN (Page Frame Number) : 그 페이지 테이블 페이지가 높은 프레임 번호
결국 그 아래 단계 페이지 테이블이 어디에 있는지 가리키는 포인터

Indirection

이러한 multi-level 구조 : Indirection 참조 레벨을 조정할 수 있다
- 먼저 page directory에서 PDE를 찾아 페이지 테이블 페이지의 위치를 얻고,
- 그 다음 그 페이지 테이블에서 실제 PTE를 찾는 2단계 접근 방식
페이지 테이블의 각 페이지를 물리 메모리 아무 곳에나 둘 수 있다.
- 필요한 부분만 페이지 단위로 늘려가며 할당이 가능

전체 동작 흐름

Vritual Address 분리
- Offset = 6bit
- VPN = 8 bit -> 다시 PD index + PT index로 분리
Page Directory lookup
- PD index로 PDE 읽기
- invalid -> exception / valid -> page-table-page의 PFN 획득
Page Table lookup
- PFN + PT index로 실제 PTE 읽기
PTE 의 Valid/Protection 확인
PFN + Offset -> Physcial Address 생성

Inverted Page Tables

기존 방식 (Page Table per Process)의 문제점

Virtual Pages 수가 매우 많음.
프로세스마다 page table을 만들면 낭비가 심해짐.
- 대부분의 페이지는 비어 있고, Page Table entry가 엄청 많다.

Inverted Page Table

Physical Page : 어느 프로세스의, 어느 Virtual Page인지를 저장
시스템 전체에 단 하나만 존재
엔트리 수 = Physical Page 수 만큼만 존재

Twitter Facebook LinkedIn