TLB와 페이지 테이블 최적화

앞 글에서 가상 주소를 물리 주소로 바꾸려면 페이지 테이블을 읽어야 한다는 것을 보았습니다. 그런데 페이지 테이블도 메모리에 있습니다. 그러면 데이터 하나를 읽으려 할 때, 먼저 메모리에서 페이지 테이블 항목을 읽어 프레임 번호를 알아내고, 그다음 메모리에서 데이터를 읽어야 합니다. 페이지 테이블이 한 단계이고 다른 캐시가 없는 단순한 모델이라면 메모리 접근이 두 배로 늘어나는 셈입니다.

이 글에서는 이 비용을 줄이는 두 가지 방법을 다룹니다. 하나는 최근의 변환 결과를 CPU 안에 담아 두는 TLB이고, 다른 하나는 거대한 페이지 테이블을 여러 단계로 나누어 실제로 쓰는 부분만 메모리에 두는 다단계 페이지 테이블입니다.

TLB: 변환 결과를 담아 두는 캐시

TLB(translation lookaside buffer)는 최근에 쓴 페이지 번호와 프레임 번호의 짝을 담아 두는 CPU 안의 작은 하드웨어 캐시입니다. CPU는 가상 주소를 만들면 먼저 그 페이지 번호로 TLB를 찾아봅니다. 찾으면 TLB 적중(TLB hit)이라고 하며, 페이지 테이블을 읽지 않고 바로 프레임 번호를 얻어 물리 주소를 만듭니다. 찾지 못하면 TLB 실패(TLB miss)라고 하며, 메모리의 페이지 테이블을 따라가 프레임 번호를 얻은 뒤 다음을 위해 그 결과를 TLB에 넣습니다. 페이지 테이블을 따라가는 이 과정을 페이지 테이블 워크(page table walk)라고 하고, x86에서는 하드웨어가 직접 합니다.

단계 개념도는 TLB 실패가 곧 페이지 폴트는 아니라는 점을 보여 줍니다. TLB 실패는 변환 결과가 캐시에 없다는 뜻일 뿐이므로, 페이지 테이블을 따라가 그 페이지가 물리 메모리에 있고 접근이 허락된다는 것을 확인하면 변환을 마치고 데이터에 접근합니다. 디스크를 읽는 일도 없습니다. 페이지 테이블을 따라갔는데 페이지가 물리 메모리에 없거나 권한이 없을 때만 페이지 폴트가 일어나 커널이 개입하며, 이는 다음 글에서 다룹니다. 또 TLB 적중이라고 해서 할 일이 모두 끝나는 것은 아니어서, 데이터 자체에 접근하는 일과 권한 검사는 여전히 남습니다.

TLB는 보통 수십에서 수천 개의 항목을 담으며, 크기와 구조는 CPU마다 다릅니다. 그래도 적중률이 높은 것은 프로그램의 메모리 접근에 2장에서 본 지역성이 있기 때문입니다. 반복문은 같은 코드 페이지를 되풀이해 실행하고, 배열을 차례로 읽으면 한 페이지 안의 데이터를 수천 번 연달아 읽습니다.

유효 접근 시간 계산하기

TLB가 얼마나 도움이 되는지는 유효 접근 시간(effective access time, EAT)으로 계산할 수 있습니다. 메모리 접근에 $t$, TLB를 찾는 데 $\epsilon$의 시간이 걸리고, TLB 적중률이 $\alpha$라고 합시다. 페이지 테이블이 한 단계이고, 페이지 폴트가 없으며, TLB를 찾은 뒤 차례로 진행하는 모델이라면, 적중할 때는 $\epsilon + t$, 실패할 때는 페이지 테이블을 한 번 더 읽으므로 $\epsilon + 2t$가 걸립니다.

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

다음 코드는 메모리 접근이 100ns일 때 적중률에 따른 유효 접근 시간을 계산합니다. TLB를 찾는 시간을 무시한 값과 5ns로 잡은 값을 함께 보입니다.

