페이지 테이블

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

상세

프로그램이 부르는 주소와 실제 메모리 주소를 이 표가 어떻게 짝짓는지가 이 절의 본론입니다. 예는 프로그램 하나와 주소 하나로 듭니다.

가상 주소와 물리 주소

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

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

표가 프로세스마다 한 벌씩이라서 이런 일이 됩니다. 같은 번호의 페이지가 각자의 표를 거쳐 서로 다른 프레임에 닿습니다.

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킬로바이트입니다. 이렇게 덩어리 단위로 메모리를 다루는 방식 전체가 페이징입니다.

표 한 줄의 생김새

표의 한 줄은 페이지 하나에 대응합니다. 이 한 줄이 페이지 테이블 엔트리입니다. 한 줄에는 프레임 번호 말고도 표시가 몇 개 더 들어갑니다.

맨 아래 표시는 메모리가 모자랄 때 쓰입니다. 어느 페이지를 내보낼지 고르는 축출 판단이 「요즘 안 읽힌 페이지」를 찾기 때문입니다.

이 줄들을 페이지 번호 순서로 늘어놓은 것이 표 전체의 모양입니다. 아래는 페이지 셋짜리 작은 표를 그린 것입니다. 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

페이지 번호는 차례대로 늘어서지만 프레임 번호는 아무 순서가 아닙니다. 페이지를 빈 프레임 아무 곳에나 놓기 때문입니다. 표의 줄 번호가 곧 페이지 번호라서 페이지 번호를 줄에 따로 적어 둘 필요가 없습니다.

주소의 두 토막

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

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

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

바뀌는 것은 위쪽 토막뿐입니다. 아래쪽 토막은 손대지 않고 그대로 물리 주소에 붙습니다. 페이지와 프레임의 크기가 같아서 덩어리 안에서의 거리가 양쪽에서 같기 때문입니다.

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

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

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

변환 한 번의 경로

주소를 바꾸는 일은 소프트웨어가 아니라 하드웨어가 합니다. 이 하드웨어가 MMU(Memory Management Unit, 메모리 관리 장치)입니다. 프로그램이 메모리를 읽거나 쓸 때마다 이 경로가 한 번씩 돕니다.

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

이 한 바퀴가 주소 변환입니다. 유효 비트가 안 서 있을 때 무슨 일이 일어나는지는 아래 「유효 비트가 안 선 줄」에 있습니다.

한 벌짜리 표의 크기

층을 두지 않고 한 벌로만 둔 표를 한 벌짜리 표라고 합니다. 이렇게 두면 크기가 문제가 됩니다.

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

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

이 표가 프로세스마다 하나씩입니다. 프로세스 백 개를 띄우면 표만 400메가바이트를 차지합니다.

주소가 64비트로 넓어지면 이 셈은 감당이 안 됩니다. 페이지 번호만 수십 비트라서 줄 수가 천문학적으로 늘어납니다. 게다가 한 프로그램이 실제로 쓰는 주소 공간은 그중 아주 좁은 구간뿐입니다. 안 쓰는 구간에도 줄을 하나씩 두는 셈입니다.

층으로 쌓은 표

그래서 표를 한 벌로 두지 않고 층으로 나눕니다. 위층 표의 한 줄은 프레임이 아니라 아래층 표를 가리킵니다. 맨 아래층 표에 가서야 프레임 번호가 나옵니다. 이렇게 쌓은 표가 다단계 페이지 테이블입니다.

페이지 번호도 층 수만큼 토막을 냅니다. 첫 토막으로 1층 표의 줄을 고릅니다. 다음 토막으로 2층 표의 줄을 고르는 식입니다.

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

층이 셋인 표에서 페이지 번호를 자르니 3 · 7 · 2 가 나왔다고 해 봅니다. 그러면 표를 이렇게 내려갑니다.

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번 줄이 층을 쌓는 이유를 보여 줍니다. 그 줄의 유효 비트를 안 세워 두면 그 아래 표는 아예 만들지 않습니다. 안 쓰는 구간이 위층에서 한 줄로 끝납니다. 프로그램이 실제로 쓰는 만큼만 표가 생기는 셈입니다.

대신 층을 내려가는 일이 늘어납니다. 층마다 표를 하나씩 읽어야 짝에 닿습니다. 이 내려가기가 페이지 테이블 워크입니다.

맨 위 표를 가리키는 레지스터

하드웨어는 맨 위 표가 물리 메모리 어디에 있는지를 알아야 내려가기를 시작할 수 있습니다. 그 물리 주소는 CPU(Central Processing Unit, 중앙 처리 장치) 안의 아주 작은 저장소 하나에 들어 있습니다. CPU 안의 이런 저장소를 레지스터라고 부릅니다.

운영체제는 프로세스를 바꿔 넣을 때 이 레지스터에 다음 프로세스의 표 주소를 적습니다. 주소 공간이 통째로 바뀌는 일이 레지스터 하나 쓰기로 끝납니다. 문맥 교환이 이 쓰기를 포함합니다.

이 레지스터를 무엇이라 부르는지는 CPU 종류마다 다릅니다. 널리 쓰이는 이름 하나가 CR3(Control Register 3, 제어 레지스터 3)입니다.

유효 비트가 안 선 줄

유효 비트가 안 선 줄을 만나면 하드웨어는 변환을 멈추고 운영체제를 부릅니다. 이 끼어듦이 페이지 폴트입니다. 권한 비트를 어긴 접근도 같은 길로 갑니다.

