В. Столлингс - Операционные системы (1114679), страница 85
Текст из файла (страница 85)
Решите ту же задачу для четырех кадров. Процесс Р ц'сс содержит восемь виртуальных страниц на диске, и ему выделено четы е ~ьикс Р ф ксированных кадра в основной памяти. Далее выполняются обращения к следующим страницам: 1, О, 2, 2, 1, 7„6, 7, О, 1, 2, О, 3, О, 4, 5, 1, 5, 2, 4, 5, 6, 7, 6, 7, 2„4, 2, 7., ~3, 3, 2, 3, кажите по иге последовательность размещения страниц в кадрах при использовании алга и . . горитма замещения наиболее долго не использовавшейся страницы. Вычислите лите Результативность обращения к основной памяти (считаем, что изначально все кадры пусты).
". Вьжолните . вите то же задание для алгоритма '*первым вошел — первым вышел*'. "- СРааните е результативности обращения к основной памяти, вычисленные в первых двух д ух заданиях„и прокомментирунте эффективность использования указанных злго ит горитмов применительно к данной последовательности ооращений. Пользовательс .ьские таблицы страниц в УАХ располагаются в виртуальных адресах снстемног 'емного пространства. Каковы преимущества такого размещения по сравнению с размещением та и м таблиц в основной памяти? Каковы недостатк го размещения? 8.6.
Предположим, что фрагмент кода »ог (1 = 1; 1 <= г» 1++» а( ) '= Ь|.1 + с(1 выполняется в памяти с т с размером страницы„равным 1000 слов. а = 1000, Напишите гипотетическую машинную программ-:, реалнз ', * приведенный фрагмент (считая, штая что машина имеет полный набор комащ~~~".,' ' " пересылки информации и между регистрами и может использовать инд регистры). Затем покажи ите последовательность обрапзения к страницам э""' - »,':Ь:. цессе выполнения кода. 8.7.
Архитектура 1ВМ Буз$еп»/370 использует двухуровневую структуру пам ", которой эти уровни назв азваны сегментами и страницами (несмотря на такая сегментация не обладает многими возможностями, рассмотрен этой главе). азмер страни ). Р ницы в данной архитектуре может быть равен 4",» ' '.:- 4 Кбайт, а размер сегмента, являющийся в данной архитектуре фикси '"' -.; ', »! ным, — либо 64 Кбайт, либо 1 Мбайт.
В архитектурах 370/ХА и 37 '" азмер страницы равен 4 Кбайт, а размер сегмента — 1 Мбайт. Каки "" размер страницы равен имущества сегментации утрачены данной ар р " а хитекту ой7 Какие выгоды ? сит сегментация Бузят/370. 8.8. Предположим, что размер страницы— ы — 4 Кбайт и что запись таблицы ст ' " .у я ля отоб»ч занимает 4 байт.
Сколько уровней таблиц страниц потребуется для отоб ния 64-битового адресного пространства, если таблица верхнего уровня ' " л мает одну страницу? Ё 8.9. Рассмотрим систему с отображением памяти н ур р а овне ст аниц и испо кием одноуровневой таблицы страниц. Предположим, что нужная нам страниц уже находится в основной памяти. а. Если обращение к памяти занимает 200 из, му у р че 6 дет авно время д » к страничной памяти? б.
Д б . б ок управления памятью, который создает ад накл ные раск, о авим л иске. П едполага,' 20 яз как при успешном, так и при неуспешном поиске. р Р езультативность поиска в Т1.В составляет о, 85')о вычислите эффек7; время доступа к памяти. в. Поясните, как результативность поиска в Тт '~ вл т '~ влияет на эффективное доступа к памяти. 8.10. Р мотрим последовательность обращения к с р ц ро т аницам процесса с изва асс ес .
сть обраще пустым ра очим множес б еством из М кадров. Последовательно раЖ,. страницам длиной Р содержит Ж различных номеров страниц. Для пр, „, ' " », ного алгоритма замещения страниц определите. а. Нижнюю границу количества прерываний из-з у - а отс тствия страницы::.':„.'~ж, 6, Верхнюю границу количества прерываний и - ут й з-за ото ствия страницьь-;."-,' з авто в провел ан 8.11. П и обсуждении алгоритма замещения страниц один из авторо про ри суждении ной. Снег равномерно засьшает» двигающейся по кругу снегоуборочной машино . Р ль „.
цевую дорогу, по которой с постоянной скоростью д вижется снегоочистите отброшенный снегоочистителем, исчезает из расс тр ма иваемой системы. а. Какому из рассмотренных в разделе 6.2 алгорит мов соответствует эта зная(? б. Какое предположение о поведении рассматривае мого алгоритма з ? .ЪФ' '- использует данная аналогия. пам бой„:, 8.12.
В архитектуре 8~370 ключ управления пам памятью и едставляет со Р ляющее поле, связанное с каждым кадро ом в основной памяти, с размере, азмеру страницы. Два бита этого ключа относятся к з ра, равным р . $.» Часть 3." страниц и представляют собой биты обращения и изменения. Бит обращения устанавливается равным 1, когда происходит чтение или запись ячейки памя ти по адресу, находящемуся внутри кадра. и равным 0 — при первой загрузке новой страницы в кадр. Бит изменения становится равным 1 при выполнении операции записи в любую ячейку памяти в пределах кадра.
Предложите спо соб определения страницы, которая не использовалась дольше других, исполь зуя только бит обращения. Ключевым параметром производительности стратегии Ъ'БЖБ является значение Я. Ог)ыт показывает, что при фиксированном значении Ч наблюдаются значительные отличия в частоте генерации прерываний на разных стадиях выполнения процесса. Кроме того, если для разных процессов используется одно и то же значение 9, их частоты генерации прерываний существенно различаются. Эти наблюдения недвусмысленно указывают на то, что динамическое изменение значения 9 в процессе жизни процесса может улучшить работу алгоритма. Предложите простейший механизм для реализации этой идеи. Предположим, что задание разделено на четыре сегмента одинакового размера и что для каждого сегмента система строит таблицу дескрипторов страниц с восемью записями.
Таким образом, описанная система представляет собой комбинацию сегментации и страничной организации. Предположим также, что размер страницы равен 2 Кбайт. а. Чему равен максимальный объем каждого сегмента? б. Каково максимальное логическое адресное пространство одного задания? в. Предположим, что рассматриваемое задание обратилось к ячейке памяти с физическим адресом 00021АЬС.
Каков формат генерируемого для этого логического адреса? Каково максимально возможное физическое адресное пространство в этой системе7 Рассмотрим страничное логическое адресное пространство, состоящее из 32 страниц по 2 Кбайт каждая, отображенное на 1-Мбайтовое физическое пространство. а. Каков формат логического адреса процессора7 6. Чему равна длина и ширина таблицы страниц (без учета битов прав доступа)? в.
Как повлияет на размер таблицы страниц уменьшение физической памяти в два раза7 Компьютер содержит кэш, основную память и диск, используемый в качестве виртуальной памяти. Если интересующее нас слово находится в каше, для достУпа к нему требуется 20 лз. Если это слово отсутствует в каше, но присутствует в основной памяти, на его загрузку в кэш требуется 60 вз. после чего процедура обращения повторяется. Если же искомое слово отсутствует в основной памяти, на его выборку с диска требуется 12 щв, после чего 60 яз затрачивается на загрузку слова в кэш„и процедура обращения к слову повторяется.
Результативность поиска в каше равна 0.9, в основной п(змяти — 0.6 Чему равно среднее время обращения к слову в описанной системе7 Ядро (Л»»1Х при необходимости динамически увеличивает стек процесса в виртуальной памяти, но никогда не уменьшает его. Рассмотрим вызов подпрограммы на языке программирования С„в которой имеется локальный массив Размером 10 Кбайт„размещаемый в стеке. Ядро увеличит сегмент стека, для того чтобы этот массив мог быть успешно размещен в стеке. При возврате из подпрограммы указатель стека перемещается, и выделенное пространство может быть освобождено ядром, но оно этого не делает.
Поясните, почему в этот момент можно уменьшить размер стека и почему ядро 1Л»)1Х не делает этого. Главаз Вир у ьнаяпамять .б 18. Изобразите схему, ан о налогичиую той, которая приведена на рис. 8., для тунльной адресации 1 ьппх. ..Ф ПРИЛОЖЕНИЕ. ХЕШ-Т~ЛИЩ1-,='=,;;:,-ж;- Рассмотрим следующую з а ЩУю заДачУ. В таблиЦе хРанитсЯ множество из Ж йэь.;; ентов, каждый из которых сос ых состоит из метки и некоторой дополнительной ~'.;'.:.':~! ормации, которую можно с считать значением элемента. Мы хотим иметь вов„" ожность выполнять с та аблицей ряд обычных операций, таких как вст даленне н поиск данного элемента по его метке.
О аь Если метки элементов предс в представляют собой числа в диапазоне от до М М. Э о простейшее решение состо состоит н использовании таблицы размером . лемейи '" меткой 1 вставляется в та л таблицу в позиции 1. При условии, что размер вев~(,;,"-',," лементов одинаков, пои поиск в таблице тривиален и сводится к индексиро аблицы на основе числово ового значения метки элемента. Кроме того, хранньмь'.'~ ьетку элемента в та лице не б не обязательно, поскольку она однозначно определяевь~::-" я положением элемента.
. Такая таблица называется таблицей прямого достуищ': ' ь11гес1 ассенн 1аЫе). Если метки не являются я числами использование подхода, основанного ф~з Ъ 1рямом доступе, все равно оста остается возможным. Обозначим элементы А(Ц, Я~Ф1. Каждый элемент К А",„' состоит из метки или ключа Й; и значения оь. Онра~ Ф 1елим функцию ото ражения ( ), б 1(А) дающую для всех ключей значения от 1 Ч" такую что г'(к )~1~~1.1 для любых 1~ г. В этом случае можно использова ' ", габлицу прямого доступа длиной М. Единственная трудность в пр и именении данной схемы возникает, когда Ж' гораздо больше, чем И, В этом случае в таблице оказывается слишком много Мвнеэ ь ~ ективному использованию па,",' использованных элементов, что приводит к н эфф мяти.
Альтернативой является использование таблиц д ы линой Ф и хранение ~~-',", ней Ю элементов (как значений, так и меток). В . В таком сл ае количество и~~. уч пользуемой памяти минимально, однако теперь труд ной задачей становится" иск нужного элемента в таблице. Применимы ра р зличные алго итмы поиска. б тРеб ющий много ВРемени е ° Последовательный поиск. Подход в лоб, требу работе с большими таблицами. ° Ассоциативный поиск. При наличии соответствующ его аппаратного обеспе ния все элементы таблицы моГут просматриваться д Ре ться о нов менно. Это и специфичный подход, который не может применяться в общем случае- ° Бинарный поиск.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
