Операционные системы. Управление ресурсами
Фиксированные разделы.
Эта модель памяти применяется в вычислительных системах, не имеющих аппаратных средств трансляции адресов. Процесс загружается в непрерывный участок памяти (раздел), привязка адресов выполняется при загрузке. Размер раздела равен размеру виртуального адресного пространства процесса, который, следовательно, не может превышать размера доступной реальной памяти. Процесс в ходе своего выполнения может выдавать запросы на выделение/освобождение памяти. Все эти запросы удовлетворяются только в пределах виртуального адресного пространства процесса, а следовательно - в пределах выделенного ему раздела реальной памяти.
Примером ОС, работающей в такой модели, памяти может быть OS/360, ныне уже не применяющаяся, но существовавшая в двух основных вариантах: MFT (с фиксированным числом задач) и MVT (с переменным числом задач). В первом варианте при загрузке ОС реальная память разбивалась на разделы оператором. Каждая задача (процесс) занимала один раздел и выполнялась в нем. Во втором варианте число разделов и их положение в памяти не было фиксированным. Раздел создавался в свободном участке памяти перед началом выполнения задачи и имел размер, равный объему памяти, заказанному задачей. Созданный раздел фиксировался в памяти на время выполнения задачи, но уничтожался при окончании ее выполнения.
В более общем случае для процесса может выделяться и несколько разделов памяти, причем их выделение/освобождение может выполняться динамически (пример - MS DOS). Однако, общими всегда являются следующие правила:
- раздел занимает непрерывную область реальной памяти;
- выделенный раздел фиксируется в реальной памяти;
- после выделения раздела процесс работает с реальными адресами в разделе.
Задача эффективного распределения памяти (в любой ее модели) сводится прежде всего к минимизации суммарного объема "дыр". Ниже мы даем определения дыр, общие для всех моделей памяти.
Дырой называется область реальной памяти, которая не может быть использована. Различают дыры внешние и внутренние.
Рисунок 3.2 иллюстрирует внешние и внутренние дыры в системе OS/360.
 Рис.3.2. Разделы в реальной памяти OS/360 |
