Страничное распределение

Лекция № 12

Тема. Сторінковий розподіл віртуальної пам'яті. Сегментний розподіл віртуальної пам'яті Сегментно-сторінковий розподіл віртуальної пам'яті.

Цель.

1. Учебная. Объяснить структуру страничной памяти и распределении адресного пространства.

2. Развивающая. Развивать логическое мышление и естественное - научное мировоззрение.

3. Воспитательная. Воспитывать интерес к научным достижением и открытием.

Межпредметные связи:

· Обеспечивающие: информатика, математика, вычислительная техника и МП, системы программирования.

· Обеспечиваемые: Стажерская практика

Методическое обеспечение и оборудование:

1. Методическая разработка к занятию.

2. Учебный план.

3. Учебная программа

4. Рабочая программа.

5. Инструктаж по технике безопасности.

Технические средства обучения: персональный компьютер.

Обеспечение рабочих мест:

· Рабочие тетради

Ход лекции.

Организационный момент.

Анализ и проверка домашней работы

3 Ответьте на вопросы:

1) В чем состоит принципиальное отличие состояний «ожидания» и «готовности» потока, ведь и в том и в другом он ожидает некоторого события?

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

3) Как делится виртуальное адресное пространство процесса?

4) Что из себя представляет назначенное виртуальное адресное пространство?

5) В чем состоит различие максимально возможного виртуального адресного простран­ство процесса и назначенного (выделенного) процессу виртуального адресного про­странства?.

6) Что называется виртуальным адресным пространством?

7) Как идентифицируются переменные и команды на разных этапах жизненного цикла программы?

8) В чем состоит функция защиты памяти?

9) Перечислите функции ОС по управлению памятью в мультипрограммной системе.

Страничное распределение

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

Размер страницы выбирается равным степени двойки: 512, 1024, 4096 байт и т. д. Это позволяет упростить механизм преобразования адресов. При создании процесса ОС загружает в оперативную память несколько его вир­туальных страниц (начальные страницы кодового сегмента и сегмента данных). Копия всего виртуального адресного пространства процесса находится на диске.
Смежные виртуальные страницы не обязательно располагаются в смежных фи­зических страницах. Для каждого процесса операционная система создает таблицу страниц — информационную структуру, содержащую записи обо всех вир­туальных страницах процесса.

Рис. 1 Страничное распределение памяти

Запись таблицы, называемая дескриптором страницы, включает следующую ин­формацию:

□ номер физической страницы, в которую загружена данная виртуальная стра­ница;

□ признак присутствия, устанавливаемый в единицу, если виртуальная страни­ца находится в оперативной памяти;

□ признак модификации страницы, который устанавливается в единицу вся­кий раз, когда производится запись по адресу, относящемуся к данной стра­нице;

□ признак обращения к странице, называемый также битом доступа, который устанавливается в единицу при каждом обращении по адресу, относящемуся к данной странице.

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

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

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

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

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

Виртуальный адрес при страничном распределении может быть представлен в виде пары (р, s_v), где р — порядковый номер виртуальной страницы процесса (нумерация страниц начинается с 0), a s_v — смещение в пределах виртуальной страницы. Физический адрес также может быть представлен в виде пары (n, s_f), где п — номер физической страницы, a s_f — смещение в пределах физической страницы. Задача подсистемы виртуальной памяти состоит в отображении (р, s_v) в (п, s_f).

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

Первое из них состоит в том, что объем страницы выбирается равным степени двойки — 2^к. Из этого следует, что смещение s может быть получено простым от­делением k младших разрядов в двоичной записи адреса, а оставшиеся старшие разряды адреса представляют собой двоичную запись номера страницы (при этом неважно, является страница виртуальной или физической). Например, если размер страницы 1 Кбайт (2¹⁰), то из двоичной записи адреса 5071₈ = 101 000 111 001₂ можно определить, что он принадлежит странице, номер ко­торой в двоичном выражении равен 10₂ и смещен относительно ее начала на 1000 111 001₂ байт (рис.2).

Рис. 2 Двоичное представление адресов

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

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

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

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

Итак, пусть произошло обращение к памяти по некоторому виртуальному адре­су. Аппаратными схемами процессора выполняются следующие действия:

