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

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

· Какое количество кадров должно быть выделено каждому активному процессу.

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

· Какие именно страницыиз рассматриваемого множества следует выбрать для замещения.

Первые два вопроса — из области управления резидентным множеством, о чем мы поговорим в следующем подразделе; термин же "стратегиязамещения" мы будем использовать для обозначения третьего вопроса.

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

Блокировка кадров

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

Основные алгоритмы

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

· оптимальный алгоритм;

· алгоритм дольше всех не использовавшиеся;

· алгоритм "первым вошел — первым вышел";

· часовой алгоритм.

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

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

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

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

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

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

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

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

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

В простейшейсхеме часовой стратегии с каждым кадром связывается один дополнительный бит, известный как бит использования. Когда страница впервые загружается в кадр, бит использования устанавливается равным 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. Положительный момент этого алгоритма состоит, в отличие от простого часового алгоритма, в преимуществе замены не изменявшихся страниц по сравнению с заменой модифицированных страниц.