Добавлен: 29.10.2018
Просмотров: 48095
Скачиваний: 190
296
Глава 3. Управление памятью
содержимое новых записей таблицы. Дайте им объяснения. (Записи, не под-
вергшиеся изменению, можно опустить.)
35. Студент заявил, что «теоретически основные алгоритмы замещения страниц
(FIFO, LRU, оптимальный) идентичны друг другу, за исключением атрибута, ис-
пользуемого для выбора замещаемой страницы».
а) Что является таким атрибутом для алгоритма FIFO? Алгоритма LRU? Опти-
мального алгоритма?
б) Дайте общий алгоритм для этих алгоритмов замещения страниц.
36. Сколько времени займет загрузка программы размером 64 Кбайт с диска, у кото-
рого среднее время поиска составляет 5 мс, время раскрутки — 5 мс, а дорожки
содержат по 1 Мбайт:
а) при размере страниц 2 Кбайт;
б) размере страниц 4 Кбайт?
Страницы разбросаны по диску случайным образом, и количество цилиндров
настолько велико, что можно не принимать в расчет вероятность того, что две
страницы будут размещены на одном и том же цилиндре.
37. У компьютера имеется четыре страничных блока. Время загрузки, время послед-
него обращения и биты R и M для каждой страницы приведены далее (время дано
в тактах системных часов).
Страница
Загружена
Последнее обращение
R
M
0
126
280
1
0
1
230
265
0
1
2
140
270
0
0
3
110
285
1
1
Какая страница будет удалена при использовании алгоритма:
а) NRU;
б) FIFO;
в) LRU;
г) «второй шанс»?
38. Предположим, что два процесса, А и Б, совместно используют страницу, отсут-
ствующую в памяти. Если процесс А потерпит ошибку на общей странице, запись
в таблице страниц процесса А должна быть обновлена, после того как страница
будет считана в память.
а) При каких условиях обновление таблицы страниц для процесса Б должно быть
задержано даже при том, что обработка ошибки отсутствия страницы процесса
А приведет к помещению совместно используемой страницы в память? Объ-
ясните.
б) Какова потенциальная стоимость задержки обновления таблицы страниц?
39. Рассмотрим следующий двумерный массив:
int X[64][64];
Вопросы
297
Предположим, что система имеет четыре страничных блока по 128 слов (в одно
слово помещается целочисленное значение). Программа, работающая с масси-
вом X, помещается как раз на одной странице и всегда занимает страницу по
адресу 0. А для подкачки данных используются оставшиеся три страничных блока.
Массив X хранится в порядке старшинства строк (то есть в памяти X[0][1] следует
за X[0][0]). Какой из приведенных далее фрагментов кода сгенерирует наименьшее
количество ошибок отсутствия страниц? Обоснуйте свой ответ и подсчитайте
общее количество таких ошибок.
Фрагмент А:
for (int j = 0; j < 64; j++)
for (int i = 0; i < 64; i++) X[i][j] = 0;
Фрагмент Б:
for (int i = 0; i < 64; i++)
for (int j = 0; j < 64; j++) X[i][j] = 0;
40. Вас наняла компания облачных вычислений, которая развертывает тысячи сер-
веров в каждом своем центре обработки данных. Недавно они узнали, что было
бы целесообразно обрабатывать ошибку отсутствия страницы на сервере А путем
считывания страницы не с его локального диска, а из оперативной памяти неко-
торых других серверов.
а) Как это может быть сделано?
б) При каких условиях такой подход был бы оправдан? Был бы осуществим?
41. Одна из первых машин с системой разделения времени, PDP-1 компании DEC,
имела память объемом 4 К 18-разрядных слов. В каждый конкретный момент
времени она содержала в памяти один процесс. Когда планировщик принимал
решение о запуске другого процесса, находящийся в памяти процесс записывался
на страничный барабан с 4 К 18-разрядных слов по окружности барабана. Запись
на барабан или чтение с него могли начинаться не только с нулевого, но и с любого
другого слова. Как вы думаете, почему был выбран именно магнитный барабан?
42. Компьютер выделяет каждому процессу 65 536 байт адресного пространства, ко-
торое разделено на страницы по 4096 байт. У рассматриваемой программы текст
занимает 32 768 байт, данные — 16 386 байт, а стек — 15 870 байт. Поместится ли
эта программа в адресном пространстве машины? А если бы размер страницы
был не 4096, а 512 байт, смогла бы тогда поместиться эта программа? На каждой
странице должны содержаться либо текст, либо данные, либо стек, но не смесь
двух или трех этих компонентов.
43. Было замечено, что количество команд, выполненных между ошибками отсутствия
страницы, прямо пропорционально количеству выделенных программе странич-
ных блоков. При удвоении доступной памяти удваивается и средний интервал
между ошибками отсутствия страницы. Предположим, что обычная команда вы-
полняется за 1 мкс, но если возникает ошибка отсутствия страницы, то она выпол-
няется за 2001 мкс (то есть на обработку ошибки затрачивается 2 мс). Если время
выполнения программы занимает 60 с и за это время возникает 15 000 ошибок
отсутствия страницы, то сколько времени заняло бы выполнение программы при
удвоении объема доступной памяти?
44. Группа разработчиков операционной системы для Frugal Computer Company об-
думывает способ снижения объема резервного хранилища, необходимого для их
298
Глава 3. Управление памятью
новой разработки. Ведущий специалист предложил вообще не сохранять текст
программы в области подкачки, а просто загружать его постранично по мере надоб-
ности непосредственно из двоичного файла. Существуют ли условия, при которых
этот замысел может быть осуществлен для текста программы? Существуют ли
условия, при которых он может быть применен в отношении данных?
45. Команда на языке машины, предназначенная для загрузки 32-разрядного слова
в регистр, содержит 32-разрядный адрес этого слова. Какое максимальное коли-
чество ошибок отсутствия страницы может быть вызвано при выполнении этой
команды?
46. Объясните разницу между внутренней и внешней фрагментацией. Какая из них
возникает в системах со страничной организацией? Какая из них возникает в си-
стемах, использующих чистую сегментацию?
47. При поддержке и сегментации, и страничной организации памяти, как в системе
MULTICS, сначала должен быть найден дескриптор сегмента, а затем идентифи-
катор страницы. Может ли таким же образом при двухуровневом поиске работать
и буфер быстрого преобразования адреса (TLB)?
48. Рассмотрим программу, у которой есть два показанных далее сегмента: содержа-
щий команды сегмент 0 и содержащий данные, используемые в режиме чтения
и записи, сегмент 1. У сегмента 0 имеется защита, позволяющая производить
только чтение и выполнение, а у сегмента 1 есть защита, позволяющая произво-
дить только чтение и запись. Система памяти относится к виртуальным системам
с подкачкой страниц по требованию, у которой есть 4-разрядный номер страницы
и 10-разрядное смещение. Таблицы страниц и защита находятся в следующем со-
стоянии (все числа в таблице являются десятичными).
Сегмент 0
Сегмент 1
Чтение и выполнение
Чтение и запись
№ виртуальной стра-
ницы
№ страничного
блока
№ виртуальной
страницы
№ страничного
блока
0
2
0
На диске
1
На диске
1
14
2
11
2
9
3
5
3
6
4
На диске
4
На диске
5
На диске
5
13
6
4
6
8
7
3
7
12
Для всех приведенных далее случаев либо дайте реальный (фактический) адрес
памяти, получающийся в результате динамического преобразования адреса, либо
идентифицируйте тип возникающей ошибки (которая может быть либо ошибкой
отсутствия страницы, либо ошибкой защиты):
а) извлечь данные из сегмента 1, страницы 1, из адреса со смещением 3;
б) сохранить данные в сегменте 0, странице 0, в адресе со смещением 16;
в) извлечь данные из сегмента 1, страницы 4, из адреса со смещением 28;
г) передать управление ячейке в сегменте 1, странице 3, со смещением 32.
Вопросы
299
49. Можете ли вы представить ситуацию, при которой была бы неприемлема идея
поддержки виртуальной памяти? Что можно было бы извлечь полезного из от-
сутствия поддержки виртуальной памяти? Обоснуйте ответ.
50. В виртуальной памяти предоставляется механизм для изолирования одного про-
цесса от другого. Какие трудности в управлении памятью могут возникать, если
разрешить одновременную работу двух операционных систем? Как эти трудности
можно разрешить?
51. Постройте гистограмму и вычислите средний и медианный размеры исполняемых
двоичных файлов на своем компьютере. В системе Windows следует взять в рас-
чет все файлы с расширениями
.exe
и
.dll
, в системе UNIX — все исполняемые
файлы в каталогах
/bin
,
/usr/bin
и
/local/bin
, не являющиеся сценариями (или
воспользуйтесь утилитой
file
, чтобы найти все исполняемые файлы). Принимая
во внимание внутреннюю фрагментацию и размер таблицы страниц, сделайте обо-
снованные предположения о размере записи в таблице страниц. Считайте, что все
программмы запускаются с одинаковой частотой и поэтому должны учитываться
на равных началах.
52. Напишите программу, моделирующую страничную систему и использующую ал-
горитм старения. В качестве параметра возьмите количество страничных блоков.
Последовательность обращений к страницам должна считываться из файла. Для
заданного файла входящих данных постройте график функции, отображающий
зависимость количества ошибок отсутствия страницы на 1000 обращений к памяти
от количества доступных страничных блоков.
53. Напишите программу, моделирующую миниатюрную систему подкачки, исполь-
зующую алгоритм WSClock. Система считается миниатюрной, поскольку будет
построена на предположении об отсутствии ссылок на запись (что не слишком
реалистично), а прекращение процесса и его создание проигнорированы (вечная
жизнь). Входными данными будут:
• пороговое значение периода восстановления;
• интервал прерывания от таймера, выраженный в виде количества обращений
к памяти;
• файл, содержащий последовательность ссылок на страницы.
а) Опишите основную структуру данных и алгоритмы в вашей реализации.
б) Покажите, что модель ведет себя ожидаемо для простого (но нетривиального)
примера ввода.
в) Постройте график функции, отображающей зависимость количества ошибок
отсутствия страницы от размера рабочего набора на 1000 обращений к памяти.
г) Объясните, что нужно для расширения программы для обслуживания потока
ссылок на страницы, который также включает записи.
54. Напишите программу, демонстрирующую влияние отсутствия нужных записей
в буфере TLB на эффективное время доступа к памяти, путем измерения времени
каждого доступа, затрачиваемого на проход большого массива.
а) Объясните главные подходы, лежащие в основе программы, и опишите, какой
демонстрации вы ожидаете от выходных данных для какой-нибудь существу-
ющей на практике архитектуры виртуальной памяти.
300
Глава 3. Управление памятью
б) Запустите программу на компьютере и опишите, насколько полученные данные
оправдали ваши ожидания.
в) Повторите задание б, но для более старого компьютера с другой архитектурой,
и объясните любые существенные различия в выходных данных.
55. Напишите программу, демонстрирующую разницу между использованием ло-
кальной и глобальной политики замещения страниц для простого случая исполь-
зования двух процессов. Вам понадобится подпрограмма, генерирующая строку
обращений к страницам на основе статистической модели. У этой модели есть N
состояний, пронумерованных от 0 до N – 1, которые представляют каждое из воз-
можных обращений к страницам, а вероятность p
1
, связанная с каждым состояни-
ем i, означает возможность того, что следующее обращение будет к той же самой
странице. В противном случае следующее обращение будет к одной из других
страниц с равной для всех них вероятностью.
а) Покажите, что подпрограмма генерации строки обращения к страницам рабо-
тает должным образом для какого-нибудь небольшого значения N.
б) Вычислите уровень ошибок отсутствия страницы для примера, в котором име-
ется один процесс и фиксированное количество страничных блоков. Объясните
правильность поведения программы.
в) Повторите задание б для двух процессов с независимой последовательностью
обращений к страницам и удвоенным количеством страничных блоков по срав-
нению с заданием б.
г) Повторите задание в, но с использованием не локальной, а глобальной политики.
Также сопоставьте уровень количества ошибок отсутствия страницы для каждо-
го процесса с уровнем, который был при использовании локальной политики.
56. Напишите программу, которая может быть использована для сравнения эффектив-
ности добавления поля тега к записям TLB, когда управление передается между
двумя программами. Поле тега используется для эффективного обозначения
каждой записи идентификатором процесса. Учтите, что TLB без тега может быть
смоделирован путем выставления требования, чтобы у всех записей TLB в любое
время имелся один и тот же тег. В качестве входных данных будут использоваться:
• количество доступных записей TLB;
• интервал прерывания от таймера, выраженный в виде количества обращений
к памяти;
• файл, содержащий последовательность записей (процесс, ссылки на страницы);
• цена обновления одной TLB-записи entry.
а) Опишите основную структуру данных и алгоритмы в вашей реализации.
б) Покажите, что модель ведет себя ожидаемо для простого (но нетривиального)
примера ввода.
в) Постройте график функции, отображающий количество обновлений TLB на
1000 обращений к памяти.