Страничная организация памяти

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

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

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

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

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

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

Режем обе памяти, виртуальную и физическую, на блоки одного размера. На x86-64 и большинстве Linux-серверов это 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), второе — штатная ситуация, ОС подгрузит и продолжит.

Тонкость реального железа: в PTE на x86-64 есть только бит P (present), а отдельного бита valid нет. Если P = 0, процессор в любом случае вызывает ядро ОС (page fault), а уже ядро по своему списку областей процесса (тому самому, что видно в /proc/<PID>/maps, см. адресное пространство) решает: адрес легальный, и страницу надо подгрузить, или нелегальный, и процесс получит SIGSEGV. То есть «valid» живёт в структурах ОС, а «present» в железе. Запись PTE на x86-64 занимает 8 байт.

Как устроен виртуальный адрес: 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 и продом

Размер страницы можно узнать у ОС:

package main
 
import (
	"fmt"
	"os"
)
 
func main() {
	fmt.Println("размер страницы:", os.Getpagesize(), "байт")
}

На Linux/x86-64 программа напечатает размер страницы: 4096 байт. На Mac с процессором Apple Silicon — 16384: там страницы по 16 КБ. Код, который где-то жёстко зашил 4096, на такой машине начинает вести себя странно. В shell то же самое показывает getconf PAGESIZE.

• Страница — единица, которой ОС выдаёт память. Рантайм Go берёт у ОС большие куски через mmap и нарезает их сам (см. управление свободной памятью), но ОС всё равно выделяет и возвращает память страницами.
• Страница — единица защиты. Права R/W и NX стоят на всей странице, поэтому код, данные только для чтения и изменяемые данные лежат в разных страницах. Это видно по строкам r-xp, r--p, rw-p в /proc/<PID>/maps.
• Copy-on-write при fork. Из главы API процессов: после fork родитель и потомок пользуются одними физическими кадрами. ОС помечает их PTE «только чтение» у обоих. Первая запись вызывает исключение защиты, ядро копирует один кадр и даёт пишущему процессу его собственную копию с правом записи. Копируется ровно одна страница, а не вся память.
• Ленивое выделение. Когда программа получает память через mmap, PTE для неё ещё нет. Кадр выделяется при первом обращении к странице. Подробнее в главах за пределами физической памяти и память в проде.

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

• Путать страницу и кадр. Страница — кусок виртуального пространства, кадр — кусок физической памяти. Таблица отображает страницы в кадры.
• Переводить offset через таблицу. Offset копируется без изменений, переводится только номер страницы.
• Считать, что таблица страниц одна на систему. Она своя у каждого процесса, и при переключении процесса ОС меняет CR3.

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

Конфигурация из главы: адрес 14 бит, страница 4 КБ, таблица VPN 0 → 2, 1 → 4, 2 → 7, 3 → 6.

1. Переведите виртуальный адрес 100.
2. Переведите виртуальный адрес 5000.
3. Сколько бит offset при странице 16 КБ? Сколько страниц в 32-битном адресном пространстве при таком размере?
4. Почему после fork копирование памяти происходит не сразу?

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

• Чем 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); ОС переключает его при смене контекста, поэтому у каждого процесса своя таблица и своя изоляция памяти.