Страница, загруженная первой

О 3

Последняя зафуженная страница

А трактуется как заново зафуженная страница

Рис. 4.12. Действие алгоритма вторая попытка : а - страницы, отсортированные в порядке очереди (FIFO); б - список страниц, если страничное прерывание произошло во время 20, а страница А имеет бит R, равный О

4.4.5. Алгоритм часы

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

Когда происходит страничное прерывание, проверяется страница, на которую указывает стрелка. Предпринимаемые действия зависят от бита R:

R = 0: страница выфужается

R = 1: бит R сбрасывается, стрелка движется вперед

Рис. 4.13. Алгоритм замещения страниц часы

Когда происходит страничное прерывание, проверяется та страница, на которую направлена стрелка. Если ее бит R равен О, страница выгружается, на ее место в часовой круг встает новая страница, а стрелка сдвигается вперед на одну позицию. Если бит R равен 1, он сбрасывается, стрелка перемещается к следующей странице. Этот процесс повторяется до тех пор, пока не находится та страница, у которой бит R = 0. Не удивительно, что алгоритм называется часами . Он отличается от алгоритма вторая попытка только своей реализацией.

4.4.6. Алгоритм LRU - страница, не использовавшаяся дольше всего

в основе этой неплохой аппроксимации оптимального алгоритма лежит наблюдение, что страницы, к которым наблюдалось многократное обращение в нескольких последних командах, вероятно, также будут часто востребованы в следующих инструкциях. И наоборот, можно полагать, что страницы, к которым ранее не возникало обращений, не будут нужны в течение долгого времени. Эта идея привела к следующему реализуемому алгоритму: когда происходит страничное прерывание, выгружается из памяти страница, которая не использовалась дольше всего. Такая стратегия замещения страниц называется LRU (Least Recently Used).

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

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

Теперь рассмотрим второй вариант аппаратной реализации алгоритма LRU. На машине с п страничными блоками оборудование LRU может поддерживать матрицу и X и бит, изначально равных нулю. Всякий раз при доступе к страничному блоку k аппаратура сначала присваивает всем битам строки k значение 1, затем приравнивает нулю все биты столбца k. В любой момент времени строка, двоичное значение которой наименьшее, является не использовавшейся дольше всего. Работа этого алгоритма продемонстрирована на рис. 4.14, где рассматриваются четыре страничных блока и следующий порядок обращения к страницам:

0 123210323

После ссылки на страницу О мы получаем ситуацию, показанную на рис. 4.14, а; после обращения к странице 1 - рис. случай 4.14, б и т. д.

Страница

Страница

Страница 0 12 3

Страница

Страница

Рис. 4.14. Алгоритм LRU с привлечением матрицы. Обращения к страницам происходят в последовательности: О, 1, 2, 3, 2, 1, О, 3, 2, 3

4.4.7. Программное моделирование алгоритма LRU

Хотя оба описанных выще алгоритма LRU в принципе осуществимы, очень мало (если вообще такие есть) мащин оснащено подобным оборудованием, в силу чего разработчики операционных систем для компьютеров, не имеющих такой аппаратуры, редко используют эти алгоритмы. Вместо них требуется программно реализуемое решение. Одна из разновидностей схемы LRU называется алгоритмом NFU (Not Frequently Used - редко использовавшаяся страница). Для него необходим программный счетчик, связанный с каждой страницей в памяти, изначально равный нулю. Во время каждого прерывания по таймеру операционная система исследует все страницы в памяти. Бит R каждой страницы (он равен О или 1) прибавляется к счетчику. В сущности, счетчики пытаются отследить, как часто имело место обращение к каждой странице. При страничном прерывании для замещения выбирается страница с наименьшим значением счетчика.

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