LRU – Least recently used

1 Связанный список всех страниц. Первая страница – только что использованная. Использовали – переместили в начало.

Недостатки:

· очень долгий даже на аппаратном уровне.

2 Страницам ввести счётчик. Удаляются страницы с наименьшим счётчиком

Использовали - +1.

Если использовали страницу, элементы строки k увеличиваются на 1, элементы столбца k обнуляются. Удаляются страницы с наименьшим значением строки.

Алгоритм нечастого использования

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

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

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