def eat(hit_ratio, memory_ns=100, tlb_ns=0):
    hit = tlb_ns + memory_ns                 # TLB에서 변환을 찾고 데이터를 읽는다
    miss = tlb_ns + memory_ns + memory_ns    # 페이지 테이블을 한 번 더 읽는다
    return hit_ratio * hit + (1 - hit_ratio) * miss

for ratio in (1.0, 0.99, 0.9, 0.8, 0.0):
    print(f"적중률 {ratio:>4.0%}: {eat(ratio):5.1f}ns (TLB 조회 5ns를 더하면 {eat(ratio, tlb_ns=5):5.1f}ns)")

적중률 100%: 100.0ns (TLB 조회 5ns를 더하면 105.0ns)
적중률  99%: 101.0ns (TLB 조회 5ns를 더하면 106.0ns)
적중률  90%: 110.0ns (TLB 조회 5ns를 더하면 115.0ns)
적중률  80%: 120.0ns (TLB 조회 5ns를 더하면 125.0ns)
적중률   0%: 200.0ns (TLB 조회 5ns를 더하면 205.0ns)

TLB를 찾는 시간을 무시하면 식은 $t(2 - \alpha)$가 되어, 적중률이 99%일 때 평균 접근 시간이 101ns로 TLB가 없을 때의 200ns보다 거의 절반으로 줄어듭니다. 적중률이 90%로 떨어지면 110ns가 되어 메모리 접근이 평균 10% 느려집니다. 이 숫자들은 가정한 값으로 계산한 것이며, 실제 CPU의 적중률은 TLB의 크기, 페이지 크기, 작업의 접근 방식에 따라 다릅니다. 또 실제 CPU는 데이터 캐시와 여러 작업의 겹침이 있어 이 단순한 계산과 다르게 동작합니다.

TLB가 한꺼번에 덮을 수 있는 메모리의 양을 TLB 도달 범위(TLB reach)라고 합니다. 4KiB 페이지에 항목이 1,024개라면 도달 범위는 4MiB입니다. 프로그램이 짧은 시간에 접근하는 메모리가 이보다 넓으면 TLB 실패가 늘어납니다. 같은 항목 수로 2MiB 페이지를 담을 수 있다면 도달 범위는 2GiB로 늘어나므로, 앞 글에서 본 큰 페이지가 TLB 실패를 줄이는 데 쓰입니다. 실제 CPU는 큰 페이지용 TLB 항목을 따로 두는 경우가 많으므로, 정확한 수는 CPU마다 확인해야 합니다.

프로세스를 바꿀 때의 TLB

프로세스마다 페이지 테이블이 다르므로, TLB에 담긴 프로세스 A의 변환 결과는 프로세스 B에게는 틀린 정보입니다. 같은 가상 페이지 번호가 A와 B에서 서로 다른 프레임을 가리키기 때문입니다. 그래서 컨텍스트 스위칭을 할 때 TLB를 어떻게 다룰지 정해야 합니다.

가장 단순한 방법은 프로세스를 바꿀 때마다 TLB를 모두 비우는(flush) 것입니다. 그러면 새 프로세스는 첫 메모리 접근부터 TLB 실패를 겪으며 페이지 테이블을 따라가고, 자주 쓰는 변환이 다시 TLB에 채워질 때까지 느려집니다. 3장에서 본 컨텍스트 스위칭의 간접 비용 가운데 하나입니다.

다른 방법은 TLB 항목마다 어느 주소 공간의 것인지를 표시하는 주소 공간 식별자(address space identifier, ASID)를 붙이는 것입니다. TLB를 찾을 때 페이지 번호와 함께 지금 프로세스의 ASID도 맞아야 적중으로 보므로, 여러 프로세스의 항목이 TLB에 섞여 있어도 혼동되지 않습니다. 그래서 프로세스를 바꿀 때 TLB를 비우지 않아도 되고, 다시 돌아왔을 때 남아 있던 항목을 그대로 씁니다. x86에서는 같은 기능을 PCID(process-context identifier)라고 부르며 12비트, 곧 4,096개의 식별자를 쓸 수 있고, ARM은 구성에 따라 8비트나 16비트 ASID를 씁니다.

