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

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

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

Q первый подходящий участок; Q самый подходящий участок; Q самый неподходящий участок.

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

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

¹ MVT (multiprogramming with a nariable number of tasks) — мультипрограммирование с пе­ременным числом задач. Эта ОС была одной из самых распространенных при эксплуати­ровании больших ЭВМ класса IBM 360 (370).

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

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

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

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