Компактные таблицы страниц (многоуровневые)

Откуда вообще берётся проблема

В прошлой главе про страничную организацию мы научились бить память на одинаковые кусочки — страницы (page) у процесса и кадры (frame, PFN — physical frame number) в физической RAM. Чтобы знать, в каком кадре лежит каждая страница, мы завели таблицу страниц (page table) — массив, где по номеру страницы (VPN — virtual page number) лежит запись (PTE — page table entry) с номером кадра и битами доступа.

У такой линейной (плоской) таблицы есть серьёзный недостаток: она занимает много места, и почти всё это место тратится впустую.

Посчитаем для классического случая: 32-битное адресное пространство и страница 4 КБ.

32-битный виртуальный адрес, страница 4 КБ = 2^12 байт
 ┌───────────────── VPN (20 бит) ─────────────┬─ offset 12 бит ─┐
 │ номер страницы                              │ смещение внутри │
 └─────────────────────────────────────────────┴─────────────────┘
 
  offset = 12 бит  → 2^12 = 4096 байт в странице
  VPN    = 20 бит  → 2^20 = 1 048 576 страниц всего
 
  Каждая PTE = 4 байта.
  Размер плоской таблицы = 2^20 * 4 байта = 4 МБ

4 МБ на один процесс. А процессов в системе — сотни. 100 процессов = 400 МБ оперативки, потраченных только на таблицы страниц, ещё до того как программы что-то полезное сделали. И это 32 бита; для 64-битных адресов плоская таблица была бы астрономической (об этом ниже).

Хуже другое: эта таблица почти вся пустая. Типичный процесс использует крошечный кусок своего адресного пространства — немного кода, немного кучи внизу и немного стека вверху. Середина — гигантская дыра, которую никто не трогает. Но плоский массив обязан хранить запись для каждой страницы, даже для тех миллионов, что никогда не будут существовать.

Адресное пространство процесса (схематично):
 
  0x00000000 ┌───────────┐  ← код, данные (используется)
             │███████████│
             ├───────────┤  ← куча, растёт к большим адресам
             │███████████│
             ├───────────┤
             │           │
             │           │   ← ОГРОМНАЯ ДЫРА
             │   пусто    │     (миллионы неиспользуемых страниц,
             │           │      но плоская таблица хранит PTE для КАЖДОЙ!)
             │           │
             ├───────────┤
             │███████████│  ← стек, растёт к меньшим адресам
  0xFFFFFFFF └───────────┘

Платить 4 МБ за описание пустоты расточительно. Вся эта глава о том, как перестать за неё платить.

Лобовое решение №1: страницы побольше

Самая простая идея: раз таблица большая из-за того, что страниц много, сделаем страницы крупнее. Меньше страниц → меньше записей → меньше таблица.

Возьмём страницу 16 КБ (2^14) вместо 4 КБ:

offset = 14 бит → VPN = 18 бит → 2^18 = 262 144 страниц
Размер таблицы = 2^18 * 4 = 1 МБ   (было 4 МБ)

Таблица ужалась в 4 раза. Здорово? Не очень. Появляется новая беда — внутренняя фрагментация (internal fragmentation). Если программе нужно всего 1 КБ под буфер, а минимальный кусок памяти — целая страница 16 КБ, то 15 КБ пропадают зря: они выделены, но не используются. Чем крупнее страница, тем больше такого «обрезка» теряется на каждом мелком выделении.

Запрос: нужно 1 КБ
┌──────────────────────────────────┐
│ █ занято 1 КБ │  пусто 15 КБ      │  ← страница 16 КБ
└──────────────────────────────────┘
                ↑ выкинутая память (internal fragmentation)

Поэтому большинство систем держат базовую страницу 4 КБ. Большие страницы (huge pages, об этом в главе про TLB) применяют точечно — для БД и JVM/Go-heap, где много памяти и важно разгрузить кэш трансляций, а не как универсальное лекарство. Один параметр (размер страницы) не может одновременно угодить и таблице, и фрагментации. Нужно что-то умнее.

Лобовое решение №2: гибрид страниц и сегментов

Вторая идея — вспомнить сегментацию. Раз пустота лежит большими непрерывными зонами (между кучей и стеком), заведём отдельную таблицу страниц на каждый сегмент (код, куча, стек) и будем хранить только те записи, что реально нужны сегменту. Для каждого сегмента — своя пара регистров base (где в памяти лежит его таблица) и bounds (сколько в ней валидных записей).

Это реально экономит память: таблицы покрывают только живые сегменты, а не всё пространство целиком. Но гибрид тащит за собой проблемы сегментации: таблицы разных сегментов имеют разный размер, их надо где-то размещать, и в свободной памяти заводится внешняя фрагментация (external fragmentation) — россыпь дырок разного калибра, в которые неудобно укладывать новые таблицы. Решение работает, но костыльно и негибко. Хочется механизма попроще и поровнее.