다음 코드는 항목 4개짜리 TLB를 (ASID, 페이지)를 키로 하는 LRU 캐시로 흉내 냅니다. 실패하면 가장 오래 쓰지 않은 항목을 빼고 새 항목을 넣습니다.

from collections import OrderedDict

class TLB:
    """(ASID, 페이지)를 키로 프레임을 담는 LRU 캐시 모델"""
    def __init__(self, size):
        self.size = size
        self.entries = OrderedDict()         # 앞쪽이 가장 오래 쓰지 않은 항목
        self.hits = self.misses = 0

    def access(self, asid, page):
        key = (asid, page)
        if key in self.entries:
            self.hits += 1
            self.entries.move_to_end(key)    # 방금 썼으므로 맨 뒤로
            return "hit"
        self.misses += 1
        evicted = None
        if len(self.entries) >= self.size:
            evicted, _ = self.entries.popitem(last=False)   # 가장 오래 쓰지 않은 것을 뺀다
        self.entries[key] = page * 10        # 페이지 테이블에서 찾았다고 가정한 프레임
        return f"miss, 퇴출 {evicted}" if evicted else "miss"

tlb = TLB(size=4)
for asid, page in [(1, 0), (1, 1), (1, 2), (1, 0), (1, 1), (2, 0), (1, 0), (2, 1), (1, 2)]:
    print(f"({asid}, {page}) {tlb.access(asid, page)}")
print(f"적중률 {tlb.hits}/{tlb.hits + tlb.misses} = {tlb.hits / (tlb.hits + tlb.misses):.1%}")
print("남은 항목(오래된 순):", list(tlb.entries))

(1, 0) miss
(1, 1) miss
(1, 2) miss
(1, 0) hit
(1, 1) hit
(2, 0) miss
(1, 0) hit
(2, 1) miss, 퇴출 (1, 2)
(1, 2) miss, 퇴출 (1, 1)
적중률 3/9 = 33.3%
남은 항목(오래된 순): [(2, 0), (1, 0), (2, 1), (1, 2)]

프로세스 1이 페이지 0, 1, 2를 처음 쓸 때는 모두 실패하고, 다시 쓰는 페이지 0과 1은 적중합니다. 프로세스 2의 페이지 0은 프로세스 1의 페이지 0과 페이지 번호가 같지만 ASID가 달라 다른 항목으로 취급되어 실패합니다. 프로세스 2로 바뀐 뒤에도 프로세스 1의 항목이 비워지지 않았으므로, 다시 프로세스 1의 페이지 0에 접근하면 적중합니다. TLB가 가득 찬 뒤로는 가장 오래 쓰지 않은 항목이 빠집니다. 키에서 ASID를 빼고 페이지 번호만 쓴다면 프로세스 1의 페이지 0과 프로세스 2의 페이지 0을 같은 항목으로 보아, 프로세스 2가 프로세스 1의 프레임에 접근하는 심각한 문제가 생깁니다.

ASID가 있어도 TLB를 비워야 할 때가 있습니다. 운영체제가 어떤 페이지의 매핑을 바꾸거나 권한을 줄이면, TLB에 남아 있는 옛 변환 결과는 더는 맞지 않습니다. 그래서 커널은 페이지 테이블을 고친 뒤 해당 항목을 TLB에서 지우는 무효화(invalidation)를 하며, 그 주소 공간을 쓰는 다른 CPU의 TLB도 지워야 하므로 다른 CPU에 인터럽트를 보내 지우게 합니다. 이를 TLB 슛다운(TLB shootdown)이라고 하며, 코어가 많은 시스템에서 무시할 수 없는 비용이 됩니다. 위의 모델은 이런 무효화를 흉내 내지 않습니다. 커널이 TLB를 다루는 방법은 Linux의 캐시와 TLB 문서에 정리되어 있습니다.

더 깊이: 커널에 들어갈 때마다 페이지 테이블을 바꾸는 PTI

