Главная / Эвм / Распределение памяти динамическими разделами

Распределение памяти динамическими разделами

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

6-3

Рис. 3.3 Распределение памяти динамическими разделами

Задачами операционной системы при реализации данного метода управления памятью является:

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

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

Загрузка задачи в выделенный ей раздел и корректировка таблиц свободных и занятых областей;

— после завершения задачи корректировка таблиц свободных и занятых областей.

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

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

Перемещаемые разделы

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

6-4

Рис. 3.4. Распределение памяти перемещаемыми разделами

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

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

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

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

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

— признак присутствия;

— признак модификации;

— признак обращения.

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

— дольше всего не использовавшаяся страница;

— первая попавшаяся страница;

— страница, к которой в последнее время было меньше всего обращений.

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

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

Виртуальный адрес при страничном распределении может быть представлен в виде пары (p, s), где P — номер виртуальной страницы процесса (нумерация страниц начинается с 0), а S — смещение в пределах виртуальной страницы. Учитывая, что размер страницы равен 2 в степени К, смещение S может быть получено простым отделением K младших разрядов в двоичной записи виртуального адреса. Оставшиеся старшие разряды представляют собой двоичную запись номера страницы P.

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

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

При страничной организации памяти

При каждом обращении к оперативной памяти аппаратными средствами выполняются следующие действия:

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

— из этой записи извлекается номер физической страницы;

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

На производительность системы со страничной организацией памяти влияют временные затраты, связанные с обработкой страничных прерываний и преобразованием виртуального адреса в физический. При часто возникающих страничных прерываниях система может тратить большую часть времени впустую, на свопинг страниц. Чтобы уменьшить частоту страничных прерываний, следовало бы увеличивать размер страницы. Кроме того, увеличение размера страницы уменьшает размер таблицы страниц, а значит, уменьшает затраты памяти. С другой стороны, если страница велика, то велика и фиктивная область в последней виртуальной странице каждой программы. В среднем на каждой программе теряется половина объема страницы, что в сумме при большой странице может составить существенную величину. Время преобразования виртуального адреса в физический в значительной степени определяется временем доступа к таблице страниц. В связи с этим таблицу страниц стремятся размещать в "быстрых" запоминающих устройствах. Это может быть, например, набор специальных регистров или память, использующая для уменьшения времени доступа ассоциативный поиск и кэширование данных.

Несмотря на многоуровневую организацию, хранение нескольких таблиц страниц большого размера по-прежнему представляют собой проблему. Ее значение особенно актуально для 64-разрядных архитектур, где число виртуальных страниц очень велико. Вариантом решения является применение инвертированной таблицы страниц (inverted page table). Этот подход применяется на машинах PowerPC, некоторых рабочих станциях Hewlett-Packard, IBM RT, IBM AS/400 и ряде других.

В этой таблице содержится по одной записи на каждый страничный кадр физической памяти. Существенно, что достаточно одной таблицы для всех процессов. Таким образом, для хранения функции отображения требуется фиксированная часть основной памяти, независимо от разрядности архитектуры, размера и количества процессов. Например, для компьютера Pentium c 256 Мбайт оперативной памяти нужна таблица размером 64 Кбайт строк.

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

Сегментное распределение памяти

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

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

— начальный физический адрес сегмента в оперативной памяти;

— размер сегмента;

— правила доступа;

— признаки модификации, присутствия, обращения к данному сегменту.

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

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

Рис. 3.7. Распределение памяти сегментами

Виртуальный адрес при сегментной организации памяти может быть представлен парой (G, s), где G — номер сегмента, а S — смещение в сегменте. Физический адрес получается путем сложения начального физического адреса сегмента, найденного в таблице сегментов по номеру G, и смещения S. Схема преобразования виртуального адреса в физический представлена на Рис. 3.8.

Рис. 3.8. Преобразование виртуального адреса в физический

При сегментной организации памяти

Недостатком данного метода распределения памяти является фрагментация на уровне сегментов и более медленное по сравнению со страничной организацией преобразование адреса.

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

Сегментно-страничное распределение представляет собой комбинацию страничного и сегментного механизма управления памятью и направлен на реализацию достоинств обоих методов. Так же как и при сегментной организации памяти, виртуальное адресное пространство процесса разделено на сегменты. Это позволяет определить разные права доступа к разным частям кодов и данных программы. Перемещение данных между памятью и диском осуществляется не сегментами, а страницами. Для этого каждый виртуальный сегмент и физическая память делятся на страницы равного размера, что позволяет более эффективно использовать память, сократив фрагментацию. В большинстве современных реализаций сегментно-страничной организации памяти все виртуальные сегменты образуют одно непрерывное линейное виртуальное адресное пространство. Для каждого процесса ОС создает отдельную таблицу сегментов, в которой содержатся дескрипторы всех сегментов процесса. Описание сегмента включает назначенные ему права доступа и другие характеристики, подобные тем, которые содержатся в дескрипторах сегментов при сегментной организации памяти. В поле базового адреса указывается не начальный физический адрес сегмента, отведенный ему при загрузке в оперативную память, а начальный линейный виртуальный адрес сегмента в пространстве виртуальных адресов. Исходный виртуальный адрес, заданный в виде пары (сегмент : смещение) однозначно преобразуется в линейный виртуальный адрес байта, который затем преобразуется в физический адрес страничным механизмом (Рис. 3.9).

Преобразование виртуального адреса в физический происходит в два этапа:

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

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

Рис. 3.9. Преобразование виртуального адреса в физический

При сегментной организации памяти

Разделяемые сегменты памяти

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

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

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

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

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