Управление виртуальной памятью

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

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

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

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

Выталкивание реже всего используемой страницы

Одной из близких к LRU стратегий является стратегия, согласно которой выталкивается наименее часто (наименее интенсивно) использовавшаяся страница (LFU). Здесь мы контролируем интенсивность использования каждой страницы. Выталкивается та страница, которая наименее часто используется или обращения к которой наименее часты. Подобный подход опять-таки кажется интуитивно оправданным, однако в то же время велика вероятность того, что удаляемая страница будет выбрана нерационально. Например, наименее интенсивно используемой может оказаться страница, которую только что переписали в основную память, и к которой успели обратиться только один раз, в то время как к другим страницам могли уже обращаться более одного раза. Теперь работающий по принципу LFU механизм вытолкнет эту страницу, а она скорее всего сразу же будет использоваться. Таким образом, практически любой метод выталкивания страниц, по-видимому, не исключает опасности принятия нерациональных решений.

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

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

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

а) бит-признак обращения      = 0, если к странице не было обращений;

= 1, если к странице были обращения;

б) бит-признак модификации  = 0, если страница не изменялась;

= 1, если страница изменялась.

Бит-признак модификации часто называют также “признаком записи” в страницу. Стратегия NUR реализуется следующим образом. Первоначально биты-признаки обращения и модификации для всех страниц устанавливаются в 0. При обращении к какой-либо странице ее бит-признак обращения устанавливается в 1, а в случае изменения содержимого страницы устанавливается в 1 ее бит-признак модификации. Когда нужно выбрать страницу для выталкивания, прежде всего мы пытаемся найти такую страницу, к которой не было обращений (поскольку мы стремимся приблизиться к алгоритму LRU). В противном случае у нас не будет другого выхода, как вытолкнуть страницу, к которой были обращения. Если к странице обращения были, мы проверяем, подверглась ли она изменению или нет. Если нет, мы заменяем ее из тех соображений, что это связано с меньшими затратами, чем в случае замены модифицированной страницы, которую необходимо будет физически переписывать во внешнюю память. В противном случае нам придется заменять модифицированную страницу.

Локальность и рабочие множества

Локальность - это свойство выполняющихся процессов, состоящее