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