Разделы с подвижными границами

Чтобы избавиться от фрагментации, можно попробовать размещать в оператив­ной памяти задачи плотно, одну за другой, выделяя ровно столько памяти, сколь­ко задача требует. Одной из первых операционных систем, в которой был реализо­ван такой способ распределения памяти, была OS MVT¹ (Multiprogramming with a Variable number of Tasks — мультипрограммирование с переменным числом за­дач). В этой операционной системе специальный планировщик (диспетчер памя­ти) ведет список адресов свободной оперативной памяти. При появлении новой задачи диспетчер памяти просматривает этот список и выделяет для задачи раз­дел, объем которой либо равен необходимому, либо чуть больше, если память вы­деляется не ячейками, а некими дискретными единицами. При этом модифициру­ется список свободных областей памяти. При освобождении раздела диспетчер памяти пытается объединить освобождающийся раздел с одним из свободных уча­стков, если таковой является смежным.

При этом список свободных участков памяти может быть упорядочен либо по ад­ресам, либо по объему. Выделение памяти под новый раздел может осуществлять­ся одним из трех основных способов:

- первый подходящий участок;

- самый подходящий участок;

- самый неподходящий участок.

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

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

Как ни странно, самым эффективным способом, как правило, является последний, по которому для нового раздела выделяется «самый неподходящий» фрагмент сво-

' Эта операционная система была одной из самых распространенных в больших ЭВМ класса IBM 360 (370).

86_____________________ Глава 3. Управление памятью в операционных системах

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

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

Данный способ распределения памяти, тем не менее, применялся достаточно дли­тельное время в нескольких операционных системах, поскольку в нем для задач выделяется непрерывное адресное пространство, а это упрощает создание систем программирования и их работу. Применяется этот способ и ныне при создании систем на базе контроллеров с упрощенной (по отношению к мощным современ­ным процессорам) архитектурой. Например, при разработке операционной систе­мы для современных цифровых АТС, которая использует 16-разрядные микро­процессоры Intel.