Общие указания

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

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

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

i) 1052

ii) 2221

iii) 5499

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

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

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

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

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

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

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

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. Архитектура IBM System/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. Компьютер содержит кэш, основную память и диск, используемый в качестве виртуальной памяти. Если интересующее нас слово находится в кэше, для доступа к нему требуется 20 ns. Если это слово отсутствует в кэше, но присутствует в основной памяти, на его загрузку в кэш требуется 60 ns, после чего процедура обращения повторяется. Если же искомое слово отсутствует в основной памяти, на его выборку с диска требуется 12 ins, после чего 60 пs затрачивается на загрузку слова в кэш, и процедура обращения к слову повторяется. Результативность поиска в кэше равна 0.9, в основной памяти — 0.6. Чему равно среднее время обращения к слову в описанной системе?

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

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

ПРИЛОЖЕНИЕ. ХЕШ-ТАБЛИЦЫ

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

Если метки элементов представляют собой числа в диапазоне от 0 до (М –1), то простейшее решениесостоит в использовании таблицы размером М- Элемент с меткой i вставляется в таблицу в позиции i. При условии, что размер всех элементов одинаков, поиск в таблице тривиален и сводится к индексированию таблицы на основе числового значения метки элемента. Кроме того, хранить метку элемента в таблице не обязательно, поскольку она однозначно определяет­ся положением элемента. Такая таблица называетсятаблицей прямого доступа(direct access table).

Если меткине являются числами, использование подхода, основанного на прямом доступе, все равно остается возможным. Обозначим элементы А[1], ..., A[N]. Каждый элементA[t] состоит из метки, или ключа ; и значения . Опре­делим функцию отображения I(k), дающую для всех ключей значения от 1 до М, такую, что для любых . В этом случае можно использовать таблицу прямого доступа длиной М.

Единственная трудность в применении данной схемы возникает, когда М гораздо больше, чем N. В этом случае в таблице оказывается слишком много не­использованных элементов, что приводит к неэффективному использованию па­мяти. Альтернативой является использование таблицы длиной N и хранение в ней N элементов (как значений, так и меток). В таком случае количество используемой памяти минимально, однако теперь трудной задачей становитсяпоиск нужного элемента в таблице. Применимы различные алгоритмы поиска.

• Последовательный поиск. Подход "в лоб", требующий много времени при работе с большими таблицами.

• Ассоциативный поиск.При наличии соответствующего аппаратного обеспече­ния все элементы таблицы могут просматриваться одновременно. Это очень специфичный подход, который не может применяться в общем случае.

• Бинарный поиск. Если метки (или их числовые отображения) расположены в таблице в возрастающем (убывающем) порядке, бинарный поиск значи­тельно быстрее последовательного (табл. 8.7) и не требует специального ап­паратного обеспечения.

Таблица 8.7. Средняя продолжительность поиска одного из N элементов в таблице размером М

Алгоритм	Продолжительность поиска
Прямой доступ
Последовательный поиск
Бинарный поиск	log2M
Линейное хеширование	2-
2-
Хеширование (переполнение с цепочками)

Многообещающе для поиска в таблице выглядит бинарный поиск. Основным его недостатком является то, что добавление нового элемента в таблицу — процесс обычно непростой и требует переупорядочения записей таблицы. Таким образом, бинарный поиск обычно используется для более или менее статичных таблиц, которые достаточно редко изменяются.

Конечно, хотелось бы избежать как перерасхода памяти при прямом доступе, так и излишней работы процессора при остальных перечисленных подходах. Наиболее часто используемым компромиссным методом являетсяхеширование. Этот метод, разработанный еще в 50-х годах, прост в реализации и имеет два достоинства. Во-первых, он позволяет найти большинство элементов за одно обращение к таблице, как при прямом доступе, а во-вторых, добавления элементов в таблицу и удаления элементов из нее выполняются без излишней сложности. Хеширование можно определить следующим образом. Предположим, что до N элементов хранятся в таблице размером М > N , причем М не намного больше N. Вставка элемента в таблицу осуществляется следующимобразом.

I1. Преобразуем метку элемента в почти случайное число п между 0 и М-1. Например, если метки представляют собой числовые значения, довольно распространенным методом является деление метки по модулю М.

I2.Используем полученное значение п в качестве индекса в хеш-таблице.

а. Если соответствующая запись в таблице пуста, значит, элемент ранее не был сохранен в таблице.

б. Если запись уже занята и ее метка соответствует искомой, значит, найден требуемый элемент.

в. Если запись занята и ее метка не соответствует заданной, продолжаем поиск в области переполнения.

Различные схемы хеширования отличаются способом обработки переполнения. Одна из широко распространенных технологий, обычно использующаяся в компиляторах, — технологиялинейного хеширования. В этом случае правило 12.б выглядит следующим образом.

12.б. Если запись занята, установить n=(n+1)modM и вернуться к шагу 12.а.