з

К предыдущей странице

л

К предыдущей главе

о

К следующей главе

и

К следующей странице


Введение. Обшие сведения.

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

1. Обшие сведения.

Основная (оперативная) память (ОП), из которой процессор выбирает для исполнения данные и команды, является дефицитным ресурсом наравне с центральным процессором (ЦП). В большинстве систем обем памяти, необходимой пользователю, превосходит имеющийся физический объем. Операционная система и вычислительная система в целом, следовательно, должны обладать возможностями логического расширения ресурса памяти и отображения логической памяти на физическую. Существуют различные способы такого отображения, т.е. построения так называемой виртуальной памяти. Эти способы определяют стратегию распределения памяти между несколькими процессами, одновременно использующими ОП. Классические схемы управления памятью описаны в литературе [1...5]. Основными из них являются следующие.


Рис.1. Схемы управления памятью

На выбор конкретной стратегии управления памятью при разработке программно-аппаратных средств ЭВМ оказывают вли- яние различные соображения:

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

Концептуально память делится на три основные области:

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

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

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

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

Другой подход заключается в создании такой ОС, которая обеспечивала бы иллюзию чрезвычайно большой памяти. Такая "иллюзорная" память называется виртуальной памятью.

В современных мультипрограммных системах наиболее часто реализуется один из основных способов управления виртуальной памятью - управление страничной памятью по запросам. При страничной организации памяти адресное пространство каждого задания делится на равные части, называемые страницами. Физическая память также делится на части одинакового размера, называемые блоками. При наличии соответствующих аппаратных средств преобразования адресов любая страница может быть помещена в любой блок памяти. Страницы программы пользователя остаются логически смежными, но соответствующие им блоки не всегда будут смежными. Важно заметить, что это преобразование не оказывает влияния на программы, т.е. не воздействует явно на адресное пространство задания. В аппаратных средствах, осуществляющих отображение адресного пространства на физическую память для каждой страницы должен быть предусмотрен специальный регистр. Совокупность этих регистров образует таблицу переадресации страниц (ТС). Эти регистры являются либо специальной частью аппаратуры, либо занимают часть основной памяти. Так как каждая страница может быть перемещена независимо от других страниц, то раздел, выделенный задаче, может не занимать непрерывный участок памяти. Непрерывность сохраняется в пределах одной страницы. Очевидно, что выбор размера страниц существенно влияет на применение этой схемы. Если размер страницы слишком велик и становится сравнимым с размером раздела, схема распределения страницами вырождается в схему с перемещаемыми разделами. Если размер страницы слишком мал, необходимо иметь много регистров переадресации, что существенно повышает стоимость вычислительной системы. В результате компромисса, учитывающего эти и другие требования, во многих системах со страничной организацией памяти используются страницы размером от 1К до 4К байтов.

На рис.2 приведен вариант схемы страничного распределения памяти.


Рис.2. Схема страничного распределения памяти (Авторские права - Емельянов С.В.)

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

Основными вопросами, которые решаются в системах со странич- ным распределением памяти являются следующие :

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

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

Если аппаратные средства преобразования адресов определяют по ТС, что бит, состветствующей страницы БС, имеет значение (-), то генерируется страничное прерывание (см.рис.3).


По таймеру интервалов Сбой страниц Переполнение рабочего набора Ошибка Страничное прерывание

Рис.3. Типы прерываний.

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

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

Копии полных адресных пространств заданий хранятся на внеш- нем запоминающем устройстве (ЗУ) (на пример, на магнитном диске - МД). Если страницу необходимо загрузить в память, она считывает- ся с внешнего ЗУ.

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

Обычно наиболее существенными в управлении страницами считаются три следующих направления:

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

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

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

Пусть x(t) есть страница, адресуемая в момент t. Тогда строку w = x(1), x(2), x(3),... x(Q) можно назвать строкой страничных ссылок или траекторией программы. Если принять, что b - это число заполненых в текущий момент страничных блоков в памяти B, тогда Q(b,t) представляет собой текущую конфигурацию программы пользователя в памяти.

В зависимости от текущей конфигурации программы Q(b,t) возможны три случая:

  • если страничная ссылка x(t) есть элемент Q(b,t-1) т.е. текущая страница находится в памяти, то никаких измене- ний в памяти не производится;
  • если страничная ссылка x(t) не принадлежит Q(b,t-1) и Q(b,t-1) меньше B, следовательно память не заполнена до конца страницами программы; тогда текущая страница загру- жается в память;
  • если x(t) не принадлежит Q(b,t-1) и Q(b,t-1)=B следовательно память полна и страницу необходимо заменить.

В этом третьем случае и подключаются алгоритмы замены. "Хороший" алгоритм замены старается минимизировать число обменных операций, необходимых для загрузки страницы в память. В литературе [ 1,5 ] описан ряд возможных алгоритмов. Некоторые из них реализованы в лабораторной работе. Студенту предоставляется возможность произвести оценку эффективности реализованных алгоритмов замены для различных конфигураций моделирующей системы.


з

К предыдущей странице

л

К предыдущей главе

о

К следующей главе

и

К следующей странице