1. Из специального регистра процессора извлекается адрес AT таблицы страниц активного процесса. На основании начального адреса таблицы страниц, номе­ра виртуальной страницы р (старшие разряды виртуального адреса) и длины отдельной записи в таблице страниц L (системная константа) определяется адрес нужного дескриптора в таблице страниц: a=AT+(pxL).

2. Из этого дескриптора извлекается номер соответствующей физической стра­ницы — n.

3. К номеру физической страницы присоединяется смещение s (младшие разряды виртуального адреса).

Типичная машинная инструкция требует 3-4 обращений к памяти (выборка команды, извлечение операндов, запись результата). И при каждом обращении происходит либо преобразование виртуального адреса в физический, либо обра­ботка страничного прерывания. Время выполнения этих операций в значитель­ной степени влияет на общую производительность вычислительной системы, поэтому столь большое внимание разработчиков уделяется оптимизации вирту­альной памяти.

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

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

При выборе страницы на выгрузку могут быть использованы различные крите­рии, смысл которых сводится к одному: на диск выталкивается страница, к которой в будущем начиная с данного

Рис.4 Схема преобразования виртуального адреса в физический

момента дольше всего не будет обращений. Поскольку точно предсказать ход вычислительного процесса невозможно, то не­возможно точно определить страницу, подлежащую выгрузке. В таких условиях решение принимается на основе неких эмпирических критериев, часто осно­вывающихся на предположении об инерционности вычислительного процесса. Так, например, из того, что страница не использовалась долгое время, делается вывод о том, что она, скорее всего, не будет использоваться и в ближайшее вре­мя. Однако привлечение критериев такого рода не исключает ситуаций, когда сразу после выгрузки страницы к ней происходит обращение и она снова должна быть загружена в память. Вероятность таких «напрасных» перемещений на­столько велика, что в некоторых реализациях виртуальной памяти вообще отка­зываются от количественных критериев и предпочитают случайный выбор, при котором на диск выгружается первая попавшаяся страница. Возникающее при этом некоторое увеличение интенсивности страничного обмена компенсируется снижением вычислительных затрат на поддержание и анализ критерия выборки страниц на выгрузку.

Наиболее популярным критерием выбора страницы на выгрузку является число обращений к ней за последний период времени. Вычисление этого критерия про­исходит следующим образом. Операционная система ведет для каждой страни­цы программный счетчик. Значения счетчиков определяются значениями при­знаков доступа. Всякий раз, когда происходит обращение к какой-либо странице, процессор устанавливает в единицу признак доступа в относящейся к данной странице записи таблицы страниц. ОС периодически просматривает признаки доступа всех страниц во всех существующих в данный момент записях таблицы страниц. Если какой-либо признак оказывается равным 1 (было обращение), то система сбрасывает его в 0, увеличивая при этом на единицу значение связанно­го с этой страницей счетчика обращений.Когда возникает необходимость уда­лить какую-либо страницу из памяти, ОС находит страницу, счетчик обращений которой имеет наименьшее значение. Для того чтобы критерий учитывал интен­сивность обращений за последний период, ОС с соответствующей периодично­стью обнуляет все счетчики.

Интенсивность страничного обмена может быть также снижена в результате так называемой упреждающей загрузки, в соответствии с которой при возникнове­нии страничного прерывания в память загружается не одна страница, содержа­щая адрес обращения, а сразу несколько прилегающих к ней страниц. Здесь ис­пользуется эмпирическое правило: если обращение произошло по некоторому адресу, то велика вероятность того, что следующие обращения произойдут по со­седним адресам.

Другим важным резервом повышения производительности системы является пра­вильный выбор размера страницы. Каким же должен быть оптимальный размер страницы? С одной стороны, чтобы уменьшить частоту страничных прерываний, следовало бы увеличивать размер страницы. С другой стороны, если страница велика, то велика и фиктивная область в последней виртуальной странице каж­дого процесса. Если учесть, что в среднем в каждом процессе фиктивная область составляет половину страницы, то в сумме при большом объеме страницы поте­ри могут составить существенную величину. Из приведенных соображений следует, что выбор размера страницы является сложной оптимизационной задачей, требующей учета многих факторов. На практике же разработчики ОС и процес­соров ограничиваются неким рациональным решением, пригодным для широко­го класса вычислительных систем. Типичный размер страницы составляет не­сколько килобайт, например, наиболее распространенные процессоры х86 и Pentium компании Intel, а также операционные системы, устанавливаемые на этих процессорах, поддерживают страницы размером 4096 байт (4 Кбайт).

