Рекомендуемая литература

Как и следовало ожидать, темы, связанные с виртуальной памятью, широко освещаются в литературе по операционным системам. В [MILE92] приведен обзор различных исследований в этой области; в [CARR84] подробно рассматриваются вопросы производительности. Заслуживает внимания и классическая статья [DENN70]. В [DOWD93] содержится анализ производительности разных алгоритмов замещения, а в [JAC098a] — обзор современного состояния разработок в области виртуальной памяти. В [JAC098b] рассматриваются вопросы аппаратной организации виртуальной памяти в современных микропроцессорах.

Всю сложность проблемы демонстрирует работа [IBM86], которая посвяще­на детальному описанию оптимизации стратегий виртуальной памятиMVS.

Одна из лучших характеристик различных схем управления памятью, использованных в разных реализациях UNIX, содержится в [VAHA96].

CARR84 Carr Virtual Memory Management—Ann Arbor, MI: UMI Research Press, 1984.

DENN70 Denning, P. Virtual Memory. — Computing Surveys, September 1970.

DOWU93 Dowdy L., Lowery C. P.S. to Operating Systems. — Upper Saddle River, NJ: Prentice Hall, 1993.

IBM86 IBM National Technical Support, Large Systems. Multiple Virtual Storage (MVS) Virtual Storage Tuning Cookbook. — Dallas Systems Center Technical Bul: letin G320 -0597, June 1986.

JAC098a Jacob В., Mudge T. Virtual Memory: Issues of Implementation.:—

Computer,June 1998.

JAC098b Jacob В., Mudge T. Virtual Memory in Contemporary Microprocessors. —JEER Micro, August 1998.

MILE92 Milenkovic M. Operating Systems: Concepts and Design.— New York: McGraw-Hill, 1992.

VAHA96 Vahalia U. UNIX Internals: The New Frontiers.— Upper Saddle River, NJ: Prentice Hall, 1996.

8.8. Задачи

8.1.Предположим, что таблица страниц текущего процесса выглядит так, как показано ниже. Все числа в таблице — десятичные, вся нумерация начинается с нуля, а все адреса представляют собой адреса отдельных байтов памяти. Размер страницы равен 1024 байт.

а. Опишите, как именно виртуальный адрес транслируется в физический адрес основной памяти

б. Какой физический адрес (если таковой имеется) соответствует каждому из приведенных виртуальных адресов? (Вы не должны пытаться обработать прерывание из-за отсутствия страницы).

1. 1052

2. 2221

3. 5499

Номер виртуальной страницы	Бит присутствия в памяти	Бит обращений	Бит модификации	Номер кадра
0	1	1	0	4
1	1	1	1	7
2	0	0	0	—
3	1	0	0	2
4	0	0	0	—
5	1	0	1	0

8.2.(В этой задаче, как и в предыдущей, все числа — десятичные, и вся нумерация начинается с нуля). Процессу выделены четыре кадра. Приведенная ниже таблица содержит время последней загрузки страницы в каждый кадр, время последнего обращения к странице в каждом кадре, а также биты обращений (R) и модификации (М). Все временные отрезки приведены относительно начала работы процесса (т.е. указаны промежутки времени от начала работы про­цесса до осуществления события, а не от события до момента рассмотрения). В настоящий момент генерируется прерывание обращения к странице номер 4. Содержимое какого кадра будет замещено в случае использования каждой из перечисленных стратегий? Поясните ваш ответ.

а. Алгоритм "первым вошел — первым вышел".

б. Алгоритм дольше всех не использовавшегося.

в. Часовой алгоритм.

г. Оптимальный алгоритм (при использовании указанной далее последовательности обращений к страницам).

д. Рассмотрите последовательность обращений к виртуальным страницам: 4,0, 0, 0, 2, 4, 2, 1, 0, 3, 2.Считая, что приведенное в таблице состояние памяти соответствует моменту непосредственно перед генерацией прерывания из-за отсутствия страницы, определите количество сгенерированных прерываний при использовании стратегии рабочего множества с размером окна, равным 4. Укажите все возникшие при этом прерывания.

	Номер виртуальной страницы	Кадр	Время загрузки	Время обращения	БитК	БитМ
	3	0	60	161	0	1
	1	1	130	160	0	0
	0	2	26	162	1	0
	3	3	20	163	1	1