Многоуровневая таблица

Центральная идея главы: саму таблицу страниц тоже разбить на страницы, а затем завести отдельную маленькую таблицу, директорию страниц (page directory), которая говорит, какие куски большой таблицы вообще существуют, а какие можно не создавать.

Аналогия: книга на 1000 страниц. Плоская таблица — это как обязательное оглавление, где для каждой из 1000 страниц напечатана строчка, даже если 950 страниц пустые. Многоуровневая таблица — это оглавление по главам: сначала список глав (директория), и только для тех глав, что реально написаны, есть подробное оглавление страниц. Пустые главы в оглавлении не упоминаются вообще — и бумага не тратится.

Технически: большую таблицу режем на куски размером ровно в одну страницу. Каждый такой кусок — это маленькая таблица второго уровня. Запись в директории (PDE — page directory entry) указывает на один такой кусок ИЛИ помечена как невалидная. Если целый кусок таблицы описывает только пустоту — мы его просто не создаём, а в директории ставим «невалидно». Вот так мы перестаём платить за дыры.

ПЛОСКАЯ ТАБЛИЦА (всё подряд, даже пустое):
 
  таблица (4 МБ непрерывно в памяти)
  ┌────────────────────────────────────────────┐
  │PTE PTE  пусто пусто пусто ... пусто  PTE PTE │  ← хранится ВСЁ
  └────────────────────────────────────────────┘
 
МНОГОУРОВНЕВАЯ (директория + только живые куски):
 
  Директория (1 страница)        Куски таблицы (по 1 странице каждый)
  ┌───────────┐
  │ PDE0  ───────────────────►   ┌─────────────┐  (код/данные)
  │ PDE1  → невалидно (нет!)     │ PTE PTE ... │
  │ PDE2  → невалидно (нет!)     └─────────────┘
  │  ...      │   эти куски         ┌─────────────┐  (стек)
  │ PDE1023 ─────────────────►   │ ... PTE PTE │
  └───────────┘   НЕ существуют    └─────────────┘
                  в памяти!

Экономия видна сразу: вместо 4 МБ сплошного массива у нас директория (одна страница, 4 КБ) плюс ровно столько кусков по 4 КБ, сколько реально нужно живым областям. Для типичного процесса это директория + 2-3 куска = несколько десятков КБ вместо 4 МБ.

Как теперь делится адрес

Раньше адрес делился на две части: VPN и offset. Теперь VPN сам разбивается на индекс в директории и индекс внутри куска таблицы. Offset не трогаем — он по-прежнему адресует байт внутри страницы.

Посчитаем для 32 бит, страница 4 КБ, PTE = 4 байта. В одну страницу-кусок влезает 4096 / 4 = 1024 = 2^10 записей. Значит на индекс внутри куска нужно 10 бит. Под директорию остаётся 20 − 10 = 10 бит.

32-битный адрес, 2 уровня:
 
 ┌── PD index ──┬── PT index ──┬──── offset ────┐
 │   10 бит     │   10 бит     │    12 бит       │
 └──────────────┴──────────────┴─────────────────┘
   какой PDE       какой PTE        байт внутри
  в директории   внутри куска        страницы
 
  2^10 = 1024 PDE в директории
  2^10 = 1024 PTE в каждом куске
  2^12 = 4096 байт смещение

Walk: проход по уровням

Когда процессор встречает виртуальный адрес и в TLB нет готового ответа (промах, TLB miss), он выполняет page-table walk — буквально «прогулку» по таблице. Для двух уровней это два обращения в память перед тем, как мы доберёмся до данных.

Разберём конкретный адрес 0x00C11064. Сначала разрежем его на части:

0x00C11064 = 0000 0000 11 | 00 0001 0001 | 0000 0110 0100
             ─────────────  ────────────  ──────────────
             PD index = 3   PT index = 17  offset = 0x064 = 100

Физический адрес директории текущего процесса хранится в регистре CR3 (на x86), с него обход и начинается.

Виртуальный адрес → разбили на (PD=3, PT=17, off=100)
 
ШАГ 0: CR3 ──► физadress директории
               ┌──────────────┐
ШАГ 1: берём   │ PDE0          │
       PDE[3]  │ PDE1          │
               │ PDE2          │
        ──────►│ PDE3  ────────┼──┐  валиден? да → адрес куска таблицы
               │ ...           │  │
               └──────────────┘  │
                                  ▼
ШАГ 2: пришли в кусок таблицы   ┌──────────────┐
       (это уже 2-е обращение   │ PTE0          │
        в память), берём        │ ...           │
        PTE[17]                  │ PTE17 ────────┼──┐  валиден? да → PFN
                                 │ ...           │  │
                                 └──────────────┘  │
                                                   ▼
