페이지 테이블

페이지 테이블은 프로그램이 부르는 메모리 주소를 실제 메모리 칸의 주소로 바꿔 줍니다. 이 표가 대개 프로그램마다 하나씩이라서 프로그램 둘이 같은 번호를 불러도 서로 다른 메모리에 닿을 수 있습니다. 채우는 쪽은 운영체제입니다. 읽어서 주소를 바꾸는 쪽은 하드웨어입니다.

상세

이 절은 표가 무엇과 무엇을 짝짓는지, 누가 그 표를 쓰고 읽는지를 다룹니다. 예는 프로세스 둘로 듭니다.

가상 주소와 물리 주소

가상 주소는 프로그램이 명령 안에 적어 내는 주소입니다. 메모리 칩에 전달되는 주소는 물리 주소입니다. 이름은 둘 다 주소지만 서로 다른 번호 체계입니다.

프로그램을 띄운 것 하나가 프로세스입니다. 같은 프로그램을 두 번 띄우면 프로세스가 둘 생깁니다. 두 프로세스는 자기 데이터가 같은 가상 주소에 있다고 봅니다. 그 데이터가 놓인 물리 주소는 서로 다릅니다.

흔한 모양에서는 표가 프로세스마다 한 벌씩이라서 이런 일이 됩니다. 아래 그림의 페이지는 가상 주소 쪽을 같은 크기로 자른 덩어리입니다. 프레임은 물리 메모리 쪽 덩어리입니다. 같은 번호의 페이지가 각자의 표를 거쳐 서로 다른 프레임에 닿습니다.

flowchart TD
    subgraph A["프로세스 A"]
        PA["3번 페이지"] --> TA["A 의 표 · 3번 줄"]
    end
    subgraph B["프로세스 B"]
        PB["3번 페이지"] --> TB["B 의 표 · 3번 줄"]
    end
    TA --> F5["5번 프레임"]
    TB --> F12["12번 프레임"]

두 주소를 갈라 놓고 사이에서 번역해 주는 구조가 가상 메모리입니다. 페이지 테이블은 그 번역에 쓰이는 표입니다.

물리 주소를 직접 쓸 때의 문제

프로그램이 물리 주소를 직접 쓰면 셋이 곤란합니다. 이 셋이 이 표가 있는 이유입니다.

첫째, 프로그램끼리 서로를 건드립니다. 잘못 계산한 주소 하나가 옆 프로그램의 데이터를 덮어씁니다. 어느 프로그램이 어느 칸을 써도 되는지 가려 주는 메모리 보호 장치가 없습니다.

둘째, 프로그램을 어느 번지에 올릴지 미리 정해야 합니다. 그 번지가 비어 있지 않으면 그 프로그램은 못 뜹니다.

셋째, 빈 칸이 흩어져 있으면 합쳐서는 충분한 메모리도 못 씁니다. 프로그램은 이어진 구간을 요구합니다. 빈 구간이 잘게 쪼개져 있으면 그 요구를 못 맞춥니다.

block-beta
columns 6
  u1["쓰는 중"] e1["빈 칸"] u2["쓰는 중"] e2["빈 칸"] u3["쓰는 중"] e3["빈 칸"]

빈 칸 셋을 넓이로만 합치면 넉넉합니다. 이어져 있지 않아서 큰 구간 하나로는 못 씁니다. 빈 칸이 이렇게 쪼개져 흩어진 상태를 단편화라고 합니다.

페이지와 프레임

주소 하나하나를 짝지어 적으면 표가 메모리 칸 수만큼 커집니다. 그래서 짝은 덩어리 단위로만 짓습니다.

가상 주소 쪽을 같은 크기로 자른 덩어리가 페이지입니다. 물리 메모리를 같은 크기로 자른 덩어리는 페이지 프레임입니다. 줄여서 프레임이라고 합니다. 둘의 크기가 같아서 페이지 하나는 빈 프레임 아무 곳에나 놓을 수 있습니다. 널리 쓰이는 페이지 크기는 4킬로바이트입니다.

표는 페이지 번호를 줄 번호로 삼는 배열입니다. 5번 페이지의 짝은 5번 줄에 있습니다. 그래서 표를 처음부터 훑어 찾지 않습니다. 페이지 번호로 줄을 곧장 집습니다.

줄 하나에는 프레임 번호와 상태 표시 몇 개가 들어갑니다. 짝이 지어져 있는지를 알리는 유효 비트가 그중 하나입니다. 읽기·쓰기·실행이 되는지를 알리는 권한 비트도 그런 표시입니다.

