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%는 위 계산에 사용한 가정이며 보장된 실측값이 아닙니다.

TLB가 최근 매핑을 재사용할 수 있는 것은 프로그램의 지역성(Locality) 덕분입니다.

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

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

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

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

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

독립 확인: 위 직렬 조회 모델에서 t=100ns, TLB 조회 비용 ε=5ns, 적중률 α=0.9입니다. hit와 miss의 비용을 먼저 구한 뒤 EAT를 계산하세요. 같은 조건에서 EAT가 110ns 이하가 되려면 적중률이 얼마 이상이어야 하나요? 페이지 폴트는 없습니다.

컨텍스트 스위칭과 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%}")

원 접근 순서를 가장 오래 쓰지 않은 키부터 나열하면 miss (1,0) 뒤 [(1,0)], miss (1,1) 뒤 [(1,0),(1,1)], miss (1,2) 뒤 [(1,0),(1,1),(1,2)]입니다. 다음 hit (1,0)은 그 키를 끝으로 옮겨 [(1,1),(1,2),(1,0)], hit (1,1)은 [(1,2),(1,0),(1,1)]을 만듭니다. miss (2,0)을 추가한 뒤 마지막 hit (1,0)을 처리하면 [(1,2),(1,1),(2,0),(1,0)]입니다. hit 3회·miss 4회로 3/7≈42.9%이며, 서로 다른 키가 4개여서 원 접근에서는 아직 퇴출이 없습니다.

독립 확인: 위 원 실행의 마지막 상태에서 (2,1), (1,2)를 순서대로 더 조회하고, miss일 때만 원 insert를 호출합니다. 각 퇴출 키와 마지막 LRU 순서, 처음부터 센 적중률을 구하세요. lookup 키에서 ASID를 제거하면 (1,0)과 (2,0)의 구분을 유지할 수 있나요?

태그가 주소 공간을 구분하는 것과 매핑 변경 뒤 캐시를 최신 상태로 만드는 것은 별개입니다. 페이지 테이블의 프레임이나 권한을 바꾸더라도 원 Python 딕셔너리가 저절로 바뀌지는 않습니다. 실제 Linux의 TLB 무효화 인터페이스는 페이지 테이블 변경 뒤 남을 수 있는 오래된 변환을 제거하는 계약을 설명합니다. 이 모형은 그런 무효화·CPU 간 전달·실제 태그 관리를 구현하지 않습니다.

다단계 페이지 테이블

문제: 페이지 테이블 크기

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%여도 넓게 흩어져 있으면 훨씬 많은 하위 테이블이 필요합니다.

한 주소로 두 단계를 따라가기

주소를 두 번 나누는 이유를 숫자로 따라가 보겠습니다. 앞 절에서는 페이지 번호 하나로 테이블을 찾았습니다. 이번에는 같은 페이지 번호를 둘로 나누어, 먼저 하위 테이블을 고르고 그 안에서 데이터 프레임을 고릅니다. 페이지 안에서의 위치인 오프셋은 바뀌지 않습니다.

앞의 32비트·4KiB 페이지 모델에서 가상 주소 0x00403008을 변환합니다. 테이블 엔트리는 4바이트이며, 선택한 두 엔트리가 메모리에 존재하고 이번 읽기를 허용한다고 가정합니다. 대규모 페이지와 캐시 효과는 제외한 계산용 예시입니다. 실제 CPU의 MMU 동작을 관측한 결과는 아닙니다.

앞 절의 20비트 페이지 번호는 0x403, 즉 1027입니다. 이 번호를 1 × 1024 + 3으로 나누어 두 인덱스로 사용합니다. 반대로 1 × 2^22 + 3 × 2^12 + 8을 합하면 처음 가상 주소 0x00403008이 됩니다.

페이지 디렉터리의 물리 시작 주소를 0x00100000으로 두겠습니다. Directory[1]에는 하위 테이블의 물리 시작 주소 0x00200000이, 그 테이블의 Table[3]에는 데이터 프레임 번호 0x12A(10진수 298)가 들어 있다고 가정합니다. 여기서는 주소·프레임 번호와 제어 비트를 따로 설명하며, 엔트리 전체 값이 주소와 같다는 뜻은 아닙니다.

마지막 물리 주소가 0x0012A008인지 확인해 보세요. 끝의 008은 원래 주소의 오프셋입니다. 결과가 다르면 테이블 인덱스에는 엔트리 크기 4를, 프레임 번호에는 페이지 크기 4096을 곱했는지 먼저 확인합니다. 엔트리를 읽은 위치 0x0020000C와 그 엔트리가 알려 주는 데이터 프레임의 시작 0x0012A000은 서로 다릅니다. 두 엔트리를 참조한다고 실제 DRAM 접근이 항상 두 번 발생하는 것도 아닙니다.

디렉터리의 한 항목은 1024 × 4KiB = 4MiB 가상 범위를 담당합니다. Directory[1]의 범위는 0x00400000부터 0x007FFFFF까지입니다. 이 작은 예시에서 사용한 페이지가 모두 그 범위에 있다면 상위 테이블 4KiB와 하위 테이블 4KiB, 총 8KiB로 매핑을 표현할 수 있습니다. 이 값은 테이블의 공간만 센 것으로 데이터 프레임의 메모리까지 포함하지 않습니다.

나머지 디렉터리 항목 아래에는 사용하지 않는 하위 테이블을 만들지 않습니다. 페이지가 여러 4MiB 범위에 흩어져 있으면 하위 테이블도 더 필요합니다. 하위 테이블이 없는 범위에 접근하면 이 정상 변환 경로를 끝까지 진행할 수 없습니다. 그렇다고 바로 디스크를 읽는다는 뜻은 아닙니다. 다음 절의 페이지 폴트 처리에서 OS가 주소 매핑과 권한을 확인하는 과정을 살펴봅니다.

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, 페이지 번호) 쌍으로 전체 테이블을 탐색해야 합니다.

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

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

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