Распределение с несколькими непрерывными разделами

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

Простейшее решение – разделить доступную оперативную память на несколько разделов фиксированного размера (Multiprogramming with Fixed number of Tasks – MFT). Каждый раздел содержит один процесс, то есть степень мультизадачности системы будет равна числу разделов. Такой подход использовался в OS/360 IBM, но недолго. Метод распределения памяти с фиксированными границами разделов нелегко приспособить к меняющемуся числу задач. Кроме того возможна недопустимая фрагментация.

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

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

Рисунок 11.5 – Действия планировщика при размещении процессов в памяти

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

Существует несколько стратегий выбора свободной области:

­ Стратегия наиболее подходящего (Best-fit Strategy). Выбирается программа, которой в свободном разделе наиболее «тесно».

­ Стратегия первого подходящего (First-fit Strategy). Выбирается программа, которая помещается в свободный раздел.

­ Стратегия наименее подходящего (Last-fit Strategy). Выбирается программа, которой в свободном разделе наиболее «свободно». В этом случае остающийся фрагмент часто достаточен для размещения еще одной программы

Фрагментация

Алгоритмы, описанные нами, приводят к так называемой внешней фрагментации. Загрузка и удаление процессов из памяти, приводит к дроблению свободной памяти на небольшие участки. Внешняя фрагментация присутствует, если свободного адресного пространства достаточно для выполнения запроса, но оно не является непрерывным.

Фрагментация вызывает различные проблемы. В самом плохом случае, свободные блоки располагаются между каждыми двумя процессами. Если бы вся эта память была объединена в единый большой блок, то можно было бы запустить большее количество процессов. Выбор стратегии распределения памяти может повлиять на фрагментацию. Внешняя фрагментация также зависит от общего объема оперативной памяти и среднего размера процесса. Статистика показывает, что даже с некоторой оптимизацией, если выделено N блоков, то 0.5 N блоков теряются из-за фрагментации, то есть 1/3 памяти недоступна (правило 50%).

Другая проблема, связанная с распределением памяти с несколькими разделами, состоит в следующем. Рассмотрим блок размером 18464 байта. Предположим, что следующему процессу требуется 1862 байта. Если мы выделим запрашиваемый блок, то свободно останется 2 байта. Накладные расходы на хранение такого блока себя не оправдывают. Общий подход – распределение слишком маленьких блоков как части запрошенных. То есть выделенный участок может быть немного больше запрошенного. Эта разница составляет внутренн юю фрагментацию (память выделена, но не используется).

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

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

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

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

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

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

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