Страничная организация памяти

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

История

Идея страничной организации памяти возникла в 1950-х годах как решение проблемы фрагментации и неэффективности, присущих более ранним схемам управления памятью, таким как динамическое распределение с переменными разделами. Первые реализации были предложены в контексте развития систем с виртуальной памятью. Одной из первых систем, применивших страничную организацию, стала Atlas (Манчестерский университет, Великобритания, 1962 год), где использовалась концепция «одноуровневого хранилища», объединяющего оперативную и внешнюю память.

В 1960-х годах страничная организация была внедрена в мейнфреймах IBM System/360 Model 67, а позже — в серии IBM System/370. Широкое распространение метод получил с появлением микропроцессоров: в архитектуре x86 поддержка страничной памяти была введена в процессоре Intel 80386 (1985 год). С тех пор страничная организация является основой управления памятью в большинстве современных операционных систем (Linux, Windows, macOS, FreeBSD) и процессорных архитектур (x86-64, ARM, RISC-V).

Основные понятия

Страница и кадр

Страница — это непрерывный блок виртуальной памяти фиксированного размера. Кадр (фрейм) — соответствующий ему блок физической памяти. Размер страницы обычно кратен степени двойки и варьируется от 4 КБ (наиболее распространённый в x86-64) до 1 ГБ (большие страницы в некоторых архитектурах). Выбор размера страницы влияет на эффективность: малые страницы уменьшают внутреннюю фрагментацию, но увеличивают размер таблиц страниц; большие страницы снижают накладные расходы на управление, но могут приводить к неполному использованию памяти.

Виртуальный адрес

Виртуальный адрес в системе со страничной организацией состоит из двух частей: номера виртуальной страницы (VPN) и смещения внутри страницы (offset). Например, для 32-битной системы с размером страницы 4 КБ (2^12 байт) старшие 20 бит адреса представляют номер страницы, а младшие 12 бит — смещение.

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

Таблица страниц — это структура данных, хранящая отображение виртуальных страниц на физические кадры. Каждая запись таблицы страниц (PTE) содержит:

• Номер физического кадра (PFN) — базовый адрес кадра в физической памяти.
• Биты состояния: присутствие (present), модификация (dirty), обращение (accessed), разрешения на чтение/запись/исполнение, пользовательский/супервизорный режим, кэширование и другие.

Если запись не содержит валидного номера кадра (бит присутствия сброшен), возникает страничное прерывание (page fault), и операционная система загружает страницу с диска или выделяет новый кадр.

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

Для экономии памяти в системах с большим виртуальным адресным пространством (например, 64-битных) используются многоуровневые таблицы страниц. В архитектуре x86-64 применяется четырёхуровневая схема: PML4 (Page Map Level 4), PDP (Page Directory Pointer), PD (Page Directory) и PT (Page Table). Каждый уровень содержит указатели на таблицу следующего уровня или на кадр. Неиспользуемые части виртуального адресного пространства не требуют выделения таблиц, что значительно сокращает объём памяти для структур управления.

Виды страничной организации

Страничная организация с подкачкой (demand paging)

Стандартный режим, при котором страницы загружаются в физическую память только при первом обращении к ним. Это позволяет процессам иметь виртуальное адресное пространство, превышающее объём доступной оперативной памяти, за счёт использования дискового пространства (своп-раздела или файла подкачки). При нехватке физических кадров операционная система применяет алгоритмы замещения страниц (например, LRU — Least Recently Used, FIFO, Clock).

Страничная организация с сегментацией

Гибридный подход, сочетающий страничную организацию с сегментацией. Виртуальное адресное пространство делится на сегменты (логические блоки, например, код, данные, стек), а каждый сегмент, в свою очередь, разбит на страницы. Такая схема использовалась в архитектуре Intel 80386 (режим защищённого режима) и позволяет задавать разные права доступа для разных сегментов. В современных x86-64 системах сегментация практически не используется, уступая место чисто страничной организации.

Обратные таблицы страниц (inverted page tables)

Альтернативный метод, применяемый в некоторых архитектурах (например, IBM PowerPC, HP PA-RISC). Вместо хранения одной записи на каждую виртуальную страницу (что требует больших таблиц в 64-битных системах), обратная таблица содержит одну запись на каждый физический кадр. Поиск отображения выполняется с помощью хеш-таблицы. Этот подход экономит память, но усложняет обработку страничных прерываний.