Linux x86-64의 페이지 테이블 격리(page table isolation, PTI)는 Meltdown처럼 사용자와 커널이 한 주소 공간을 함께 쓴다는 점을 노리는 공격을 막는 대책입니다. PTI 문서에 따르면 커널은 사용자 프로그램을 실행할 때만 쓰는 페이지 테이블을 한 벌 더 두고, 그 테이블에는 커널에 들어가고 나오는 데 필요한 최소한의 커널 데이터만 매핑합니다. 그래서 인터럽트, 시스템 콜, 예외로 커널에 들어가고 나올 때마다 CR3에 써서 두 페이지 테이블을 바꾸어야 하며, CR3에 쓰는 일만으로도 백 클록 정도가 듭니다.

더 큰 비용은 TLB에서 생깁니다. PCID가 없는 CPU에서는 CR3에 쓸 때마다 TLB 전체가 비워지므로, 시스템 콜이나 인터럽트가 한 번 일어날 때마다 TLB를 처음부터 다시 채워야 합니다. PCID가 있으면 CR3에 쓸 때 특별한 비트를 세워 TLB 전체를 비우지 않고 페이지 테이블을 바꿀 수 있으므로, 커널 진입과 복귀, 컨텍스트 스위칭 때의 비용이 줄어듭니다. PTI는 CONFIG_MITIGATION_PAGE_TABLE_ISOLATION을 켜고 빌드한 커널에서 쓰이며, 부팅할 때 nopti나 pti= 커널 매개변수로 끌 수 있습니다.

다단계 페이지 테이블

한 단계 페이지 테이블은 너무 크다

32비트 주소와 4KiB 페이지를 쓰면 페이지가 $2^{20}$, 약 100만 개입니다. 항목 하나가 4바이트라면 한 단계 페이지 테이블은 4MiB를 차지하고, 프로세스마다 하나씩 있으므로 프로세스가 100개라면 페이지 테이블만으로 400MiB가 필요합니다. 64비트 주소라면 사정은 훨씬 나빠집니다.

그런데 대부분의 프로세스는 주소 공간의 아주 일부만 씁니다. 낮은 주소에 코드와 데이터가, 높은 주소에 스택이 있고, 그 사이의 거대한 영역은 비어 있습니다. 쓰지 않는 영역까지 항목을 모두 만들어 두는 것은 낭비입니다.

페이지 테이블도 페이지로 나눈다

다단계 페이지 테이블(multi-level page table)은 페이지 테이블 자체를 페이지 크기의 조각으로 나누고, 실제로 쓰는 조각만 만들어 둡니다. 32비트 x86의 기본 방식인 2단계 테이블에서는 가상 주소를 세 부분으로 나눕니다.

페이지 디렉터리는 항목이 1,024개로 4KiB이며, 각 항목이 2단계 테이블 하나를 가리킵니다. 2단계 테이블도 항목 1,024개로 4KiB이고, 각 항목이 데이터 프레임을 가리킵니다. 디렉터리 항목 하나가 맡는 가상 주소의 범위는 1,024 × 4KiB = 4MiB입니다. 어떤 4MiB 범위를 전혀 쓰지 않는다면, 그 범위를 맡는 디렉터리 항목은 비어 있다고 표시하고 2단계 테이블을 만들지 않습니다. 그래서 쓰는 영역이 디렉터리 항목 10개 아래에 모여 있다면, 페이지 테이블은 디렉터리 4KiB와 2단계 테이블 10개 40KiB, 모두 44KiB면 됩니다. 다만 같은 양의 메모리라도 넓게 흩어져 있으면 2단계 테이블이 훨씬 많이 필요합니다.

주소 하나를 따라가기

가상 주소 0x00403008을 2단계 테이블로 변환해 보겠습니다. 페이지 디렉터리는 물리 주소 0x00100000에서 시작하고, 디렉터리의 1번 항목은 0x00200000에서 시작하는 2단계 테이블을, 그 테이블의 3번 항목은 프레임 0x12A를 가리킨다고 합시다. 항목 하나는 4바이트이고, 두 항목 모두 유효하며 읽기가 허락된다고 가정합니다.

addr = 0x00403008
dir_index = (addr >> 22) & 0x3FF             # 상위 10비트
table_index = (addr >> 12) & 0x3FF           # 중간 10비트
offset = addr & 0xFFF                        # 하위 12비트
print(f"디렉터리 인덱스 {dir_index}, 테이블 인덱스 {table_index}, 오프셋 {offset}")