유효 비트가 1이면 「섰다」고 말합니다. 0이면 「꺼졌다」고 합니다.

채우는 쪽과 읽는 쪽

표를 채우고 고치는 쪽은 운영체제입니다. 프로세스에 메모리를 내줄 때 빈 프레임을 고르고 그 번호를 줄에 적습니다.

표를 읽어 주소를 바꾸는 쪽은 하드웨어입니다. 이 하드웨어가 MMU(Memory Management Unit, 메모리 관리 장치)입니다.

프로그램이 메모리를 읽거나 쓸 때마다 가상 주소를 물리 주소로 바꾸는 일이 일어납니다. 그 일은 MMU 가 합니다. 운영체제는 끼어들지 않습니다.

표를 한 벌로 두면 너무 커집니다. 그래서 실제 기계는 대개 표를 여러 층으로 쌓습니다. 위층 줄이 아래층 표를 가리키는 모양입니다. 이렇게 층으로 쌓은 표가 다단계 페이지 테이블입니다.

MMU 는 맨 위 표가 물리 메모리 어디에 있는지 알아야 아래층으로 내려갈 수 있습니다. 그 주소는 CPU(Central Processing Unit, 중앙 처리 장치) 안의 작은 저장소 하나에 들어 있습니다. CPU 안의 이런 저장소가 레지스터입니다.

맨 위 표에서 아래층으로 줄을 따라 내려가며 짝을 찾습니다. 이 내려가기에 붙은 이름이 페이지 테이블 워크입니다. 아래에서도 「내려가기」라고 적습니다.

운영체제는 프로세스를 바꿔 넣을 때 이 레지스터에 다음 프로세스의 표 주소를 적습니다. 프로세스를 바꿔 넣는 이 일이 문맥 교환입니다.

이 쓰기 하나로 맨 위 표가 바뀝니다. 그 아래 층도 따라 바뀝니다. 다만 하드웨어가 곁에 적어 둔 옛 변환 결과는 따로 치워야 합니다.

변환 한 번의 경로

가상 주소는 두 토막으로 읽힙니다. 위쪽 토막이 페이지 번호입니다. 아래쪽 토막은 페이지 안에서 몇 바이트째인지를 가리키는 오프셋입니다. 오프셋은 바뀌지 않고 물리 주소에 붙습니다.

MMU 가 표를 읽어 주소를 바꿀 때 도는 경로입니다. 층이 하나인 표로 그렸습니다.

flowchart TD
    V["가상 주소 · 페이지 번호 + 오프셋"] --> T["표에서 그 번호의 줄을 읽는다"]
    T --> C{"유효 비트가 서 있나"}
    C -->|서 있다| F["프레임 번호를 얻는다"]
    C -->|안 서 있다| X["변환을 멈추고 운영체제를 부른다"]
    F --> R["물리 주소 · 프레임 번호 + 오프셋"]

주소 변환은 이 한 바퀴를 가리킵니다.

유효 비트가 꺼진 줄

유효 비트가 꺼진 줄을 만나면 하드웨어는 변환을 멈추고 운영체제를 부릅니다. 하드웨어가 이렇게 운영체제를 부르는 것을 페이지 폴트라고 합니다. 권한 비트를 어긴 접근도 같은 길로 갑니다.

flowchart TD
    X["변환을 멈추고 운영체제를 부른다"] --> Q{"왜 멈췄나"}
    Q -->|아직 안 올린 페이지| L["빈 프레임에 올린다"]
    Q -->|내려보냈던 페이지| L
    Q -->|프로그램에 없는 주소| K["프로그램을 끝낸다"]
    Q -->|권한 비트를 어긴 접근| K
    L --> U["표를 고친다"]
    U --> RE["멈춘 명령을 다시 실행한다"]

앞의 두 갈래는 표를 고치고 멈춘 명령을 다시 실행합니다. 저장 장치로 내려보냈던 페이지를 다시 올리는 오르내림이 스와핑입니다. 프로그램에 없는 주소였을 때 개발자가 보는 것이 세그멘테이션 폴트입니다.

앞의 두 갈래 덕에 모든 페이지가 처음부터 메모리에 있을 필요가 없습니다. 건드리는 페이지만 그때그때 올리는 방식이 디맨드 페이징입니다.

표를 안 쓰는 기계와 폴트를 피하는 기계

주소를 바꿔 주는 하드웨어가 아예 없는 기계도 있습니다. 작은 임베디드 기계가 그렇습니다. 그런 기계에서는 프로그램이 부르는 주소가 곧 물리 주소입니다. 페이지 테이블도 없습니다.

