Стратегии выталкивания страниц
Как мы указали выше, программы управления памятью, входящие в ОС, должны решать, какую страницу следует удалить из ОП, чтобы освободить место для поступающей страницы. Очевидно, что для обеспечения оптимальных скоростных характеристик и эффективного использования ресурсов следует заменять ту страницу, к которой не будет новых обращений в течение наиболее длительного времени - принцип оптимальности. Рассматриваемые нами в дальнейшем стратегии выталкивания страниц будем рассматривать с точки зрения соответствия принципу оптимальности.
Выталкивание случайной страницы
Можно пойти по самому простому принципу при выталкивании страниц - выталкивать случайную страницу. В этом случае стратегия будет характеризоваться малыми издержками и не являться дискриминационной по отношению к пользователям. Однако такая стратегия выбирается крайне редко, именно вследствие непредсказуемости выбора страницы для выталкивания.
Выталкивание первой пришедшей страницы (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 является и не слишком дорогой и достаточно эффективной.
Рабочее множество
Working set of pages
При использовании этой стратегии выталкивается страница, которая не входит в подмножество наиболее активно используемых страниц процесса. Остановимся более подробно на этой стратегии. Деннинг13 предложил оценивать интенсивность подкачки страниц для программы согласно концепции, которую он назвал теорией поведения программы с рабочим множеством, где под рабочим множеством понимается подмножество страниц, к которым процесс активно обращается.
В работе Деннинга утверждается, что для обеспечения эффективного выполнения программы необходимо, чтобы ее рабочее множество находилось в ОП, в противном случае может возникнуть режим чрезмерно интенсивной подкачки страниц, так называемое пробуксовывание или трешинг, поскольку программа будет многократно подкачивать одни и те же страницы из внешней памяти.
t-w w t
Время
выполнения
процесса
Страницы, к которым обращается
процесс в течение этого временного
интервала, составляют рабочее
множество этого процесса W(t,w)
Рис. 15 Определение рабочего множества страниц процесса
Рабочее множество страниц процесса W(t,w) в момент времени t есть набор страниц, к которым процесс обращается в течение интервала времени процесса от t-w до t, где время процесса - это время, в течение которого процесс имеет в своем распоряжении ЦП. Переменная w называется размером окна рабочего множества, причем выбор величины этого окна играет решающую роль с точки зрения эффективности стратегии управления памятью по рабочему множеству.
Во время работы процесса его рабочие множества динамически меняются. Иногда к текущему рабочему множеству добавляются или из него удаляются некоторые страницы. Иногда происходят резкие изменения, например, когда процесс переходит к этапу, требующему совершенно нового рабочего множества. В связи с этим, задача реализации четкой стратегии управления памятью по рабочим множествам является достаточно сложной и требует контроля за возможными перегрузками ОП и возникновением вследствие этого трешинга (trashing).
При использовании управления памятью с помощью рабочих множеств, страницы, которые больше не нужны, должны каким-то образом выводится из рабочих множеств. Обычно существует промежуток времени, по истечении которого ненужные страницы перемещаются из ОП.
Некоторые системы предусматривают возможность добровольного освобождения страниц, т.е. выполняющийся процесс в явном виде сообщает системе, что какая-то конкретная страница ему больше не понадобится.