Страничная организация W2K

При создании процесса в принципе ему полностью доступно пользовательское пространстворазмером 2 Гбайт (минус 128 Кбайт). Это пространство разделяется на страницы фиксированного размера, каждая из которых может быть загружена в основную память.На практике для простоты учета страница может находиться в одном из трех состояний.

1. Доступна. Страница в настоящее время не используется процессом.

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

3. Размещена. Страницы, для которых диспетчер виртуальной памяти выде­ляет память в страничном файле (т.е. дисковом файле, в которыйзаписываются страницы при удалении их из основной памяти).

Различие между зарезервированной и размещенной памятью (1) позволяет минимизировать дисковое пространство, предназначенное определенному про­цессу, тем самым сохраняя это пространство для других процессов, и (2) раз­решает потоку или процессу объявить объем памяти, который будет быстро выделен при необходимости.

Схема управления резидентным множеством, используемая в W2K, — переменное распределение с локальной областью видимости (см. табл. 8.4). При первой активации процесса ему в качестве рабочего множества передается некоторое количество кадров основной памяти. Когда процесс обращается к странице, отсутствующей в памяти, одна из резидентных страниц этого процесса выгружается и на ее место загружается требующаяся страница. Рабочие множества активных процессов настраиваются во время работы с использованием следующих общих соглашений.

• При большом размере основной памяти диспетчер виртуальной памяти позволяет расти резидентным множествам активных процессов. Для этого при генерации прерывания из-за отсутствия страницы новая страница загружается в память, но старая при этом не выгружается.

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

РЕЗЮМЕ. КЛЮЧЕВЫЕ ТЕРМИНЫ И КОНТРОЛЬНЫЕ ВОПРОСЫ

Для эффективного использования процессора и систем ввода-вывода желательно поддерживать в основной памяти как можно большее количество процессов одновременно. Кроме того, желательно освободить программиста от ограничений, накладываемых на размер создаваемых им программ.

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

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

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

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

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

• Стратегия размещения. В случае выбора системы с использованием только сегментации все вновь загружаемые сегменты должны быть размещены в доступном пространстве в памяти.

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

• Управление резидентным множеством. Операционная система должна решать, какой именно объем памяти должен быть отведен тому или иному процессу при его загрузке в память. Этот объем может быть выделен статически, в момент создания процесса,либо изменяться динамически в процессе работы.

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

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

Ключевые термины

Ассоциативное отображение

Пропускная способность

Стратегия размещения

Рабочее множество страниц

Буфер поиска трансляции

Резидентное множество

Таблица сегментов

Виртуальная память

Сегмент

Таблица страниц

Внешняя фрагментация

Сегментация

Управление резидентным множеством

Внутренняя фрагментация

Страница

Кадр

Страничная организация

Физическая память

Кусочное распределение

Стратегия выборки

Хеширование

Локализация

Стратегия замещения страниц

Хеш-таблица

Прерывание из-за отсутствия страницы

Контрольные вопросы

8.1. В чем состоит отличие между простой страничной организацией и страничной организацией виртуальной памяти?

8.2. Поясните эффект снижения пропускной способности системы.

8.3. Почему принцип локализации так важен для использования виртуальной памяти?

8.4.Какие элементы обычно содержатся в записи таблицы страниц? Вкратце опишите каждый элемент.

8.5.В чем заключается цель буфера поиска трансляции (TLB)?

8.6.Вкратце опишите различные стратегии выборки страниц.

8.7.В чем заключается отличие между управлением резидентныммножеством и стратегией замещения страниц?

8.8. Как соотносятся между собой алгоритм замещения "первым вошел — первым вышел" и часовой?

8.9. В чем заключается буферизация страниц?

8.10.Почему невозможно объединить стратегию глобального замещения со стратегией фиксированного размещения?

8.11.В чем состоит разница между резидентным и рабочим множествами?

8.12. В чем состоит разница между очисткой по требованию и предварительной очисткой?

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

Как и следовало ожидать, темы, связанные с виртуальной памятью, широко освещаются в литературе по операционным системам. В [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.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.а.