Размер страницы влияет также на количество записей в таблицах страниц. Чем меньше страница, тем более объемными являются таблицы страниц процессов и тем больше места они занимают в памяти.Учитывая, что в современных процес­сорах максимальный объем виртуального адресного пространства процесса, как правило, не меньше 4 Гбайт (2³²), то при размере страницы 4 Кбайт (2¹²) и длине записи 4 байта для хранения таблицы страниц может потребоваться 4 Мбайт памяти! Выходом в такой ситуации является хранение в памяти только той час­ти таблицы страниц, которая активно используется в данный период времени — так как сама таблица страниц хранится в таких же страницах физической памя­ти, что и описываемые ею страницы, то принципиально возможно временно вы­теснять часть таблицы страниц из оперативной памяти.

Именно такой результат может быть достигнут путем более сложной структури­зации виртуального адресного пространства, при котором все множество вирту­альных адресов процесса делится на разделы, а разделы делятся на страницы (рис.5). Все страницы имеют одинаковый размер, а разделы содержат одина­ковое количество страниц. Если размер страницы и количество страниц в разделе выбрать равными степени двойки (2^к и 2ⁿ соответственно), то принадлежность виртуального адреса к разделу и странице, а также смещение внутри страницы можно определить очень просто: младшие k двоичных разрядов дают смещение, следующие n разрядов представляют собой номер виртуальной страницы, а ос­тавшиеся старшие разряды (обозначим их количество m) содержат номер раздела.

Для каждого раздела строится собственная таблица страниц. Количество дескрип­торов в таблице и их размер подбираются такими, чтобы объем таблицы оказался равным объему страницы. Например, в процессоре Pentium при размере страницы 4 Кбайт длина дескриптора страницы составляет 4 байта и количество записей в таблице страниц, помещающейся на страницу, равняется соответственно 1024. Каж­дая таблица страниц описывается дескриптором, структура которого полностью совпадает со структурой дескриптора обычной страницы. (Файловый дескриптор — неотрицательное целое число, присваиваемое ОС открытому процессом файлу). Эти дескрипторы сведены в таблицу разделов, называемую также каталогом страниц. Физический адрес таб­лицы разделов активного процесса содержится в специальном регистре процессора и поэтому всегда известен операционной системе. Страница, содержащая таблицу разделов, никогда не выгружается из памяти, в противном случае работа виртуаль­ной памяти была бы невозможна.

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

Проследим более подробно схему преобразования адресов для случая двухуровне­вой структуризации виртуального адресного пространства (рис. 6):

1. Путем отбрасывания k+n младших разрядов в виртуальном адресе определя­ется номер раздела, к которому принадлежит данный виртуальный адрес.

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

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

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

Рис. 5 Структура виртуального адресного пространства с разделами

Рис. 6 Схема преобразования виртуального адреса для двухуровневой структуризации адресного пространства

Страничное распределение памяти может быть реализовано в упрощенном вариан­те, без выгрузки страниц на диск. В этом случае все виртуальные страницы всех процессов постоянно находятся в оперативной памяти. Такой вариант страничной организации хотя и не предоставляет пользователю преимуществ работы с вирту­альной памятью большого объема, но сохраняет другое достоинство страничной организации — позволяет успешно бороться с фрагментацией физической памяти. Действительно, во-первых, программу можно разбить на части и загрузить в разроз­ненные участки свободной памяти, во-вторых, при загрузке виртуальных страниц никогда не образуется неиспользуемых остатков, так как размеры виртуальных и физических страниц совпадают. Такой режим работы системы управления памятью используется в некоторых специализированных ОС, когда требуется высокая реак­тивность системы и способность выполнять переменный набор приложений (при­мер — ОС семейства Novell NetWare 3.x и 4.x).