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

Обновлено: 05.07.2024

Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники.
Эта отметка установлена 14 мая 2011.

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

Поддержка такого режима присутствует в большинстве 32битных и 64битных процессоров. Такой режим является классическим для почти всех современных ОС, в том числе Windows и семейства UNIX. Широкое использование такого режима началось с процессора VAX и ОС VMS с конца 70х годов (по некоторым сведениям, первая реализация). В семействе x86 поддержка появилась с поколения 386, оно же первое 32битное поколение.

Содержание

Решаемые задачи

Концепции

Процессор содержит в себе небольшой объём сверхбыстрой ассоциативной памяти, т. н. TLB (Translation Lookaside Buffer), в котором содержится преобразование нескольких (часто 64) виртуальных адресов страниц в физические. Все обращения процессора к памяти подлежат трансляции адресов через TLB.

Так как 64 строк таблицы явно недостаточно для реальных задач, в архитектуре используются таблицы страниц, размещённые в основной памяти. Каждая таблица страниц сама является страницей с теми же требованиями по выравниваю и тем же размером, и состоит из записей таблицы страниц (page table entries — PTE). Широко используется и отображение самой таблицы страниц как одной из страниц данных для внесения изменений в записи.

Запись таблицы страниц обычно содержит в себе следующую информацию:

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

Формат записей таблиц, их размер, размер страницы и организация таблиц зависит от типа процессора, а иногда и от режима его работы.

Исторически, x86 использует 32битные PTE, 32битные виртуальные адреса, 4KB страницы, 1024 записи в таблице, двухуровневые таблицы, старшие 10 бит виртуального адреса — номер записи в директории, следующие 10 — номер записи в таблице, младшие 12 — адрес внутри страницы. Начиная с Pentium Pro процессор поддерживает страницы размером 4Мб.

Процессор x86 в режиме PAE (Physical Address Extension) и в режиме x86_64 (long mode), использует 64битные PTE (из них реально задействованы не все биты физического адреса, от 36 в PAE до 48 в некоторых x86_64), 32битные виртуальные адреса, 4KB страницы, 512 записей в таблице, трехуровневые таблицы с 4 директориями и 4 записями в супер-директории, старшие 2 бита виртуального адреса — номер записи в супер-директории, следующие 9 — в директории, следующие 9 — в таблице. Физический адрес директории или же супер-директории загружен в один из управляющих регистров процессора.

При использовании PAE вместо 4Мб страниц используются двухмегабайтные. См. также PSE.

В архитектуре x86_64 возможно использовать страницы размером 4 килобайта (4096 байт), 2 мегабайта, и (в некоторых AMD64) 1 гигабайт.

Некоторые процессоры (MIPS) не имеют обращающегося к таблице микрокода, и генерируют отказ страницы сразу после неудачи поиска в TLB, обращение к таблице и её интерпретация возлагаются уже на обработчик отказа страницы. Это лишает таблицы страниц требования соответствовать жёстко заданному на уровне аппаратуры формату.

Причины отказа страницы (page fault):

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

Отображаемые в память файлы

Обработчик отказа страницы в ядре способен прочитать данную страницу из файла.

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

Отображаемые в память файлы используется в ОС Windows, а также ОС семейства UNIX, для загрузки исполняемых модулей и динамических библиотек. Они же используются утилитой GNU grep для чтения входящего файла, а также для загрузки шрифтов в ряде графических подсистем.

Страничная и сегментная виртуальная память

Наличие таких концепций в программировании уменьшает применимость арифметики указателей, и приводит к огромным проблемам с переносимостью кода с/на такие архитектуры. Так, например, значительная часть ПО с открытым кодом изначально разрабатывалась для бессегментных 32битных платформ со страничной памятью и не может быть перенесена на сегментные архитектуры без серьёзной переработки.

Виртуальная память и дисковый кэш

Совершенно очевидно, что данная структура является уже готовым дисковым кэшем. Использование её в качестве кэша также решает проблему когерентности файла, доступного через read/write, и его же, отображенного в память.

Таким образом, пути кэшированного ввода/вывода в дисковый файл (FsRtlCopyRead в Windows и аналогичная ей generic_file_read() в Linux) реализуются как копирования данных в физические страницы, отображенные на файл.

Такая организация кэша является единственной в Windows, эта ОС вообще не имеет классического блочного кэша диска. Метаданные файловых систем кэшируются путем создания лже-файлов (IoCreateStreamFileObject) и создания страничного кэша для них.

Соображения безопасности

