СКИПОДы 2007 полная версия (1127795), страница 13
Текст из файла (страница 13)
Это действительно так простопотому, что мы не можем достаточно точно прогнозировать будущее. В связи с этимнеобходима такая стратегия выталкивания страниц, которая обеспечивала бы принятиерациональных решений в большинстве случаев и в то же время не требовала большихнакладных расходов.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Свойство локальности наблюдается также и в работе операционных систем, в частности приуправлении памятью. Свойство это скорее эмпирическое (наблюдаемое), чем теоретическиобоснованное. Локальность никак нельзя гарантировать, однако ее вероятность зачастуювесьма велика.
Например, в системах со страничной организацией мы наблюдаем, чтопроцессы обычно «оказывают предпочтение» определенным подмножествам своих страници что эти страницы обычно размещаются по соседству друг с другом в виртуальномадресном пространстве процесса. Это не значит, что процесс не будет иметь ссылок накакую-либо новую страницу — если бы это было так, то процессы вообще не могли быдаже начать выполнение. Это просто означает, что процесс будет, как правило,сосредоточивать свои обращения в течение некоторого временного интервала на некоторомконкретном подмножестве своих страниц.9.6 Подкачка страниц по запросуТрадиционно считается, что наиболее рационально загружать в основную память страницы,необходимые для работы процесса, по его запросу. Не следует переписывать из внешнейпамяти в основную ни одной страницы до тех пор, пока к ней явно не обратитсявыполняющийся процесс, В пользу такой стратегии можно привести несколько аргументов:·Теория вычислимости, в частности проблема останова (Mi67, Не77), говорит о том,что путь, который выберет программа при своем выполнении, точно предсказатьневозможно.
Поэтому любая попытка заранее загрузить страницы в память в предвидениитого, что они потребуются в работе, может оказаться неудачной — будут загружены не тестраницы.·Подкачка страниц по запросу гарантирует, что в основную память будутпереписываться только те страницы, которые фактически необходимы для работыпроцессов.·Накладные расходы на то, чтобы определить, какие страницы следует передавать восновную память, минимальны. Стратегии вталкивания с упреждением могут потребоватьзначительных дополнительных затрат процессорного времени.Подкачка страниц по запросу, как показывает рис. 9.7, имеет свои проблемы.
Процессдолжен накапливать в памяти, требуемые ему страницы по одной. При появлении ссылки накаждую новую страницу процессу приходится ждать, когда эта страница будет передана восновную память. В зависимости от того, сколько страниц данного процесса уже находятсяв основной памяти, эти периоды ожидания будут обходиться все более дорого, посколькуожидающие процессы будут занимать все больший объем памяти. Рис.
9.7 иллюстрируетпонятие произведения «пространство— время», которое часто применяется в операционныхсистемах для оценки использования памяти процессом. Произведение «пространство—время» соответствует площади «под кривой» на этом рисунке. Оно является комплекснымпоказателем, отражающим как объем, так и время использования памяти процессом.Уменьшение произведения «пространство—время» за счет периодов ожидания процессомнужных ему страниц является важнейшей целью всех стратегий управления памятью.9.6 Подкачка страниц с упреждениемГлавный критерий эффективности управления ресурсами можно сформулироватьследующим образом: интенсивность использования каждого ресурса должна определятьсяотносительной ценностью этого ресурса.
Так, в настоящее время стоимость аппаратурырезко снижается, и поэтому значительно снижается относительная ценность машинноговремени по сравнению с временем, затрачиваемым человеком. Сейчас разработчикиоперационных систем активно ищут пути уменьшения количества времени, в течениекоторого пользователям приходится ждать получения результатов от компьютера. Одним из42весьма перспективных в этом смысле является метод подкачки страниц с упреждением (сопережением).При упреждающей подкачке операционная система пытается заблаговременно предсказать,какие страницы потребуются процессу, а затем, когда в основной памяти появляетсясвободное место, загружает в нее эти страницы.
Пока процесс работает со своими текущимистраницами, система запрашивает новые страницы, которые будут уже готовы киспользованию, когда процесс к ним обратится. Если решения о выборе страниц дляподкачки принимаются правильно, то удается значительно сократить общее времявыполнения данного процесса.Метод подкачки страниц с упреждением характеризуется следующими преимуществами:·Если в большинстве случаев удается принимать правильные решения о выборестраниц для подкачки, то время выполнения процесса значительно уменьшается.
Поэтомуимеет смысл пытаться создавать механизмы упреждающей подкачки, даже если от нихнельзя ожидать абсолютной точности.·Во многих случаях вполне можно находить правильные решения. Если такоепринятие решений удается реализовать при относительно малых затратах, то выполнениеданного процесса можно значительно ускорить, не замедляя при этом работы другихактивных процессов.·Поскольку аппаратура вычислительных машин все более дешевеет, последствиянеоптимальных решений становятся менее серьезны.
Сейчас мы можем позволить себеприобрести дополнительную основную память, обеспечивающую накоплениедополнительных страниц, которые механизм упреждающей подкачки будет передавать восновную память.9.8 Освобождение страницПри управлении памятью по рабочему множеству программы говорят нам, какие страницыони хотят использовать, явно обращаясь к этим страницам. Страницы, которые больше ненужны, должны каким-то образом выводиться из рабочих множеств.
Существует обычнопериод времени, в течение которого ненужные страницы все еще остаются в основнойпамяти.Когда выясняется, что некоторая страница больше не понадобится, пользователь может пособственной инициативе выдать сигнал об удалении страницы из памяти (отказаться отстраницы) с освобождением соответствующего страничного кадра. Благодаря этому будетисключен период задержки, неизбежный в случае, если предоставить системе возможностьестественным порядком вывести эту страницу из рабочего множества процесса.Подобное «добровольное освобождение» страниц может исключить непроизводительноеиспользование памяти и ускорить выполнение программ.
Однако большинствопользователей современных вычислительных машин даже не знают, что такое страница,поэтому их вообще нельзя просить принимать решения на системном уровне. Включениекоманд освобождения страниц в прикладные программы пользователя может значительнозамедлить их разработку.Можно надеяться, что реально эта проблема будет решена при помощи компиляторов иоперационных систем, которые будут автоматически обнаруживать ситуации, требующиеосвобождения, страниц, причем, делать это гораздо быстрее, чем позволяют стратегии сиспользованием рабочих, множеств страниц.9.9 Размер страниц43В системах со страничной организацией реальная память обычно разбивается настраничные кадры фиксированного размера.
Какой величины следует выбирать размер этихстраничных кадров? Какой величины следует выбирать размер страницы? Должны ли всестраницы в системе иметь одинаковый размер либо следует использовать страницынескольких различных размеров? Если используются различные размеры страниц, тодолжны ли большие размеры страниц быть целыми кратными меньших размеров?Для ответа на эти вопросы требуется тщательный анализ и всестороннее пониманиевозможностей аппаратных и программных средств и области применения конкретнойсистемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