ENTRY = 4                                    # 항목 하나의 크기(바이트)
directory_base = 0x00100000
directory = {1: 0x00200000}                  # 디렉터리 항목 -> 하위 테이블의 시작 주소
tables = {0x00200000: {3: 0x12A}}            # 하위 테이블 -> {인덱스: 프레임 번호}

entry_addr = directory_base + dir_index * ENTRY
table_base = directory[dir_index]
print(f"1. 디렉터리 항목 {entry_addr:#010x} 읽기 -> 하위 테이블 {table_base:#010x}")
entry_addr = table_base + table_index * ENTRY
frame = tables[table_base][table_index]
print(f"2. 테이블 항목 {entry_addr:#010x} 읽기 -> 프레임 {frame:#x}")
print(f"3. 물리 주소 {frame * 4096 + offset:#010x}")

디렉터리 인덱스 1, 테이블 인덱스 3, 오프셋 8
1. 디렉터리 항목 0x00100004 읽기 -> 하위 테이블 0x00200000
2. 테이블 항목 0x0020000c 읽기 -> 프레임 0x12a
3. 물리 주소 0x0012a008

앞 글의 한 단계 테이블이었다면 페이지 번호 0x403(1,027)으로 바로 항목을 찾았을 것입니다. 2단계 테이블은 이 번호를 1 × 1,024 + 3으로 나누어, 상위 1로 디렉터리 항목을, 하위 3으로 2단계 테이블 항목을 찾습니다. 디렉터리 항목의 주소는 디렉터리 시작에 인덱스 × 항목 크기를 더한 0x00100004이고, 거기서 2단계 테이블의 시작 0x00200000을 얻습니다. 2단계 테이블 항목의 주소 0x0020000C에서 프레임 0x12A를 얻고, 그 프레임의 시작 0x0012A000에 오프셋 8을 더해 물리 주소 0x0012A008이 됩니다. 결과의 끝 008이 원래 주소의 오프셋 그대로라는 점을 확인해 보세요. 계산이 맞지 않는다면 인덱스에는 항목 크기 4를, 프레임 번호에는 페이지 크기 4,096을 곱했는지부터 확인합니다.

항목을 읽은 위치와 그 항목이 알려 주는 프레임의 위치는 다르다는 점도 구분해야 합니다. 0x0020000C는 2단계 테이블 항목이 있는 곳이고, 0x0012A000은 데이터가 있는 프레임의 시작입니다. 또 이 과정에서 항목을 두 번 읽는다고 실제로 DRAM에 두 번 접근하는 것은 아닙니다. 페이지 테이블 항목도 CPU의 데이터 캐시에 담길 수 있고, CPU에 따라서는 중간 단계의 항목을 따로 캐시하기도 합니다.

어떤 범위의 2단계 테이블이 없는데 그 범위에 접근하면, 변환을 끝까지 진행하지 못하고 페이지 폴트가 일어납니다. 이것이 곧 디스크를 읽는다는 뜻은 아니며, 커널이 그 주소가 프로세스가 쓸 수 있는 범위인지부터 확인합니다. 이 과정은 다음 글에서 다룹니다.

x86-64의 4단계 페이지 테이블

x86-64에서 48비트 가상 주소와 4KiB 페이지를 쓰면 페이지 테이블은 4단계입니다. 단계마다 9비트씩, 곧 항목 512개짜리 4KiB 테이블을 씁니다.

TLB 실패가 나면 하드웨어는 최대 네 단계의 항목을 차례로 읽어야 합니다. 단계가 깊을수록 TLB 실패의 대가가 커지므로, TLB의 적중률이 더욱 중요해집니다. 2MiB 큰 페이지는 PD 단계의 항목이 직접 프레임을 가리켜 세 단계만, 1GiB 큰 페이지는 PDPT 단계에서 끝나 두 단계만 거치므로 실패의 대가도 줄어듭니다. 더 넓은 주소가 필요한 시스템을 위해, 지원하는 CPU와 커널 설정에서는 5단계 페이지 테이블로 57비트 가상 주소, 곧 128PiB의 공간을 쓸 수 있습니다.

