2. Алгоритмы выделения памяти

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

Первый и самый простой в реализации алгоритм заключается в том, что менеджер ищет в списке первый подходящий участок, то есть участок, размер которого больше чем запрашиваемый размер. В случае учета памяти с помощью списка блоков это приводит к прямому просмотру списка в поисках нужного участка. Как только подходящий участок найден, он разбивается на две части: первая отдается процессу выдавшему запрос, вторая – остается неиспользуемой (свободной). Для ситуации с рис. 1 запрос на выделение участка размером в 24 байта процессом «F» приведет к изменению списка блоков как представлено на рис. 3.

рис. 3. Изменение состояния памяти и списка блоков
при выделении 24 байт по алгоритму «первый подходящий»
(пунктиром обозначен свободный блок из которого происходило выделение участка)

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

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

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