Методы распределения памяти без использования внешней памяти
Этот простейший способ управления оперативной памятью состоит в том, что память, незанятая ядром ОС, разбивается на несколько непрерывных областей фиксированной величины, называемых разделами.
Разделы характеризуются именем, типом, границами. Такое разбиение может быть выполнено вручную оператором во время старта системы или во время ее установки. После этого границы разделов не изменяются.
В каждом разделе в каждый момент времени может располагаться по одному процессу. Очередной новый процесс, поступивший на выполнение, помещается либо в общую очередь, либо в очередь к некоторому разделу.
Схема с фиксированными разделами: (a) – с общей очередью процессов, (b) – с отдельными очередями процессов
Менеджер памяти сравнивает объем памяти, требуемый для нового процесса, с размерами свободных разделов, выбирает подходящий, также производит загрузку программы в этот раздел и настройку адресов.
Как правило, происходит условное разбиение физического адресного пространства. Связывание логических адресов процесса и физических происходит на этапе его загрузки в конкретный раздел.
На этапе трансляции разработчик программы может задать раздел, в котором ее следует выполнять. Это позволяет сразу, без использования перемещающего загрузчика, получить машинный код, настроенный на конкретную область памяти.
Распределение памяти разделами с фиксированными границами
Преимуществом данного метода является простота реализации. Недостатки:
1) уровень мультипрограммирования заранее ограничен
числом разделов, поскольку в каждом разделе может выполняться один процесс.
2) Разбиение памяти на разделы не позволяет выполнять
процессы, программы которых не помещаются ни в один из разделов, но для которых было бы достаточно памяти нескольких разделов.
3) наличие достаточно большого объема неиспользуемй памяти.
Такой способ управления памятью применялся в ранних мультипрограммных ОС ( IBM OS/360 (MFT), DEC RSX-11). Сейчас этот метод метод распределения памяти находит применение в системах реального времени. Детерминированность вычислительного процесса систем реального времени (заранее известен набор выполняемых задач, их требования к памяти, а иногда и моменты запуска) компенсирует недостаточную гибкость данного способа управления памятью.
Следовательно желательно:
- выделять раздел такого объема, который нужен текущему процессу;
- размещать процессы не в одной непрерывной области памяти, а в нескольких областях.
В этом случае память машины заранее не делится на разделы. Сначала вся память, отводимая для приложений, свободна. Каждому вновь поступающему на выполнение приложению на этапе создания процесса выделяется вся необходимая ему память, а если достаточный объем памяти отсутствует, то приложение не принимается на выполнение и процесс для него не создается. Данный способ предполагает, что программный код во время выполнения не перемещается, поэтому настройка адресов может быть проведена единовременно во время загрузки. После завершения процесса память освобождается, и на это место может быть загружен другой процесс. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных разделов произвольного размера.
t1 t2 t3 t4 t5
Динамика распределения памяти между процессами (серым цветом показана неиспользуемая память)
В какой раздел помещать процесс, если их несколько? Для этого используются стратегии размещения. Они позволяют определить, в какое местоосновной памяти следует помещать поступающие программы и данные. Их три:
1) Стратегия первого подходящего (First fit). Задание помещается в первый подходящий по размеру раздел.
Cписок свободных областей упорядочивается по адресам. Диспетчер памяти просматривает этот список и выделяет программе раздел в той области, которая первой подойдет по объему. В этом случае, если такой фрагмент имеется, то в среднем необходимо просмотреть половину списка. При освобождении раздела также необходимо просмотреть половину списка. Правило «первый подходящий» приводит к тому, что память для небольших задач преимущественно будет выделяться в области младших адресов и, следовательно, это будет увеличивать вероятность того, что в области старших будут образовываться фрагменты достаточно большого объема.
2)Стратегия самого подходящего (Best fit). Процесс помещается в тот раздел, где после его загрузки остется меньше всего свободного места.
Список свободных областей упорядочен по возрастанию объема этих фрагментов. При просмотре списка для нового раздела будет использован фрагмент свободной памяти, объем которой наиболее точно соответствует требуемому. Требуемый раздел будет определяться по-прежнему в результате просмотра в среднем половины списка. Однако оставшийся фрагмент оказывается настолько малым, что в нем уже вряд ли удастся поместить какой-либо еще раздел и при этом фрагмент попадет в начало списка.
3) Стратегия наименее подходящего (самого неподходящего) (Worst fit). При помещении в самый большой раздел в нем остается достаточно места для возможного размещения еще одного процесса.
Список свободных областей упорядочивается по убыванию объема свободного фрагмента. Очевидно, что если есть фрагмент памяти требуемого объема, то он сразу же и будет найден. Т.к. этот фрагмент является самым большим, то, скорее всего, после выделения из него раздела памяти для задачи оставшаяся область памяти еще сможет быть использована в дальнейшем.
Моделирование показало, что доля полезно используемой памяти в первых двух случаях больше, при этом первый способ несколько быстрее.
Выбор стратегии размещения процесса между первым подходящим и наиболее подходящим слабо влияет на величину фрагментации. Любопытно, что метод наиболее подходящего может оказаться наихудшим, так как он оставляет множество мелких незанятых блоков.
Попутно заметим, что перечисленные стратегии широко применяются и другими компонентами ОС, например, для размещения файлов на диске.
Функциями менеджера памяти ОС при данном методе распределения памяти являются:
1) ведение таблиц свободных и занятых областей, в которых указываются начальные адреса и размеры участков памяти;
2) анализ требований к памяти при создании нового процесса; просмотр таблицы свободных областей и выбор среди имеющихся раздела, размер которого достаточен для размещения кодов и данных нового процесса (в соответствие с одной из стратегий размещения)
3) загрузка программы в выделенный ей раздел и корректировка таблиц свободных и занятых областей;
4) корректировка таблиц свободных и занятых областей после завершения процесса.
Связывание адресов может осуществляться на этапах загрузки и выполнения.
Преимущество - более высокая гибкость.
Недостаток – фрагментация памяти. Фрагментация – это наличие большого числа несмежных участков свободной памяти очень маленького размера (фрагментов). Настолько маленького, что ни одна из вновь поступающих программ не может поместиться ни в одном из участков, хотя суммарный объем фрагментов может составить значительную величину, намного превышающую требуемый объем памяти.
Одним из методов борьбы с фрагментацией является перемещение всех занятых участков в сторону старших или младших адресов, так, чтобы вся свободная память образовывала единую свободную область.
Распределение памяти перемещаемыми разделами
В дополнение к функциям ОС при распределении памяти динамическими разделами, в данном случае она должна еще время от времени копировать содержимое разделов из одного места памяти в другое, корректируя таблицы свободных и занятых областей. Эта процедура называется сжатием. Сжатие может выполняться либо при каждом завершении процесса, либо только тогда, когда для вновь создаваемого процесса нет свободного раздела достаточного размера. В первом случае требуется меньше вычислительной работы при корректировке таблиц свободных и занятых областей, а во втором – процедура сжатия выполняется реже.
Так как программы перемещаются по оперативной памяти в ходе своего выполнения, то в данном случае невозможно выполнить настройку адресов с помощью перемещающего загрузчика и более подходящим является динамическое преобразование адресов.
Недостатки.
Хотя процедура сжатия и приводит к более эффективному использованию памяти, она может потребовать значительного времени, что часто перевешивает преимущества данного метода.
Концепция сжатия применяется и при использовании других методов распределения памяти, когда отдельному процессу выделяется не одна сплошная область памяти, а несколько несмежных участков памяти произвольного размера (сегментов). Такой подход был использован в ранних версиях OS/2, в которых память распределялась сегментами, а возникавшая при этом фрагментация устранялась путем периодического перемешивания сегментов.
Описанные выше схемы недостаточно эффективно используют память, поэтому в современных схемах управления памятью не принято размещать процесс в оперативной памяти одним непрерывным блоком.
Логическое адресное пространство каждого процесса делится на части одинакового, фиксированного для данной системы размера, называемые виртуальными страницами.
Вся оперативная память также делится на части такого же размера, называемые физическими страницами (или блоками).
Для упрощения механизма преобразования адресов размер страницы обычно выбирается, равным степени двойки 2: 512, 1024 и т.д. Типичный размер страницы составляет несколько килобайт, например 4096 байт (4 Кбайт). Страницы не перекрываются.
Говорят, что оперативная память разбивается на физические страницы, а программа – на виртуальные.
В общем случае размер логического адресного пространства не является кратным размеру страницы, поэтому последняя страница каждого процесса дополняется фиктивной областью.
Передача информации между памятью и диском всегда осуществляется целыми страницами.
Логический адрес в страничной системе это упорядоченная пара (Nвс, Oвс), где Nвс – порядковый номер страницы процесса в ЛАП, Oвс - смещение в пределах страницы Nвс, на которой размещается адресуемый элемент.
Физический адрес - упорядоченная пара (Nфс, Oфс), где Nфс – порядковый номер страницы процесса в ФАП, Oфс - смещение в пределах страницы Nфс.
Из этого следует, что смещение Oфс может быть получено простым отделением кмладших разрядов в двоичной записи адреса, а оставшиеся старшие разряды адреса представляют собой двоичную запись номера страницы.
Пусть размер страницы равен 1 Кбайт (). Тогда из двоичной записи адреса 101 000 111 001 можно определить Nфс = 10, Oфс = 1 000 111 001 (байт).
Двоичное представление адресов
Из рисунка видно, что номер страницы и ее начальный адрес легко могут быть получены один из другого дополнением или отбрасыванием к нулей, соответствующих смещению.
В пределах страницы непрерывная последовательность
логических адресов однозначно отображается в непрерывную последовательность физических адресов, что на практике означает равенство смещений в логическом и физическом адресах, т.е. Oвс= Oфс.
Разбиение адресного пространства на страницы осуществляется ОС незаметно для пользователя. Поэтому адрес является двумерным лишь с точки зрения операционной системы, а с точки зрения пользователя адресное пространство процесса остается линейным.
При создании процесса ОС загружает в оперативную память несколько его виртуальных страниц, необходимых для старта процесса. Копия всего логического адресного пространства процесса находится на диске. Смежные виртуальные страницы не обязательно располагаются в смежных физических страницах.
Если текущей страницы в главной памяти нет, она должна быть переписана (подкачана) из внешней памяти.
Схема страничного распределения памяти
Система отображения виртуальных адресов процессов в физические сводится к отображению виртуальных страниц в физические и представляет собой таблицу страниц. Для каждого процесса ОС создает информационную структуру - таблицу страниц. Каждая запись этой таблицы кроме служебной (управляющей) информации содержит номер физической страницы, в которую загружена соответствующая виртуальная страница. Управляющая информация содержит:
- признак присутствия, установленный в 1, если виртуальная страница находится в ОП;
- признак модификации, который устанавливается в 1 всякий раз, когда производится запись по адресу, относящемуся к данной странице;
- признак обращения к странице (бит доступа, который устанавливается в 1 при каждом обращении по адресу, относящемуся к данной странице.
Информация из таблицы страниц используется для решения вопроса о необходимости перемещения той или иной страницы между памятью и диском, а также для преобразования логического(виртуального) адреса в физический. Сами таблицы страниц, так же как и описываемые ими страницы, размещаются в оперативной памяти. Адрес таблицы страниц включается в контекст соответствующего процесса.
При активизации очередного процесса ОС в специальный регистр процессора загружает начальный адрес его таблицы страниц. При каждом обращении к памяти происходит поиск номера виртуальной страницы, содержащей требуемый адрес. Затем по этому номеру определяется нужный элемент таблицы страниц и из него извлекается описывающая страницу информация. Далее анализируется признак присутствия. Если данная виртуальная страница находится в оперативной памяти, то выполняется преобразование виртуального адреса в физический, т.е. логический адрес заменяется физическим адресом, указанным в записи таблицы страниц. Если же нужная виртуальная страница в данный момент выгружена на диск, то происходит так называемое страничное прерывание. Выполняющийся процесс переводится в состояние ожидания, и активизируется другой процесс из очереди готовых.
Обработка страничного прерывания приводит к тому, что затребованная страница подкачивается из конкретного места внещней памяти в свободный страничный кадр физической памяти и продолжается прерванный код. При отсутствии свободных страниц на диск выгружается страница в соответсвии с принятой в данной ОС стратегии замещения.
Пусть произошло обращение к памяти по некоторому логическому адресу.
Схема преобразования логического адреса в физический при страничной организации памяти
Аппаратными схемами процессора выполняются следующие действия по преобразованию логического адреса в физический:
1) из специального регистра процессора (регистр таблицы страниц) извлекается начальный адрес таблицы страниц активного процесса (Aнтс).
2) по этому адресу, по номеру виртуальной страницы Nвс (старшие разряды виртуального адреса) и длине записи в таблице страниц (системная константа Sстр) определяется адрес нужной записи Aтс в таблице страниц , Aтс = Aнтс + (Nвс * Sстр)
3) из этой записи извлекается номер соответствующей физической
страницы Nфс;
4) линейный физический адрес Aлф находится присоединением смещения Oвс к номеру физической страницы Aлф = Nфс || Oвс.
На производительность системы со страничной организацией памяти влияют временные затраты, связанные с обработкой страничных прерываний и преобразованием виртуального адреса в физический. При часто возникающих страничных прерываниях система может тратить большую часть времени на перекачку страниц.
Время преобразования логического адреса в физический в значительной степени определяется временем доступа к таблице страниц. Для уменьшения времени преобразования адресов во всех процессорах предусмотрен аппаратный механизм получения физического адреса по виртуальному. С этой же целью таблицу страниц стремятся размещать в "быстрых" запоминающих устройствах. Это может быть, например, набор специальных регистров или память, использующая для уменьшения времени доступа, ассоциативный поиск и кэширование данных.
Важным параметром, влияющим на произвоительность, является размер страницы. Он должен быть достаточно большим, чтобы уменьшить размер таблицы страниц и уменьшить частоту страничных прерываний и достаточно малым, чтобы уменьшить фиктивную область в последней странице каждого процесса. В среднем на каждой программе теряется половина объема страниц, что в сумме при большом размере страницы может составить сущесивенную величину.
Применяется в поздних OS/2, а также в Windows NT, 2000, XP.
Страничное распределение памяти может быть реализовано в упрощенном варианте, без выгрузки страниц на диск. В этом случае все виртуальные страницы всех процессов постоянно находятся в оперативной памяти. Такой вариант страничной организации хотя и не предоставляет пользователю виртуальной памяти, но почти исключает фрагментацию. Это происходит потому, что программа может загружаться в несмежные области, а также из-за того, что при загрузке виртуальных страниц никогда не образуется остатков (Novell Netware 3.x, 4.x.) .
: 512, 1024 и т.д. Типичный размер страницы составляет несколько килобайт, например 4096 байт (4 Кбайт). Страницы не перекрываются.
). Тогда из двоичной записи адреса 101 000 111 001 можно определить Nфс = 10, Oфс = 1 000 111 001 (байт).
линейный физический адрес Aлф находится присоединением смещения Oвс к номеру физической страницы Aлф = Nфс || Oвс.