Алгоритмы выделения участков памяти по запросу

Рис. 47. Слияние свободных блоков в результате освобождения памяти

Рис. 45. Список свободных блоков после выполнения запроса на освобождение памяти

Freemem (p1, 100) Getmem (p5, 50)

 

Рис. 46. Распределение области памяти кучи после выполнения запросов на освобождение / выделение памяти

 

Если освобождаемый участок памяти вплотнуюприлегает с одной или двух сторон к свободным участкам, происходит слияние и образуется более крупный свободный блок (рис.47).

Freemem (p2, 200)

 

 

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

 

Алгоритм “первого подходящего”. При очередном запросе на выделение памяти администратор кучи подбирает в списке свободных блоков первый встретившийся блок, размер которого не меньше требуемого. В среднем необходим просмотр половины всего списка свободных блоков. Недостаток этого алгоритма заключается в том, что он не сохраняет крупные свободные блоки.

Алгоритм “наиболее подходящего”. При очередном запросе на выделение памяти администратор кучи подбирает в списке свободных блоков наименьший блок, размер которого больше или равен запросу. Алгоритм “наиболее подходящего” обеспечивает сохранение более крупных свободных блоков, но может потребовать просмотра всего списка свободных блоков. Кроме того, со временем этот алгоритм имеет тенденцию к созданию большого количества свободных блоков малого размера, которые не смогут удовлетворить ни один запрос на выделение памяти. Администратор кучи Turbo Pascal реализует алгоритм “наиболее подходящего”.

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

Алгоритм “близнецов”. Идея этого алгоритма состоит в том, что организуются списки свободных блоков отдельно для каждого размера 2^k, 0 <= k <= m. Вся область памяти кучи состоит из 2^m слов, которые, можно считать, имеют адреса с 0 по 2^m – 1. Первоначально свободным является весь блок из 2^m слов. Далее, когда требуется блок из 2^k слов, а свободных блоков такого размера нет, расщепляется на две равные части блок большего размера; в результате появится блок размера 2^k (т.е. все блоки имеют длину, кратную 2). Когда один блок расщепляется на два (каждый из которых равен половине первоначального), эти два блока называются близнецами. Позднее, когда оба близнеца освобождаются, они опять объединяются в один блок. Преимуществом этого алгоритма является скорость, но его реализация усложняется за счет необходимости вести систему списков свободных блоков.