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

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

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

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

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

 

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

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

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

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

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

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

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

 

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

Существуют и другие алгоритмы.

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

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

 

Контрольные вопросы:

1) Опишите исключительные ситуации при работе с памятью.

2) Приведите стратегии управления страничной памятью.

3) Опишите глобальные и локальные алгоритмы замещения.

4) Приведите алгоритм замещения FIFO, аномалию Белейди.

5) Приведите оптимальный алгоритм замещения.

6) Приведите алгоритм замещения LRU.

7) Приведите алгоритм замещения NFU.