Их цель — решить какую страницу или сегмент следует удалить из оперативной памяти, чтобы освободить место для помещения поступающей страницы или сегмента, если оперативная память полностью занята.
Стратегии выталкивания страниц
Как мы указали выше, программы управления памятью, входящие в ОС, должны решать, какую страницу следует удалить из ОП, чтобы освободить место для поступающей страницы. Очевидно, что для обеспечения оптимальных скоростных характеристик и эффективного использования ресурсов следует заменять ту страницу, к которой не будет новых обращений в течение наиболее длительного времени — принцип оптимальности. Рассматриваемые нами в дальнейшем стратегии выталкивания страниц будем рассматривать с точки зрения соответствия принципу оптимальности.
Выталкивание случайной страницы
Можно пойти по самому простому принципу при выталкивании страниц — выталкивать случайную страницу. В этом случае стратегия будет характеризоваться малыми издержками и не являться дискриминационной по отношению к пользователям. Однако такая стратегия выбирается крайне редко, именно вследствие непредсказуемости выбора страницы для выталкивания.
Выталкивание первой пришедшей страницы (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 является и не слишком дорогой и достаточно эффективной.
