Реализация модели распределения памяти перемещаемыми разделами с перемещением в сторону старших адресов со сжатием при каждом

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

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

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

   Рис. 5 Соотношение объемов виртуального адресного пространства и физической памяти: виртуальное адресное пространство превосходит объем физической памяти (а), виртуальное адресное пространство меньше объема физической памяти (б)

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

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

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

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

     Обычно виртуальное адресное пространство процесса делится на две непрерывные части: системную и пользовательскую. В некоторых ОС (например, Windows NT, OS/2) эти части имеют одинаковый размер — по 2 Гбайт, хотя в принципе деление может быть и другим, например 1 Гбайт — для ОС, и 2 Гбайт — для прикладных программ. Часть виртуального адресного пространства каждого процесса, отводимая под сегменты ОС, является идентичной для всех процессов. Поэтому при смене активного процесса заменяется только вторая часть виртуального адресного пространства, содержащая его индивидуальные сегменты, как правило, — коды и данные прикладной программы (рис. 6). Архитектура современных процессоров отражает эту особенность структуры виртуального адресного пространства, например, в процессорах Intel Pentium существует два типа системных таблиц: одна — для описания сегментов, общих для всех процессов, а другая — для описания индивидуальных сегментов данного процесса. 

     При смене процесса первая таблица остается неизменной, а вторая заменяется новой.

   Рис. 6 Общая и индивидуальные части виртуальных адресных пространств

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

   1.2 Алгоритмы распределения памяти

      Следует ли назначать каждому процессу одну непрерывную область физической памяти или можно выделять память «кусками»? Должны ли сегменты программы, загруженные в память, находиться на одном месте в течение всего периода выполнения процесса или можно ее время от времени сдвигать? Что делать, если сегменты программы не помещаются в имеющуюся память? Разные ОС по-разному отвечают на эти и другие базовые вопросы управления памятью. Обозначим наиболее общие подходы к распределению памяти, которые были характерны для разных периодов развития операционных систем. Некоторые из них сохранили актуальность и широко используются в современных ОС, другие же представляют в основном только познавательный интерес, хотя их и сегодня можно встретить в специализированных системах. На рис.7 все алгоритмы распределения памяти разделены на два класса: алгоритмы, в которых используется перемещение сегментов процессов между оперативной памятью и диском, и алгоритмы, в которых внешняя память не привлекается.

   Рис. 7 Классификация методов распределения памяти

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

      В этом случае память машины не делится заранее на разделы. Сначала вся память, отводимая для приложений, свободна. Каждому вновь поступающему на выполнение приложению на этапе создания процесса выделяется вся необходимая ему память (если достаточный объем памяти отсутствует, то приложение не принимается на выполнение и процесс для него не создается). После завершения процесса память освобождается, и на это место может быть загружен другой процесс. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных участков (разделов) произвольного размера. На рис.8 показано состояние памяти в различные моменты времени при использовании динамического распределения. Так, в момент t₀ в памяти находится только ОС, а к моменту t₁ память разделена между 5 процессами, причем процесс П4, завершаясь, покидает память. На освободившееся от процесса П4 место загружается процесс П6, поступивший в момент t₃.

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

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

   Распределение памяти динамическими разделами  лежит в основе подсистем управления памятью многих мультипрограммных  операционных системах 60-70-х годов, в частности такой популярной операционной системы, как OS/360.

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

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

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

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

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

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

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

2.1 Алгоритм реализации модели распределения памяти перемещаемыми разделами

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

    Пусть массив А, состоящий из десяти ячеек – вся свободная память операционной системы, тогда пусть каждая ячейка массива имеет 256 Мб свободной памяти (таким образом вся память составляет 2560 Мб).

    Перед началом непосредственной загрузки процессов выведем на экран сообщение  'pameat polnosteu svobodna' и массив, представляющий свободную память ( A[i] ).

    Затем при помощи команды языка паскаль случайным образом будем загружать процессы , размером от 0 Mб до 512 Mб в  любые свободные ячейки массива. Запись будем производиться таким образом, что если для загрузки приходит процесс,  больший чем максимальный размер ячейки(256), то ячейка куда он пришёл обнуляется , а из соседней с ней ячейки массива вычитается недостающая память( то есть, если  например во вторую ячейку приходит процесс 260Мб, то эта ячейка обнуляет значение свободной памяти, а  в соседнюю с ней ячейку записывается новое значение свободной памяти 252Мб).А если для загрузки приходит процесс, меньший чем максимальный размер ячейки(256), то из ячейки ,куда он пришёл вычитается размер данного процесса. Каждая загрузка сопровождается соответствующим сообщением, содержащим размер занимаемой памяти процесса, и выводом массива А[i] с загруженным процессом.

    После каждой загрузки процесса производится процедура сдвига и сжатия.

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

    Массив, преобразованный в ходе сдвига и сжатия, на экран выводится после сообщения 'posle sdviga i sgatiea'. После этого на экране появляется сообщение 'zagruzit eshe proces y/n', которое подразумевает нажатие двух символов: либо «y», что означает загрузку нового процесса и соответствующую процедуру сдвига и сжатия, либо «n», после чего происходит автоматический выход из программы.