하드웨어가 있어도 페이지 폴트를 피해야 하는 쪽이 있습니다. 정해진 시간 안에 응답해야 하는 시스템이 그렇습니다. 폴트 한 번이 그 시간을 넘길 수 있어서입니다.

그래서 쓸 페이지를 미리 다 올려 두고 내려보내지 않게 묶습니다. 표는 쓰던 대로 씁니다. 피하는 것은 표가 아니라 폴트입니다.

복잡도

페이지 번호로 줄을 집는 표에서는 조회가 표의 층 수만큼 메모리 읽기로 끝납니다. 그 횟수는 프로세스가 쓰는 페이지가 늘어도 그대로입니다. 해시로 찾는 표는 같은 칸에 몰린 줄 수가 횟수를 정합니다. 표가 차지하는 공간은 표를 어떻게 세웠느냐에 따라 비례하는 대상이 바뀝니다.

비용은 메모리 읽기 횟수로 셉니다. 원하던 값을 읽는 한 번은 어느 경우나 따로 듭니다. 아래 표의 수는 그 한 번을 뺀 표 읽기만입니다.

최근 짝을 적어 두는 TLB

표가 메모리 안에 있으니 값 하나를 읽으려면 표를 먼저 읽어야 합니다. 그래서 하드웨어는 최근 변환 결과를 담아 두는 작은 저장소를 따로 둡니다. 이것이 TLB(Translation Lookaside Buffer, 변환 색인 버퍼)입니다.

찾던 페이지의 짝이 TLB 에 있으면 표를 아예 안 읽습니다. 이것이 최선입니다. 없으면 표를 처음부터 내려갑니다. 이것이 최악입니다. 평균은 TLB 에서 짝을 찾는 비율이 정합니다.

읽기 · 쓰기 · 공간

표를 세우는 방식은 넷입니다. 한 벌짜리 표는 층 없이 줄을 한 벌로 늘어놓습니다. 다단계 페이지 테이블은 위층 줄이 아래층 표를 가리키도록 층으로 쌓습니다. 아래에서 k 는 그 층 수입니다.

해시 페이지 테이블은 페이지 번호를 해시해 칸을 고릅니다. 역 페이지 테이블은 프레임마다 줄 하나를 두고 해시로 찾습니다.

표를 고친 뒤 TLB 에 남은 옛 짝은 틀린 값이 됩니다. 고친 쪽이 그 짝을 지워야 합니다. 빼먹으면 프로그램이 엉뚱한 프레임을 읽습니다.

해시 페이지 테이블은 칸 수를 미리 정해 두고 씁니다. 쓰려는 프레임 수에 맞춰 크기를 고릅니다.

한 벌짜리 표의 크기

주소가 32비트이고 페이지가 4킬로바이트인 기계를 놓고 셈합니다. 오프셋이 12비트를 가져가니 페이지 번호에 남는 것은 20비트입니다.

20비트로 나올 수 있는 값이 백만 가지 남짓이라 표도 백만 줄 남짓이 됩니다. 한 줄이 4바이트면 표 하나가 4메가바이트입니다. 이 표가 프로세스마다 하나씩이라 프로세스 백 개면 표만 400메가바이트입니다.

주소가 64비트로 넓어지면 줄 수가 감당할 수 없이 늘어납니다. 한 프로그램이 쓰는 주소 공간은 대개 그중 좁은 구간뿐입니다. 안 쓰는 구간에도 줄을 두는 셈이라 한 벌짜리 표는 듬성듬성해집니다. 다단계 페이지 테이블은 비어 있는 넓은 구간을 위층 줄 하나에 「없음」으로 적고 끝냅니다.

빅오 표기와 층 수

자료구조의 비용은 빅오 표기법으로 적습니다. O(1) 은 데이터가 늘어도 드는 비용이 그대로라는 뜻입니다.

다단계 페이지 테이블의 조회도 O(1) 입니다. 층 수가 기계마다 정해진 값이라 페이지가 몇 개든 내려가는 횟수가 같기 때문입니다. 그래도 표기와 따로 층 수는 비용입니다. 층 하나를 더하면 TLB 에 짝이 없을 때마다 메모리 읽기가 하나 늘어납니다.

해시 페이지 테이블과 역 페이지 테이블은 해시테이블과 같은 비용을 냅니다. 줄이 고르게 흩어지면 평균 O(1) 입니다. 한 칸에 몰리면 몰린 줄 수만큼 읽습니다.

큰 페이지로 줄이는 읽기

