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

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

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

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

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