운영체제는 왜 짝이 없는지를 보고 셋 중 하나로 처리합니다. 앞의 두 갈래는 표를 고치고 멈춘 명령을 다시 실행하는 같은 꼬리로 합류합니다. 셋째 갈래만 거기서 끝납니다.

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

첫째, 아직 안 올린 페이지면 저장 장치에서 읽어 빈 프레임에 올립니다. 그리고 표를 고친 뒤 멈춰 있던 명령을 다시 실행시킵니다. 프로그램 쪽에서는 그 명령이 오래 걸렸다는 것 말고는 아무 일도 없습니다.

둘째, 메모리가 모자라 저장 장치로 내려보냈던 페이지면 다시 올립니다. 이 오르내림이 스와핑입니다.

셋째, 프로그램에 없는 주소를 부른 것이면 그 프로그램을 끝냅니다. 이때 개발자가 보는 것이 세그멘테이션 폴트입니다.

앞의 두 경우 덕에 주소 공간의 모든 페이지가 메모리에 있을 필요가 없어집니다. 건드리는 페이지만 그때그때 올리는 이 방식이 디맨드 페이징입니다.

변환 비용과 TLB

표가 메모리 안에 있다는 데서 비용이 나옵니다. 값 하나를 읽으려면 표를 먼저 읽어야 합니다. 그러고 나서 원하던 값을 읽습니다. 층이 셋이면 표 읽기 셋에 값 읽기 하나를 더해 메모리 읽기가 넷이 됩니다.

그래서 하드웨어는 최근 변환 결과를 담아 두는 작은 저장소를 하나 더 둡니다. 이것이 TLB(Translation Lookaside Buffer, 변환 색인 버퍼)입니다. 찾던 페이지의 짝이 거기 있으면 표를 아예 안 읽습니다.

여기서 운영체제의 책임이 하나 생깁니다. 표의 한 줄을 고치면 TLB 에 남은 옛 짝은 틀린 값이 됩니다. 고친 쪽이 그 항목을 지워 줘야 합니다. 이 일을 빼먹으면 프로그램이 엉뚱한 프레임을 읽습니다.

페이지 크기를 키우는 선택도 여기에 걸립니다. 페이지가 크면 같은 메모리를 더 적은 줄로 덮습니다. 그래서 표가 작아집니다.

TLB 칸 수는 정해져 있어서 한 칸이 덮는 범위도 같이 넓어집니다. 같은 칸 수로 더 넓은 메모리를 덮는 셈입니다. 대신 한 페이지 안에서 안 쓰는 부분이 늘어 메모리가 남습니다. 이렇게 키운 것이 거대 페이지입니다.

찾는 비용과 차지하는 공간

자료구조가 얼마나 걸리는지는 빅오 표기법으로 적습니다. O(1) 은 데이터가 늘어도 걸리는 시간이 그대로라는 뜻입니다.

페이지 테이블은 배열처럼 번호로 줄을 바로 찾습니다. 몇 번째 줄인지가 페이지 번호에서 계산되기 때문에 표를 훑지 않습니다.

층이 늘어도 O(1) 인 까닭은 층 수가 미리 정해진 값이기 때문입니다. 페이지가 몇 개든 내려가는 횟수는 같습니다. 그래도 읽기 횟수는 층 수만큼 늘어나므로 표기와 별개로 층 수는 비용입니다.

거꾸로 세운 표

지금까지 본 표는 페이지 번호로 줄을 찾습니다. 그래서 프로세스마다 한 벌씩 필요합니다.

거꾸로 프레임 하나에 줄 하나를 두는 방식도 있습니다. 줄 수가 물리 메모리의 프레임 수로 고정됩니다. 그래서 표 크기가 프로세스 수와 무관해집니다. 기계 전체에 한 벌이면 끝납니다.

대신 페이지 번호로 줄을 바로 못 찾습니다. 페이지 번호를 숫자 하나로 줄여 줄 번호를 계산하는 해시 방식으로 찾아 들어갑니다. 이 방식이 역 페이지 테이블입니다. 찾는 방법을 달리한 갈래로 해시 페이지 테이블이 있습니다.

flowchart TD
    PN["페이지 번호"] --> H["해시로 줄 번호를 계산한다"]
    subgraph T["기계에 한 벌뿐인 표"]
        R0["0번 줄 = 0번 프레임"]
        R1["1번 줄 = 1번 프레임"]
        R2["2번 줄 = 2번 프레임"]
    end
    H --> R1

이 표가 없는 기계

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

실시간 시스템에서는 하드웨어가 있어도 이 표에 기대는 것을 피합니다. 페이지 폴트 한 번이 정해진 응답 시간을 넘길 수 있어서입니다. 쓸 페이지를 처음에 다 올려 두고 내려가지 않게 묶는 방법을 씁니다.

관련 항목

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

페이지 테이블 엔트리 · 유효 비트 · 권한 비트 · 페이지 번호 · 오프셋 · 다단계 페이지 테이블

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

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

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

MMU · CPU · 커널 · 레지스터 · CR3 · 페이지 테이블 워크

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

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

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

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

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

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

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

역 페이지 테이블 · 해시 페이지 테이블 · 세그멘테이션 · 섀도 페이지 테이블 · 2단계 주소 변환

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

자료구조 · 메모리 관리 · 운영체제 · 프로세스