 |
|
Архитектурные средства поддержки виртуальной памяти.
Очевидно, что невозможно создать полностью машинно-независимый компонент управления виртуальной памятью. С другой стороны, имеются существенные части программного обеспечения, связанного с управлением виртуальной памятью, для которых детали аппаратной реализации совершенно не важны. Одним из достижений современных ОС является грамотное и эффективное разделение средств управления виртуальной памятью на аппаратно-независимую и аппаратно-зависимую части. Коротко рассмотрим, что и каким образом входит в аппаратно-зависимую часть подсистемы управления виртуальной памятью. Компоненты аппаратно-независимой подсистемы рассмотрены в следующей главе.
Итак, мы имеем большое (для 32-разрядных архитектур это обычно 2**32 = 4 Гб) виртуальное адресное пространство и физическое пространство существенно меньшего размера. Пользовательский процесс или ОС должны иметь возможность осуществить запись по виртуальному адресу, а задача ОС сделать так, чтобы записанная информация оказалась в физической памяти (впоследствии при нехватке оперативной памяти она может быть вытеснена во внешнюю память).
Таким образом, важный компонент менеджера виртуальной памяти система или функция отображения (трансляции) адресов. Механизм преобразования виртуальных адресов в физические должен предусматривать ведение таблиц, показывающих, какие области виртуальной памяти в текущий момент находятся в физической памяти и где именно размещаются. Если бы такое отображение осуществлять побайтно, то информация об отображении была бы велика, и для ее хранения потребовалось бы больше реальной памяти, чем для процессов. Необходим способ, позволяющий существенно сократить объем информации отображения. Поэтому обычно отображаемая информация группируется в блоки (программа занимает целое количество блоков памяти).
Страничная память
В наиболее простом и наиболее часто используемом случае страничной виртуальной памяти виртуальная память и физическая представляются состоящими из наборов блоков или страниц одинакового размера. Виртуальные адреса делятся на страницы (page), соответствующие единицы в физической памяти образуют страничные кадры (page frames), а в целом система поддержки страничной виртуальной памяти называется пейджингом (paging). Передача информации между памятью и диском всегда осуществляется целыми страницами. Страницы, в отличие от сегментов, имеют фиксированную длину, обычно являющуюся степенью числа 2, и не могут перекрываться.
Виртуальный адрес в страничной системе упорядоченная пара (p,d), где p - номер страницы в виртуальной памяти, а d - смещение в рамках страницы p, где размещается адресуемый элемент. Процесс может выполняться, если его текущая страница находится в оперативной памяти. Если текущей страницы в главной памяти нет, она должна быть переписана (подкачана) из внешней памяти. Поступившая страница может быть размещена в любой свободный страничный кадр. Система отображения виртуальных адресов в физические сводится к системе отображения виртуальных страниц в физические и представляет собой таблицу страниц.
Для преобразования адресного пространства каждого процесса используется одна или несколько таблиц страниц, которые обычно хранятся в оперативной памяти. Для ссылки на таблицу страниц используется специальный регистр процессора. Особенности хранения таблицы страниц описаны ниже. Интерпретация виртуального (логического) адреса показана на рис. 9.1
Рис. 9.1 Связь логического и физического адресов при страничной организации памяти.
Динамическое преобразование адресов в системе осуществляется следующим образом. Выполняемый процесс обращается по виртуальному адресу v = (p,d). Механизм отображения ищет номер страницы p в таблице отображения и определяет, что эта страница находится в страничном кадре p', формируя реальный адрес из p' и d.
Например, в машинной инструкции move reg,0, адрес 0 находится на первой виртуальной странице, которая может быть локализована, во втором страничном кадре. В реальных системах функция отображения хранит бит присутствия страницы в физической памяти. При отсутствии страницы в памяти возникает исключительная ситуация, называемая страничное нарушение (page fault). Обработка страничного нарушения приводит к тому, затребованная страница подкачивается из конкретного места вторичной памяти в свободный страничный кадр физической памяти и продолжается прерванный код. При отсутствии свободных страничных кадров на диск выгружается мало используемая страница.
Номер страницы, как индекс хранится в таблице страниц (page table), которая адресуется при помощи специального регистра процессора, и позволяет определить номер кадра по виртуальному адресу. Помимо этой основной задачи при помощи атрибутов, записанных в строке таблицы страниц, можно организовать контроль доступа к конкретной странице и ее защиту.
Используя схему пэйджинга, мы не имеем внешней фрагментации. Однако сталкиваемся с внутренней фрагментацией: адресное пространство процесса занимает целое число страниц, и в среднем половина страницы на процесс пропадает.
Важный аспект - различие точек зрения пользователя и системы на используемую память. С точки зрения пользователя его память - единое непрерывное пространство, содержащее, только одну программу. Реальное отображение скрыто от пользователя и контролируется ОС. Заметим, что процессу пользователя недоступна чужая память. Он не имеет возможности адресовать память за пределами своей таблицы страниц, которая включает только его собственные страницы.
Для управления физической памятью ОС поддерживает структуру таблицы кадров. Она имеет одну запись на каждый физический кадр, показывающий его состояние.
Отображение должно происходить корректно даже в сложных случаях. ОС поддерживает одну или несколько (при наличии нескольких сегментов памяти) таблиц страниц для каждого процесса, для ссылки, на которую, как уже говорилось, обычно используется специальный регистр. При переключении процессов диспетчер должен найти его таблицу страниц, указатель на которую, таким образом, входит в контекст процесса.
В большинстве современных компьютеров со страничной организацией виртуальной памяти все таблицы страниц хранятся в основной памяти, а быстрота доступа к элементам таблицы текущей виртуальной памяти достигается, как будет показано ниже, за счет наличия сверхбыстродействующей буферной памяти (кэша).
11. Сегментная и сегментно-страничная организации памяти
Существуют две другие схемы организации виртуальной памяти: сегментная и сегментно-страничная. Идеи сегментации изложены во введении к предыдущей главе. При сегментной организации виртуальный адрес по-прежнему является двумерным и состоит из двух полей - номера сегмента и смещения внутри сегмента. Заметим, что с точки зрения ОС сегменты являются логическими сущностями и их главное назначение хранение и защита однородной информации (кода, данных и т.д.).
С точки зрения пользователя процесс представляется обычно не как линейный массив байтов, а как набор сегментов переменного размера (данные, код, стек). Сегментация - схема управления памятью, поддерживающая этот взгляд пользователя. Сегменты содержат процедуры, массивы, стек или скалярные величины, но обычно не содержат информацию смешанного типа.
Программисты, пишущие на языках низкого уровня должны иметь представление о сегментной организации, явным образом меняя значения сегментных регистров (это хорошо видно по текстам программ, написанных на Ассемблере). Логическое адресное пространство - набор сегментов. Каждый сегмент имеет имя, размер и другие параметры (уровень привилегий, разрешенные виды обращений, флаги присутствия). Пользователь специфицирует каждый адрес двумя величинами: именем сегмента и смещением. (В отличие от схемы пэйджинга, где пользователь задает только один адрес, который разбивается hardware на номер страницы и смещение, прозрачным для программиста образом.)
Каждый сегмент - линейная последовательность адресов от 0 до максимума. Различные сегменты могут иметь различные длины, которые могут меняться динамически (например, сегмент стека). В элементе таблицы сегментов помимо физического адреса начала сегмента (если виртуальный сегмент содержится в основной памяти) содержится длина сегмента. Если размер смещения в виртуальном адресе выходит за пределы размера сегмента, возникает прерывание.
Логический адрес - упорядоченная пара v=(s,d), номер сегмента и смещение внутри сегмента.
В системах, где сегменты поддерживаются аппаратно, эти параметры обычно хранятся в таблице дескрипторов сегментов, а программа обращается к этим дескрипторам по номерам‑селекторам. При этом в контекст каждого процесса входит набор сегментных регистров, содержащих селекторы текущих сегментов кода, стека, данных и др. и определяющих, какие сегменты будут использоваться при разных видах обращений к памяти. Это позволяет процессору уже на аппаратном уровне определять допустимость обращений к памяти, упрощая реализацию защиты информации от повреждения и несанкционированного доступа.
Рис. 9.2 Преобразование логического адреса при сегментной организации памяти.
Аппаратная поддержка сегментов относительно слабо распространена (главным образом на процессорах архитектуры Intel) и характеризуется довольно медленной загрузкой селекторов в сегментные регистры, выполняемая при каждом переключении контекста и при каждом переходе между разными сегментами. В системах с чисто страничной организацией памяти для описания типового адресного пространства процесса, представляющего собой набор сегментов, сегментация реализуется на уровне, независимом от аппаратуры.
Хранение в памяти сегментов большого размера может оказаться неудобным. Возникает идея их пейджинга. При сегментно-страничной организации виртуальной памяти происходит двухуровневая трансляция виртуального адреса в физический. В этом случае виртуальный адрес состоит из трех полей: номера сегмента виртуальной памяти, номера страницы внутри сегмента и смещения внутри страницы. Соответственно, используются две таблицы отображения - таблица сегментов, связывающая номер сегмента с таблицей страниц, и отдельная таблица страниц для каждого сегмента.
Рис. 9.3 Формирование физического адреса при сегментно-страничной организации памяти.
Сегментно-страничная организация виртуальной памяти позволяла совместно использовать одни и те же сегменты данных и программного кода в виртуальной памяти разных задач (для каждой виртуальной памяти существовала отдельная таблица сегментов, но для совместно используемых сегментов поддерживались общие таблицы страниц).
Таблица страниц
Организация таблицы страниц один из ключевых элементов механизмов страничного и сегментно-страничного преобразований. Рассмотрим структуру таблицы страниц более детально.
Итак, виртуальный адрес состоит из виртуального номера страницы (high-order bits) и смещения (low-order bits). Номер виртуальной страницы используется как индекс в таблице страниц для нахождения записи (entry) о виртуальной странице. Из этой записи в таблице страниц находится номер кадра (page frame number), затем прибавляется смещение и формируется физический адрес. Помимо этого запись в таблице страниц содержит информацию об атрибутах страницы, в частности биты защиты.
Основную проблему для эффективной реализации таблицы страниц создают большие размеры виртуальных адресных пространств современных компьютеров, которые обычно определяются разрядностью архитектуры процессора. Самыми распространенными на сегодняшний день являются 32-разрядные процессоры, позволяющие создавать виртуальные адресные пространства такого размером 4 Гб (для 64-разрядных компьютеров эта величина равна 2**64б).
Подсчитаем примерный размер таблицы страниц. В 32-битном адресном пространстве при размере страницы 4К (Intel) получаем 1М страниц, а в 64-битном и того более. Т.о. таблица должна иметь 1М строк (entry), причем запись в строке состоит из нескольких байт. Заметим, что каждый процесс, нуждается в своей таблице страниц (а в случае сегментно-страничной схемы по одной на каждый сегмент). Итак, в этом случае таблица страниц может быть слишком большой.
Кроме того, отображение должно быть быстрым. Отображение должно быть быстрым т.к. оно делается при каждом обращении к памяти, которое происходи практически в каждой машинной инструкции. Эта проблема решается главным образом за счет реализации ассоциативной памяти (см. следующий раздел).
Для того чтобы избежать необходимости иметь огромную таблицу в памяти все время, а хранить лишь несколько ее фрагментов (это возможно опять же на основании свойства локальности!), многие компьютеры используют многоуровневую таблицу страниц.
Количество уровней в таблице страниц зависит от конкретных особенностей архитектуры. Можно привести примеры реализации одноуровневого (DEC PDP-11), двухуровневого (Intel, DEC VAX), трехуровневого (Sun SPARC, DEC Alpha) paging'а, а также paging'а с задаваемым количеством уровней (Motorola). Функционирование RISC процессора MIPS R2000 осуществляется вообще без таблицы страниц. Здесь поиск нужной страницы, если эта страница отсутствует в ассоциативной памяти, должна взять на себя ОС (так называемый zero level paging).
12. Стратегии управления страничной памятью. Алгоритмы замещения(выталкивания) страниц.
Обычно рассматривают три стратегии:
Стратегия выборки (fetch policy) - в какой момент следует переписать страницу из вторичной памяти в первичную. Выборка бывает по запросу и с упреждением. Алгоритм выборки вступает в действие в тот момент, когда процесс обращается к не присутствующей странице, содержимое которой в данный момент находится на диске (в своп файле или отображенном файле), и потому является ключевым алгоритмом свопинга. Он обычно заключается в загрузке страницы с диска в свободную физическую страницу и отображении этой физической страницы в то место, куда было произведено обращение, вызвавшее исключительную ситуацию.
Существует модификация алгоритма выборки, которая применяет еще и опережающее чтение (с упреждением), т.е. кроме страницы, вызвавшей исключительную ситуацию, в память также загружается несколько страниц, окружающих ее (так называемый кластер). Такой алгоритм призван уменьшить накладные расходы, связанные с большим количеством исключительных ситуаций, возникающих при работе с большими объемами данных или кода, кроме того, оптимизируется и работа с диском, поскольку появляется возможность загрузки нескольких страниц за одно обращение к диску.
Стратегия размещения (placement policy) - определить в какое место первичной памяти поместить поступающую страницу. В системах со страничной организацией в любой свободный страничный кадр (в системах с сегментной организацией - нужна стратегия, аналогичная стратегии с переменными разделами).
Стратегия замещения (replacement policy) - какую страницу нужно вытолкнуть во внешнюю память, чтобы освободить место. Разумная стратегия замещения позволяет оптимизировать хранение в памяти самой необходимой информации и тем самым снизить частоту страничных нарушений.