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

В прошлой главе про страничную организацию мы научились бить память на одинаковые кусочки — страницы (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 МБ за то, чтобы описать 99% пустоты — расточительство. Вся эта глава про то, как перестать платить за пустоту.

Лобовое решение №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 — буквально «прогулку» по таблице. Для двух уровней это два обращения в память перед тем, как мы доберёмся до данных.

Разберём на конкретном адресе. Пусть PD index = 3, PT index = 17, offset = 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-е обращение в память)

Ключевой момент: если на ШАГЕ 1 окажется, что PDE[3] невалиден — значит, всего этого куска таблицы не существует, мы экономим память, и заодно сразу понимаем, что такой страницы у процесса нет (можно кинуть page fault). Нам не нужно было заранее выделять 1024 пустых PTE — мы просто не завели кусок.

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

Бесплатного ничего не бывает. Плоская таблица — это одно обращение в память на трансляцию (взять 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 бит виртуального адреса (этого хватает на 256 ТБ). Даже двух уровней тут не хватит: сама директория стала бы гигантской. Поэтому в дело идут 4 уровня (а в новых системах с 5-уровневыми таблицами — 5). Каждый уровень индексируется своими 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 так важен.

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

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

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

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

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

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

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