Замещение страницы, которая не использовалась в последнее время (NUR)

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

В её основе лежит предположение о том, что к страницам, которые не использовались в предшествующие периоды времени, в последующие периоды вряд ли появится новое обращение, и следовательно, такие страницы могут быть временно удалены из ОП.

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

1. Бит обращения. Равен нулю, если к странице не было обращений, и единице, если они были.

2. Бит модификации или изменения. Равен нулю, если информация на странице не менялась, и единице в противном случае.

Данная стратегия реализуется следующим образом. Изначально, все биты-признаки всех страниц устанавливаются в ноль. При обращении к какой-либо странице, её бит-признак устанавливается в единицу, а в случае изменения содержимого страницы, в единицу устанавливается бит-признак модификации. Когда требуется найти страницу для замещения, прежде всего, рассматриваются те страницы, к которым не было обращений, что соответствует идее принципа оптимальности LRU.

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

Если не изменявшиеся страницы отсутствуют, то для замещения выбирается любая из модифицированных страниц.

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

Этот способ имеет один недостаток – существует вероятность того, что в результате периодического сброс в ноль битов обращений из памяти будут удалены часто используемые страницы. Однако такое состояние возможно лишь на короткий промежуток времени, сразу после сброса битов обращений. Если страницы используются активно, то их биты обращений быстро будут переведены в состояние единицы.

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

Из множества всех указанных групп в первую очередь выбираются страницы из групп с меньшими номерами.

В группу 2 включаются страницы, биты обращения которых были предварительно сброшены.

Алгоритм замещения NUR характеризуется наименьшими затратами, поэтому находит применение на практике.

Дата добавления: 2014-10-10; просмотров: 408; Нарушение авторских прав

Мы поможем в написании ваших работ!