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

⏱ 30 мин · 🧩 заданий: 6

Проблема размера

Одноуровневая таблица должна иметь запись на каждую возможную виртуальную страницу:

Архитектура	Страниц	Размер таблицы
32 бита, страница 4 КиБ, запись 4 Б	2²⁰	4 МиБ на процесс
48 бит, страница 4 КиБ, запись 8 Б	2³⁶	512 ГиБ на процесс!

Но процесс использует ничтожную часть адресного пространства: код внизу, стек вверху, между ними пустота.

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

Номер страницы делится на части. Первая часть — индекс в таблице верхнего уровня, её запись указывает на таблицу следующего уровня, и так далее. Для пустых участков таблицы нижних уровней не создаются.

i386: два уровня

виртуальный адрес (32 бита) ┌────────────┬────────────┬──────────────┐ │ каталог 10 │ таблица 10 │ смещение 12 │ └─────┬──────┴─────┬──────┴──────┬───────┘ │ │ │ cr3 ──▶ каталог │ │ страниц │ │ ┌────────┐ │ │ │ ... │ ▼ │ │ PDE ───┼─▶ таблица │ │ ... │ страниц │ └────────┘ ┌────────┐ │ │ PTE ───┼─▶ кадр + смещение = физический адрес └────────┘

1024 записи по 4 байта = 4 КиБ — каждая таблица ровно в одну страницу.

x86-64: четыре уровня

47 39 38 30 29 21 20 12 11 0 ┌──────────┬──────────┬──────────┬──────────┬─────────────┐ │ PML4 (9) │ PDPT (9) │ PD (9) │ PT (9) │ смещение 12 │ └──────────┴──────────┴──────────┴──────────┴─────────────┘ cr3 → PML4 → PDPT → PD → PT → кадр

512 записей по 8 байт = 4 КиБ. 48-битное пространство = 256 ТиБ. Новые процессоры поддерживают и 5 уровней (57 бит).

Цена многоуровневости

Каждый уровень — ещё одно обращение к памяти. При промахе TLB в 4-уровневой схеме, чтобы прочитать одну ячейку, нужно 4 + 1 = 5 обращений.

Задача 7

«4-х уровневая организация таблиц страниц» означает: каждый промах TLB стоит 4 служебных обращения к памяти — по одному на чтение записи каждого уровня. Это главный множитель в ответе.

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

Инвертированная таблица страниц

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

инвертированная таблица (одна на систему): индекс = номер кадра ┌───────┬───────────────┬────────────┐ │ кадр │ PID процесса │ вирт. стр. │ ├───────┼───────────────┼────────────┤ │ 0 │ ядро │ 0x800 │ │ 1 │ 412 │ 0x403 │ │ 2 │ 977 │ 0x403 │ │ ... │ ... │ ... │ └───────┴───────────────┴────────────┘ поиск (PID, страница) → кадр: через хеш-таблицу, иначе пришлось бы просматривать все записи

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

Используется: PowerPC (хешированная таблица страниц, которую аппаратура просматривает при промахе TLB), IA-64 (как вариант), исторически IBM System/38 и RT PC.

В ядрах ОС с прямыми таблицами тоже есть структура «по кадру»: в Linux — массив struct page (по одному на физический кадр) с обратными отображениями (rmap) «какие PTE ссылаются на этот кадр». Страничному демону это нужно, чтобы при вытеснении кадра найти и исправить все отображения.

Задача 2: инвертированная таблица страниц

Это структура данных ядра уровня управления физическими ресурсами: она описывает физические кадры памяти. На архитектурах вроде PowerPC её просматривает и аппаратура при промахе TLB — тогда это ещё и аппаратный уровень. Обычная таблица страниц — уровни ядра и аппаратуры (MMU обходит её на x86).

Итог

Одноуровневая таблица слишком велика; многоуровневая создаёт таблицы только для используемых участков.
i386: 2 уровня по 10 бит; x86-64: 4 уровня по 9 бит; число записей = страница / размер записи.
Каждый уровень — одно обращение к памяти при промахе TLB.
Инвертированная таблица — запись на физический кадр, одна на систему, поиск через хеш; PowerPC.

Войдите, чтобы отмечать пройденные уроки.

	Прямая (многоуровневая)	Инвертированная
Одна запись на виртуальную страницу
Одна запись на физический кадр
Своя таблица у каждого процесса
Одна таблица на всю систему
Размер зависит от объёма физической памяти
Поиск по номеру страницы — прямой индекс
Поиск — через хеш по (PID, номер страницы)
Легко отобразить один кадр в несколько процессов