Ответы 190 страниц, страница 9

Стратегии вталкивания. Их цель - определить, в какой момент следует переписать страницу или сегмент из вторичной памяти в первичную. Вталкивание по запросу (по требованию) предполагает, что система ждет ссылки на страницу или сегмент от выполняющего процесса и только после появления ссылки начинает переписывать данную страницу или сегмент в первичную память. Вталкивание с упреждением (опережением) предполагает, что система пытается заблаговременно определить, к каким страницам или сегментам будет обращаться процесс. Если вероятность обращения высока и в первичной памяти имеется свободное место, то соответствующие страницы или сегменты будут переписываться в основную память еще до того, как к ним будет явно производиться обращение.

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

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

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

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

· Принцип оптимальности.

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

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

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

· Первой выталкивается наименее часто использовавшаяся страница (LFU).

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

· Рабочее множество.

9.3.1 Принцип оптимальности

Принцип оптимальности (De70) говорит о том, что для обеспечения оптимальных скоростных характеристик и эффективного использования ресурсов следует заменять ту страницу, к которой в дальнейшем не будет новых обращений в течение наиболее длительного времени. Можно, конечно, продемонстрировать, что подобная стратегия действительно оптимальна, однако реализовать ее, естественно, нельзя, поскольку мы не умеем предсказывать будущее.

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

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

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

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

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

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

Однако, как установили Билейди, Нельсон и Шедлер (Ве69b), в стратегии FIFO определенные последовательности обращений к страницам приводят в действительности к увеличению количества прерываний по отсутствию страницы при увеличении количества страничных кадров, выделяемых процессу. Это явление носит название «аномалии FIFO».

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

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

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

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

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

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

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

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

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

а) бит-признак обращения

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

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

б) бит-признак модификации

= 0, если страница не изменялась;

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

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

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

Описанный выше алгоритм NUR предусматривает существование четырех групп страниц:

Группа 1

Обращений не было

Модификаций не было

Группа 2

Обращений не было

Модификация была

Группа 3

Обращения были

Модификаций не было

Группа 4

Обращения были

Модификация была

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

9.4 Локальность

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

Свойство локальности проявляется как во времени, так и в пространстве. Временная локальность — это концентрация во времени. Если, например, в 15 ч наблюдается солнечная погода, то можно с достаточно высокой вероятностью считать (но, естественно, без всяких гарантий), что было солнечно в 14 ч 30 мин и будет солнечно в 15 ч 30 мин. Пространственная локальность означает, что соседние объекты будут, как правило, характеризоваться одинаковыми свойствами. Если опять-таки взять в качестве примера погоду, то в случае, когда в одном городе солнечно, можно с достаточно высокой вероятностью (но без всяких гарантий) считать, что и в близлежащих городах солнечно.

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

9.6 Подкачка страниц по запросу

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