Поддержка данного флага появилась в архитектуре x86 как часть режима PAE (Physical Address Extension) в поколении Pentium 4, под большим давлением со стороны специалистов по безопасности (см. архивы NTBugTraq). Установка данного флага на страницах стека и кучи (heap) позволяет реализовать аппаратно защиту от исполнения данных, что делает невозможной работу многих разновидностей вредоносного ПО, в том числе, например, злонамеренную эксплуатацию многих брешей в Internet Explorer (брешь декабря 2008 года, см. MS knowledge base, не может быть задействована в случае включенной DEP).

Поддержка PAE в Windows, дающая возможность включения защиты от исполнения данных, появилась в Windows 2000, она включена по умолчанию в серверных версиях Windows и отключена в клиентских.

Поддержка памяти свыше 4Гб в Windows

Для любого обращения к памяти свыше отметки 4Гб (то есть более, чем примерно 3.2Гб) требуется поддержка контроллером (то есть северным мостом чипсета) такой конфигурации. Современные чипсеты (например Intel G33) такую поддержку имеют.

Также требуется настройка BIOS под названием memory remapping, отображающая регион [3.2…4] на [4..4.8].

Процессор x86 вне режима PAE использует 32битные PTE и физические адреса, то есть ему недоступно ничто, находящееся выше отметки 4Гб (см. также PSE-36 об одном из вариантов обхода данного ограничения). Таким образом, для использования памяти более, чем примерно 3.2Гб в ОС она должна поддерживать PAE. Для Windows это опция загрузки, для Linux — опция построения ядра.

Кроме того, Microsoft принудительно отключила поддержку физических адресов выше 4Гб по политико-маркетинговым соображениям в следующих ОС:

Поддержка физических адресов выше 4Гб имеется в следующих версиях:

всe 64битные версии
32битная Windows Vista SP1 (поддержка включена по умолчанию, но её подключение нередко может требовать набора команд в командной строке)
32битный Windows Server 2003, отличный от Web Edition
32битный Windows Server 2008

Таким образом, для того, чтобы использовать память выше 3.2Гб в Windows, нужны а) поддержка чипсетом б) правильные настройки BIOS в) правильная версия Windows г) правильная опция загрузки (с поддержкой PAE) д) поддержка 36-битного адресного пространства драйверами устройств.

Эта форма организации виртуальной памяти во многом похожа на сегментную. Основные различия заключаются в том, что все страницы, в отличие от сегментов, имеют одинаковые размеры, а разбиение виртуального адресного пространства процесса на страницы выполняется системой автоматически. Типичный размер страницы – несколько килобайт. Для процессоров Pentium, например, страница равна 4 Кб.

Все виртуальные адреса одного процесса относятся к единому линейному пространству, Проще сказать, виртуальный адрес выражается одним числом, от 0 до некоторого максимума. Старшие разряды двоичного представления этого адреса определяют номер виртуальной страницы, а младшие разряды – смещение от начала страницы. Например, для страниц по 4 Кб смещение занимает 12 младших разрядов адреса.

Физическая память также считается разбитой на части, размеры которых совпадают с размером виртуальной страницы. Эти части называются физическими страницами или страничными кадрами (page frames). Таблица страниц процесса по структуре похожа на таблицу сегментов. Для каждой виртуальной страницы она содержит режим доступа, флаг присутствия страницы в памяти, номер страничного кадра, флаг чистоты. Если страница отсутствует в памяти, ее данные сохраняются в файле подкачки, который в этом случае чаще называют страничным файлом (page file).

Простейший вариант схемы преобразования виртуального страничного адреса в физический адрес показан на рис. 5‑3.

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

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

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

Размер пространства виртуальных адресов каждого процесса может быть огромным, ибо он определяется только разрядностью адреса. Для 32-разрядных процессоров этот размер равен 2 32 = 4 Гб. В настоящее время трудно представить программу, которой может всерьез понадобиться столько памяти, да и компьютер с таким объемом памяти – вещь не рядовая[12]. На самом деле, программа обычно использует лишь небольшую часть своего адресного пространства, не более нескольких десятков или, в крайнем случае, сотен мегабайт. Только эти используемые страницы и должны быть отображены на физическую память. Тем не менее, суммарный объем страниц, используемых всеми процессами в системе, обычно превосходит объем имеющейся физической памяти, поэтому использование страничного файла становится неизбежным.

Управление замещением страниц в физической памяти в современных РС строится по принципу загрузки по требованию (demand paging). Это означает следующее. Когда программа только лишь планирует использование определенной области виртуальной памяти (например, для хранения массива переменных, описанного в программе), соответствующие виртуальные страницы помечаются в таблице страниц как существующие, но находящиеся в данный момент на диске. В некоторых системах при этом за виртуальной страницей действительно закрепляются конкретные блоки в страничном файле, хотя из соображений экономии дисковой памяти это можно сделать позже, когда реально потребуется записать страницу на диск. Выделение страниц физической памяти не выполняется до тех пор, пока программа не обратится к одной из ячеек виртуальной страницы. При этом происходит аппаратное прерывание по отсутствию страницы в памяти. Это прерывание обрабатывает часть ОС, которая называется менеджером памяти. Менеджер должен выполнить следующие действия:

