Другие алгоритмы

Выталкивание редко используемой страницы. NFU (Not Frequently Used) алгоритм.

Программная реализация алгоритма, близкого к LRU.

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

Один из таких возможных алгоритмов - это алгоритм NFU.

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

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

К счастью, возможна небольшая модификация алгоритма, которая реализует "забывание". Достаточно, чтобы при каждом прерывании по времени содержимое каждого счетчика сдвигалось вправо на 1 бит, а уже затем производилось бы его увеличение для страниц с установленным флагом обращения (рис. 3-27 Таненбаум).

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

Для полноты картины можно упомянуть еще несколько алгоритмов.

Например, алгоритм Second-Chance - модификации FIFO, которая позволяет избежать потери часто используемых страниц - анализ бита r(reference) для самой старой страницы. Если бит 1, то страница в отличие от FIFO не выталкивается, а очищается бит и страница становится в конец очереди. Если на все страницы ссылались, он превращается в FIFO. Данный алгоритм использовался в BSD Unix.

В компьютере Макинтош использован алгоритм NRU(Not Recently-Used), где страница жертва выбирается на основе анализа битов модификации и ссылки.

Имеется также и много других алгоритмов замещения. Объем этого курса не позволяет рассмотреть их подробно. Подробное описание различных алгоритмов замещения имеется в монографиях Дейтела, Цикритиса, Таненбаума и др.

Дата добавления: 2014-12-16