위층 줄이 아래층 표 대신 큰 물리 메모리 덩어리를 바로 가리킬 수 있습니다. 그러면 내려가기가 그 층에서 끝납니다. 이렇게 크게 잡은 페이지가 거대 페이지입니다.

flowchart TD
    subgraph UP["위층 표"]
        E1["줄 하나 · 아래층 표를 가리킨다"]
        E2["줄 하나 · 큰 덩어리를 바로 가리킨다"]
    end
    subgraph DN["아래층 표"]
        E3["줄 하나 · 프레임을 가리킨다"]
    end
    subgraph MEM["물리 메모리"]
        SM["4킬로바이트 프레임"]
        BG["이어진 큰 덩어리 · 거대 페이지"]
    end
    E1 --> E3 --> SM
    E2 --> BG

거대 페이지는 읽기를 두 쪽에서 줄입니다. 내려가는 층이 줄어듭니다. TLB 한 칸이 덮는 범위도 넓어집니다. 대가는 한 페이지 안에서 안 쓰는 부분이 늘어 메모리가 남는다는 것입니다.

주소 공간을 넓히는 쪽은 반대로 갑니다. 주소를 넓히면 페이지 번호 비트가 늘어 한 층이 받는 비트로는 모자랍니다. 그래서 층을 하나 더 둡니다.

층이 하나 늘면 표가 차지하는 메모리와 내려가는 시간이 같이 늘어납니다. 그래서 같은 기계가 층 수가 다른 방식을 여럿 두고 고르게 하기도 합니다.

예시

실물 셋입니다. 하드웨어 둘과 그 위의 운영체제 커널 하나입니다. 주소를 페이지 단위로 짝지어 바꾸는 방식을 페이징이라고 합니다. 아래 셋은 그 방식을 몇 층 표로 돌리는지가 다릅니다.

하드웨어 하나는 RISC-V 입니다. RISC(Reduced Instruction Set Computer, 축소 명령어 집합 컴퓨터) 계열의 명령어 집합입니다. 같은 모양이 기계마다 이름만 달리 박혀 있습니다.

메비바이트는 2의 20제곱 바이트입니다. 기비바이트는 2의 30제곱 바이트입니다. 메가바이트·기가바이트와 가까운 크기를 가리키는 다른 단위입니다.

x86-64 4단계 페이징

x86-64 에서 프로그램이 내는 쪽 주소의 이름은 선형 주소(linear address)입니다. 앞 절들이 가상 주소라고 부른 것이 여기서는 이 이름입니다. 4단계 페이징은 48비트 선형 주소를 52비트 물리 주소로 바꿉니다. 한꺼번에 닿을 수 있는 선형 주소 공간은 최대 256테라바이트입니다.

맨 위 표는 PML4 표(Page Map Level 4)입니다. 그 물리 주소를 CR3 의 51~12번 비트가 듭니다. 표는 어느 층이든 4096바이트입니다. 8바이트 줄 512개로 이루어집니다.

512는 2의 9제곱이라 한 층이 주소 9비트를 씁니다. 네 층의 이름은 위에서부터 PML4 표 · 페이지 디렉터리 포인터 표 · 페이지 디렉터리 · 페이지 테이블입니다. 맨 아래 층 이름이 이 표제어와 겹칩니다. x86-64 에서 「페이지 테이블」이라고 하면 네 층 가운데 맨 아래 한 층을 뜻합니다.

packet-beta
0-11: "오프셋 12"
12-20: "페이지 테이블 9"
21-29: "페이지 디렉터리 9"
30-38: "디렉터리 포인터 9"
39-47: "PML4 9"

위쪽 9비트부터 한 토막씩 써서 층을 내려갑니다. 47~39번 비트가 PML4 표의 줄을 고릅니다. 그 줄 하나는 512기가바이트 범위를 맡습니다. 마지막 페이지 테이블 줄이 4킬로바이트 페이지 하나의 프레임을 줍니다.

flowchart TD
    C["CR3 · PML4 표의 물리 주소"] --> L4["PML4 표 · 47~39번 비트 · 줄 하나가 512기가바이트"]
    L4 --> L3["페이지 디렉터리 포인터 표 · 38~30번 비트 · 줄 하나가 1기가바이트"]
    L3 --> L2["페이지 디렉터리 · 29~21번 비트 · 줄 하나가 2메가바이트"]
    L2 --> L1["페이지 테이블 · 20~12번 비트 · 줄 하나가 4킬로바이트"]
    L1 --> P["4킬로바이트 페이지 · 11~0번 비트가 오프셋"]

