Таблица страниц

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

Назначение и принцип работы

В современных вычислительных системах с виртуальной памятью каждый процесс оперирует виртуальными адресами, которые не совпадают с физическими адресами ячеек памяти. Преобразование виртуального адреса в физический называется трансляцией адреса. Таблица страниц хранит записи (Page Table Entries, PTE), которые для каждой виртуальной страницы (блока виртуальной памяти фиксированного размера) указывают номер соответствующей физической страницы (фрейма) в оперативной памяти.

Когда процессор обращается к памяти, блок управления памятью (Memory Management Unit, MMU) аппаратно выполняет трансляцию адреса. Он разбивает виртуальный адрес на номер виртуальной страницы и смещение внутри страницы. По номеру виртуальной страницы MMU находит соответствующую запись в таблице страниц, извлекает из неё номер физического фрейма и объединяет его со смещением, получая физический адрес. Если запись в таблице страниц отсутствует (например, страница выгружена на диск), возникает исключение (page fault), и операционная система загружает нужную страницу в память.

Структура записи таблицы страниц

Каждая запись таблицы страниц (PTE) содержит несколько полей, которые управляют доступом и состоянием страницы. Типичный набор полей в архитектуре x86-64 включает:

• Бит присутствия (Present) — указывает, находится ли страница в физической памяти. Если бит сброшен, обращение к странице вызывает page fault.
• Бит чтения/записи (Read/Write) — разрешает или запрещает запись на страницу.
• Бит пользовательского режима (User/Supervisor) — определяет, доступна ли страница для выполнения кода в пользовательском режиме.
• Бит изменения (Dirty) — устанавливается MMU при записи на страницу; используется для отслеживания страниц, которые нужно сохранить на диск при выгрузке.
• Бит обращения (Accessed) — устанавливается MMU при любом доступе (чтении или записи) к странице; используется для алгоритмов замещения страниц.
• Номер физического фрейма (Physical Frame Number) — адрес физической страницы в оперативной памяти.

Размер записи таблицы страниц зависит от архитектуры. В 32-битных системах (x86) PTE обычно занимает 4 байта, в 64-битных (x86-64) — 8 байт.

Типы таблиц страниц

Одноуровневая таблица страниц

Простейшая реализация, при которой вся таблица страниц представляет собой линейный массив записей, индексируемых номером виртуальной страницы. Для 32-битного адресного пространства с размером страницы 4 КБ требуется таблица из 2^20 (1 048 576) записей. При размере записи 4 байта таблица занимает 4 МБ — значительный объём для каждого процесса. В современных системах одноуровневая таблица практически не используется из-за неэффективности по памяти.

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

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

В архитектуре x86-64 используется четырёхуровневая таблица страниц (PML4, PDPT, PD, PT). Каждый уровень индексируется 9 битами виртуального адреса, а оставшиеся 12 бит отводятся под смещение внутри страницы (размер страницы — 4 КБ). Такая структура позволяет адресовать до 48 бит виртуального адресного пространства (256 ТБ).

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

В альтернативном подходе, используемом в некоторых архитектурах (например, PowerPC), таблица страниц содержит записи для физических фреймов, а не для виртуальных страниц. Каждая запись хранит идентификатор процесса и номер виртуальной страницы, которые отображаются на данный физический фрейм. Поиск выполняется аппаратно с помощью хеш-таблицы. Инвертированная таблица занимает фиксированный объём, пропорциональный размеру физической памяти, а не виртуального адресного пространства.

Аппаратная поддержка и TLB

Поскольку таблица страниц хранится в оперативной памяти, каждый доступ к памяти при трансляции адреса потребовал бы нескольких обращений к памяти (для прохода по уровням иерархии), что значительно снизило бы производительность. Для ускорения трансляции используется кэш быстрых преобразований — буфер ассоциативной трансляции (Translation Lookaside Buffer, TLB). TLB хранит недавно использованные пары «номер виртуальной страницы — номер физического фрейма». При обращении к памяти MMU сначала проверяет TLB; если запись найдена (TLB hit), трансляция выполняется за один такт. Если записи нет (TLB miss), MMU обращается к таблице страниц в памяти, выполняет трансляцию и помещает результат в TLB.

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

Управление таблицами страниц в операционной системе

Операционная система отвечает за создание, поддержание и освобождение таблиц страниц для каждого процесса. При создании процесса ядро выделяет память под корневую таблицу (например, PML4 в x86-64) и заполняет её записями, отображающими виртуальную память процесса. При завершении процесса таблицы страниц освобождаются.

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

Примеры реализации

Linux

В ядре Linux таблицы страниц реализованы для различных архитектур. Для x86-64 используется четырёхуровневая таблица. Ядро предоставляет API для работы с таблицами страниц, включая функции выделения и освобождения страниц, изменения атрибутов доступа и обработки page fault. В современных версиях Linux (начиная с 5.0) поддерживается пятиуровневая таблица страниц для адресации до 57 бит виртуального адресного пространства.

Windows

В Windows NT также используется многоуровневая таблица страниц, аналогичная x86-64. Ядро Windows управляет таблицами страниц через диспетчер памяти (Memory Manager). Для поддержки больших страниц (2 МБ и 1 ГБ) в Windows реализована поддержка огромных страниц (Large Pages), которые уменьшают количество записей в таблицах и снижают нагрузку на TLB.

Критика и ограничения

Использование таблиц страниц связано с рядом проблем:

• Накладные расходы на память — даже при многоуровневой структуре таблицы страниц могут занимать значительный объём, особенно при большом количестве процессов.
• Задержки при трансляции — TLB miss может приводить к нескольким обращениям к памяти, что снижает производительность.
• Сложность управления — поддержка таблиц страниц требует сложного кода в ядре ОС, особенно при реализации таких функций, как копирование при записи (copy-on-write) и разделение страниц.
• Уязвимости безопасности — ошибки в реализации таблиц страниц могут приводить к утечкам данных между процессами или к повышению привилегий (например, уязвимости типа Meltdown и Spectre, связанные с предсказанием ветвлений и кэшированием TLB).

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание, 2015)
• Бовет Д., Чезати М. «Ядро Linux. Описание процесса» (3-е издание, 2006)
• Intel 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide
• AMD64 Architecture Programmer’s Manual, Volume 2: System Programming
• McKusick M. K., Neville-Neil G. V., Watson R. N. M. «The Design and Implementation of the FreeBSD Operating System» (2-е издание, 2014)