Оптимизация функционирования страничной виртуальной памяти

В настоящее время известно несколько методов повышения эффективности функционирования страничной виртуальной памяти. К ним относятся [17]:

1. более сложная структуризация виртуального адресного пространства, например, двухуровневая (типичная для 32-битовой адресации);
2. использование специального высокоскоростного кэша для хранения части записей таблицы страниц, который обычно называют буфером быстрого преобразования адреса, или буфером поиска трансляции (translation lookaside buffer – TLB);
3. выбор оптимального размера страницы виртуальной памяти;
4. эффективное управление страничным обменом.

Остановимся на возможностях реализации этих методов.

Рассмотрим вариант двухуровневой страничной организации. При такой схеме имеется каталог таблиц страниц, в котором каждая запись указывает на таблицу страниц. Таким образом, если размер каталога – X, а максимальный размер таблицы страниц – Y, то процесс может состоять максимум из X и Y страниц. Обычно максимальный размер таблицы страниц определяется условием ее размещения на одной странице (такой подход используется в процессоре Pentium).

На рис. 6.12 приведен пример двухуровневой схемы, типичной для 32-битовой адресации. Подобная схема позволяет существенно сохранить размер пользовательской таблицы страниц, размещаемой в основной памяти (с 4 Мбайт до 4 Кбайт). В данном случае виртуальное адресное пространство пользовательского процесса может составлять 2³² = 4 Гбайт. При объеме страницы 2¹² = 4 Кбайт в этом пространстве размещается 2³² / 2¹² = 2²⁰ страниц. Таким образом, пользовательская таблица страниц будет иметь 2²⁰ 4-байтных записей общим объемом 4 Мбайт. Разместить такие таблицы для нескольких процессов в ОП нереально. В двухуровневой схеме это и не требуется. В основной памяти постоянно находится корневая таблица, содержащая 1024 записей, указывающих на начальный адрес пользовательской таблицы страниц (ее объем, как указано выше, 4 Мбайт). Указание на начальный адрес корневой таблицы (активного процесса) заносится в регистр процессора. Первые 10 бит виртуального адреса используются для индексации в корневой таблице для поиска записей о странице пользовательской таблицы.

Рис. 6.12. Двухзвенная схема таблиц страниц

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

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

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

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

Рис. 6.13. Буфер быстрой переадресации

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

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

В организации TLB имеется ряд особенностей. Поскольку TLB содержит только некоторые из записей таблицы страниц (32 в процессоре Pentium), индексация записей в TLB на основе номера страницы не представляется возможной. Вместо этого каждая запись TLB должна наряду с полной информацией из записи таблицы страниц включать также номер виртуальной страницы. Процессор аппаратно способен одновременно опрашивать все записи TLB для определения того, какая из них соответствует заданному номеру страницы. Такой подход известен как ассоциативное отображение (associative mapping), в отличие от прямого отображения, или индексирования, применяемого для поиска в таблице страниц, как показано на рис. 6.14.

Рис. 6.14. Ассоциативная память

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

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

Рис. 6.15. Использование кэша оперативной памяти

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

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

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

Рис. 6.16. Изменение частоты страничных прерываний

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

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

Реально размеры страниц различных компьютеров составляют следующие значения: 512 байт (семейство VAX, IBM AS/400), 4 Кбайт (IBM 370, MIPS), 8 Кбайт (DEC Alpha), от 4 Кбайт до 4 Мбайт (Pentium).

Решение об используемом размере страниц связано также с размером физической памяти и размером программы. Нужно также учитывать тот факт, что современные технологии программирования приводят к снижению локализации ссылок процесса. Например, объектно-ориентированные технологии стимулируют применение множества мелких модулей кода и данных с обращениями к большому количеству объектов за относительно короткое время (если программа на языке С для небольших задач занимает 3 – 4 Кбайт, то та же программа на Visual С++ займет сотни Кбайт). Многопоточные приложения приводят к внезапным изменениям в потоке команд и обращениям к памяти, разбросанным по сильно отличающимся адресам.

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

Учитывая все эти обстоятельства, в рядах компьютеров применяются множественные размеры страниц (что, однако, весьма сложно как в аппаратном аспекте, так и в программном в части операционной системы). Множественные размеры страниц обеспечивают гибкость, необходимую для использования TLB. Большие непрерывные области адресного пространства процесса, например программный код, могут отображаться с использованием небольшого количества страниц, в то время как стеки потоков могут использоваться для отображения страницы малого размера.

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

Для управления страничным обменом нужно решить следующие задачи [10, 17]:

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

В соответствии с этими задачами ниже перечислены стратегии ОС для управления виртуальной памятью.

Наименование	Возможные алгоритмы (решения)
Стратегия выборки (когда?)	По требованию, предварительная выборка
Стратегия размещения (где?)	Первый подходящий раздел (для сегментной виртуальной памяти). Любая страница физической памяти (для сегментно-страничной и страничной организации виртуальной памяти)
Стратегия замещения (какие?)	Оптимальный выбор, дольше всех неиспользовавшиеся. Первым вошел – первым вышел (FIFO), часовой, буферизация страниц
Управление резидентным множеством (сколько?)	Фиксированный размер, переменный размер, локальная и глобальная области видимости
Стратегия очистки (когда?)	По требованию, предварительная очистка
Управление загрузкой (сколько?)	Рабочее множество, критерии L=S и 50%

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

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

Предварительная выборка планируется программистом при разработке программы. Тем не менее, выгодность предварительной выборки не доказана.

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

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

Стратегия замещения определяет выбор страниц в основной памяти для замещения их загружаемыми из вторичной памяти страницами. Эта стратегия связана с решением следующих вопросов:

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

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

• оптимальный алгоритм;
• алгоритм дольше всех не использующейся страницы;
• алгоритм "первым вошел – первым вышел" (FIFO);
• часовой алгоритм и др.

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

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

Хотя алгоритм дольше всех не использующейся страницы близок к оптимальному, он труден в реализации и приводит к значительным накладным расходам. Разработано достаточно много алгоритмов, основанных на данной стратегии, многие из них представляют собой варианты схемы, известной как часовая стратегия (clock policy).

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

Рис. 6.17. Часовая стратегия замещения

При замещении страницы указатель перемещается к следующему кадру в буфере. Когда наступает время замещения страницы, ОС сканирует буфер для поиска кадра, бит использования которого равен 0. При этом когда в процессе поиска встречается кадр с битом использования, равным 1, он сбрасывается в 0. Первый же встречный кадр с нулевым битом использования выбирается для замещения. Если все кадры имеют бит использования, равный 1, указатель совершает полный круг и возвращается к начальному положению, заменяя страницу в этом кадре. Буфер кадров страниц представлен в виде круга, напоминающего часы, откуда и произошло название стратегии.

На рис. 6.17 приведен простейший пример использования часовой стратегии. Для замещения доступны n-1 кадров основной памяти, представленных в виде циклического буфера. Непосредственно перед тем как заместить страницу в буфере загружаемой из вторичной памяти страницей 11, указатель буфера указывает на кадр 1, содержащий страницу 1. Приступаем к выполнению часового алгоритма. Поскольку бит использования страницы 17 в кадре 2 равен 1, эта страница не замещается. Бит ее использования сбрасывается, а указатель перемещается к следующему кадру 3. Здесь находится страница 19, бит использования которой равен 0. Эта страница выбирается для замещения. На ее место загружается страница 11, бит использования которой переводится в 1. Указатель переводится на следующий кадр 4, и на этом выполнение алгоритма завершается. Повысить эффективность часового алгоритма можно путем увеличения количества используемых при его работе битов [17].