Внешней дырой называется область реальной памяти, которая не распределена никакому процессу, но слишком мала, чтобы удовлетворить запрос на память. На Рис 3.2.б суммарный размер свободных областей, возможно, превышает запрос, но каждая из этих областей в отдельности меньше запроса, поэтому все эти свободные области являются внешними дырами.
Для управления памятью формируются те или иные управляющие структуры (заголовки), которые также занимают память. В некоторых системах общий объем заголовочной памяти может быть очень большим, и в таких случаях следует учитывать также и заголовочные дыры - области памяти, которые содержат не используемую в данный момент управляющую информацию. В системах с реальной памятью заголовочные дыры практически отсутствуют.
Хотя в любом случае невозможность использовать память является злом, внешние дыры, являются "меньшим злом", так как, во-первых, блок свободной памяти становится дырой из за малого своего размера, а "малый" - понятие относительное, во-вторых, в моделях памяти с динамической трансляцией адресов существуют методы борьбы с внешними дырами.
Модель с фиксированными разделами представляет весьма ограниченную версию управления памятью. Вытеснение здесь вообще не реализуется, процесс, которому недостает памяти, просто блокируется до освобождения требуемого ресурса (в OS/360 MFT можно было наблюдать даже такое явление: задача, требующая объема памяти, превышающего размер раздела, просто "запирала" этот раздел до перезагрузки системы). Стратегия подкачки здесь примитивная: весь процесс размещается в реальной памяти при его создании.
В варианте MFT практически отсутствует и стратегия размещения: процесс размещается с начала раздела, а решение о размещении раздела и о распределении задач по разделам принимает оператор. А вот в варианте MVT, поскольку границы разделов не зафиксированы, ОС необходимо принимать решение о размещении. В этой ОС уровень мультипрограммирования был невысок (обычно 4 - 5 процессов), поэтому стратегия размещения принималась простейшая, а вот в системах с более высоким уровнем мультипрограммирования и, следовательно, со значительной фрагментацией памяти может оказаться целесообразным выбор более сложной и гибкой стратегии.
Первый вопрос, решаемый в стратегии размещения - способ представления свободной памяти. Существует два основных метода такого представления: списки свободных блоков и битовые карты. В первом методе ОС из свободных блоков памяти организует линейный список и хранит адрес начала этого списка. При обработке такого списка должна учитываться необходимость слияния двух смежных свободных блоков в один свободный блок суммарного размера. Эта задача может быть существенно упрощена, если список упорядочивается по возрастанию адресов блоков. Во втором методе память условно разбивается на некоторые единицы распределения (параграфы) и создается "карта памяти" (memory map) - битовый массив в котором каждый бит соответствует одному параграфу памяти и отображает его состояние: 1 - занят, 0 - свободен. Поиск свободного блока требуемого размера сводится к поиску цепочки нулевых бит требуемой длины. Выбор размера параграфа определяется компромиссом между потерями памяти на внутренних дырах (при большом размере параграфа) и потерями на размещение в памяти самой карты (при малом размере параграфа).
При не очень большой фрагментации памяти списки свободных блоков занимают меньше места, чем карта, но их обработка несколько сложнее.
Выбранная структура представления свободной памяти не ограничивает выбор стратегии размещения.
Простейшей стратегией размещения является стратегия "первый подходящий" (first hit): просматривается список свободных блоков (или карта памяти) и выбирается первый же найденный блок, у которого размер не меньше требуемого.
Если размер найденного блока превышает запрошенный, то оставшаяся его часть оформляется как свободный блок. При всей своей простоте эта стратегия дает неплохие результаты и применяется в большинстве систем с фиксированными разделами и с сегментацией (см. ниже). При значительной фрагментации алгоритм может быть модифицирован кольцевым поиском. Если всякий раз поиск начинается с начала списка/карты, то маленькие свободные участки будут накапливаться в списка/карты и для нахождения свободного блока значительной длины надо будет сначала выбрать и отбросить много маленьких блоков. При кольцевом поиске поиск всякий раз начинается с того места, на котором он закончился в прошлый раз, а при достижении конца списка/карты - продолжается с начала. Таким приемом сокращается среднее время поиска.
Другой несложной стратегией является "самый подходящий" (best hit): просматривается весь список свободных блоков (или карта памяти) и выбирается блок, размер которого равен запросу или превышает его на минимальную величину. Хотя на первый взгляд этот метод может показаться более эффективным, он дает в среднем худшие результаты, чем "первый подходящий". Во-первых, это объясняется тем, что здесь следует обязательно просмотреть весь список или карту, во-вторых, тем, что здесь более интенсивно накапливаются внешние дыры, так как остатки от "самых подходящих" блоков оказываются маленького размера. Существенным же преимуществом этой стратегии является то, что она охраняет большие свободные блоки от "разбазаривания по мелочам".
Первый недостаток метода "самый подходящий" может быть преодолен при упорядочении списка свободных блоков по возрастанию размеров: полный просмотр списка тогда не потребуется, но будет усложнена задача слияния смежных блоков. Еще более ускоряет поиск разбиение списка свободных блоков на несколько подсписков, каждый из подсписков содержит блоки, размер которых ограничен сверху и снизу. Поиск ускоряется за счет просмотра только подсписка, соответствующего запросу, если в подсписке выбирать первый подходящий, то отчасти сглаживается и острота проблемы внешних дыр.
При представлении свободной памяти в виде карты аналогичный эффект может быть получен при создании нескольких карт разного масштаба и поиске по той карте, масштаб которой соответствует запрошенному размеру блока.
Поскольку модель с фиксированными разделами ограничивает виртуальное адресное пространство размерами реальной памяти, возникает проблема больших программ, не вмещающихся в доступную память. Преодоление этого ограничения достигается созданием программ с оверлейной (overlay - перекрытие) структурой. Структура межмодульных вызовов оверлейной программы имеет вид дерева. В корне дерева (нулевой уровень) находится модуль-монитор, из которого происходят обращения к модулям, расположенным на ветвях дерева. Каждый модуль первого уровня в свою очередь может быть корнем поддерева и т.д. Принцип оверлейности или перекрытия заключается в том, что ветви дерева занимают одни и те же области в виртуальном адресном пространстве программы. Поскольку модули, расположенные в разных ветвях дерева, не могут выполняться одновременно, то только монитор является резидентным в оперативной памяти все время выполнения программы, ветви же сменяют друг друга в одной и той же области памяти. На самом деле построить программу, имеющую идеальную древовидную структуру, довольно трудно, поскольку при этом обязательно догматическое соблюдение дисциплины программирования "сверху вниз". Необходимо тщательно следить, чтобы ветви дерева не пересекались: никакой модуль не имеет права передавать управление в модуль, расположенный на другой ветви, или обращаться к данным, определенным в модуле другой ветви. Реальные программы обычно нарушают эти правила, так как при их разработке используется комбинация дисциплин "сверху вниз" и "снизу вверх", за счет чего появляются низкоуровневые процедуры, обращения к которым производится из любых ветвей дерева. Выход из противоречия состоит либо в помещении этих процедур в корневой модуль, либо в создании еще одной или нескольких резидентных областей для размещения модулей, содержащих эти процедуры.
В системах, поддерживающих развитые средства создания оверлейных программ (та же OS/360), выполнение функции именования - отображения имен входных точек и общих переменных на виртуальное адресное пространство возлагается на редактор связей (link editor), который и формирует содержимое адресного пространства процесса в соответствии с оверлейной структурой, описываемой программистом с помощью специального языка. На Рисунке 3.3 представлен пример оверлейной структуры программы.
 а). межмодульные связи  a) б). распределение памяти Рис.3.3. Пример оверлейной структуры программы |
- В вычислительной системе имеются специальные регистры, в которых содержатся значения верхней и нижней границы адресов, к которым доступ разрешается. При любом обращении к памяти аппаратура сравнивает заданный адрес с этими граничными значениями и, если адрес не лежит в границах, выполняет прерывание-ловушку. При размещении процесса в памяти ОС определяет для него эти границы и записывает их значения в контекст процесса (вектор состояния процессора). При переключении контекста на данный процесс эти значения загружаются в регистры границ и, таким образом, ограничивается область памяти, к которой имеет доступ процесс. В контексте самой ОС граничные адреса, естественно, соответствуют всему имеющемуся объему памяти.
- Реальная память разбивается на "блоки защиты" одинакового размера. С каждым таким блоком связан некоторый код - ключ. При размещении процесса ОС дает ему какой-то ключ доступа, сохраняет ключ в векторе состояния и присваивает тот же ключ всем блокам памяти, выделенным этому процессу. При любом обращении к памяти аппаратура сравнивает ключ текущего процесса с ключом блока, к которому производится обращение, и выполняет прерывание-ловушку, если эти ключи не совпадают.Сама ОС, конечно же, имеет "универсальный ключ", дающий ей доступ к любому блоку.
