TLB와 페이지 테이블 최적화

페이지 테이블은 메모리에 저장됩니다. 그런데 메모리에 접근하려면 먼저 페이지 테이블을 조회해야 하고, 페이지 테이블 자체도 메모리에 있으니 메모리 접근이 한 번 더 필요합니다. 데이터 하나를 읽으려면 메모리를 두 번 접근해야 합니다 — 페이지 테이블 참조 + 실제 데이터. 성능이 절반으로 떨어집니다. 이 문제를 해결하는 것이 TLB입니다.

TLB의 역할

TLB(Translation Lookaside Buffer)는 최근 사용된 페이지-프레임 매핑을 저장하는 고속 하드웨어 캐시입니다. CPU 칩 안에 위치하며, 연관 메모리(Associative Memory)로 구현되어 모든 엔트리를 동시에(병렬로) 비교할 수 있습니다.

동작 과정

1. CPU가 논리 주소를 생성합니다.
2. 페이지 번호로 TLB를 병렬 검색합니다 (하드웨어가 모든 엔트리를 동시 비교).
3. TLB 히트(Hit): 프레임 번호를 즉시 얻어 물리 주소를 생성합니다. 추가 메모리 접근 없음.
4. TLB 미스(Miss): 메모리의 페이지 테이블을 참조하여 프레임 번호를 얻고, 결과를 TLB에 저장(캐싱)합니다.

유효 접근 시간 (EAT) 계산

메모리 접근 시간을 $t$, TLB 검색 시간을 $\epsilon$ (보통 무시 가능), TLB 적중률을 $\alpha$라고 하면:

$EAT = \alpha \times (t + \epsilon) + (1 - \alpha) \times (2t + \epsilon)$

$\epsilon$을 무시하면:

$EAT = \alpha \times t + (1 - \alpha) \times 2t = t \times (2 - \alpha)$

TLB 크기는 보통 64~2048개 엔트리로 작지만, 적중률은 99% 이상을 달성합니다. 프로그램의 지역성(Locality) 덕분입니다.

시간적 지역성: 최근 접근한 주소를 곧 다시 접근합니다 (루프, 함수 재호출). 공간적 지역성: 접근한 주소 근처를 곧 접근합니다 (배열 순차 접근, 인접 코드).

4KB 페이지 × 1024개 TLB 엔트리 = 4MB의 주소 공간을 TLB가 커버합니다. 대부분의 워킹 셋이 이 범위 안에 들어갑니다. 대규모 페이지(2MB)를 사용하면 TLB 커버리지가 2GB로 확대됩니다.

컨텍스트 스위칭과 TLB

프로세스마다 페이지 테이블이 다릅니다. 컨텍스트 스위칭 시 TLB 처리 방법은 두 가지입니다.

TLB 플러시 (Flush)

가장 단순한 방법: 컨텍스트 스위칭 시 TLB 전체를 비웁니다. 새 프로세스의 첫 번째 메모리 접근부터 TLB 미스가 발생하여 페이지 테이블을 참조합니다. TLB가 워밍업 되기까지 성능이 떨어집니다.

이것이 컨텍스트 스위칭의 숨겨진 비용입니다. 레지스터 저장/복원은 수십 나노초이지만, TLB 워밍업에 수천~수만 나노초가 소요될 수 있습니다.

ASID (Address Space Identifier)

TLB 엔트리에 프로세스 ID(ASID)를 태그합니다. TLB에 여러 프로세스의 매핑이 동시에 존재해도, ASID로 구분하므로 충돌이 없습니다. 컨텍스트 스위칭 시 TLB를 비울 필요가 없어 성능이 크게 향상됩니다.

x86에서는 PCID(Process Context IDentifier)라는 이름으로 12비트(4096개 ID)를 지원합니다. ARM에서는 8비트(256개) ASID를 지원합니다.

