Виртуальная память

Как система держит открытыми 50 вкладок Chrome, Photoshop и IDE одновременно, имея всего 16 ГБ RAM? Виртуальная память переадресует обращения процесса через MMU и таблицы страниц - физически в RAM лежит только активный рабочий набор, остальное выгружено на диск или ещё не загружено. Каждый процесс видит изолированное адресное пространство на всю машину, и всё это прозрачно для программиста.

• **Почему Chrome жрёт так много памяти?** Каждая вкладка - отдельный процесс с виртуальным адресным пространством в десятки гигабайт. Но физически используется ~2-3 ГБ благодаря paging и shared memory. Paging позволяет Chrome жертвовать памятью ради безопасности (изоляция вкладок).
• **Как работает swap на SSD?** macOS агрессивно использует swap даже при 32 ГБ RAM. Почему? Вытесняя редко используемые страницы (например, код инициализации приложения), OS освобождает RAM под активные данные и файловый кеш. Результат: приложения запускаются быстрее.
• **Meltdown и Spectre: уязвимости виртуальной памяти.** Атаки 2018 года эксплуатировали speculative execution для чтения памяти ядра через TLB side-channel. Патч KPTI вызвал просадку производительности на 5-30% из-за TLB flush при каждом syscall. Безопасность vs скорость.

Цели урока

• Объяснить paging: фиксированный размер 4K, отображение через page table
• Multi-level page tables (x86-64: 4 уровня, 48-bit virtual address)
• TLB: hardware cache трансляций, hit rate ~99%, miss обходится в десятки ns
• Алгоритмы page replacement: FIFO, LRU, Clock, Linux active/inactive lists
• Различать demand paging, copy-on-write, mmap и когда какой применять

Paging: страничная организация памяти

**Виртуальная память** даёт каждой программе адресовать всю машину - адреса от 0 до 2⁴⁸ - даже если физически RAM всего несколько GB. Механизм, который это вытягивает - **paging**: память делится на куски фиксированного размера, трансляция адреса идёт на лету через MMU.

**Как работает paging?** Память делится на **страницы (pages)** фиксированного размера (обычно 4 КБ). Виртуальный адрес программы разбивается на две части: 1. **Номер страницы** (page number) 2. **Смещение внутри страницы** (offset) OS переводит виртуальный адрес в физический через **таблицу страниц (page table)**.

**Почему именно 4 КБ страницы?** - Слишком маленькие (512 байт) → огромная page table, много накладных расходов - Слишком большие (1 МБ) → внутренняя фрагментация (программе нужно 5 КБ, выделяется 1 МБ) - 4 КБ - баланс между накладными расходами и фрагментацией Новые CPU поддерживают **huge pages** (2 МБ, 1 ГБ) для баз данных и HPC.

**Ключевое преимущество paging:** программы могут использовать больше памяти, чем физически установлено RAM. Неактивные страницы выгружаются на диск (**swapping**). Программа не замечает - OS прозрачно подгружает их при обращении.

**Protection через paging.** Каждая запись в page table имеет **биты защиты**: Read/Write/Execute. Попытка записи в read-only страницу → **segmentation fault**. OS изолирует процессы: процесс A не может получить доступ к памяти процесса B - их page tables не пересекаются.

Page Tables: устройство и многоуровневые таблицы

**Page Table** - это структура данных, которая хранит маппинг виртуальных страниц на физические фреймы. Звучит просто, но реализация полна хитростей. Наивная одноуровневая таблица была бы гигантской!

**Решение: многоуровневые (hierarchical) page tables.** Вместо одной огромной таблицы - дерево таблиц. x86-64 использует **4-уровневую структуру**: PML4 → PDPT → PD → PT. Если виртуальные страницы не используются, соответствующие таблицы даже не выделяются!

**Каждая запись в page table (PTE - Page Table Entry)** содержит не только адрес физического фрейма, но и метаданные:

**Биты в Page Table Entry (x86-64):** - **Present (P):** Страница в RAM или на диске (swap) - **Read/Write (R/W):** Можно ли писать - **User/Supervisor (U/S):** Доступна ли userspace программам - **Accessed (A):** Была ли страница прочитана (для page replacement) - **Dirty (D):** Была ли страница изменена (нужно сохранить при swap) - **Execute Disable (XD/NX):** Защита от выполнения кода в данных (против exploits)

**Copy-on-Write (COW)** - хитрая оптимизация. При `fork()` Linux не копирует всю память родителя - просто обе page tables указывают на те же физические фреймы, но с битом `R/W = 0`. При попытке записи → page fault → OS делает реальную копию страницы.

**Инверсная page table** (inverted PT) - альтернативный подход. Вместо таблицы на каждый виртуальный адрес - таблица на каждый физический фрейм. Размер пропорционален физической RAM, а не виртуальному пространству. Используется в некоторых архитектурах (PowerPC, IA-64), но поиск медленнее - нужен hash table.

Translation Lookaside Buffer (TLB)

**Проблема:** при 4-уровневой page table каждый доступ к памяти требует 4 дополнительных обращений к RAM (по уровню на каждую таблицу). Это катастрофически медленно! Решение - **TLB (Translation Lookaside Buffer)** - аппаратный кеш для page table entries.

**TLB - это полностью ассоциативный кеш** внутри CPU. Обычно 64-512 записей. При доступе к виртуальному адресу MMU **параллельно** проверяет все записи TLB. Совпадение (TLB hit) → моментальный перевод. Промах (TLB miss) → медленный page walk по таблицам.

**Характеристики TLB (современный x86-64):** - **L1 DTLB:** 64 entries для данных (data TLB) - **L1 ITLB:** 128 entries для инструкций (instruction TLB) - **L2 TLB:** 1536 entries (shared для кода и данных) - **Hit rate:** обычно 95-99% (locality of reference) - **Miss penalty:** ~100-200 тактов (page walk) Без TLB современные процессоры были бы в 5-10 раз медленнее!

**TLB flush** - критический момент. При смене контекста (переключение на другой процесс) TLB становится бесполезен - там записи старого процесса! OS должна **очистить TLB**. На x86 это происходит при записи в регистр CR3 (указатель на корневую page table).

**PCID (Process Context ID)** - оптимизация для избежания TLB flush. Современные CPU помечают каждую запись в TLB идентификатором процесса (PCID). При смене контекста TLB не очищается - просто сравнивается PCID. Экономия тысяч тактов на каждом context switch.

**Huge pages и TLB.** Обычная страница 4 КБ, huge page - 2 МБ или 1 ГБ. Одна TLB запись для huge page покрывает в 512 раз больше памяти! Базы данных (PostgreSQL, MySQL) используют huge pages для снижения TLB miss.

Page Replacement: алгоритмы вытеснения

Программа использует 4 ГБ памяти, но физически доступно только 2 ГБ RAM. Половина страниц находится на диске (swap). При обращении к странице на диске возникает **page fault** - OS должна загрузить её в RAM. Но RAM полна: нужно **вытеснить (evict)** какую-то страницу. Выбор алгоритма вытеснения напрямую определяет производительность.