물리 주소의 51~12번 비트는 마지막 줄에서 옵니다. 11~0번 비트는 선형 주소에서 바뀌지 않고 옵니다. 중간 층 줄이 큰 페이지를 바로 가리키면 2메가바이트나 1기가바이트 페이지가 됩니다. 5단계 페이징은 57비트 주소의 56~48번 비트로 층을 하나 더 씁니다.

4킬로바이트 페이지를 가리키는 줄의 주요 비트는 이렇습니다.

A 비트와 D 비트는 프로세서가 켭니다. 변환에 줄을 쓸 때마다 그 줄의 A 를 켭니다. 쓰기가 있으면 마지막 줄의 D 를 켭니다.

한번 켠 비트를 프로세서가 끄지는 않습니다. 끄는 것은 소프트웨어만 합니다. 메모리 관리 소프트웨어가 페이지를 메모리에 올리고 내릴 때 이 두 비트를 씁니다.

리눅스 커널의 다섯 층

리눅스 커널은 페이지 테이블을 현재 다섯 층으로 정의합니다. 위에서부터 PGD · P4D(Page Level 4 Directory) · PUD(Page Upper Directory) · PMD(Page Middle Directory) · PTE(Page Table Entry) 입니다. 각 아키텍처의 코드가 이 다섯 층을 그 하드웨어의 제약에 맞춥니다.

맨 아래 이름 하나가 헷갈립니다. PTE 는 Page Table Entry 의 줄임이지만 리눅스에서는 줄 하나가 아니라 맨 아래 층의 표를 가리킵니다. 리눅스 1.0 때는 한 벌짜리 표의 줄 하나를 가리켰습니다. 2단계 표가 들어오면서 줄들의 배열로 뜻이 바뀌었습니다.

아키텍처가 층을 다 안 쓰면 남는 층을 접습니다(folding). 접힌 층은 컴파일할 때 건너뛰도록 바뀝니다. P4D 는 하드웨어가 다섯 층을 쓰는 기계에서만 쓰입니다. 나머지 기계에서는 접힙니다.

flowchart TD
    subgraph FIVE["다섯 층 기계"]
        G1["PGD"] --> D1["P4D"] --> U1["PUD"] --> M1["PMD"] --> T1["PTE · 맨 아래 층의 표"]
    end
    subgraph FOUR["네 층 기계"]
        G2["PGD"] --> U2["PUD"] --> M2["PMD"] --> T2["PTE · 맨 아래 층의 표"]
        D2["P4D · 접혀서 건너뛴다"]
    end

층마다 아래층을 가리키는 포인터의 배열입니다. 층마다 포인터가 몇 개인지는 아키텍처가 정합니다.

사용자 공간 프로세스는 저마다 자기 PGD 를 갖습니다. 그 포인터는 프로세스의 메모리 문맥인 struct mm_struct 안에 있습니다. 커널 자신의 맨 위 표는 swapper_pg_dir 입니다.

거대 페이지는 PMD 나 PUD 의 줄이 바로 가리킵니다. 그러면 PTE 까지 안 내려가고 내려가기가 중간 층에서 끝납니다. 거대 페이지는 대개 2메가바이트에서 1기가바이트에 걸칩니다.

RISC-V Sv39

RISC-V 는 가상 주소 폭이 다른 방식을 여럿 둡니다. Sv39 는 39비트 가상 주소 공간을 4킬로바이트 페이지로 나눕니다. 많은 시스템에는 39비트면 넉넉하다고 보고 둔 방식입니다. 48비트인 Sv48 은 표가 차지하는 메모리와 내려가는 시간을 늘리는 대가로 주소 공간을 넓힙니다.

27비트 가상 페이지 번호(VPN, Virtual Page Number)를 세 층 표로 44비트 물리 페이지 번호(PPN, Physical Page Number)로 바꿉니다. 12비트 오프셋은 바뀌지 않습니다. VPN 은 층마다 9비트씩 세 토막으로 갈리고 아래 그림의 각괄호 안 숫자가 그 토막 번호입니다.

packet-beta
0-11: "오프셋 12"
12-20: "VPN[0] 9"
21-29: "VPN[1] 9"
30-38: "VPN[2] 9"
39-63: "38번 비트와 같아야 한다 25"

64비트 주소의 63~39번 비트는 38번 비트와 같아야 합니다. 다르면 페이지 폴트 예외가 납니다.

맨 위 표의 물리 페이지 번호는 satp 레지스터가 듭니다. 같은 레지스터에 ASID(Address Space Identifier) 칸과 변환 방식을 고르는 MODE 칸도 있습니다.

ASID 는 주소 공간마다 하나씩 붙는 번호입니다. 이 번호가 있어서 적어 둔 변환을 치우는 일을 주소 공간 단위로 할 수 있습니다.

