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

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

На рис. 5. 2 представлена схема алгоритмов распределения памяти.

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

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

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

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

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

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

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

Корректировка таблиц свободных и занятых областей. Эта операция проводится после завершения процесса.

Однако этому методу распределения присущ серьезный недостаток, связанный с фрагментацией памяти. Фрагментация - это наличие большого числа несмежных участков свободной памяти малого размера (фрагментов), настолько малого, что ни одна из вновь поступающих программ не может уместиться ни в одном из участков, хотя суммарный объем фрагментов может составить значительную величину, намного превышающую требуемый объем памяти. Этот метод управления памятью лежит в основе подсистем управления памятью первых ОС 60–70-х годов.

Перемещаемые разделы

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

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

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

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