ШАГ 3: склеиваем PFN + offset(100) = физический адрес,
       читаем сами данные (3-е обращение в память)

Досчитаем с конкретными числами. Пусть CR3 = 0x00100000, в PDE[3] записан кадр 0x2A (там лежит нужный кусок таблицы), а в PTE[17] этого куска — PFN 0x5C3.

адрес PDE[3]  = CR3 + 3 × 4      = 0x00100000 + 0xC  = 0x0010000C
              → читаем: кусок таблицы в кадре 0x2A
адрес PTE[17] = 0x2A × 4096 + 17 × 4 = 0x0002A000 + 0x44 = 0x0002A044
              → читаем: PFN = 0x5C3
физический    = 0x5C3 × 4096 + 0x064   = 0x005C3000 + 0x64 = 0x005C3064

Каждая запись занимает 4 байта, поэтому адрес записи = начало таблицы + индекс × 4. Offset, как и в одноуровневой таблице, переезжает без изменений.

Главное: если на шаге 1 окажется, что PDE[3] невалиден, значит, всего этого куска таблицы не существует. Память на него не тратится, и сразу понятно, что таких страниц у процесса нет: процессор вызывает ядро ОС (page fault). Не нужно было заранее выделять 1024 пустых PTE, кусок просто не заведён. Один кусок покрывает 1024 страницы × 4 КБ = 4 МБ адресов.

Цена: больше обращений в память

Бесплатного ничего не бывает. Плоская таблица — это одно обращение в память на трансляцию (взять PTE), плюс обращение за данными. Двухуровневая — это два обращения за трансляцию (директория, потом кусок), плюс за данными. Каждое лишнее хождение в RAM — это десятки-сотни наносекунд, целая вечность для CPU.

Почему это всё равно работает и не убивает производительность? Потому что нас спасает TLB — маленький сверхбыстрый кэш готовых трансляций VPN→PFN прямо в процессоре. Walk по уровням случается только при промахе TLB. А промахи редки: благодаря локальности программа подолгу топчется по одним и тем же страницам, и 99%+ обращений ловят попадание в TLB за один такт. Глубокая многоуровневая таблица платит дорого лишь изредка, а в обычном горячем цикле её как будто и нет.

Обычное обращение (TLB hit):
  адрес → TLB → PFN → данные        (быстро, 1 обращение в RAM)
 
Промах (TLB miss), 2-уровневая таблица:
  адрес → TLB(нет) → walk: директория → кусок → PFN
        → заполнили TLB → данные      (дорого, 3 обращения в RAM)

Это и есть фундаментальный размен (trade-off): многоуровневая таблица экономит память ценой более дорогого промаха. На пустоту мы больше не тратимся, а редкие дорогие walks амортизируются кэшем.

Почему уровней бывает больше двух

Вернёмся к 64 битам. Процессоры x86-64 используют не все 64 бита адреса, а 48 (2⁴⁸ байт = 256 ТиБ). Старшие 16 бит обязаны повторять бит 47, такие адреса называют каноническими; поэтому пользовательские адреса выглядят как 0x00007f..., а адреса ядра ОС как 0xffff....

Сколько заняла бы плоская таблица? Страница 4 КБ, значит VPN = 48 − 12 = 36 бит, 2³⁶ записей по 8 байт:

  2^36 × 8 байт = 2^39 байт = 512 ГиБ на КАЖДЫЙ процесс

Две ступени тоже не спасают: директория получилась бы гигантской. Поэтому x86-64 использует 4 уровня (на новых процессорах ядро может включить 5 уровней и 57-битные адреса). Каждый уровень индексируется своими 9 битами.

x86-64, 48-битный адрес, страница 4 КБ, 4 уровня:
 
 ┌─ L4 ─┬─ L3 ─┬─ L2 ─┬─ L1 ─┬──── offset ────┐
 │ 9бит │ 9бит │ 9бит │ 9бит │     12 бит      │
 └──────┴──────┴──────┴──────┴─────────────────┘
   PML4   PDPT    PD     PT       байт в странице
 
  9 бит на уровень → 2^9 = 512 записей в каждой таблице
  (512 записей * 8 байт = 4096 = ровно одна страница)

Принцип тот же, только walk теперь четырёхшаговый, и ветку на любом уровне можно не создавать, если за ней пустота. Каждая таблица любого уровня занимает ровно одну страницу, поэтому её можно положить в любой свободный кадр. Промах TLB при 4 уровнях стоит до 4 обращений в память (процессоры кэшируют верхние уровни, поэтому в среднем меньше), и это ещё один аргумент, почему TLB так важен.

Разрежем на индексы реальный адрес из пользовательской половины:

package main
 
import "fmt"
 