packet-beta
0-43: "PPN 44 · 맨 위 표"
44-59: "ASID 16"
60-63: "MODE 4"

표 주소와 ASID 를 한 레지스터에 둔 까닭은 문맥 교환 때 둘을 한 번에 바꾸려는 것입니다. 따로 바꾸면 옛 주소 공간에 새 변환이 섞일 수 있습니다.

표는 8바이트 줄 2의 9제곱 개라 크기가 페이지 하나와 같습니다. 줄의 아래 비트는 이렇습니다.

어느 층의 줄이든 리프 줄이 될 수 있습니다. 그래서 4킬로바이트 페이지 말고도 2메비바이트 메가페이지와 1기비바이트 기가페이지를 씁니다.

A 와 D 를 다루는 방식은 둘입니다. Svade 확장이 있으면 그 비트가 꺼진 채 접근할 때 페이지 폴트 예외가 납니다. 없으면 하드웨어가 줄을 고쳐 비트를 켭니다.

형태

이 절은 페이지 테이블의 생김새를 세 겹으로 다룹니다. 줄 하나의 칸, 주소가 갈리는 비트 자리, 줄이 늘어선 표 전체입니다. 아키텍처마다의 비트 이름은 「예시」 절이 받습니다.

표 한 줄의 생김새

줄 하나는 프레임 번호와 상태 비트 몇 개로 이루어집니다. 이 한 줄이 페이지 테이블 엔트리입니다.

위 세 칸은 운영체제가 적고 하드웨어가 지킵니다. 아래 두 칸은 방향이 거꾸로입니다. 하드웨어가 켜 두면 운영체제가 읽고 끕니다.

운영체제는 아래 두 칸으로 메모리가 모자랄 때를 대비합니다. 접근 비트가 꺼진 페이지는 요즘 안 쓰인 것이라 내보낼 후보가 됩니다. 내보낼 페이지를 고르는 일을 축출이라고 합니다. 저장 장치에 사본이 있는 페이지라면 수정 비트가 꺼져 있을 때 사본과 내용이 같습니다. 그래서 다시 쓸 필요 없이 버릴 수 있습니다.

주소의 두 토막

페이지 크기가 정해져 있으니 가상 주소는 두 토막으로 읽힙니다. 위쪽 토막은 페이지 번호입니다. 아래쪽 토막은 그 페이지 안에서 몇 바이트째인지를 가리키는 오프셋입니다.

오프셋이 몇 비트인지는 페이지 크기가 정합니다. 페이지가 4킬로바이트면 그 안의 한 바이트를 가리키는 데 12비트가 듭니다. 주소가 32비트라면 비트 자리가 이렇게 갈립니다.

packet-beta
0-11: "오프셋"
12-31: "페이지 번호"

바뀌는 것은 위쪽 토막뿐입니다. 페이지와 프레임의 크기가 같아서 덩어리 안에서의 거리가 양쪽에서 같기 때문입니다.

주소를 16진수로 적으면 토막이 눈에 보입니다. 16진수 한 글자가 4비트라서 오프셋 12비트는 뒤의 세 글자입니다.

가상 주소     0x00003ABC
페이지 번호    0x00003   // 표에서 찾을 줄
오프셋        0xABC     // 손대지 않는다
프레임 번호    0x00081   // 표가 알려 준 값
물리 주소     0x00081ABC

앞 세 줄이 프로그램이 낸 주소를 가른 것입니다. 뒤 두 줄은 표를 한 번 읽고 나온 결과입니다.

줄이 늘어선 배열

줄들은 페이지 번호 순서로 빈틈없이 늘어섭니다. 아래는 페이지 셋짜리 작은 표입니다. 1번 페이지는 아직 짝이 없어 유효 비트가 꺼져 있습니다.

flowchart TD
    subgraph P["프로세스의 페이지"]
        P0["0번 페이지"]
        P1["1번 페이지"]
        P2["2번 페이지"]
    end
    subgraph T["페이지 테이블"]
        T0["0번 줄 · 프레임 8"]
        T1["1번 줄 · 유효 비트 꺼짐"]
        T2["2번 줄 · 프레임 3"]
    end
    subgraph M["물리 메모리"]
        F3["3번 프레임"]
        F8["8번 프레임"]
    end
    P0 --> T0 --> F8
    P1 --> T1
    P2 --> T2 --> F3

페이지 번호는 차례대로 늘어서지만 프레임 번호는 아무 순서가 아닙니다. 페이지를 빈 프레임 아무 곳에나 놓기 때문입니다.