**Оптимальный алгоритм (OPT / Belady's):** вытеснять страницу, которая НЕ понадобится дольше всего. Идеально! Но... требует знания будущего. Невозможно реализовать, используется только для сравнения.

**Основные алгоритмы page replacement:** 1. **FIFO** - First-In-First-Out (самая старая страница) 2. **LRU** - Least Recently Used (давно не использовалась) 3. **Clock (Second Chance)** - аппроксимация LRU 4. **LFU** - Least Frequently Used (редко используется) 5. **Working Set** - на основе locality Линукс использует вариацию Clock (аппроксимация LRU).

**FIFO (First-In-First-Out)** - простейший алгоритм. Храним очередь страниц, вытесняем самую старую. Проблема: старая страница может быть активно используемой! Классический пример - **Belady's Anomaly**: при увеличении RAM количество page faults может расти.

**LRU (Least Recently Used)** - вытеснять страницу, к которой дольше всего не обращались. Интуитивно правильно (locality of reference), но **дорого реализовать точно**. Нужно отслеживать время каждого доступа - накладные расходы.

**Clock Algorithm (Second Chance)** - аппроксимация LRU. Используем **Accessed bit** в PTE (hardware автоматически ставит при доступе). OS проходит по страницам циклически (как стрелка часов). Если `Accessed=1` → сбросить в 0 (дать второй шанс). Если `Accessed=0` → вытеснить.

**Working Set Model.** Программы демонстрируют **locality of reference**: в каждый момент времени активно используется лишь подмножество страниц (**working set**). Если RAM меньше working set → постоянные page faults (**thrashing**). Если больше → спокойная работа.

**Linux Page Replacement:** двухсписочная структура. **Active list** - страницы, использованные недавно. **Inactive list** - кандидаты на вытеснение. Периодический процесс `kswapd` перемещает страницы между списками на основе Accessed bit. При нехватке памяти вытесняются страницы из inactive list (приоритет: чистые → грязные).

Ключевые идеи

• **Paging - основа виртуальной памяти.** Память делится на страницы (4 КБ), виртуальные адреса переводятся в физические через page tables. Программы могут использовать больше памяти, чем физически установлено RAM, благодаря swapping.
• **Многоуровневые page tables экономят память.** Одноуровневая таблица для 64-бит системы заняла бы сотни гигабайт. Иерархическая структура (4 уровня на x86-64) выделяет таблицы только для используемых регионов - overhead ~0.2%.
• **TLB - критичный для производительности кеш.** Без TLB каждый доступ к памяти требовал бы 5 обращений к RAM (page walk). TLB кеширует виртуально-физический маппинг, ускоряя перевод в ~5 раз. TLB miss и thrashing - основные враги производительности.
• **Page replacement - trade-off между алгоритмической сложностью и качеством решений.** Оптимальный алгоритм (OPT) требует знания будущего. LRU хорош, но дорог. Clock (Second Chance) - аппроксимация LRU, используемая в Linux. Swap не зло, а механизм выживания при нехватке памяти.

Связанные темы

Виртуальная память - фундамент современных OS, связанный с множеством других концепций:

• Управление памятью — Виртуальная память - высокоуровневая абстракция. Под капотом: физическое выделение фреймов, buddy allocator, slab cache
• Процессы и потоки — Каждый процесс имеет своё виртуальное адресное пространство. fork() использует Copy-on-Write для эффективности
• Файловые системы — mmap() позволяет маппить файлы в виртуальную память. Page cache использует те же механизмы, что и виртуальная память
• Безопасность ОС — Биты защиты в PTE (NX, U/S) предотвращают exploit'ы. ASLR рандомизирует виртуальные адреса для защиты от атак

Вопросы для размышления

• При проектировании OS для устройства с 512 МБ RAM (роутер, IoT): оправдан ли swap, и какой алгоритм page replacement минимизирует накладные расходы при ограниченных ресурсах?
• Huge pages (2 МБ) ускоряют базы данных, но не применяются по умолчанию для всех приложений. Какие trade-off'ы делают их нежелательными в общем случае?
• Как изменилась бы архитектура виртуальной памяти, если бы RAM и диск имели одинаковую latency? Оставался бы смысл в TLB и page replacement?

Связанные уроки

• os-07-memory — Виртуальная память - надстройка над физической
• os-09-filesystems — Memory-mapped files объединяют VM и файловую систему
• os-02-processes — Изоляция процессов реализована через виртуальные адресные пространства
• os-11-security — ASLR и защита памяти - функции виртуальной памяти
• db-14-mvcc