Зачем вообще придумали страницы

В прошлой главе про сегментацию мы разрезали память процесса на куски разного размера: код, стек, куча. Это убрало часть проблем, но породило новую боль — внешнюю фрагментацию. Память постепенно превращалась в «швейцарский сыр»: свободного места вроде много, но оно раскидано мелкими дырками, и положить туда новый кусок целиком не получается.

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

А теперь придумаем правило: все парковочные места одинаковые, под стандартный размер. Любая машина встаёт на любое свободное место. Никаких щелей «не того размера» — место либо занято, либо свободно, и подходит под что угодно. Внешняя фрагментация исчезает как явление.

Именно это и есть страничная организация (paging): мы режем память не на куски разного размера, а на одинаковые блоки фиксированного размера.

Ключевая мысль главы: одинаковый размер блоков убивает внешнюю фрагментацию и делает управление памятью простым «списком свободных кадров».

Страницы и кадры: два слова, которые надо запомнить

Режем обе памяти — виртуальную и физическую — на блоки одного размера. Обычно 4 КБ (4096 байт). У этих блоков разные имена, и их важно не путать:

• Страница (page, virtual page) — блок в виртуальном адресном пространстве процесса. Нумеруются с нуля: страница 0, 1, 2, …
• Кадр / фрейм (frame, physical frame, PFN — Page Frame Number) — блок в физической (реальной) оперативной памяти.

Размеры совпадают, поэтому любая виртуальная страница влезает в любой физический кадр — как любая машина на любое стандартное место.

   ВИРТУАЛЬНОЕ адр. пространство          ФИЗИЧЕСКАЯ память (RAM)
   процесса (например 16 КБ)              (например 64 КБ)
   каждая клетка = страница 4 КБ          каждая клетка = кадр 4 КБ
 
   ┌───────────────┐ page 0              ┌───────────────┐ frame 0  (ядро)
   │   код         │ ───────┐           ├───────────────┤ frame 1  (другой proc)
   ├───────────────┤ page 1         └──►├───────────────┤ frame 2  ◄ page 0
   │   куча        │ ─────────────┐     ├───────────────┤ frame 3  (свободно)
   ├───────────────┤ page 2       └────►├───────────────┤ frame 4  ◄ page 1
   │   ...         │                    ├───────────────┤ frame 5  (свободно)
   ├───────────────┤ page 3 ──────────►├───────────────┤ frame 6  ◄ page 3
   │   стек        │                    ├───────────────┤ frame 7  ◄ page 2
   └───────────────┘                    └───────────────┘ ...

Что нарисовано: виртуальные страницы процесса лежат в физических кадрах вразнобой — страница 0 в кадре 2, страница 1 в кадре 4, страница 2 в кадре 7. Подряд в виртуальном пространстве вовсе не значит подряд в RAM. И это нормально: процесс видит свою память «ровной и непрерывной» (иллюзия из главы про адресное пространство), а на деле она размазана по свободным кадрам.

Кто помнит, какая страница в каком кадре? Специальная таблица. Знакомьтесь.

Таблица страниц: телефонная книга процесса

Таблица страниц (page table) — это структура, которая хранит отображение «номер виртуальной страницы (VPN) → номер физического кадра (PFN)». Своя у каждого процесса: у процесса A страница 0 может жить в кадре 2, а у процесса B та же страница 0 — в кадре 9. Поэтому одинаковые виртуальные адреса у разных процессов спокойно указывают на разную физическую память — вот вам и изоляция.

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

   Таблица страниц процесса A
   индекс = VPN        запись = PTE (Page Table Entry)
   ┌──────┬───────────────────────────────┐
   │ VPN  │ PFN  │ valid present R/W user  │
   ├──────┼───────────────────────────────┤
   │  0   │  2   │   1      1    1    1     │  → страница 0 в кадре 2
   │  1   │  4   │   1      1    1    1     │  → страница 1 в кадре 4
   │  2   │  7   │   1      1    0    1     │  → только чтение
   │  3   │  6   │   1      1    1    1     │
   │  4   │  -   │   0      -    -    -     │  → невалидна (обращение = SIGSEGV)
   │ ...  │      │                         │
   └──────┴───────────────────────────────┘

Обратите внимание: VPN — это сам индекс, его в записи не хранят. По номеру страницы мы просто прыгаем в нужную строку таблицы, как в массиве.