8.3.Процесс обращается к страницам А, В, С,Dи Е в следующем порядке:ABCDABEABCDE. Примените алгоритм замещения "первым вошел — первым вышел" и определите количество пересылок страниц в процессе выполнения указанных обращений, если работа процесса выполняется с тремя изначально пустыми кадрами основной памяти. Решите ту же задачу для четырех кадров.

8.4.Процесс содержит восемь виртуальных страниц на диске, и ему выделено че­тыре фиксированных кадра в основной памяти. Далее выполняются обраще­ния к следующим страницам:

1, 0, 2. 2, 1, 7, 6, 7. 0, 1, 2, 0. 3, 0, 4. 5. 1, 5, 2, 4, 5, 6, 7, 6, 7, 2, 4, 2, 7, 3, 3, 2, 3.

а. Укажите последовательность размещения страниц в кадрах при использовании алгоритма замещения наиболее долго не использовавшейся страницы. Вычислите результативность обращения к основной памяти (считаем, что изначально все кадры пусты).

б. Выполните то же задание для алгоритма "первым вошел — первым вышел".

в. Сравните результативности обращения к основной памяти, вычисленные в пер­вых двух заданиях, и прокомментируйте эффективность использования указан­ных алгоритмов применительно к данной последовательности обращений.

8.5.Пользовательские таблицы страниц вVAXрасполагаются в виртуальных адре­сах системного пространства. Каковы преимущества такого размещения по сравнению с размещением таблиц в основной памяти? Каковы недостатки этого размещения?

8.6.Предположим, что фрагмент кода

for (i = 1; i <= n; i++)

