Часовой алгоритм
В простейшей схеме часовой стратегии с каждым кадром связывается один дополнительный бит, известный как бит использования. Когда страница впервые загружается в кадр, бит использования устанавливается равным 1. При последующих обращениях к странице, вызвавших прерывание из-за отсутствия страницы, этот бит устанавливается равным 1. При работе алгоритма замещения множество кадров, являющихся кандидатами на замещение (текущий процесс, локальная область видимости, вся основная память или глобальная область видимости), рассматривается как циклический буфер, с которым связан указатель. При замещении страницы указатель перемещается к следующему кадру в буфере.
Когда наступает время замещения страницы, операционная система сканирует буфер для поиска кадра, бит использования которого равен 0. Всякий раз, когда в процессе поиска встречается кадр с битом использования, равным 1, он сбрасывается в 0. Первый же встреченный кадр с нулевым битом использования выбирается для замещения. Если все кадры имеют бит использования, равный 1, указатель совершает полный круг и возвращается к начальному положению, заменяя страницу в этом кадре. Как видим, эта стратегия схожа со стратегией "первым вошел — первым вышел", но отличается тем, что кадры, имеющие установленный бит использования, пропускаются алгоритмом. Буфер кадров страниц представлен в виде круга, откуда и произошло название стратегии (другое название – стратегия круговой замены страниц). Ряд операционных систем используют различные варианты часовой стратегии (например, Multics).
На рис. 10.15 приведен простейший пример использования часовой стратегии. Для замещения доступны п-1 кадры основной памяти, представленные в виде циклического буфера. Непосредственно перед тем, как заместить страницу в буфере загружаемой из вторичной памяти страницей 727, указатель буфера указывает на кадр 2, содержащий страницу 45. Теперь приступим к выполнению часового алгоритма.
Поскольку бит использования страницы 45 в кадре 2 равен 1, эта страница не замещается; вместо этого ее бит использования сбрасывается, а указатель перемещается к следующему кадру. Не замещается также страница 191 из кадра 3; в соответствии с алгоритмом сбрасывается ее бит использования. В следующем кадре (номер 4) бит использования страницы равен 0. Таким образом, страница 556 замещается загружаемой в основную память страницей 727, бит использования которой устанавливается равным 1. Далее указатель буфера переходит к кадру 5, и на этом выполнение алгоритма завершается. Для экономии места на рис. 8.16 бит использования обозначен как use.
Поведение часового алгоритма показано на рис. 10.13. Наличие звездочки означает, что бит использования соответствующей страницы равен 1, а стрелочка указывает текущее положение указателя. Заметим, что данный алгоритм пытается защитить страницы 2 и 5 от замещения.
На рис. 10.16 показаны результаты эксперимента, в котором сравнивались четыре рассмотренных в этом разделе алгоритма; предполагается, что количество отводимых процессу кадров постоянно.
Рис. 10.15. Пример работы часового алгоритма
Рис. 10.16. Сравнение различных стратегий замещения страниц
Проводились также исследования по сравнению алгоритмов при распределении переменного количества кадров процессу, а также при глобальной и локальной областях видимости. Как выяснилось, по производительности часовой алгоритм наиболее близок к алгоритму дольше всех неиспользовавшегося.
Повысить эффективность часового алгоритма можно путем увеличения количества используемых при его работе битов. (С другой стороны, уменьшение количества битов до нуля дает нам алгоритм "первым вошел — первым вышел").
Во всех поддерживающих страничную организацию процессорах с каждой страницей в основной памяти (а следовательно, с каждым кадром) связан бит модификации. Этот бит используется для указания того, что данная страница не может быть замещена до тех пор, пока ее содержимое не будет записано обратно во вторичную память. Этот бит может использоваться часовым алгоритмом следующим образом. Принимая во внимание биты использования и модификации, все кадры можно разделить на четыре категории:
использован давно, не модифицирован (и = 0, т = 0);
использован недавно, не модифицирован (и = 1, т = 0);
использован давно, модифицирован (и = 0, т = 1);
использован недавно, модифицирован (и = 1, т — 1).
Используя эту классификацию, изменим часовой алгоритм, который теперь будет описан следующим образом (рис. 10.17).
Рис. 10.17. Часовой алгоритм замещения страниц
Сканируем буфер кадров, начиная с текущего положения. В процессе сканирования бит использования не изменяется. Первая же страница с состоянием (и = 0, т = 0) замещается.
Если выполнение первого шага алгоритма не увенчалось успехом, ищем страницу с параметрами (и = 0, т = 1). Если таковая найдена, она замещается. В процессе выполнения данного шага у всех просмотренных страниц сбрасывается бит использования.
Если выполнение предыдущего шага не дало результата, указатель возвращается в исходное положение, но у всех страниц значение бита использования сброшено в 0. Повторим шаг 1 и, при необходимости, шаг 2. Очевидно, на этот раз требуемая страница будет найдена.
Такой алгоритм использован в схеме виртуальной памяти Macintosh. Положительный момент этого алгоритма состоит, в отличие от простого часового алгоритма, в преимуществе замены не изменявшихся страниц по сравнению с заменой модифицированных страниц.
Итак, часовой алгоритм циклически проходит по всем страницам буфера в поисках страницы, которая не была модифицирована со времени загрузки и давно не использовалась. Такая страница — хороший кандидат на замещение, особенно с учетом того, что ее не надо записывать на диск. Если при первом проходе кандидатов на замещение не нашлось, алгоритм снова проверяет буфер, теперь уже в поисках модифицированной, давно не использовавшейся страницы. Хотя такая страница и должна быть записана перед замещением, в соответствии с принципом локализации она вряд ли понадобится в ближайшем будущем. Если и этот проход окажется неудачным, все страницы помечаются как давно не использованные, и выполняется третий проход.