Устройство и работа

Трансляция адресов

Процессор, выполняя инструкцию, формирует виртуальный адрес. Блок управления памятью (MMU — Memory Management Unit) извлекает номер виртуальной страницы и выполняет поиск в таблице страниц. Для ускорения трансляции используется буфер ассоциативной трансляции (TLB — Translation Lookaside Buffer) — кэш, хранящий недавно использованные отображения. Если отображение найдено в TLB (попадание), физический адрес формируется немедленно. При промахе TLB MMU обращается к таблице страниц в оперативной памяти (walk), что может занять несколько циклов.

Обработка страничного прерывания

Если запись таблицы страниц отсутствует или недействительна, процессор генерирует исключение (page fault). Операционная система:

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

Замещение страниц

При нехватке свободных кадров ОС выбирает страницу для вытеснения. Распространённые алгоритмы:

• LRU — вытесняется страница, к которой дольше всего не было обращений.
• FIFO — вытесняется самая старая страница.
• Clock — приближение LRU с использованием бита обращения.
• Алгоритм Нила — вытесняется страница, которая не будет использована в ближайшем будущем (теоретический оптимум).

Применение и значение

Страничная организация памяти является основой для реализации:

• Виртуальной памяти — каждый процесс получает изолированное адресное пространство, что повышает безопасность и стабильность системы.
• Свопинга — вытеснение целых страниц на диск позволяет выполнять программы, размер которых превышает объём оперативной памяти.
• Разделения памяти между процессами — несколько процессов могут отображать одни и те же физические страницы (например, разделяемые библиотеки, межпроцессное взаимодействие через разделяемую память).
• Копирования при записи (Copy-on-Write) — при создании процесса (fork) страницы родителя и потомка совместно используют одни и те же физические кадры до момента записи, что экономит память и ускоряет создание процессов.

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

Основные недостатки страничной организации:

• Накладные расходы на таблицы страниц — в 64-битных системах многоуровневые таблицы могут занимать значительный объём памяти, хотя и меньше, чем одноуровневые.
• Промахи TLB — при переключении контекста между процессами TLB часто сбрасывается, что приводит к снижению производительности. Современные процессоры поддерживают тегированные TLB (с идентификаторами адресного пространства, ASID) для уменьшения этой проблемы.
• Внутренняя фрагментация — если процесс использует неполную страницу, оставшаяся часть страницы пропадает (например, при размере страницы 4 КБ и выделении 1 байта теряется 4095 байт).
• Задержки при страничных прерываниях — обращение к диску может занимать миллисекунды, что критично для систем реального времени.

Альтернативы

Другие методы управления памятью включают:

• Сегментация — деление памяти на логические блоки переменного размера (использовалась в Intel 8086, OS/2).
• Плоская модель памяти — все адреса являются физическими (применяется во встраиваемых системах без MMU).
• Страничная организация с большими страницами (huge pages) — в архитектурах x86-64 поддерживаются страницы размером 2 МБ и 1 ГБ для снижения накладных расходов.

Интересные факты

• В системах Linux размер страницы по умолчанию составляет 4 КБ, но для некоторых приложений (базы данных, виртуализация) можно включить большие страницы (hugepages) через файловую систему hugetlbfs.
• В процессорах ARMv8-A размер страницы может быть 4 КБ, 16 КБ или 64 КБ, что выбирается на этапе конфигурации ядра.
• Архитектура RISC-V поддерживает страничную организацию с размерами страниц 4 КБ, 2 МБ и 1 ГБ, а также экспериментальные схемы с 64 КБ.

Источники

• Таненбаум Э., Бос Х. Современные операционные системы. 4-е изд. — СПб.: Питер, 2015.
• Сильбершац А., Гэвин П., Гэгн Г. Операционные системы: внутреннее устройство и принципы проектирования. 9-е изд. — М.: Вильямс, 2016.
• Intel Corporation. Intel® 64 and IA-32 Architectures Software Developer’s Manual. Volume 3A: System Programming Guide. — 2023.
• ARM Limited. ARM Architecture Reference Manual ARMv8-A. — 2022.
• Документация ядра Linux: «Memory Management» (kernel.org).