줄에는 페이지 번호가 적혀 있지 않습니다. 줄이 놓인 순서가 곧 페이지 번호입니다. 그래서 n번 줄의 주소는 「표의 시작 주소 + n × 줄 크기」로 바로 나옵니다. 조회가 훑기 없이 한 번에 끝나는 까닭이 이 배치입니다.

갈래

갈래를 가르는 축은 둘입니다. 페이지 번호에서 줄을 어떻게 찾느냐, 그리고 그 대가로 표 크기가 무엇에 비례하느냐입니다. 앞의 둘은 페이지 번호를 줄 번호로 씁니다. 뒤의 둘은 해시로 찾습니다.

한 벌짜리 표

가장 단순한 모양입니다. 층을 두지 않고 줄을 한 벌로만 늘어놓습니다. 줄을 찾는 데 표 읽기 한 번이면 됩니다. 덮으려는 주소 범위가 넓어질수록 줄 수가 그만큼 늘어납니다.

안 쓰는 구간에도 줄이 있어 대개 듬성듬성합니다. 가상 주소 공간 전체를 한 벌로 덮으려 들면 줄 수가 감당할 수 없이 늘어납니다. 그래서 실제 기계는 그렇게 두지 않습니다.

리눅스가 처음 나왔을 때 표가 이 모양 하나였습니다. 4킬로바이트 페이지에 줄 1024개짜리 표 하나(swapper_pg_dir)로 4메가바이트를 덮었습니다. 그때 리누스 토르발스의 첫 컴퓨터에 꽂힌 물리 메모리도 4메가바이트였습니다.

다단계 페이지 테이블

페이지 번호를 다시 토막 냅니다. 첫 토막으로 1층 표의 줄을 고릅니다. 그 줄이 가리키는 2층 표에서 다음 토막으로 줄을 고릅니다. 맨 아래층 줄에 가서야 프레임 번호가 나옵니다.

층이 셋인 표에서 페이지 번호를 자르니 3 · 7 · 2 가 나왔다고 해 봅니다.

block-beta
columns 4
  s1["1층 색인 · 3"] s2["2층 색인 · 7"] s3["3층 색인 · 2"] off["오프셋"]

flowchart TD
    subgraph L0["1층 표"]
        A0["3번 줄"]
        A1["9번 줄 · 유효 비트 꺼짐"]
    end
    subgraph L1["2층 표"]
        B0["7번 줄"]
    end
    subgraph L2["3층 표"]
        C0["2번 줄 · 프레임 번호"]
    end
    A0 --> B0 --> C0

9번 줄이 층을 쌓는 이유입니다. 그 줄의 유효 비트를 꺼 두면 그 아래 표는 아예 만들지 않습니다. 넓은 빈 구간이 위층 한 줄로 끝나서 쓰는 만큼만 표가 생깁니다.

대가는 층마다 표를 하나씩 읽는 내려가기입니다. x86-64 의 4·5단계 페이징, RISC-V 의 Sv39, 리눅스 커널의 다섯 층이 이 모양입니다.

해시 페이지 테이블

페이지 번호를 해시 함수에 넣어 표의 칸을 고릅니다. 같은 칸에 몰린 줄은 사슬로 잇거나 정해진 묶음 안의 빈 줄에 받습니다. 이렇게 몰리는 것이 해시 충돌입니다. 주소 공간이 아주 넓고 듬성듬성해도 층을 여럿 내려가지 않습니다.

줄 번호가 페이지 번호가 아닙니다. 그래서 줄마다 「어느 가상 페이지의 짝인지」를 적어 둡니다. 찾을 때 그 값을 대 봅니다.

Power ISA(Instruction Set Architecture, 명령어 집합 구조)의 해시 페이지 테이블(HTAB, Hashed Page Table)이 묶음 방식입니다. 16바이트 줄 8개를 PTEG(Page Table Entry Group, 페이지 테이블 엔트리 묶음)라는 128바이트 묶음으로 둡니다. 1차 해시로 고른 묶음의 줄 8개를 대 봅니다. 2차 해시를 켠 기계라면 2차 해시로 고른 묶음의 줄 8개까지 더해 최대 16개를 대 봅니다.

flowchart TD
    V["가상 페이지 번호"] --> H1["1차 해시"]
    V --> H2["2차 해시 · 켠 기계에서만"]
    subgraph HT["해시 페이지 테이블"]
        G1["1차 묶음 · 줄 8개"]
        G2["2차 묶음 · 줄 8개"]
    end
    H1 --> G1
    H2 --> G2

