TLB와 페이지 테이블 최적화

페이지 테이블은 메모리에 저장됩니다.

그런데 메모리에 접근하려면 먼저 페이지 테이블을 조회해야 하고, 페이지 테이블 자체도 메모리에 있으니 메모리 접근이 한 번 더 필요합니다.

단일 단계 페이지 테이블과 캐시가 없는 단순 모델에서는 데이터 하나를 읽기 위해 두 번의 메모리 참조가 필요합니다. 실제 CPU의 다단계 테이블·캐시·병렬 처리까지 포함한 성능이 항상 절반이라는 뜻은 아닙니다.

이 문제를 해결하는 것이 TLB입니다.

TLB의 역할

TLB(Translation Lookaside Buffer)는 최근 사용된 페이지-프레임 매핑을 저장하는 고속 하드웨어 캐시입니다.

CPU 내부에서 페이지 번호와 주소 공간 태그를 빠르게 비교합니다. 완전 연관 또는 집합 연관 구조, 계층별 용량은 CPU마다 다릅니다.

동작 과정

1. CPU가 논리 주소를 생성합니다.
2. 페이지 번호와 필요한 주소 공간 태그로 TLB를 검색합니다.
3. TLB 히트(Hit): 프레임 번호를 즉시 얻어 물리 주소를 생성합니다. 주소 변환을 위한 페이지 테이블 walk를 피합니다. 실제 데이터 접근과 권한 검사는 남습니다.
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)$

이 표는 $\epsilon=0$인 계산입니다. 접근 시간 증가율을 처리량 감소율과 혼동하지 않습니다.

TLB 용량과 적중률은 CPU·페이지 크기·워크로드에 따라 다릅니다. 99%는 위 계산에 사용한 가정이며 보장된 실측값이 아닙니다.

프로그램의 지역성(Locality) 덕분입니다.

시간적 지역성: 최근 접근한 주소를 곧 다시 접근합니다 (루프, 함수 재호출).

공간적 지역성: 접근한 주소 근처를 곧 접근합니다 (배열 순차 접근, 인접 코드).

4KB 페이지 × 1024개 TLB 엔트리 = 4MB의 주소 공간을 TLB가 커버합니다.

워킹 셋이 이 도달 범위를 넘거나 매핑이 같은 집합에 집중되면 미스가 증가할 수 있습니다.

2MiB 페이지를 같은 1,024개 엔트리로 캐시할 수 있다고 가정하면 도달 범위는 2GiB입니다. 실제 대규모 페이지용 TLB 용량은 별도로 확인합니다.

컨텍스트 스위칭과 TLB

프로세스마다 페이지 테이블이 다릅니다.

컨텍스트 스위칭 시 TLB 처리 방법은 두 가지입니다.

TLB 플러시 (Flush)

가장 단순한 방법: 컨텍스트 스위칭 시 TLB 전체를 비웁니다.

새 프로세스의 첫 번째 메모리 접근부터 TLB 미스가 발생하여 페이지 테이블을 참조합니다.

TLB가 워밍업 되기까지 성능이 떨어집니다.

이것이 컨텍스트 스위칭의 숨겨진 비용입니다.

추가 비용은 캐시 상태와 다음 프로세스의 접근 패턴에 따라 달라지므로 고정 시간으로 비교할 수 없습니다.

ASID (Address Space Identifier)

TLB 엔트리에 주소 공간 식별자(ASID)를 태그합니다.

TLB에 여러 프로세스의 매핑이 동시에 존재해도, ASID로 구분하므로 충돌이 없습니다.

전환 때 기존 매핑을 보존할 수 있습니다. 주소 공간 태그를 재사용하거나 페이지 매핑·권한을 바꿀 때 필요한 무효화까지 없어지는 것은 아닙니다.

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

ARM은 아키텍처·구성에 따라 8비트 또는 16비트 ASID를 지원합니다.

아래는 양수 용량의 TLB에 miss인 키만 삽입하는 LRU 모형입니다. (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의 비 PAE, 4KiB 페이지 모델):

1단계 테이블(Page Directory)은 1024개 엔트리로 항상 메모리에 있습니다(4KB).

각 엔트리가 2단계 테이블을 가리킵니다.

2단계 테이블은 사용되는 것만 메모리에 올립니다.

사용 영역이 약 10개의 디렉토리 엔트리 아래에 모이면 하위 테이블 약 40KiB와 상위 테이블 4KiB로 표현할 수 있습니다. 사용 바이트가 1%여도 넓게 흩어져 있으면 훨씬 많은 하위 테이블이 필요합니다.

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

x86-64의 48비트 주소·4KiB 페이지 모드에서는 4단계 페이지 테이블을 거칩니다.

4단계 walk에는 최대 4개의 테이블 엔트리 참조가 필요합니다. 중간 엔트리와 데이터 캐시가 적중하면 이 모두가 DRAM 접근이 되는 것은 아닙니다.

TLB 히트가 99%라면 대부분의 경우 이 오버헤드를 피할 수 있지만, TLB 미스 시 페널티가 큽니다.

대규모 페이지(2MB)를 사용하면 3단계, 1GB 페이지는 2단계만 거치므로 미스 페널티가 줄어듭니다.

Linux는 지원 CPU와 커널 설정에서 5단계 페이지 테이블(PML5)을 사용할 수 있습니다. 57비트 주소 모드의 전체 가상 범위는 128PiB이며, 사용자 주소 공간은 이 전체와 구분해야 합니다.

역 페이지 테이블

일반 페이지 테이블은 논리 주소 → 물리 주소 방향입니다.

프로세스 수만큼 테이블이 존재합니다.

역 페이지 테이블(Inverted Page Table)은 반대입니다.

물리 프레임별로 어떤 프로세스의 어떤 페이지가 들어 있는지를 기록합니다.

시스템 전체에 테이블이 하나만 있습니다.

테이블 크기가 물리 메모리의 프레임 수에 비례하므로, 프로세스 수에 관계없이 일정합니다.

물리 메모리가 4GB이고 4KB 페이지이면, 엔트리 수는 $2^{20} \approx 100$만 개로 고정됩니다.

단점: 주소 변환 시 (프로세스 ID, 페이지 번호) 쌍으로 전체 테이블을 탐색해야 합니다.

선형 탐색 대신 해시 테이블 등을 결합해 평균 조회 비용을 줄일 수 있습니다. 해시 충돌 처리와 공유 페이지의 여러 가상 매핑은 추가 설계가 필요합니다.

실제 하드웨어의 해시 페이지 테이블과 여기서 설명한 물리 프레임당 한 항목인 개념 모델은 동일한 구조로 단정하지 않습니다.

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