Страничная память (Операционные Системы)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:49, 24 августа 2017.

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

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

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

  • Поддержка изоляции процессов и защиты памяти путём создания своего собственного виртуального адресного пространства для каждого процесса
  • Поддержка изоляции области ядра от кода пользовательского режима
  • Поддержка памяти «только для чтения» и неисполняемой памяти
  • Поддержка отгрузки давно не используемых страниц в область подкачки на диске
  • Поддержка отображённых в память файлов, в том числе загрузочных модулей
  • Поддержка разделяемой между процессами памяти, в том числе с копированием-по-записи для экономии физических страниц
  • Поддержка системного вызова fork() в ОС семейства UNIX
  • Уменьшение внешней фрагментации – использование блоков фиксированного размера в виртуальной и физической памяти, все запросы на выделение памяти будут кратны, не будет оставаться некратных зон.

Механизм работы

В самом простом и наиболее распространенном случае страничной организации памяти (или paging) как логическое адресное пространство, так и физическое представляются состоящими из наборов блоков или страниц одинакового размера. При этом образуются логические страницы(page), а соответствующие единицы в физической памяти называют физическими страницами или страничными кадрами (page frames).Страницы (и страничные кадры) имеют фиксированную длину, обычно являющуюся степенью числа 2, и не могут перекрываться. Каждый кадр содержит одну страницу данных. При такой организации внешняя фрагментация отсутствует, а потери из-за внутренней фрагментации, поскольку процесс занимает целое число страниц, ограничены частью последней страницы процесса.

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

Преобразование адресов в страничной памяти

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

Число записей в одной таблице ограничено и зависит от размера записи и размера страницы. Используется многоуровневая организация таблиц, часто 2 или 3 уровня, иногда 4 уровня (для 64-разрядных архитектур).

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

Управление страничным разбиением памяти обычно возлагается на специальную микросхему MMU (Memory Managment Unit - устройство управления памятью). В микропроцессоре i80486 и выше это устройство встроено в процессор.

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

В процессе страничного преобразования старшие 20 бит 32-х битного линейного адреса заменяются новым значением - номером физической страницы. Младшие же 12 бит линейного адреса определяют положение байта внутри страницы и остаются неизменными.

Для уменьшения размера таблицы страниц в микропроцессорах x86 предусмотрена двухуровневая схема преобразования адреса. Основой страничного преобразования служит регистр управления CR3, содержащий 20-ти битный физический базовый адрес каталога страниц текущей задачи. Предполагается, что каталог выровнен по границе страничного кадра, постоянно находится в памяти и не участвует в свопинге. Корневая страница, называемая каталогом страниц, содержит 1024 32-х битных дескриптора, называемых элементами каталога страниц PDE (Page Directory Entry). Каждый из них адресует подчиненную таблицу страниц. Каждая из этих таблиц содержит 1024 32-х битных дескриптора, называемая элементами таблицы страниц. PTE (Page Table Entry). Каждый PTE содержит адрес страничного кадра в физической памяти. Собственно преобразование линейных адресов в физические состоит из следующих действий:

  • Старшие 10 бит 31 - 22 линейного адреса, дополненные двумя младшими нулями, служат индексом PDE.
  • Средние 10 бит 21 - 12 линейного адреса, дополненные двумя младшими нулями, индексируют таблицу страниц PTE. Элемент PTE содержит 20-битный базовый адрес страничного кадра в физической памяти.

Этот базовый адрес из элемента PTE объединяется с младшими 12-ю битами линейного адреса, образуя 32-х битный физический адрес.

Страничная память x86

Исторически x86 использует 32-битные PTE, 32-битные виртуальные адреса, 4KB-страницы, 1024 записи в таблице, двухуровневые таблицы. Старшие 10 бит виртуального адреса — номер записи в директории, следующие 10 — номер записи в таблице, младшие 12 — адрес внутри страницы.[2]

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

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

Страничное прерывание

Если обращение к памяти не может быть оттранслировано через TLB, то микрокод процессора обращается к таблицам страниц и пытается загрузить PTE оттуда в TLB. Если и после такой попытки сохранились проблемы, то процессор исполняет специальное прерывание, называемое «отказ страницы» (page fault).[3] Обработчик этого прерывания находится в подсистеме виртуальной памяти ядра ОС.
Обработка прерываний по отказу из-за недоступности данных.

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

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

Алгоритм работы страничного прерывания:

  1. Когда страница выгружается, ОС устанавливает бит присутствия (valid – является ли валидной ячейка) PTE=0. И там же в РТЕ записывает куда она была соответственно выгружена.
  2. Когда же процесс обращается к этой странице, то происходит исключение, т.к. Valid=0,т.е. бит валидности установлен в 0 – страница не использовалась.
  3. После того, как произошло исключение ОС передает управление обработчику страничного прерывания
  4. Обработчик находит то место, куда была выгружена страница
  5. Считывает эту страницу в фрейм физической памяти, обновляет РТЕ, ставит бит валидности (присутствия) в 1.
  6. В физической памяти появляется новая страница.

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

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

