Виртуальная память: страничная организация адреса

Страничная организация виртуальной памяти - это способ, которым операционная система создаёт для каждого процесса иллюзию большого непрерывного адресного пространства, физически разбросанного по кускам оперативной памяти и диску. Процесс работает с виртуальными адресами, а реальное размещение данных по физическим ячейкам берёт на себя связка «таблица страниц плюс блок управления памятью». Разберём, как виртуальный адрес распадается на номер страницы и смещение, как таблица страниц переводит его в физический, зачем нужен буфер TLB и что происходит при page fault. Ниже есть калькулятор трансляции - впишите свой адрес и размер страницы, чтобы увидеть разбор по битам.

Зачем нужна виртуальная память

Без виртуальной памяти программа адресовала бы физические ячейки напрямую. Это порождает три проблемы: процессы могут затереть данные друг друга, программе нужен непрерывный блок памяти целиком, а суммарный объём всех процессов не может превысить размер ОЗУ. Виртуальная память снимает все три ограничения сразу.

Идея в том, чтобы ввести промежуточный слой адресации. Процесс оперирует виртуальными адресами из своего изолированного пространства (например, 0 .. $2^{48}-1$), а аппаратный блок управления памятью (MMU) на лету переводит каждый такой адрес в физический - реальный адрес в микросхемах ОЗУ. Перевод и называется трансляцией адреса.

Страничная организация - самый распространённый способ устроить эту трансляцию. И виртуальное, и физическое пространство нарезаются на блоки одинакового фиксированного размера: виртуальные блоки зовут страницами (pages), физические - фреймами или рамками (frames). Размер блока - степень двойки, классически 4 КБ ($2^{12}$ байт).

Рассчитать для своей задачи

Как виртуальный адрес делится на части

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

• Смещение внутри страницы (offset) - младшие $p$ бит, где размер страницы равен $2^p$ байт. Для страницы 4 КБ это младшие 12 бит.
• Номер виртуальной страницы (VPN) - все старшие биты, оставшиеся после смещения.

Если виртуальный адрес занимает $n$ бит, а страница - $2^p$ байт, то под номер страницы отводится $n - p$ старших бит, под смещение - $p$ младших. Формально:

$$\text{VPN} = \left\lfloor \frac{A}{2^p} \right\rfloor, \qquad \text{offset} = A \bmod 2^p$$

где $A$ - виртуальный адрес. Деление на $2^p$ и остаток от него - это просто сдвиг вправо на $p$ бит и взятие младших $p$ бит, поэтому MMU выполняет разбиение мгновенно, без арифметики деления.

Смысл такого деления в том, что смещение при трансляции не меняется: байт остаётся на той же позиции внутри блока, переезжает только сам блок. Поэтому переводить нужно лишь номер страницы - этим занимается таблица страниц. О том, как двоичная запись адреса соответствует этим полям, полезно держать в голове связь с позиционными системами счисления и кодированием: каждое поле адреса - это группа разрядов фиксированной длины.

Таблица страниц: отображение страниц во фреймы

Таблица страниц (page table) - структура в памяти, которая для каждого процесса задаёт отображение «номер виртуальной страницы → номер физического фрейма». Она индексируется по VPN: берём номер страницы как индекс, читаем соответствующую запись и получаем номер фрейма.

Физический адрес собирается обратно из двух частей:

$$\text{PA} = \text{frame} \times 2^p + \text{offset}$$

то есть номер фрейма сдвигается влево на $p$ бит, и к нему дописывается неизменное смещение. Каждая запись таблицы (page table entry, PTE) хранит не только номер фрейма, но и служебные биты:

• бит присутствия (valid/present) - лежит ли страница сейчас в ОЗУ;
• биты прав доступа - чтение, запись, исполнение;
• бит обращения (accessed) и бит модификации (dirty) - для алгоритмов вытеснения;
• иногда бит «нельзя кэшировать» и биты пользователь/ядро.

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

Плоская таблица на всё адресное пространство заняла бы сотни гигабайт, причём почти вся была бы пустой. Решение - иерархическая таблица: номер страницы сам разбивается на несколько полей, каждое из которых индексирует свой уровень.

В архитектуре x86-64 с 4 КБ страницами VPN из 36 бит делится на четыре поля по 9 бит. Каждое поле индексирует одну таблицу на 512 записей ($2^9$). Трансляция идёт сверху вниз: старшие 9 бит выбирают запись в таблице верхнего уровня, та указывает на таблицу следующего уровня и так далее, пока последний уровень не даст номер фрейма.

