Недостатки алгоритма NFU

Отличительная особенность в реализации алгоритма NFU.

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

Способы реализации алгоритма LRU

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

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

Алгоритм LRU используется достаточно часто и считается хорошим алгоритмом, но основная проблема заключается в его реализации.

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

2. Использование специального устройства: например, можно иметь 64-битный указатель, который автоматически увеличивается на 1 после каждой инструкции, а в таблице страниц иметь соответствующее поле, в которое заносится значение указателя при каждой ссылке на страницу.

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

Программная реализация алгоритма NFU (Not Frequently Used) близка к алгоритму LRU.

Реализации LRU требуют специальной аппаратной поддержки, которой большинство современных процессоров не предоставляет, поэтому удобно иметь алгоритм, достаточно близкий к LRU, но не требующий сложной специальной поддержки. Одним из таких алгоритмов является алгоритм NFU, для которого требуются программные счетчики (по одному на каждую страницу), изначально равные нулю. При каждом прерывании по времени (а не после каждой инструкции) операционная система сканирует все страницы в памяти, и у каждой страницы с установленным флагом обращения увеличивает на единицу значение счетчика, а флаг обращения сбрасывает. Таким образом, кандидатом на освобождение оказывается страница с наименьшим значением счетчика как страница, к которой реже всего обращались. И так в таблицу страниц добавляется запись – счетчик обращений к странице: чем меньше значение счетчика, тем реже она использовалась.

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

2. Недостатком алгоритмаNFU является длительность процесса сканирования таблиц страниц.

9. Алгоритм замещения страниц Рабочий набор

Для реализации алгоритма Рабочий набор используются следующие понятия:

· замещение страниц по запросу – когда страницы загружаются по требованию, а не заранее, т. е. процесс прерывается и ждет загрузки страницы;

· буксование – когда каждую следующую страницу приходится процессу загружать в память;

· рабочий набор – это множество страниц, которое процесс использовал до определенного момента времени.

В алгоритме Рабочий набор для того, чтобы не происходило частых прерываний, загружаются заранее часто запрашиваемые страницы, а остальные страницы подгружаются по необходимости; определяется функция w(k,t), где рабочий набор – это множество страниц к, которое процесс использовал до момента времени t.

9.1. Зависимость рабочего набора w(k,t) от количества запрошенных страниц.

На прямолинейном участке рабочий набор выходит в насыщение; значение функции w(k,t) в режиме насыщения может служить для рабочего набора (множества страниц), который необходимо загружать до запуска процесса (до t).

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

9.2. Способы реализации алгоритма замещения страниц Рабочий набор.