· найти свободную физическую страницу;

· если свободной страницы нет (а ее чаще всего нет), то по определенному алгоритму выбрать занятую страницу, которая будет вытеснена на диск;

· на освободившуюся физическую страницу прочитать блок страничного файла, закрепленный за запрошенной виртуальной страницей;

· повторить обращение к запрошенному виртуальному адресу, теперь уже присутствующему в физической памяти.

Последующие обращения к виртуальным адресам той же страницы будут успешно выполняться, пока страница не будет, в свою очередь, вытеснена на диск.

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

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

Менеджер памяти работает в иной ситуации. Обращения к памяти происходят с огромной частотой, при выполнении почти каждой команды процессора. Абсолютно нереально при каждом обращении предпринимать какие-то программные действия. Из этого следует, что алгоритм выбора вытесняемой страницы должен опираться на аппаратную поддержку. Поскольку алгоритм LRU не так просто реализовать аппаратно, вместо него часто используют алгоритмы, более простые в реализации, пусть даже они менее эффективны.

Недостатком страничной организации является то, что при большом объеме виртуального адресного пространства сама таблица страниц должна быть очень большой. При размере страницы 4 Кб и адресном пространстве 4 Гб таблица должна содержать миллион записей! Однако вряд ли программа процесса постоянно использует весь огромный диапазон адресов. Как правило, на каждом интервале времени интенсивно используются только некоторые части таблицы страниц (это еще одно проявление локальности ссылок). Желательно иметь возможность вытеснять на диск временно неиспользуемые части таблицы страниц. Такая возможность в современных процессорах обеспечивается использованием более сложной, двухуровневой схемы страничной адресации. В этой схеме все адресное пространство делится на разделы равной величины, каждый из которых описывается отдельной небольшой таблицей страниц. Имеется также каталог таблиц страниц, который описывает текущее состояние каждой таблицы точно так же, как сама таблица страниц описывает состояние страниц памяти. Те таблицы страниц, которые долго не используются, вытесняются на диск и соответствующим образом помечаются в каталоге. Виртуальный адрес делится не на две, а на три части. Старшие разряды адреса указывают позицию таблицы в каталоге, средние разряды – позицию страницы в таблице, младшие – смещение адреса от начала страницы.

· найти свободную физическую страницу;

· повторить обращение к запрошенному виртуальному адресу, теперь уже присутствующему в физической памяти.

Страничная организация (paging) – стратегия управления памятью , при которой:

логическая память делится на страницы – смежные области одинаковой длины, обычно – степень 2 (например, 512 слов);
физическая память , соответственно, делится на фреймы такого же размера;
распределение логической памяти происходит с точностью до страницы;
физическая память процесса может не быть непрерывной;
связь между логической и физической памятью процесса осуществляется с помощью таблицы страниц – системной структуры, выделяемой процессу для трансляции его логических адресов в физические.

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

Цели страничной организации – обеспечить возможность не смежного распределения физической памяти для процессов, а также расширить пространство логической памяти.

При страничной организации логический адрес обрабатывается системой особым образом – как структура (p, d):его старшие разряды обозначают номер страницы, младшие – смещение внутри страницы. Номер страницы (p) трактуется как индекс в таблице страниц, соответствующий элемент которой содержит базовый адрес начала страницы в физической памяти. Смещение внутри страницы (d) добавляется к ее базовому адресу. В результате формируется физический адрес , передаваемый в устройство управления памятью .

Архитектура трансляции адресов при страничной организации изображена на рис. 16.3.

На рис. 16.4 приведен пример страничной организации , который демонстрирует, что, в отличие от непрерывной логической памяти процесса, соответствующие фреймы страниц в основной памяти могут быть расположены не смежно: логической странице 0 соответствует фрейм 1, странице 1 – фрейм 4, странице 2 – фрейм 3, странице 3 – фрейм 7.

На рис. 16.5 приведен другой возможный пример страничной организации : логическая и физическая память разбита на блоки по 4 страницы подряд; в таблице страниц хранится не номер страницы, а номер блока страниц. Например, в элементе 0 таблицы страниц хранится номер блока 5, по которому адрес начала блока вычисляется домножением содержимого элемента таблицы страниц на размер блока, равный 4 (результат – 20).

