--- title: "Компактные таблицы страниц (многоуровневые)" description: "В прошлой главе про страничную организацию мы научились бить память на одинаковые кусочки — страницы (page) у процесса и кадры (frame, PFN — physical frame number) в физической…" canonical: https://graphlms.ru/os/book/smaller-tables course: "Операционные системы" updated: 2026-10-12 lang: ru publisher: GraphLMS --- # Компактные таблицы страниц (многоуровневые) > Источник: https://graphlms.ru/os/book/smaller-tables — курс «Операционные системы», GraphLMS. ## Откуда вообще берётся проблема В прошлой главе про [страничную организацию](/os/book/paging) мы научились бить память на одинаковые кусочки — **страницы** (page) у процесса и **кадры** (frame, PFN — physical frame number) в физической RAM. Чтобы знать, в каком кадре лежит каждая страница, мы завели **таблицу страниц** (page table) — массив, где по номеру страницы (VPN — virtual page number) лежит запись (PTE — page table entry) с номером кадра и битами доступа. У такой **линейной** (плоской) таблицы есть серьёзный недостаток: она занимает много места, и почти всё это место тратится впустую. Посчитаем для классического случая: 32-битное адресное пространство и страница 4 КБ. ```text 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-битных адресов плоская таблица была бы астрономической (об этом ниже). Хуже другое: эта таблица почти вся **пустая**. Типичный процесс использует крошечный кусок своего адресного пространства — немного кода, немного кучи внизу и немного стека вверху. Середина — гигантская дыра, которую никто не трогает. Но плоский массив обязан хранить запись для **каждой** страницы, даже для тех миллионов, что никогда не будут существовать. ```text Адресное пространство процесса (схематично): 0x00000000 ┌───────────┐ ← код, данные (используется) │███████████│ ├───────────┤ ← куча, растёт к большим адресам │███████████│ ├───────────┤ │ │ │ │ ← ОГРОМНАЯ ДЫРА │ пусто │ (миллионы неиспользуемых страниц, │ │ но плоская таблица хранит PTE для КАЖДОЙ!) │ │ ├───────────┤ │███████████│ ← стек, растёт к меньшим адресам 0xFFFFFFFF └───────────┘ ``` Платить 4 МБ за описание пустоты расточительно. Вся эта глава о том, как перестать за неё платить. ## Лобовое решение №1: страницы побольше Самая простая идея: раз таблица большая из-за того, что страниц много, сделаем страницы крупнее. Меньше страниц → меньше записей → меньше таблица. Возьмём страницу 16 КБ (2^14) вместо 4 КБ: ```text offset = 14 бит → VPN = 18 бит → 2^18 = 262 144 страниц Размер таблицы = 2^18 * 4 = 1 МБ (было 4 МБ) ``` Таблица ужалась в 4 раза. Здорово? Не очень. Появляется новая беда — **внутренняя фрагментация** (internal fragmentation). Если программе нужно всего 1 КБ под буфер, а минимальный кусок памяти — целая страница 16 КБ, то 15 КБ пропадают зря: они выделены, но не используются. Чем крупнее страница, тем больше такого «обрезка» теряется на каждом мелком выделении. ```text Запрос: нужно 1 КБ ┌──────────────────────────────────┐ │ █ занято 1 КБ │ пусто 15 КБ │ ← страница 16 КБ └──────────────────────────────────┘ ↑ выкинутая память (internal fragmentation) ``` Поэтому большинство систем держат базовую страницу 4 КБ. Большие страницы (huge pages, об этом в главе про [TLB](/os/book/tlb)) применяют точечно — для БД и JVM/Go-heap, где много памяти и важно разгрузить кэш трансляций, а не как универсальное лекарство. Один параметр (размер страницы) не может одновременно угодить и таблице, и фрагментации. Нужно что-то умнее. ## Лобовое решение №2: гибрид страниц и сегментов Вторая идея — вспомнить [сегментацию](/os/book/segmentation). Раз пустота лежит большими непрерывными зонами (между кучей и стеком), заведём **отдельную таблицу страниц на каждый сегмент** (код, куча, стек) и будем хранить только те записи, что реально нужны сегменту. Для каждого сегмента — своя пара регистров base (где в памяти лежит его таблица) и bounds (сколько в ней валидных записей). Это реально экономит память: таблицы покрывают только живые сегменты, а не всё пространство целиком. Но гибрид тащит за собой проблемы сегментации: таблицы разных сегментов имеют **разный размер**, их надо где-то размещать, и в свободной памяти заводится **внешняя фрагментация** (external fragmentation) — россыпь дырок разного калибра, в которые неудобно укладывать новые таблицы. Решение работает, но костыльно и негибко. Хочется механизма попроще и поровнее. ## Многоуровневая таблица Центральная идея главы: **саму таблицу страниц тоже разбить на страницы**, а затем завести отдельную маленькую таблицу, **директорию страниц** (page directory), которая говорит, какие куски большой таблицы вообще существуют, а какие можно не создавать. Аналогия: книга на 1000 страниц. Плоская таблица — это как обязательное оглавление, где для **каждой** из 1000 страниц напечатана строчка, даже если 950 страниц пустые. Многоуровневая таблица — это оглавление по **главам**: сначала список глав (директория), и только для тех глав, что реально написаны, есть подробное оглавление страниц. Пустые главы в оглавлении не упоминаются вообще — и бумага не тратится. Технически: большую таблицу режем на куски размером ровно в одну страницу. Каждый такой кусок — это маленькая таблица второго уровня. Запись в директории (PDE — page directory entry) указывает на один такой кусок ИЛИ помечена как невалидная. Если целый кусок таблицы описывает только пустоту — мы его **просто не создаём**, а в директории ставим «невалидно». Вот так мы перестаём платить за дыры. ```text ПЛОСКАЯ ТАБЛИЦА (всё подряд, даже пустое): таблица (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 бит. ```text 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](/os/book/tlb) нет готового ответа (промах, TLB miss), он выполняет **page-table walk** — буквально «прогулку» по таблице. Для двух уровней это два обращения в память перед тем, как мы доберёмся до данных. Разберём конкретный адрес `0x00C11064`. Сначала разрежем его на части: ```text 0x00C11064 = 0000 0000 11 | 00 0001 0001 | 0000 0110 0100 ───────────── ──────────── ────────────── PD index = 3 PT index = 17 offset = 0x064 = 100 ``` Физический адрес директории текущего процесса хранится в регистре **CR3** (на x86), с него обход и начинается. ```text Виртуальный адрес → разбили на (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`. ```text адрес 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](/os/book/swapping)). Не нужно было заранее выделять 1024 пустых PTE, кусок просто не заведён. Один кусок покрывает 1024 страницы × 4 КБ = 4 МБ адресов. ## Цена: больше обращений в память Бесплатного ничего не бывает. Плоская таблица — это одно обращение в память на трансляцию (взять PTE), плюс обращение за данными. Двухуровневая — это **два** обращения за трансляцию (директория, потом кусок), плюс за данными. Каждое лишнее хождение в RAM — это десятки-сотни наносекунд, целая вечность для CPU. Почему это всё равно работает и не убивает производительность? Потому что нас спасает **TLB** — маленький сверхбыстрый кэш готовых трансляций VPN→PFN прямо в процессоре. Walk по уровням случается **только при промахе TLB**. А промахи редки: благодаря [локальности](/os/book/tlb) программа подолгу топчется по одним и тем же страницам, и 99%+ обращений ловят попадание в TLB за один такт. Глубокая многоуровневая таблица платит дорого лишь изредка, а в обычном горячем цикле её как будто и нет. ```text Обычное обращение (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 байт: ```text 2^36 × 8 байт = 2^39 байт = 512 ГиБ на КАЖДЫЙ процесс ``` Две ступени тоже не спасают: директория получилась бы гигантской. Поэтому x86-64 использует **4 уровня** (на новых процессорах ядро может включить 5 уровней и 57-битные адреса). Каждый уровень индексируется своими 9 битами. ```text 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 так важен. Разрежем на индексы реальный адрес из пользовательской половины: ```go play 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) } ``` ```text 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 для каждой из двух областей: ```text 1 (PML4) + 2 × (PDPT + PD + PT) = 7 страниц × 4 КБ = 28 КБ ``` 28 КБ вместо 512 ГиБ. Реальному сервису с сотнями мегабайт памяти нужно больше таблиц нижнего уровня (одна PT покрывает 512 × 4 КБ = 2 МБ), но счёт идёт на мегабайты, а не на сотни гигабайт. ### Huge pages: обход короче Большие страницы из главы [TLB](/os/book/tlb) хорошо ложатся на эту схему. Если в записи уровня PD стоит специальный флаг (PS, page size), обход на ней останавливается: запись указывает не на таблицу PT, а сразу на кадр размером 2 МБ. Offset тогда занимает 9 + 12 = 21 бит. Если флаг стоит на уровне PDPT, страница занимает 1 ГиБ и offset 30 бит. Меньше уровней — короче обход при промахе и меньше таблиц. ## Сравнительная таблица | Подход | Память на таблицу | Внутр. фрагментация | Внеш. фрагментация | Цена промаха | |--------|-------------------|---------------------|--------------------|--------------| | Плоская таблица | очень много (вся, даже пустота) | нет | нет | 1 обращение | | Крупные страницы | меньше | большая | нет | 1 обращение | | Гибрид с сегментами | мало | нет | есть | 1 обращение | | Многоуровневая | мало (платим только за живое) | нет | нет (куски = размер страницы) | N обращений | Многоуровневая берёт лучшее: платим только за используемые области, куски ровно по странице (никакой внешней фрагментации), мелкая страница (никакой внутренней). Платим за это лишь более дорогим — но редким — промахом TLB. ## Инвертированная таблица (кратко) Есть и совсем другой подход — **инвертированная таблица страниц** (inverted page table). Идея: вместо «по таблице на каждый процесс» завести **одну** таблицу на всю систему — по записи на каждый физический кадр. То есть таблица описывает не «какая страница где», а «в этом кадре лежит страница такого-то процесса». Память это экономит шикарно: размер таблицы зависит от объёма физической RAM, а не от числа процессов и размера их адресных пространств. Минус — поиск: чтобы по (процесс, VPN) найти кадр, нужен не прямой индекс, а просмотр/хэширование. На практике строят хэш-таблицу поверх. Такой подход применяли, например, в PowerPC. Знать про него полезно, но мейнстрим (x86-64, ARM) — это многоуровневые таблицы. > Интерактивный симулятор «Многоуровневая таблица»: Адрес делится на L1|L2|offset. Внешний каталог указывает на подтаблицы; если запись каталога пуста — подтаблица вообще не выделена (так экономится память). За это платим вторым обращением в память. Запустить: https://graphlms.ru/os/book/smaller-tables > Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/smaller-tables ## Частые ошибки - Считать, что многоуровневая таблица ускоряет трансляцию. Она экономит память, а промах 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? Ответы. (1) `0x00403ABC` = `0000 0000 01 | 00 0000 0011 | 1010 1011 1100`: PD = 1, PT = 3, offset = `0xABC`. (2) Директория 4 КБ плюс два куска таблицы (каждый покрывает 4 МБ): 12 КБ. (3) Таблица уровня занимает одну страницу: 4096 / 8 = 512 = 2⁹ записей. (4) Три: PML4, PDPT, PD (обход останавливается на PD). ## Что спрашивают на собесе - Почему плоская таблица страниц неэффективна и в чём именно «платим за пустоту». - Как многоуровневая таблица экономит память: что хранит директория и почему невалидный PDE экономит целый кусок таблицы. - Как делится виртуальный адрес при двух (и четырёх) уровнях — уметь посчитать число бит на индекс, зная размер страницы и размер PTE. - Сколько обращений в память стоит промах TLB при N-уровневой таблице и почему это не убивает производительность (роль TLB и локальности). - Размен крупных страниц: что выигрываем по таблице и что теряем на внутренней фрагментации. - Чем инвертированная таблица отличается от прямой и какой у неё минус. ## Вопросы для самопроверки **Квиз «Многоуровневые таблицы страниц»** 1. В чём главная проблема плоской (линейной) таблицы страниц? - Она не работает на 32-битных системах - Она занимает много памяти, храня записи даже для неиспользуемых (пустых) страниц (верно) - Она не поддерживает биты прав доступа - Она слишком медленная при попадании в TLB - Пояснение: Плоский массив обязан хранить PTE для каждой возможной страницы, включая огромную дыру между кучей и стеком. 99% записей описывают пустоту, но память под них всё равно тратится. 2. За счёт чего многоуровневая таблица экономит память? - Куски таблицы, описывающие только пустоту, просто не создаются (PDE помечен невалидным) (верно) - Хранит таблицу на диске вместо RAM - Сжимает записи алгоритмом упаковки - Делает страницы крупнее - Пояснение: Большая таблица режется на куски размером в страницу. Если целый кусок покрывает только неиспользуемые адреса, его не создают, а в директории ставят невалидный PDE. Так мы не платим за пустоту. 3. 32-битный адрес, страница 4 КБ, PTE = 4 байта, двухуровневая таблица. Сколько бит отводится под индекс в директории (PD index)? - Ответ: 10 - Пояснение: offset = 12 бит (4 КБ). В кусок-страницу влезает 4096/4 = 1024 = 2^10 записей, значит PT index = 10 бит. На VPN всего 20 бит, остаётся 20 − 10 = 10 бит на PD index. 4. Сколько обращений в память нужно для трансляции при промахе TLB в двухуровневой таблице (не считая чтения самих данных)? - Ответ: 2 - Пояснение: Сначала читаем PDE из директории (1), по нему идём в кусок таблицы и читаем PTE (2). Только потом получаем PFN. Само чтение данных по физическому адресу — отдельное, третье обращение. 5. Что верно про размен (trade-off) многоуровневых таблиц? (выберите все верные) - Экономят память по сравнению с плоской таблицей (верно) - Редкость промахов TLB амортизирует дорогой walk (верно) - Промах TLB стоит дороже (несколько обращений в память) (верно) - Полностью устраняют необходимость в TLB - Пояснение: Многоуровневая таблица экономит память, но платит более дорогим walk при промахе. TLB не устраняется — наоборот, он критически важен: благодаря локальности промахи редки, и дорогой walk случается нечасто. 6. Почему увеличение размера страницы (например до 16 КБ) — плохое универсальное решение проблемы размера таблицы? - Растёт внутренняя фрагментация: мелкие выделения теряют остаток большой страницы (верно) - Адрес больше нельзя разбить на VPN и offset - Перестаёт работать TLB - Таблица становится только больше - Пояснение: Крупная страница уменьшает число записей, но если программе нужен 1 КБ, а минимальный кусок — 16 КБ, то 15 КБ пропадают зря. Это внутренняя фрагментация, она растёт с размером страницы.