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

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

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

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

К тому же имеет место некоторое явление, называемое аномалией FIFO. Его суть заключается в том, что иногда увеличение количества страничных кадров, выделяемых процессу, приводит к увеличению частоты прерываний по отсутствию нужных страниц для этого процесса. Рассмотрим рисунок:

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

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

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

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

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

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

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

Этот механизм предусматривает введение двух аппаратных битов-признаков на страницу. Это

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

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

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

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

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