class TLB:
    """간단한 TLB 시뮬레이터"""
    def __init__(self, size=64):
        self.size = size
        self.entries = {}  # {(asid, page): frame}
        self.access_order = []
        self.hits = 0
        self.misses = 0

    def lookup(self, asid, page_num):
        key = (asid, page_num)
        if key in self.entries:
            self.hits += 1
            self.access_order.remove(key)
            self.access_order.append(key)
            return self.entries[key]
        self.misses += 1
        return None

    def insert(self, asid, page_num, frame_num):
        key = (asid, page_num)
        if len(self.entries) >= self.size:
            # LRU 교체
            evict = self.access_order.pop(0)
            del self.entries[evict]
        self.entries[key] = frame_num
        self.access_order.append(key)

    def hit_ratio(self):
        total = self.hits + self.misses
        return self.hits / total if total > 0 else 0

# 시뮬레이션
tlb = TLB(size=4)
accesses = [(1,0), (1,1), (1,2), (1,0), (1,1), (2,0), (1,0)]
for asid, page in accesses:
    if tlb.lookup(asid, page) is None:
        tlb.insert(asid, page, page * 10)  # 가상 프레임
print(f"TLB 적중률: {tlb.hit_ratio():.1%}")

다단계 페이지 테이블

문제: 페이지 테이블 크기

32비트 시스템에서 4KB 페이지를 사용하면 페이지 테이블 엔트리가 $2^{20} \approx 100$만 개입니다. 엔트리당 4바이트라면 페이지 테이블 하나가 4MB를 차지합니다. 프로세스가 100개이면 페이지 테이블만으로 400MB가 필요합니다.

대부분의 프로세스는 주소 공간의 극히 일부만 사용합니다. Text 세그먼트(낮은 주소)와 Stack 세그먼트(높은 주소) 사이의 거대한 중간 영역은 비어 있습니다. 사용하지 않는 영역의 100만 개 엔트리까지 메모리에 올려두는 것은 낭비입니다.

해결: 계층적 분할

다단계 페이지 테이블(Multi-level Page Table)은 "페이지 테이블 자체를 페이지 단위로 나누고, 사용하는 부분만 메모리에 올리는" 아이디어입니다.

2단계 페이지 테이블 (32비트 x86):

1단계 테이블(Page Directory)은 1024개 엔트리로 항상 메모리에 있습니다(4KB). 각 엔트리가 2단계 테이블을 가리킵니다. 2단계 테이블은 사용되는 것만 메모리에 올립니다. 주소 공간의 1%만 사용하는 프로세스는 2단계 테이블 10여 개(약 40KB)만 존재합니다. 4MB 대비 100배 절약입니다.

64비트의 4단계 페이지 테이블

64비트 x86-64는 실제로 48비트 가상 주소를 사용하며, 4단계 페이지 테이블을 거칩니다.

4단계를 거치면 메모리 접근이 4번 추가로 필요합니다. TLB 히트가 99%라면 대부분의 경우 이 오버헤드를 피할 수 있지만, TLB 미스 시 페널티가 큽니다. 대규모 페이지(2MB)를 사용하면 3단계, 1GB 페이지는 2단계만 거치므로 미스 페널티가 줄어듭니다.

Linux 6.0+는 5단계 페이지 테이블(PML5)을 지원하여 57비트 가상 주소(128PB)를 사용할 수 있습니다.

역 페이지 테이블

일반 페이지 테이블은 논리 주소 → 물리 주소 방향입니다. 프로세스 수만큼 테이블이 존재합니다.

역 페이지 테이블(Inverted Page Table)은 반대입니다. 물리 프레임별로 어떤 프로세스의 어떤 페이지가 들어 있는지를 기록합니다. 시스템 전체에 테이블이 하나만 있습니다.

테이블 크기가 물리 메모리의 프레임 수에 비례하므로, 프로세스 수에 관계없이 일정합니다. 물리 메모리가 4GB이고 4KB 페이지이면, 엔트리 수는 $2^{20} \approx 100$만 개로 고정됩니다.

단점: 주소 변환 시 (프로세스 ID, 페이지 번호) 쌍으로 전체 테이블을 탐색해야 합니다. $O(N)$ 탐색은 느리므로, 해시 테이블과 함께 구현하여 $O(1)$ 룩업을 달성합니다.

IBM PowerPC, UltraSPARC 등이 역 페이지 테이블을 사용했습니다.

다음 절에서는 페이지가 물리 메모리에 없을 때 발생하는 페이지 폴트와 요구 페이징을 다루겠습니다.