ПОД (пособие) (1184372), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

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

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

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

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

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

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

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

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

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

Один изшироко распространенных способов решения этой проблемы заключается в том, что всебиты-признаки обращений периодически сбрасываются в 0, с тем чтобы механизмвталкивания оказался в исходном состоянии, а затем снова разрешается установка этихбитов-признаков в 1 обычным образом при обращениях. Правда, в этом случае существуетопасность того, что могут быть вытолкнуты даже активные страницы, однако только втечение короткого периода после сброса битов-признаков, поскольку почти немедленнобиты-признаки обращений для этих страниц будут снова установлены в 1.Описанный выше алгоритм NUR предусматривает существование четырех групп страниц:Группа 1Обращений не былоМодификаций не былоГруппа 2Обращений не былоМодификация былаГруппа 3Обращения былиМодификаций не былоГруппа 4Обращения былиМодификация былаСтраницы групп о меньшими номерами следует выталкивать в первую очередь, а сбольшими — в последнюю.

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

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

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

Характеристики

Список файлов книги