Биты в записи (PTE)

Каждая запись (PTE) — это не только номер кадра, но и набор флагов-битов. Самые важные:

Разница valid и present важна на собесах. valid = «эта часть адресного пространства легальна» (например, между кучей и стеком огромная дыра — там всё невалидно). present = «страница легальна, но прямо сейчас её нет в RAM, она выгружена на диск». Первое — это ошибка программиста (segfault), второе — штатная ситуация, ОС подгрузит и продолжит.

Как устроен виртуальный адрес: VPN | offset

Самое красивое в paging: чтобы понять, в какой странице лежит адрес, не нужно ничего вычислять делением. Адрес просто разбивается на две части по битам.

• Старшие биты → VPN (номер виртуальной страницы): в какой странице мы.
• Младшие биты → offset (смещение): на сколько байт внутри страницы.

Сколько бит на offset? Ровно столько, чтобы адресовать любой байт внутри страницы. Страница 4 КБ = 4096 = 2¹² байт → offset 12 бит. Остальные биты адреса — это VPN.

   Пример: виртуальное пространство 16 КБ, страница 4 КБ.
   16 КБ = 2^14  → адрес 14 бит.
   страница 4 КБ = 2^12 → offset 12 бит.
   значит VPN = 14 - 12 = 2 бита (4 страницы: 0..3).
 
    13 12 │ 11 10 9 8 7 6 5 4 3 2 1 0
   ┌──┬──┬┼──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
   │V │V ││ o  o  o  o  o  o  o  o  o  o  o  o│
   └──┴──┴┴──────────────────────────────────┘
    └─VPN─┘ └─────────── offset ──────────────┘
     2 бита          12 бит

Что нарисовано: 14-битный адрес. Два старших бита — VPN (выбирает одну из 4 страниц), двенадцать младших — offset (выбирает байт внутри страницы 0..4095).

Важнейшая деталь: offset при трансляции не меняется. Внутри страницы и внутри кадра расположение байтов одинаковое (блоки же равны по размеру). Мы переводим только «номер страницы → номер кадра», а смещение копируем как есть.

Трансляция шаг за шагом

Давайте проследим, как процессор превращает виртуальный адрес в физический.

   ВИРТУАЛЬНЫЙ адрес
   ┌────────┬───────────────┐
   │  VPN   │    offset      │
   └───┬────┴───────┬────────┘
       │            │
       │ (1) индекс  │  (3) offset копируется без изменений
       ▼            │
   ┌──────────────┐ │
   │ page table   │ │
   │  [VPN] = PTE │ │
   └───┬──────────┘ │
       │ (2) берём PFN из PTE
       │            │
       ▼            ▼
   ┌────────┬───────────────┐
   │  PFN   │    offset      │
   └────────┴───────────────┘
   ФИЗИЧЕСКИЙ адрес

Пошагово:

1. Достаём VPN — берём старшие биты адреса.
2. Идём в таблицу страниц по индексу VPN, читаем PTE. Проверяем valid (иначе segfault) и present (иначе page fault). Достаём PFN.
3. Собираем физический адрес: PFN ставим в старшие биты, offset из исходного адреса — в младшие. Готово.

Адрес самой таблицы процессор знает из специального регистра (на x86 это CR3, его же называют page-table base register). При переключении процессов ОС меняет CR3 — и вся «телефонная книга» мгновенно становится другой. Это часть смены контекста.

Числовой пример (досчитаем руками)

Возьмём ту же конфигурацию: пространство 16 КБ, страница 4 КБ, offset 12 бит, VPN 2 бита. Пусть в таблице: VPN 0 → PFN 2, VPN 1 → PFN 4, VPN 2 → PFN 7. Физическая память пусть 64 КБ = 2¹⁶ → физадрес 16 бит (PFN 4 бита + offset 12).

Транслируем виртуальный адрес 9438.

   9438 в двоичном (14 бит): 10 0100 1101 1110
                             └┬┘ └────┬──────┘
                            VPN=10₂   offset=0100 1101 1110₂
                            VPN = 2   offset = 1246
 
   шаг 1: VPN = 2
   шаг 2: page_table[2] = PFN 7  → 7 в двоичном (4 бита) = 0111
   шаг 3: физадрес = PFN(0111) | offset(0100 1101 1110)
                   = 0111 0100 1101 1110₂
                   = 7 * 4096 + 1246
                   = 28672 + 1246
                   = 29918

