СКИПОДы 2007 полная версия (1127795), страница 12
Текст из файла (страница 12)
Однаков процессе преобразования адресов существует много моментов, когда обстоятельствамогут складываться не столь благоприятно. Просмотр таблицы сегментов может показать,что сегмента s в первичной памяти нет; при этом возникает прерывание по отсутствиюсегмента, операционная система найдет нужный сегмент во внешней памяти, сформируетдля него таблицу страниц и загрузит соответствующую страницу в первичную память, бытьможет, вместо некоторой существующей страницы этого или какого-либо другого процесса.Когда сегмент находится в первичной памяти, обращение к таблице страниц можетпоказать, что нужной страницы в первичной памяти все же нет. При этом произойдетпрерывание по отсутствию страницы, операционная система возьмет управление на себя,найдет данную страницу во внешней памяти и загрузит ее в первичную память (бытьможет, опять-таки с замещением другой страницы).
Как и при чисто сегментной системе,адрес виртуальной памяти может выйти за рамки сегмента и произойдет прерывание повыходу за пределы сегмента. Или контроль по битам-признакам защиты можетвыявить, что операция, выполнение которой запрашивается по указанному виртуальномуадресу, не разрешена, вследствие чего произойдет прерывание по защите сегмента.Операционная система должна предусматривать обработку всех этих ситуаций.Ассоциативная память (или аналогично высокоскоростная кэшпамять) играет решающуюроль в обеспечении эффективной работы механизма динамического преобразованияадресов. Если преобразование адресов производить с помощью чисто прямого отображенияс ведением в первичной памяти полного набора таблиц соответствия виртуальных иреальных адресов, типичное обращение к виртуальной памяти потребовало бы циклапамяти для доступа к таблице сегментов, второго цикла памяти для доступа к таблицестраниц и третьего для доступа к нужному элементу в реальной памяти.
Таким образом,каждое обращение к адресуемому элементу занимало бы три цикла памяти, т. е. реальноебыстродействие вычислительной системы составило бы лишь приблизительно треть отноминального значения, а две трети затрачивалось бы на преобразование адресов!Интересно, что при всего лишь восьми или шестнадцати ассоциативных регистрахразработчики добиваются для многих систем показателей быстродействия, составляющих90 и более процентов полных скоростных возможностей их управляющих (центральных)процессоров.На рис.
8.26 показана подробная структура таблиц, необходимых для комбинированнойстранично-сегментной системы. На самом верхнем уровне этой структуры находитсятаблица процессов, которая содержит по строке для каждого процесса, известного системе.Строка таблицы процессов, соответствующая конкретному процессу, указывает на таблицусегментов этого процесса.
Каждая строка таблицы сегментов процесса указывает натаблицу страниц соответствующего сегмента, а каждая строка таблицы страниц указываетлибо на страничный кадр, в котором размещается данная страница, либо на адрес внешнейпамяти, где можно найти эту страницу. В системе с большим количеством процессов,сегментов и страниц вся эта табличная структура может занимать значительную долюпервичной памяти. Здесь следует учитывать, что преобразование адресов производится вовремя выполнения быстрее, если все таблицы находятся в первичной памяти. Однако чембольше таблиц в памяти, тем меньшее количество процессов система в состоянииподдерживать в текущий период, а это может приводить к снижению пропускнойспособности.
Разработчики операционных систем должны анализировать многие подобныевзаимозависимости и принимать тщательно сбалансированные компромиссные решения —37только в этом случае можно обеспечить и эффективную загрузку системы, и оперативноепредоставление ее услуг пользователям.9.2 Стратегии управления виртуальной памятьюСтратегии вталкивания. Их цель - определить, в какой момент следует переписать страницуили сегмент из вторичной памяти в первичную. Вталкивание по запросу (по требованию)предполагает, что система ждет ссылки на страницу или сегмент от выполняющегопроцесса и только после появления ссылки начинает переписывать данную страницу илисегмент в первичную память.
Вталкивание с упреждением (опережением) предполагает, чтосистема пытается заблаговременно определить, к каким страницам или сегментам будетобращаться процесс. Если вероятность обращения высока и в первичной памяти имеетсясвободное место, то соответствующие страницы или сегменты будут переписываться восновную память еще до того, как к ним будет явно производиться обращение.Стратегии размещения. Их цель — определить, в какое место первичной памяти помещатьпоступающую страницу или сегмент.
В системах со страничной организацией решение оразмещении принимается достаточно тривиально, поскольку поступающая страница можетбыть помещена в любой свободный страничный кадр. Системы с сегментной организациейтребуют стратегий размещения, аналогичных тем, которые мы обсуждали применительно ксистемам мультипрограммирования с переменными разделами.Стратегии выталкивания.
Их цель — решить, какую страницу или сегмент следует удалитьиз первичной памяти, чтобы освободить место для помещения поступающей страницы илисегмента, если первичная память полностью занята.9.3 Стратегии выталкивания страницВ системах со страничной организацией все страничные кадры бывают, как правило,заняты. В этом случае программы управления памятью, входящие в операционную систему,должны решать, какую страницу следует удалить из первичной памяти, чтобы освободитьместо для поступающей страницы.
Мы рассмотрим следующие стратегии выталкиваниястраниц.·······Принцип оптимальности.Выталкивание случайной страницы.Первой выталкивается первая пришедшая страница (FIFO).Первой выталкивается дольше всего не использовавшаяся страница (LRU).Первой выталкивается наименее часто использовавшаяся страница (LFU).Первой выталкивается не использовавшаяся в последнее время страница (NUR).Рабочее множество.9.3.1 Принцип оптимальностиПринцип оптимальности (De70) говорит о том, что для обеспечения оптимальныхскоростных характеристик и эффективного использования ресурсов следует заменять тустраницу, к которой в дальнейшем не будет новых обращений в течение наиболеедлительного времени. Можно, конечно, продемонстрировать, что подобная стратегиядействительно оптимальна, однако реализовать ее, естественно, нельзя, поскольку мы неумеем предсказывать будущее.В связи с этим для обеспечения высоких скоростных характеристик и эффективногоиспользования ресурсов мы попытаемся наиболее близко подойти к принципуоптимальности, применяя различные методы выталкивания страниц, приближающиеся коптимальному.389.3.2 Выталкивание случайной страницыЕсли нам нужно иметь стратегию выталкивания страниц, которая характеризовалась бымалыми издержками и не являлась бы дискриминационной по отношению к каким-либоконкретным пользователям, то можно пойти по очень простому пути - выбирать случайнуюстраницу.
В этом случае все страницы, находящиеся в основной памяти, могут бытьвыбраны для выталкивания с равной вероятностью, в том числе даже следующая страница,к которой будет производиться обращение (и которую, естественно, удалять из памятинаиболее нецелесообразно).
Поскольку подобная стратегия по сути как бы рассчитана на«слепое» везение и похожа на подход «пан или пропал», в реальных системах онаприменяется редко.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 механизм вытолкнет эту страницу, а она скорее всего сразу же будетиспользоваться.Таким образом, практически любой метод выталкивания страниц, по-видимому, неисключает опасности принятия нерациональных решений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
