Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем

Подождите немного. Документ загружается.

положение в памяти не было фиксированным. Раздел создавался в

свободном участке памяти перед началом выполнения задачи и имел

размер, равный объему памяти, заказанному задачей. Созданный раздел

фиксировался в памяти на время выполнения задачи, но уничтожался при

окончании ее выполнения.

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

разделов памяти, причем их выделение/освобождение может выполняться

динамически (пример – MS DOS). Однако общими всегда являются

следующие правила:

• раздел занимает непрерывную область реальной памяти;

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

• после выделения раздела процесс работает с реальными адресами

в разделе.

Задача эффективного распределения памяти (в любой ее модели)

сводится, прежде всего, к минимизации суммарного объема дыр. Ниже мы

даем определения дыр, общие для всех моделей памяти.

Дырой называется область реальной памяти, которая не может быть

использована. Различают дыры внешние и внутренние. Рисунок 3.2

иллюстрирует внешние и внутренние дыры в системе OS/360.

Рисунок 3.2 Разделы в реальной памяти OS/360

Внешней дырой называется область реальной памяти, которая не

выделена никакому процессу, но слишком мала, чтобы удовлетворить

запрос на память. На рисунке 3.2.а суммарный размер свободных областей

превышает запрос, но каждая из этих областей в отдельности меньше

запроса, поэтому все эти свободные области являются внешними дырами.

Внутренней дырой называется память, которая выделена процессу,

но им не используется. Так, на рисунке 3.2.б процессу 1 выделен раздел P1,

но виртуальное адресное пространство процесса меньше размера раздела,

оставшееся пространство раздела составляет внутреннюю дыру.

Для управления памятью формируются те или иные управляющие

структуры (заголовки), которые также занимают память. В некоторых

системах общий объем заголовочной памяти может быть очень большим, и

в таких случаях следует учитывать также и заголовочные дыры – области

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

управляющую информацию. В системах с реальной памятью заголовочные

дыры практически отсутствуют.

Хотя в любом случае невозможность использовать память является

потерей ресурса, внешние дыры, являются "меньшим злом", так как, во-

первых, блок свободной памяти становится дырой из-за малого своего

размера, а "малый" – понятие относительное, во-вторых, в моделях памяти

с динамической трансляцией адресов существуют методы борьбы с

внешними дырами.

Модель с фиксированными разделами представляет весьма

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

реализуется, процесс, которому недостает памяти, просто блокируется до

освобождения требуемого ресурса (в 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 Пример оверлейной структуры программы

В модели с фиксированными разделами после загрузки процесса все

обращения к памяти в нем производятся по реальным адресам.

Следовательно, ничто не может помешать процессу обратиться к памяти,

принадлежащей другому процессу или даже самой ОС, и последствия

такого обращения могут быть фатальными. Защита от такого доступа

должна поддерживаться аппаратно. Приведем два примера такой защиты.

1) В вычислительной системе имеются специальные регистры, в

которых содержатся значения верхней и нижней границ адресов, к

которым доступ разрешается. При любом обращении к памяти аппаратура

сравнивает заданный адрес с этими граничными значениями и, если адрес

не лежит в границах, выполняет прерывание-ловушку. При размещении

процесса в памяти ОС определяет для него эти границы и записывает их

значения в контекст процесса (вектор состояния процессора). При

переключении контекста на данный процесс эти значения загружаются в

регистры границ и таким образом ограничивается область памяти, к

которой имеет доступ процесс. В контексте самой ОС граничные адреса,

естественно, соответствуют всему имеющемуся объему памяти.

2) Реальная память разбивается на "блоки защиты" одинакового

размера. С каждым таким блоком связан некоторый код – ключ. При

размещении процесса ОС дает ему какой-то ключ доступа, сохраняет ключ

в векторе состояния и присваивает тот же ключ всем блокам памяти,

выделенным этому процессу. При любом обращении к памяти аппаратура

сравнивает ключ текущего процесса с ключом блока, к которому

производится обращение и выполняет прерывание-ловушку, если эти

ключи не совпадают. Сама ОС, конечно же, имеет "универсальный ключ"

дающий ей доступ к любому блоку.

3.3. Односегментная модель

Нам неизвестны ОС, поддерживающие односегментную модель "в

чистом виде", но ее рассмотрение облегчит понимание более сложных

моделей.

Внешне (с точки зрения программиста) эта модель очень похожа на

модель с фиксированными разделами: программа-процесс готовится в

плоском виртуальном адресном пространстве. Процесс занимает

непрерывное пространство виртуальной памяти, и в реальную память он

также загружается в один непрерывный раздел (сегмент). Сегмент может

начинаться с любого адреса реальной памяти и иметь любой раздел, не

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

сегментной модели состоит в том, что она использует аппаратную

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

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

виртуальные адреса, и лишь при каждом конкретном обращении

виртуальный адрес аппаратно переводится в реальный. В вычислительной

системе, поддерживающей односегментную модель, должен существовать

регистр дескриптора сегмента, содержимое которого состоит из двух

полей: начального (базового) адреса сегмента в реальной памяти и длины

сегмента. Когда процесс размещается в памяти, для выделенного ему

сегмента формируется дескриптор, который записывается в вектор

состояния в контексте процесса. При переключении контекста дескриптор

сегмента загружается в аппаратный регистр дескриптора сегмента и

служит той "таблицей трансляции", по которой аппаратура переводит

виртуальные адреса в реальные. Сама трансляция адресов происходит по

простейшему алгоритму. Поскольку виртуальное адресное пространство

процесса представляет собой линейную последовательность адресов,

начинающуюся с 0, виртуальный адрес является простым смещением

относительно начала сегмента. Реальный адрес получается сложением

виртуального адреса с базовым адресом, выбранным из дескриптора

сегмента, как показано на рисунке 3.4. Единственный путь для выхода

процесса за пределы своего виртуального адресного пространства –

задание виртуального адреса, большего, чем размер сегмента. Этот путь

легко может быть перекрыт, если аппаратура при трансляции адресов

будет сравнивать виртуальный адрес с длиной сегмента и выполнять

прерывание-ловушку, если виртуальный адрес больше.

Рисунок 3.4 Односегментная модель

То обстоятельство, что процесс работает в виртуальных адресах,

делает возможным перемещение сегментов в реальной памяти. Переместив

процесс в другую область реальной памяти, ОС просто изменяет поле

базового адреса в дескрипторе его сегмента. Поскольку, как и в модели с

фиксированными разделами, реальная память распределяется

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

стратегии размещения. Но возможное здесь перемещение сегментов

является эффективным способом борьбы с внешними дырами. Сегменты

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

между ними не оставалось, все свободное пространство сливается в один

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

последующего распределения.

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

адресов, является вытеснение сегментов. Если даже после перемещения

сегментов запрос на память не может быть удовлетворен, то ОС может

переписать какой-либо сегмент на внешнюю память и освободить

занимаемую им реальную память. Поскольку контекст процесса, который

содержится в вытесненном сегменте, сохраняется, то впоследствии ОС

может вновь загрузить этот сегмент в реальную память, откорректировать

базовый адрес в его дескрипторе и возобновить выполнение процесса.

Перемещение сегментов и (см. ниже) страниц между оперативной и

внешней памятью и наоборот – называется свопингом (swapping), а

составные его части – вытеснением (swap out) и подкачкой (swap in).

Поскольку в модели происходит вытеснение сегментов, должна быть

реализована какая-то его стратегия. Естественно, что наилучшим

кандидатом на вытеснение должен быть сегмент процесса, находящегося в

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

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

операции ввода-вывода. При вводе-выводе, использующем канал или