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

Алгоритм LRU (выталкивание дольше всего не использовавшейся страницы)

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

Одно из последствий открытия аномалии Belady - поиск оптимального алгоритма. Этот алгоритм имеет минимальную частоту fault'ов среди всех алгоритмов. Он прост: замещай страницу, которая не будет использоваться в течение длительного периода времени.

Каждая страница помечается числом инструкций, которые будут выполнены, прежде чем на эту страницу будет сделана первая ссылка.

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

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

Ключевое отличие между FIFO и оптимальным алгоритмом в том, что один смотрит назад, а другой вперед. Если использовать прошлое, для аппроксимации будущего, имеет смысл замещать страницу, которая не использовалась в течение долгого времени. Такой подход называется алгоритм LRU (least recently used).

LRU часто используется и считается хорошим. Основная проблема - реализация. Необходимо иметь связанный список всех страниц в памяти, в начале которого будут часто используемые страницы. Причем он должен обновляться при каждой ссылке. Много времени нужно на поиск страниц в списке. Есть вариант реализации со специальным устройством. Например, - иметь 64-битный указатель, который автоматически увеличивается на 1 после каждой инструкции и в таблице страниц иметь соответствующее поле, в которое заносится значение указателя при каждой ссылке на страницу. При возникновении page fault'а выгружается страница с наименьшим указателем.

Как оптимальный алгоритм, так и LRU не страдают от аномалии Белейди. Существует класс алгоритмов, называемых стековыми (stack) алгоритмами, которые не проявляют аномалии Белейди. Это алгоритмы, для которых множество страниц в памяти для n кадров всегда подмножество страниц для n+1 кадра. LRU таковым является.

Заметим, что никакая реализация LRU неприемлема без специального оборудования помимо стандартных регистров. Если, например, задействовать прерывание для модификации полей, то это будет замедлять ссылку к памяти в 10 раз.

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

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

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

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

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

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