Рассчитать для своей задачи

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

TLB: кэш трансляций

Если бы каждый доступ к памяти требовал прохода по всем уровням таблицы, программа замедлилась бы в разы. Спасает TLB (Translation Lookaside Buffer) - небольшой ассоциативный кэш внутри MMU, который хранит последние использованные пары «номер страницы → номер фрейма».

Алгоритм трансляции с TLB:

1. MMU берёт VPN из виртуального адреса и ищет его в TLB.
2. Попадание (TLB hit) - фрейм берётся из кэша за один такт, проход по таблице не нужен.
3. Промах (TLB miss) - MMU выполняет полный обход таблицы (page walk), находит фрейм, дописывает пару в TLB и продолжает.

TLB работает потому, что у программ высокая локальность ссылок: обращения группируются вокруг небольшого числа страниц. На практике процент попаданий превышает 99%, поэтому средняя стоимость трансляции близка к одному такту. Эффективное время доступа считают как взвешенное среднее:

$$T_\text{эфф} = h \cdot T_\text{hit} + (1 - h)\cdot T_\text{miss}$$

где $h$ - доля попаданий в TLB. Тот же принцип взвешенного среднего лежит в основе оценки кэшей всех уровней процессора.

Page fault: страница не в памяти

Если бит присутствия в записи таблицы сброшен, нужной страницы в ОЗУ нет - она либо ещё не загружалась, либо вытеснена на диск. Обращение к ней вызывает page fault - аппаратное исключение, которое передаёт управление операционной системе.

Обработчик page fault действует так:

1. Проверяет, легально ли обращение (адрес в пределах выделенной памяти, права доступа корректны). Если нет - процесс получает ошибку сегментации.
2. Находит свободный фрейм; если свободных нет, выбирает жертву по алгоритму вытеснения (LRU, Clock, FIFO) и при необходимости записывает её dirty-страницу на диск.
3. Загружает требуемую страницу с диска в выбранный фрейм.
4. Обновляет запись таблицы (ставит бит присутствия и номер фрейма) и перезапускает прервавшуюся инструкцию.

Слишком частые page fault приводят к трешингу (thrashing): система тратит почти всё время на подкачку страниц вместо полезной работы. Это происходит, когда совокупному набору активных страниц процессов не хватает физической памяти.

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

• Путают страницу и фрейм. Страница - блок виртуального пространства, фрейм - блок физического. Они равны по размеру, и трансляция меняет номер блока, но не размер.
• Считают, что смещение тоже переводится. Смещение переходит из виртуального адреса в физический без изменений - переводится только номер страницы.
• Берут неверное число бит под смещение. Под смещение идёт ровно $\log_2$ от размера страницы: для 4 КБ это 12 бит, для 8 КБ - 13, а не «округлённое» значение.
• Смешивают page fault и segmentation fault. Первое - нормальная подкачка, второе - недопустимое обращение.
• Забывают про TLB при оценке скорости. Без учёта высокого процента попаданий в TLB кажется, что многоуровневая таблица катастрофически медленна, хотя на деле почти все трансляции идут из кэша.

FAQ

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

Почему размер страницы - всегда степень двойки? Чтобы деление адреса на номер страницы и смещение сводилось к битовым операциям. При размере $2^p$ смещение - это младшие $p$ бит, а номер страницы - старшие; MMU выделяет их сдвигом, без медленного деления. Произвольный размер потребовал бы настоящего деления на каждом доступе.

Что хранит запись таблицы страниц кроме номера фрейма? Биты присутствия, прав доступа (чтение/запись/исполнение), бит обращения и бит модификации (для алгоритмов вытеснения), а также флаги кэшируемости и уровня привилегий. Сам номер фрейма занимает старшие биты записи, служебные биты - младшие.

Коротко

Страничная организация виртуальной памяти разбивает виртуальный адрес на номер страницы (старшие биты) и смещение (младшие $p$ бит при размере страницы $2^p$). Таблица страниц отображает номер страницы во фрейм, смещение переходит без изменений, а физический адрес собирается как $\text{frame} \times 2^p + \text{offset}$. Многоуровневые таблицы экономят память, TLB кэширует трансляции и держит среднюю стоимость близкой к одному такту, а page fault штатно подгружает отсутствующую страницу с диска.