맞는 줄이 없으면 페이지 폴트입니다. 이 표의 크기는 2의 n제곱 바이트(18 ≤ n ≤ 46)에서 고릅니다. 큰 페이지를 안 쓰면 묶음 수를 쓰려는 프레임 수의 절반 이상으로 두기를 권합니다.

표가 작으면 프레임을 받은 페이지 가운데 일부를 표에 못 담을 수 있습니다. 2차 해시를 켠 기계에서 한 쌍의 묶음에 16개 넘게 몰릴 때 그런 일이 납니다. 표를 키우면 그런 충돌이 덜 나지만 어떤 크기에서도 안 난다고 보장하지는 못합니다.

역 페이지 테이블

줄 번호를 가상 페이지가 아니라 물리 프레임으로 삼습니다. 프레임마다 줄이 하나입니다. 줄에는 「어느 프로세스의 어느 페이지가 여기 있나」를 적습니다.

기계 전체에 표가 한 벌입니다. 그래서 크기는 물리 메모리에 묶입니다. 프로세스 수와는 무관합니다. 대신 가상 주소에서 프레임을 찾을 때 색인이 안 되어 해시를 붙여야 합니다.

flowchart TD
    V["가상 주소"] --> H["해시"]
    H --> A["해시 앵커 표 · 한 줄"]
    subgraph IPT["역 페이지 테이블 · 프레임마다 한 줄"]
        R1["5번 줄 · 다른 가상 주소"]
        R2["12번 줄 · 찾던 가상 주소"]
    end
    A --> R1 --> R2
    R2 --> F["줄 번호 12 = 12번 프레임"]

IBM(International Business Machines)이 1983년에 특허를 출원한 주소 변환 장치가 이 모양입니다. 해시 앵커 표(HAT, Hash Anchor Table)와 역 페이지 테이블(IPT, Inverted Page Table) 둘로 이루어집니다. 그 특허가 든 구현은 물리 메모리의 프레임마다 HAT 줄 하나와 IPT 줄 하나를 둡니다.

IPT 줄에는 그 프레임을 쓰는 가상 쪽 주소가 세그먼트 번호와 가상 페이지 번호로 적혀 있습니다. 가상 주소를 해시해 HAT 줄을 고르면 그 줄이 IPT 줄 사슬의 첫 줄을 가리킵니다. 사슬을 따라가며 가상 주소를 대 봅니다. 맞는 IPT 줄의 번호가 곧 프레임 번호입니다.

사슬 끝은 줄 안의 표시 비트가 알립니다. 끝까지 못 찾으면 그 주소에는 짝이 없습니다.

관련 항목

페이지 테이블을 이루는 구성 요소

페이지 테이블 엔트리 · 유효 비트 · 권한 비트 · 접근 비트 · 수정 비트 · 페이지 번호 · 오프셋 · 프레임 번호

페이지 테이블이 짝지어 주는 두 주소

가상 주소 · 물리 주소 · 선형 주소 · 페이지 · 페이지 프레임 · 주소 공간 · 페이지 크기

페이지 테이블을 읽고 고치는 주체

MMU · CPU · 운영체제 · 커널 · 레지스터 · CR3 · satp · 페이지 테이블 워크

표를 다시 읽는 횟수를 줄이는 장치

TLB · TLB 미스 · TLB 플러시 · ASID · CPU 캐시 · 거대 페이지

페이지 테이블을 고치게 만드는 사건

페이지 폴트 · 세그멘테이션 폴트 · 스와핑 · 축출 · 스레싱 · 복사 후 쓰기

페이지 테이블이 떠받치는 운영체제 기능

가상 메모리 · 페이징 · 메모리 보호 · 프로세스 격리 · 메모리 매핑 · 디맨드 페이징 · 문맥 교환

페이지 테이블의 하위 종류

다단계 페이지 테이블 · 해시 페이지 테이블 · 역 페이지 테이블 · 해시 앵커 테이블 · PTEG

같은 일을 다른 모양으로 하는 방식

세그멘테이션 · 섀도 페이지 테이블 · 2단계 주소 변환 · 기수 트리

페이지 테이블을 채택한 아키텍처와 커널

x86-64 · x86 · RISC-V · Sv39 · Power ISA · 리눅스 커널 · 5단계 페이징

페이지 테이블이 기대는 자료구조

배열 · 해시테이블 · 해시 함수 · 해시 충돌 · 빅오 표기법

페이지 테이블이 속하는 상위 분류

자료구조 · 메모리 관리 · 메모리 · 프로세스

페이지 단위 배치와 얽힌 단편화

단편화 · 외부 단편화 · 내부 단편화