Таблица страниц (Page Table) состоит из 4-байтовых элементов (Entries). Эти элементы называются PTE (Page Table Entries) и представляют собой по сути - указатели на страницы, по формату - структуры данных.
Структура таблицы:

  1. P (Present - присутствие). Если 0, то страница не отображена на физическую память. Это значит, что она либо не определена, либо её содержимое было записано на диск операционной системой в процессе свопинга. Если происходит обращение к неприсутствующей странице (у которой бит P = 0), то процессор генерирует исключение страничного нарушения (#PF). Соответствует нулевому биту.
  2. R / W (Read / Write - Чтение / Запись). Если 0, то для этой страницы разрешено только чтение, 1 - чтение и запись.
  3. U / S (User / Supervisor - Пользователь / Система). Если 0, то доступ к странице разрешён только с нулевого уровня привилегий, если 1 - то со всех.
  4. PWT (Write-Through - Сквозная запись). Когда этот флаг установлен, разрешено кэширование сквозной записи (write-through) для данной страницы, когда сброшен - кэширование обратной записи (write-back).
  5. PCD (Cache Disabled - Кэширование запрещено). Когда установлен, кэширование данной страницы запрещено. Кэширование страниц запрещают для портов ввода/вывода, отображённых на память либо в случаях, когда кэширование не даёт выигрыша в производительности. Также, кэширование запрещается при обработке исключений и отладке в ситуациях, связанных с программированием кэшей.
    Формат элемента таблицы страниц
  6. A (Accessed - Доступ). Устанавливается процессором каждый раз, когда он производит обращение к данной странице. Процессор не сбрасывает этот флаг - его может может сбросить программа, чтобы потом, через некоторое время определить, был ли доступ к этой странице, или нет.
  7. D (Dirty - Грязный). Устанавливается каждый раз, когда процессор производит запись в данную страницу. Этот флаг также не сбрасывается процессором и может использоваться программой, чтобы определить, была ли запись в страницу или нет.
  8. PAT (Page Table Attribute Index - Индекс атрибута таблицы страниц). Для процессоров, которые используют таблицу атрибутов страниц (PAT - page attribute table), этот флаг используется совместно с флагами PCD и PWT для выбора элемента в PAT, который выбирает тип памяти для страницы. Этот бит введён в процессоре Pentium III, а для процессоров, не использующих PAT, бит PAT должен быть равен 0.
  9. G (Global Page - Глобальная страница). Когда установлен, определяет глобальную страницу. Такая страница остаётся достоверной в кэшах TLB при перезагрузке регистра CR3 или переключении задач. Этот бит был введён в Pentium Pro, для процессоров младше Pentium Pro, этот бит зарезервирован и должен быть равен 0.
  10. Биты с 9 по 11 не используются процессором.
  11. Биты с 12 по 31 несут в себе базовый адрес страницы, с которого начинается страница, другими словами - это физический адрес, на который отображена данная страница.

Если страница не присутствует в памяти (бит P=0), то процессор не использует все остальные биты элемента PTE и программа может их использовать по своему усмотрению.

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

Каждый процесс имеет свой собственный набор таблиц страниц. Регистр «директория страниц» перегружается при каждом переключении контекста процесса. Также необходимо очистить ту часть TLB, которая относится к этому процессу.

В большинстве случаев ядро ОС помещается в то же адресное пространство, что и процессы, для него резервируется верхние 1-2 гигабайта 32-битного адресного пространства каждого процесса. Целью этих действий является предотвращение переключению таблиц страниц при входе в ядро на выходе из него. Страницы ядра помечаются как недоступные для кода режима пользователя.

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

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

Работа менеджера памяти Windows

Для управления виртуальной памятью в операционной системе Windows предусмотрен специальный менеджер Virtual Memory Manager (VMM). Он является составной частью ядра операционной системы и представляет собой отдельный процесс, постоянно находящийся в оперативной памяти. Основная задача VMM заключается в управлении страницами виртуальной памяти.[4]

Каждому процессу VMM выделяет часть физической памяти, которая называется рабочим набором (Working Set). Кроме того, VMM создает базу состояния страниц (page-frame database), которая организована как шесть списков страниц одного типа. Выделяют следующие типы страниц:

  • Valid — рабочая страница используется процессом. Такие страницы памяти реально существуют в физической памяти. Если процесс освобождает страницу памяти, то VMM убирает ее из списка Valid. Если процесс пытается обратиться к странице, которой нет в списке Valid, то происходит страничное прерываниие и VMM может отвести процессу новую страницу. Страницы типа Valid в таблице страниц описываются как присутствующие (P = 1);
  • Modified — модифицированная страница, то есть страница, содержимое которой было изменено. В таблице страниц данные страницы отмечаются как отсутствующие (P = 0) и переходные (T = 1);
  • Standby — резервная страница, содержимое которой не изменялось. В таблице страниц такие страницы отмечаются как отсутствующие (P = 0) и переходные (T = 1);
  • Free — свободная страница, на которую не ссылается ни один рабочий набор и которой нет ни в одной таблице страниц. В список Free помещаются страницы, которые освободились после окончания процесса.

Свободные страницы могут применяться, однако прежде они подлежат процедуре обнуления (заполнения нулями). Процедурой обнуления страниц занимается специальная подпрограмма менеджера памяти Zero Page Thread;

  • Zeroed — пустая страница, которая является свободной и обнуленной. Такие страницы готовы к использованию любым процессом;
  • Bad — страница, которая вызывает аппаратные ошибки и не может применяться ни одним процессом.

Как уже отмечалось, если какой-нибудь процесс обращается к странице, которой нет в рабочем наборе (в списке Valid), то возникает ошибка обращения к странице. В этом случае задача VMM заключается в том, чтобы разрешить данную ситуацию и выделить странице свободной физической памяти для хранения данных, к которым обратился процесс. Существует два варианта развития событий:

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

В идеале замещению должна подлежать та страница, к которой в будущем не будет обращений, или страница, которая не будет использоваться дольше других. Однако достоверного способа определить, какая именно страница отвечает перечисленным критериям, нет. Поэтому менеджер памяти применяет следующий алгоритм. Он периодически просматривает список рабочих страниц (Valid) и помечает их как отсутствующие (P = 0). Однако данные страницы не удаляются из рабочего процесса — они остаются на месте и просто переводятся из категории Valid в категорию модифицированных (Modified) или резервных (Standby) страниц ( никаких изменений в содержимом этих страниц не производится). Если измененная таким образом страница требуется какому-нибудь процессу, то происходит обращение к ней и возникает ошибка обращения к странице. Но поскольку в действительности страница находится в физической памяти и ее содержимое не подвергалось изменению, то менеджеру памяти достаточно перевести данную страницу обратно в категорию Valid, сделав ее доступной для процесса. Если же страница не используется в течение длительного времени процессами и обращений к ней не происходит, она со временем переводится в категорию свободных (Free) страниц, а затем обнуляется и переводится в категорию пустых (Zeroed) страниц.

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

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

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

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

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

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

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

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

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

Существуют две другие схемы организации управления памятью: сегментная и сегментно-страничная.[5] Сегменты, в отличие от страниц, могут иметь переменный размер. При сегментной организации виртуальный адрес является двумерным как для программиста, так и для операционной системы, и состоит из двух полей – номера сегмента и смещения внутри сегмента. Главное отличие сегментной организации от страничной в том, что в последней линейный адрес преобразован в двумерный операционной системой для удобства отображения, а сегментной двумерность адреса является следствием представления пользователя о процессе не в виде линейного массива байтов, а как набор сегментов переменного размера.

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

Каждый сегмент – линейная последовательность адресов, начинающаяся с 0. Максимальный размер сегмента определяется разрядностью процессора (при 32-разрядной адресации это 232 байт или 4 Гбайт). Размер сегмента может меняться динамически (например, сегмент стека). В элементе таблицы сегментов помимо физического адреса начала сегмента обычно содержится и длина сегмента. Если размер смещения в виртуальном адресе выходит за пределы размера сегмента, возникает исключительная ситуация.

Сегментно-страничное преобразование адресов

Логический адрес – упорядоченная пара v=(s,d), номер сегмента и смещение внутри сегмента.

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

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

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

Примечания

  1. Страничная память [Электронный ресурс] : Материал из Википедии — свободной энциклопедии : Версия 78062763, сохранённая в 02:32 UTC 29 апреля 2016 / Авторы Википедии // Википедия, свободная энциклопедия. — Электрон. дан. — Сан-Франциско: Фонд Викимедиа, 2016. — Режим доступа: http://ru.wikipedia.org/?oldid=78062763
  2. Материал из электронного ресурса - Формирование адреса при страничном преобразовании - Режим доступа[2]
  3. Материал из электронного ресурса - Страничное прерывание - Режим доступа[3]
  4. Материал из электронного ресурса - Принцип работы менеджера памяти - Режим доступа[4]
  5. Материал из электронного ресурса - Сегментная и сегментно-страничная организация памяти - Режим доступа[5]