Проверка здравым смыслом: внутри страницы мы на смещении 1246, и в кадре 7 мы тоже окажемся на смещении 1246 от его начала (7×4096 = 28672). 28672 + 1246 = 29918. Сошлось. Offset переехал нетронутым — как и обещали.

За что мы платим: две цены paging

Бесплатного счастья не бывает. У страничной организации две расплаты.

Цена 1: таблицы большие. Таблица — это запись на каждую виртуальную страницу, даже если процесс ей не пользуется. Прикинем для реальной 32-битной системы:

   адрес 32 бита, страница 4 КБ (offset 12 бит)
   ⇒ VPN = 32 - 12 = 20 бит ⇒ 2^20 = 1 048 576 страниц
   каждая запись PTE ≈ 4 байта
   размер таблицы = 1 048 576 * 4 байта = 4 МБ
 
   и это НА КАЖДЫЙ процесс!
   100 процессов ⇒ 400 МБ только под таблицы. Жуть.

Большая часть этих 4 МБ — пустые записи (valid=0), ведь типичный процесс не использует все 4 ГБ. Хранить плотный массив с дырами расточительно. Решение — многоуровневые (иерархические) таблицы, им посвящена отдельная глава про компактные таблицы: таблица сама разбивается на страницы, и пустые куски просто не выделяются.

Цена 2: лишнее обращение в память. Чтобы транслировать адрес, процессору надо сначала сходить в RAM за PTE, и только потом — за самими данными. То есть каждое обращение к памяти превращается в два: одно за переводом, одно за данными. Память и так самое медленное звено — а мы её нагрузку удвоили.

   БЕЗ paging:        load X  →  [─── RAM: данные ───]               1 поход
 
   С paging (наивно): load X  →  [─ RAM: читаем PTE ─]  →            2 похода
                                 [─── RAM: данные ───]    в 2 раза медленнее!

Это абсолютно неприемлемо по скорости. Спасает аппаратный кэш переводов — TLB, который запоминает недавние пары «VPN → PFN», чтобы не лазить в таблицу каждый раз. Это тема следующей главы про TLB, и она напрямую вытекает из цены 2.

Связь с Go и продом

• Размер страницы 4 КБ всплывает повсюду. Аллокатор Go берёт память у ОС большими кусками (арены) и нарезает их сам, чтобы реже дёргать системные вызовы; но базовая единица, которой оперирует ОС под капотом, — это страница.
• mmap (см. память в проде) отображает файл/память страницами; первое обращение к ещё не загруженной странице — это тот самый page fault.
• Гранулярность защиты — страница. Бит R/W стоит на странице целиком, поэтому read-only данные, исполняемый код и изменяемую кучу ОС держит в разных страницах.
• Latency. Понимание «обращение к памяти стоит дорого, а с трансляцией — ещё дороже» объясняет, почему cache-friendly структуры данных и локальность доступа так влияют на производительность. Это перекликается с моделью памяти в курсе Go.

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

• Чем paging лучше сегментации? Одинаковый размер блоков убирает внешнюю фрагментацию: любую страницу можно положить в любой свободный кадр, не нужна компактация. Платим внутренней фрагментацией (последняя страница неполная) и большими таблицами.
• Как виртуальный адрес делится на части? Младшие биты — offset (их число = log₂ размера страницы; для 4 КБ это 12 бит), старшие — VPN. Offset при трансляции не меняется, переводится только VPN → PFN.
• В чём разница между valid и present битами? valid — легален ли участок адресного пространства (нарушение → segfault); present — находится ли страница сейчас в RAM (если нет → page fault, ОС подгрузит с диска).
• Почему таблица страниц такая большая и что с этим делают? Запись на каждую виртуальную страницу, даже неиспользуемую (для 32 бит и 4 КБ — около 4 МБ на процесс). Решают многоуровневыми таблицами, не выделяя память под пустые куски.
• Какая главная цена paging по скорости и как её снижают? Каждое обращение к памяти требует дополнительного похода в RAM за PTE (удвоение трафика). Снижают кэшем переводов — TLB.
• Где хранится адрес таблицы страниц текущего процесса? В регистре (CR3 на x86); ОС переключает его при смене контекста, поэтому у каждого процесса своя таблица и своя изоляция памяти.