func main() {
	va := uint64(0x7f3a12345678) // виртуальный адрес
 
	offset := va & 0xfff     // младшие 12 бит
	pt := (va >> 12) & 0x1ff // следующие 9 бит: индекс в таблице PT
	pd := (va >> 21) & 0x1ff // индекс в PD
	pdpt := (va >> 30) & 0x1ff
	pml4 := (va >> 39) & 0x1ff
 
	fmt.Printf("VA     = %#x\n", va)
	fmt.Printf("PML4   = %d\n", pml4)
	fmt.Printf("PDPT   = %d\n", pdpt)
	fmt.Printf("PD     = %d\n", pd)
	fmt.Printf("PT     = %d\n", pt)
	fmt.Printf("offset = %#x (%d)\n", offset, offset)
}

VA     = 0x7f3a12345678
PML4   = 254
PDPT   = 232
PD     = 145
PT     = 325
offset = 0x678 (1656)

0x1ff — это девять единиц в двоичном виде, маска для одного индекса; >> 12, >> 21, >> 30, >> 39 сдвигают нужную девятку бит в младшие разряды.

Сколько памяти уходит на таблицы у реального маленького процесса? Пусть код и куча лежат в начале адресного пространства (индекс PML4 = 0), а стек у верхней границы пользовательской половины (индекс 255). Нужны одна таблица PML4 и по одной цепочке PDPT → PD → PT для каждой из двух областей:

  1 (PML4) + 2 × (PDPT + PD + PT) = 7 страниц × 4 КБ = 28 КБ

28 КБ вместо 512 ГиБ. Реальному сервису с сотнями мегабайт памяти нужно больше таблиц нижнего уровня (одна PT покрывает 512 × 4 КБ = 2 МБ), но счёт идёт на мегабайты, а не на сотни гигабайт.

Huge pages: обход короче

Большие страницы из главы TLB хорошо ложатся на эту схему. Если в записи уровня PD стоит специальный флаг (PS, page size), обход на ней останавливается: запись указывает не на таблицу PT, а сразу на кадр размером 2 МБ. Offset тогда занимает 9 + 12 = 21 бит. Если флаг стоит на уровне PDPT, страница занимает 1 ГиБ и offset 30 бит. Меньше уровней — короче обход при промахе и меньше таблиц.

Сравнительная таблица

Многоуровневая берёт лучшее: платим только за используемые области, куски ровно по странице (никакой внешней фрагментации), мелкая страница (никакой внутренней). Платим за это лишь более дорогим — но редким — промахом TLB.

Инвертированная таблица (кратко)

Есть и совсем другой подход — инвертированная таблица страниц (inverted page table). Идея: вместо «по таблице на каждый процесс» завести одну таблицу на всю систему — по записи на каждый физический кадр. То есть таблица описывает не «какая страница где», а «в этом кадре лежит страница такого-то процесса».

Память это экономит шикарно: размер таблицы зависит от объёма физической RAM, а не от числа процессов и размера их адресных пространств. Минус — поиск: чтобы по (процесс, VPN) найти кадр, нужен не прямой индекс, а просмотр/хэширование. На практике строят хэш-таблицу поверх. Такой подход применяли, например, в PowerPC. Знать про него полезно, но мейнстрим (x86-64, ARM) — это многоуровневые таблицы.

Частые ошибки

• Считать, что многоуровневая таблица ускоряет трансляцию. Она экономит память, а промах TLB делает дороже.
• Забывать умножать индекс на размер записи при вычислении адреса PTE: индекс 17 — это смещение 17 × 4 байта (или × 8 на x86-64), а не 17 байт.
• Думать, что на 64-битных системах таблица описывает все 2⁶⁴ байт. На x86-64 используется 48 (или 57) бит.

Проверьте себя

1. 32 бита, страница 4 КБ, два уровня. Разрежьте адрес 0x00403ABC на PD index, PT index и offset.
2. Процесс использует только первые 8 МБ адресного пространства (32 бита, два уровня, страница 4 КБ). Сколько памяти займут его таблицы?
3. x86-64, страница 4 КБ, запись 8 байт. Почему на каждый уровень приходится ровно 9 бит?
4. Сколько обращений в память нужно при промахе TLB для страницы 2 МБ на x86-64?

Что спрашивают на собесе

• Почему плоская таблица страниц неэффективна и в чём именно «платим за пустоту».
• Как многоуровневая таблица экономит память: что хранит директория и почему невалидный PDE экономит целый кусок таблицы.
• Как делится виртуальный адрес при двух (и четырёх) уровнях — уметь посчитать число бит на индекс, зная размер страницы и размер PTE.
• Сколько обращений в память стоит промах TLB при N-уровневой таблице и почему это не убивает производительность (роль TLB и локальности).
• Размен крупных страниц: что выигрываем по таблице и что теряем на внутренней фрагментации.
• Чем инвертированная таблица отличается от прямой и какой у неё минус.