Выталкивание случайной страницы

Стратегии выталкивания страниц

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

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

Выталкивание первой пришедшей страницы (FIFO)

First-in-first-out

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

Самостоятельно рассмотреть вопрос: “Аномалия FIFO”[Дейтел р.9.3.3.1]

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

Least-recently-used

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

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

Least-frequently-used

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

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

Not-used-recently

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

Поскольку желательно заменять ту страницу, которая в период нахождения в ОП не изменялась, то реализация NUR предусматривает использование двух признаков на страницу:

· Бит-признак обращения 0 - если обращений не было;

1 - если обращения были;

· Бит-признак модификации 0 - если страница не изменялась;

1 - если изменялась.

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

Следует отметить, что из рассмотренных выше стратегий NUR является и не слишком дорогой и достаточно эффективной.