역 페이지 테이블

지금까지의 페이지 테이블은 가상 페이지에서 물리 프레임을 찾는 방향이었고, 프로세스마다 하나씩 있었습니다. 역 페이지 테이블(inverted page table)은 반대 방향으로, 물리 프레임마다 항목을 하나 두고 그 프레임에 어느 프로세스의 어느 가상 페이지가 들어 있는지 적어 둡니다. 시스템 전체에 테이블이 하나뿐이고, 크기가 프로세스 수가 아니라 물리 메모리의 프레임 수로 정해집니다. 물리 메모리가 4GiB이고 4KiB 페이지라면 항목은 $2^{20}$개로 고정됩니다.

대신 주소를 바꿀 때 (프로세스 ID, 가상 페이지 번호)를 가진 항목을 찾으려면 테이블 전체를 뒤져야 합니다. 그래서 실제로는 해시 테이블을 함께 써서 평균 탐색 비용을 줄이며, 해시 충돌을 처리하는 방법과, 공유 메모리처럼 한 프레임을 여러 가상 페이지가 가리키는 경우를 표현하는 방법이 따로 필요합니다. PowerPC 같은 일부 아키텍처가 해시 페이지 테이블을 쓰지만, 그 구조가 여기서 설명한 개념 모델과 똑같은 것은 아닙니다.

정리

• TLB는 최근의 페이지 번호와 프레임 번호의 짝을 담는 CPU 안의 캐시로, 적중하면 페이지 테이블을 읽지 않고 변환합니다. TLB 실패는 페이지 테이블을 따라가야 한다는 뜻일 뿐 페이지 폴트가 아닙니다.
• 유효 접근 시간은 적중률이 높을수록 메모리 접근 한 번의 시간에 가까워지며, 프로그램의 지역성 덕분에 적중률이 높게 유지됩니다.
• 프로세스를 바꿀 때 TLB를 비우는 대신 ASID나 PCID로 항목을 구분하면 다른 프로세스의 항목을 남겨 둘 수 있습니다. 매핑을 바꿀 때는 해당 항목의 무효화가 여전히 필요합니다.
• 다단계 페이지 테이블은 페이지 테이블도 페이지 크기로 나누어 쓰는 부분만 만들어 둡니다. 주소를 단계별 인덱스로 나누어 차례로 따라가며, 오프셋은 끝까지 그대로입니다.
• x86-64는 4단계 테이블을 쓰고 큰 페이지는 단계를 줄이며, 역 페이지 테이블은 물리 프레임마다 항목을 두어 테이블 크기를 고정합니다.

연습 문제

1. TLB 조회 시간이 있을 때

메모리 접근이 100ns, TLB 조회가 5ns, 적중률이 90%입니다. 본문의 모델로 적중할 때와 실패할 때의 시간, 유효 접근 시간을 구하세요. 같은 조건에서 유효 접근 시간이 110ns 이하가 되려면 적중률이 얼마 이상이어야 하나요?

2. TLB 모델을 이어서 실행하기

본문의 TLB 모델에서 마지막 상태로부터 (1, 0), (2, 0), (1, 1)을 차례로 더 조회하면 각각 적중인지 실패인지, 실패라면 어떤 항목이 빠지는지 구하세요. 처음부터 센 적중률은 얼마가 되나요?

3. 2단계 테이블로 다른 주소 변환하기

본문의 2단계 테이블 설정에서 디렉터리 1번 항목이 가리키는 2단계 테이블의 5번 항목이 프레임 0x0B7을 가리킨다고 합시다. 가상 주소 0x00405FFF를 변환해 디렉터리 인덱스, 테이블 인덱스, 오프셋, 두 항목을 읽는 주소, 물리 주소를 구하세요.

다음 글 요구 페이징과 페이지 폴트에서는 페이지가 물리 메모리에 없을 때 일어나는 페이지 폴트를 커널이 어떻게 처리하는지, 그리고 fork에서 쓰는 쓰기 시 복사가 어떻게 동작하는지 살펴봅니다.