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

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

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

Рассмотрим процесс распределения памяти, показанный на рис.3.6. Для каждого загружаемого процесса создается новый раздел с размерами, соответствующими размеру процесса. На рис.3.6,а система последовательно выделила память пяти процессам, и 1 000 байт памяти остались свободными, что недостаточно для загрузки очередного процесса. Когда завершается процесс 2, его раздел освобождается, и новый раздел отводится процессу 6. Как показано на рис.3.6,б, этот новый раздел занимает часть памяти, которая отводилась процессу 2. Остаток от прежнего раздела процесса 2 остается свободным.

Рис. 3.6. Распределение памяти с использование разделов

с подвижными границами

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

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

Эта проблема решается при помощи метода, называемого уплотнением памяти (рис.3.7) и состоящего в перемещении всех занятых разделов к одному или другому краю основной памяти. Благодаря этому вместо многочисленных небольших «дыр», обычных для мультипрограммирования с переменными разделами, мы получаем е­диный большой свободный участок памяти. А уж если вся свободная память представлена одним участком, то ожидающее задание может выполняться, если ему требуется память, не превышающая размера этого единого полученного в результате уплотнения участка. Уплотнение памяти называют дефрагментацией памяти, а среди программистов бытует термин «сбор мусора».

Рис. 3.7. Уплотнение памяти

Уплотнение памяти имеет свои недостатки:

- оно отнимает ресурсы системы, которые можно было бы испо­льзовать продуктивно;

- во время уплотнения памяти система должна прекращать любые другие работы. Результатом этого могут стать непрогнозируемые времена ответа для пользователей диалогового режима и это может оказаться неприемлемым для систем реального времени;

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

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

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

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

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

Наименее подходящее размещение на первый взгляд кажется весьма странным. Однако более тщательное рассмотрение показывает, что выбор наименее подходящего по размеру также имеет сильные интуитивные аргументы в свою пользу. Этот принцип говорит о том, что при помещении программы в основную память нужно занимать свободный участок, имеющий наиболее далекий размер, т. е. максимальный воз­можный свободный участок. Интуитивный аргумент в пользу такого подхода достаточно прост: после помещения программы в большой свободный участок остающийся свободный участок зачастую также оказывается большим и, таким образом, в нем можно разместить относительно большую новую программу.

Рис. 3.8. Размещение процесса D длиной 6000 байт в памяти

по принципу занятия

а) первого подходящего по размеру участка

б) наиболее подходящего по размеру участка

в) наименее подходящего по размеру участка