2 3 2 1 5 2 4 5 3 2 5 2

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

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

На рис. 8.15 приведен пример выполнения алгоритма дольше всех неиспользовавшегося элемента с тем же потоком данных, что и для оптимального алгоритма.

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

На рис. 8.15 описанная стратегия приводит к шести прерываниям из-за отсутствия страницы. Заметим, что предыдущая стратегия распознает, что чаще других используются страницы 2 и 5. в то время как стратегия "первым во­шел — первым вышел" на это неспособна.

Хотя стратегия дольше всех неиспользовавшегося элемента и близка к оп­тимальной, она трудна в реализации и приводит к значительным накладным расходам. Стратегия "первым вошел — первым вышел" реализуется очень просто, но относительно редко приводит к хорошим результатам. В течение долгого времени разработчики операционных систем испытывали различные алгоритмы, пытаясь достичь увеличения производительности стратегии дольше всех неиспользовавшегося элемента при значительном снижении накладных расходов. Многие из этих алгоритмов представляют собой варианты схемы, известной как часовая стратегия (clockpolicy).

В простейшей схеме часовой стратегии с каждым кадром связывается один дополнительный бит, известный как бит использования. Когда страница впервые загружается в кадр, бит использования устанавливается равным 1. При последующих обращениях к странице, вызвавших прерывание из-за отсутствия страницы, этот бит устанавливается равным 1. При работе алгоритма замещения множество кадров, являющихся кандидатами на замещение (текущий процесс, локальная область видимости, вся основная память или глобальная область видимости, рассматривается как циклический буфер, с которым связан указатель. При замещении страницы указатель перемещается к следующему кадру в буфере. Когда наступает время замещения страницы, операционная система сканирует буфер для поиска кадра, бит использования которого равен 0. Всякий раз, когда в процессе поиска встречается кадр с битом использования, равным 1, он сбрасывается в 0. Первый же встреченный кадр с нулевым битом использования выбирается для замещения. Если все кадры имеют бит использования, равный 1, указатель совершает полный круг и возвращается к начальному положению, заменяя страницу в этом кадре. Как видим, эта стратегия схожа со стратегией "первым вошел — первым вышел; но отличается тем, что кадры, имеющие установленный бит использования, пропускаются алгоритмом. Буфер кадров страниц представлен в виде круга, откуда и произошло название стратегии. Ряд операционных систем используют различные варианты часовой стратегии (например,Multics[CORB68]).

На рис. 8.16 приведен простейший пример использования часовой стратегии. Для замещения доступны (n-1) кадры основной памяти, представленные в виде циклического буфера. Непосредственно перед тем, как заместить страницу в буфере загружаемой из вторичной памяти страницей 727, указатель буфера указывает на кадр 2, содержащий страницу 45. Теперь приступим к выполнению часового алгоритма. Поскольку бит использования страницы 45 в кадре 2 равен 1, эта страница не замещается; вместо этого ее бит использования сбрасывается, а указатель перемещается к следующему кадру. Не замещается также страница 191 из кадра 3; в соответствии с алгоритмом сбрасывается ее бит использования. В следующем кадре (номер 4) бит использования страницы равен 0. Таким образом, страница 556 замещается загружаемой в основную память страницей 727, бит использования которой устанавливается равным 1. Далее указатель буфера переходит к кадру 5, и на этом выполнение алгоритма завершается. Для экономии места на рис. 8.16 бит использования обозначен какuse.

Поведение часового алгоритма показано на рис. 8.15. Наличие звездочки означает, что бит использования соответствующей страницы равен 1, а стрелочка указывает текущее положение указателя. Заметим, что данный алгоритм пытается защитить страницы 2 и 5 от замещения.

На рис. 8.17 показаны результаты эксперимента ([BAER80]), в котором сравнивались четыре рассмотренных в этом разделе алгоритма; предполагается, что количество отводимых процессу кадров постоянно. Результат основан на выполнении 0.25Х10" обращений к памяти в программе на языкеFORTRANс использованием страниц размером 256 слов. Эксперимент проводился с выделением процессу 6, 8, 10, 12 и 14 кадров. Различия в используемых алгоритмах наиболее четко видны при малом количестве кадров (при этом алгоритм "первым вошел — первым вышел" более чем в два раза хуже оптимального). Практически такие же результаты представлены в [FINK88], где максимальное отклонение также оказывалось больше, чем в 2 раза. В этой работе моделировалось влияние различных стратегий на сгенерированной последовательности обращений к страницам длиной 10000 обращений к виртуальному пространству из 100 страниц. Для достижения эффекта локализации использовалось экспоненциальное распределение вероятности ссылок к конкретной странице.

Проводились также исследования по сравнению алгоритмов при распределении переменного количества кадров процессу, а также при глобальной и локальной областях видимости ([CARR81,CARR84]). Как выяснилось, по производительности часовой алгоритм наиболее близок к алгоритму дольше всех неиспользовавшегося.

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

• использован давно, не модифицирован (n= 0,т =0);

• использован недавно, не модифицирован (n= 1,т =0);

• использован давно, модифицирован (n =0, т =1);

• использован недавно, модифицирован (n =1,т== 1).

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

1. Сканируем буфер кадров, начиная с текущего положения. В процессе ска­нирования бит использования не изменяется. Первая же страница с состоя­нием (n= 0,т = О)замещается.

2. Если выполнение первого шага алгоритма не увенчалось успехом, ищем страницу с параметрами (n =0, т= 1). Если таковая найдена, она замеща­ется. В процессе выполнения данного шага у всех просмотренных страниц сбрасывается бит использования.

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

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

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

Буферизация страниц

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

Есть еще одна интересная стратегия, которая может повысить производительность страничной организации при использовании простейшего алгоритма замещения. Это — буферизация страниц, использованная в VAXVMS. В качестве алгоритма замещения страниц используется простейший алгоритм "первым вошел — первым вышел". Для повышения его производительности замещаемая страница не теряется, а вносится в один из двух списков; в список свободных страниц, если страница не модифицировалась, или в список модифицированных страниц. Заметим, что физически страница не перемещается — вместо этого ее запись удаляется из таблицы страниц и переносится в список свободных или модифицированных страниц,

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

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

Простейшая версия буферизации страниц реализована в операционной сис­теме Mach[RASH88]. В этой операционной системе не делается различий между модифицированными и немодифицированными страницами.

Стратегия замещения и размер кэша

Как отмечалось ранее, размер основной памяти со временем становится все больше, как, впрочем, и размер приложений. Утешением может служить то, что размеры кэшей также увеличиваются. Большие — до нескольких мегабайтов — кэши в настоящее время вполне возможны [BORG90]. При использовании кэшей большого размера замещение страниц виртуальной памяти может влиять на производительность. Если кадр страницы, выбранный для замещения, располагается в кэше, то вместе с потерей страницы из блока кэша теряется весь блок.

В системах с использованием буферизации того или иного вида производительность кэша можно увеличить путем добавления к стратегии замещения стратегию размещения страниц в буфере. Большинство операционных систем размещают страницы в буфере в произвольных кадрах, как правило, с использованием алгоритма "первым вошел — первым вышел". Исследования в [KESS92] показали, что правильный выбор стратегии размещения может привести к уменьшению неуспешных поисков в кэше на 10-20%.

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

Управление резидентным множеством

Размер резидентного множества

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

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

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

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

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

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

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

Область видимости замещения

Область видимости стратегии замещения можно классифицировать как локальную или глобальную. Стратегии обоих типов активируются прерыванием обращения к странице при отсутствии свободных кадров. Локальная стратегия замещения выбирает страницу только среди резидентных страниц того процесса, который стал причиной прерывания. Глобальная стратегия замещения рассматривает в качестве кандидатов на замещение все незаблокированные страницы в основной памяти, независимо от принадлежности конкретной страницы тому или иному процессу. Хотя локальная стратегия и проще для анализа, нет убедительных доказательств того, что она дает лучшие результаты по сравнению с глобальной стратегией, которая привлекает своей простотой реализации и минимальными накладными расходами [CARR84, МАЕК87].

Имеется связь между областью видимости замещения и размером резидентного множества (табл. 8.4), фиксированное резидентное множество приводит к локальной стратегии замещения — для поддержания фиксированного размера резидентного множества удаляемая из основной памяти страница должна быть замещена другой страницей того же процесса. Стратегия переменного распределения, естественно, совместима с глобальным замещением: замена страницы одного процесса в основной памяти страницей другого процесса приводит к перераспределению размеров содержащихся в основной памяти частей процессов. Мы также узнаем, что переменное распределение может работать и с локальным замещением. А теперь рассмотрим все три возможных сочетания в отдельности.

Таблица 8.4. Управление резидентным множеством

Фиксированное распределение Переменное распределение	Локальное замещение Глобальное замещение
	Количество кадров процесса фиксировано Страница для замещения выбирается среди выделенных процессу кадров	Невозможно
	Количество выделенных процес­су кадров может время от вре­мени изменяться Страница для замещения выби­рается среди выделенных про­цессу кадров	Страница для замещения вы­бирается среди всех доступ­ных кадров в основной памя­ти; это приводит к изменению размера резидентного множе­ства процесса