a[il=b[i] +c[i].

выполняется в памяти с размером страницы, равным 1000 слов. Пусть n =1000. Напишите гипотетическую машинную программу, реализующую приведенный фрагмент (считая, что машина имеет полный набор команд для пересылки информации между регистрами и может использовать индексные регистры). Затем покажите последовательность обращения к страницам в процессе выполнения кода.

8.7.АрхитектураIBMSystem/370 использует двухуровневую структуру памяти, в которой эти уровни названы сегментами и страницами (несмотря на то что такая сегментация не обладает многими возможностями, рассмотренными в этой главе). Размер страницы в данной архитектуре может быть равен 2 или 4 Кбайт, а размер сегмента, являющийся в данной архитектуре фиксированным. — либо 64 Кбайт, либо I Мбайт. В архитектурах 370/ХА и 370/ESAразмер страницы равен 4 Кбайт, а размер сегмента — 1 Мбайт. Какие преимущества сегментации утрачены данной архитектурой? Какие выгоды приносит сегментацияSystem/370?

8.8.Предположим, что размер страницы — 4 Кбайт и что запись таблицы страниц занимает 4 байт. Сколько уровней таблиц страниц потребуется для отображения 64-битового адресного пространства, если таблица верхнего уровня занимает одну страницу?

8.9.Рассмотрим систему с отображением памяти на уровне страниц и использованием одноуровневой таблицы страниц. Предположим, что нужная нам таблица страниц уже находится в основной памяти.

а. Если обращение к памяти занимает 200 ns, чему будет равно время доступа к страничной памяти?

б. Добавим блок управления памятью, который создает накладные расходы в 20 nsкак при успешном, так и при неуспешном поиске. Предполагая, что результативность поиска вTLBсоставляет 85%, вычислите эффективное время доступа к памяти.

в. Поясните, как результативность поиска в TLB влияет на эффективное время доступа к памяти.

8.10.Рассмотрим последовательность обращения к страницам процесса с изначально пустым рабочим множеством изМкадров. Последовательность обращений к страницам длиной Р содержитNразличных номеров страниц. Для произвольного алгоритма замещения страниц определите.

а. Нижнюю границу количества прерываний из-за отсутствия страницы.

б. Верхнюю границу количества прерываний из-за отсутствия страницы.

8.11.При обсуждении алгоритма замещения страниц один из авторов провел аналогию с двигающейся по кругу снегоуборочной машиной. Снег равномерно засыпает кольцевую дорогу, по которой с постоянной скоростью движется снегоочиститель. Снег, отброшенный снегоочистителем, исчезает из рассматриваемой системы.

а. Какому из рассмотренных в разделе 8.2 алгоритмов соответствует эта аналогия?

б. Какое предположение о поведении рассматриваемого алгоритма замещения использует данная аналогия?

8.12.В архитектуреS/370 ключ управления памятью представляет собой управляющее поле, связанное с каждым кадром в основной памяти, с размером кадра, равным размеру страницы. Два бита этого ключа относятся к замещению страниц и представляют собой биты обращения и изменения. Бит обращения устанавливается равным 1, когда происходит чтение или запись ячейки памяти по адресу, находящемуся внутри кадра, и равным 0 — при первой загрузке новой страницы в кадр. Бит изменения становится равным 1 при выполнении операции записи в любую ячейку памяти в пределах кадра. Предложите способ определения страницы, которая не использовалась дольше других, используя только бит обращения.

8.13.Ключевым параметром производительности стратегииVSWSявляется значениеQ. Опыт показывает, что при фиксированном значенииQнаблюдаются значительные отличия в частоте генерации прерываний на разных стадиях выполнения процесса. Кроме того, если для разных процессов используется одно и то же значение Q, их частоты генерации прерываний существенно различаются. Эти наблюдения недвусмысленно указывают на то, что динамическое изменение значенияQа процессе жизни процесса может улучшить работу алгоритма. Предложите простейший механизм для реализации этой идеи.

8.14.Предположим, что задание разделено на четыре сегмента одинакового размера и что для каждого сегмента система строит таблицу дескрипторов страниц с восемью записями. Таким образом, описанная система представляет собой комбинацию сегментации и страничной организации. Предположим также, что размер страницы равен 2 Кбайт.

а. Чему равен максимальный объем каждого сегмента?

б. Каково максимальное логическое адресное пространство одного задания?

в. Предположим, что рассматриваемое задание обратилось к ячейке памяти с физическим адресом 00021АВС. Каков формат генерируемого для этого логического адреса? Каково максимально возможное физическое адресное пространство в этой системе?

8.15.Рассмотрим страничное логическое адресное пространство, состоящее из 32 страниц по 2 Кбайт каждая, отображенное на 1-Мбайтовое физическое пространство.

а. Каков формат логического адреса процессора?

б. Чему равна длина и ширина таблицы страниц (без учета битов прав доступа)?

в. Как повлияет на размер таблицы страниц уменьшение физической памяти в два раза?

8.16.Компьютер содержит кэш, основную память и диск, используемый в качестве виртуальной памяти. Если интересующее нас слово находится в кэше, для доступа к нему требуется 20ns.Если это слово отсутствует в кэше, но присутствует в основной памяти, на его загрузку в кэш требуется 60ns,после чего процедура обращения повторяется. Если же искомое слово отсутствует в основной памяти, на его выборку с диска требуется 12ins,после чего 60пsзатрачивается на загрузку слова в кэш, и процедура обращения к слову повторяется. Результативность поиска в кэше равна 0.9, в основной памяти — 0.6. Чему равно среднее время обращения к слову в описанной системе?

8.17.ЯдроUNIXпри необходимости динамически увеличивает стек процесса в виртуальной памяти, но никогда не уменьшает его. Рассмотрим вызов подпрограммы на языке программирования С, в которой имеется локальный массив размером 10 Кбайт, размещаемый в стеке. Ядро увеличит сегмент стека, для того чтобы этот массив мог быть успешно размещен в стеке. При возврате из подпрограммы указатель стека перемещается, и выделенное пространство может быть освобождено ядром, но оно этого не делает. Поясните, почему в этот момент можно уменьшить размер стека и почему ядроUNIXне делает этого.

8.18.Изобразите схему, аналогичную той, которая приведена на рис. 8.5, для вир­туальной адресацииLinux.