Использования списка свободных фреймов иллюстрируется на рис. 16.6.

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

Страничная организация памяти основана на том, что физическое и виртуальное адресные пространства разбиваются на фрагменты постоянной длины. Размер страницы выбирается кратным степени 2, т.к. это позволяет максимально просто выполнять преобразование ВА в ФА на аппаратном уровне. Наиболее распространенный размер страницы равен 212 = 4096 байт. Все страницы нумеруются от 0 до N. Тем самым ВАП состоит из 232 / 212 = 220 = 1 Мбайт страниц, а число реальных физических страниц зависит от размера установленной памяти.

Так, для объема основной памяти 128 Мб получим 32 Кбайт страниц. Можно сказать, что страница – это просто некоторый диапазон адресов: страница 0 определяет адреса от 0 до 4095 (или 0FFFh), страница 1 – от 4096 до 8191 (или от 1000h до 1FFFh), страница 2 – от 8192 до 12287 (от 2000h до 2FFFh) и т.д. Видно, что номер страницы однозначно определяет соответствующий этой странице диапазон адресов.

При создании транслятором исполняемого машинного кода назначение виртуальных адресов командам и элементам данных начинается с нулевой страницы и идет в порядке следования страниц. Каждый виртуальный адрес задается номером страницы Nv и смещением Sv относительно начала страницы: ВА = (Nv , Sv).

Если размер страницы равен 4096 байт, то смещение для любой страницы будет принимать значения от 0 до 4095. Тем самым полный 32-х разрядный виртуальный адрес разбивается на две составляющие: младшие 12 разрядов (т.е. 3 полубайта) определяют смещение на странице, а старшие 20 разрядов (5 полубайтов) определяют номер страницы. Например, виртуальный адрес 002A4C38 разбивается следующим образом

Поскольку ВАП и ФАП разбиты на страницы совершенно одинаково, замена ВА на ФА сводится только к замене номера страницы, смещение при этом остается неизменным! Это является важнейшим преимуществом страничной организации и одной из основных причин столь высокой популярности этого способа организации памяти в современных ОС. Замена номера страницы в виртуальном адресе сводится к действиям с отдельными битами и чрезвычайно эффективно выполняется на аппаратном уровне.

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

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

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

Если при запуске процесса в основной памяти нет достаточного количества свободных страниц, чтобы разместить весь код и данные, то загружается только часть страниц, остальные сохраняются на диске и в таблице страниц помечаются как отсутствующие. При необходимости любая отсутствующая страница может быть загружена в память с назначением ей свободной физической страницы. Наоборот, система может вытеснить на диск часть или даже все страницы процесса. Такой обмен страницами между основной и дисковой памятью называют страничным обменом, или своппингом (swap – обмен). Часто перемещаемые на диск страницы сохраняются в специальном файле, называемом страничным файлом, или файлом подкачки. Каждая такая операция сопровождается соответствующими изменениями в таблице страниц.

Алгоритм преобразования ВА в ФА можно представить следующим образом. Пусть при выполнении некоторой команды процессору необходимо обратиться к памяти по виртуальному адресу. Тогда система, используя реализованную в процессоре аппаратную поддержку, выполняет следующее:

из виртуального адреса выделяется номер виртуальной страницы;
с помощью системного регистра производится обращение к текущей таблице страниц; из таблицы по номеру виртуальной страницы выбирается запись-дескриптор;
анализируется признак присутствия данной страницы в памяти;
если страница отображена в память, то из дескриптора извлекается номер назначенной физической страницы, который заменяет номер виртуальной страницы, и тем самым формируется реальный физический адрес;
если страницы в памяти нет, то генерируется так называемое страничное прерывание, обработчик которого должен найти на диске и загрузить в память необходимую страницу;
на время выполнения этих действий процессор может переключиться на обработку другого потока;
если при загрузке нужной виртуальной страницы для нее есть свободная физическая страница, то загрузка выполняется, в таблицу страниц заносится соответствующий номер, устанавливается признак присутствия страницы и вычисляется физический адрес;
если ни одной свободной страницы нет, то система вынуждена:

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

выбрать страницу, к которой было меньше всего обращений;
выбрать страницу, которая не использовалась дольше всех.

большие накладные расходы на поддержку таблиц страниц: одна таблица может требовать нескольких мегабайт памяти для своего хранения;
разбиение кода и данных на виртуальные страницы носит механический характер и никак не учитывает логическую структуру построения программы; это может приводить, например, к тому, что начало кода некоторой подпрограммы будет находиться на одной странице, а конец – на другой, что приведет к лишним страничным прерываниям при выполнении единой подпрограммы.

Читайте также: