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

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

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

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

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

4.9.3. Фрагментация

Если блоки переменной длины выделяются или освобождаются в произвольном порядке, то список свободных блоков может стать очень длинным, особенно если блоки при освобождении не укрупняются. Это приводит к ситуации, когда в ответ на очередной запрос о выделении памяти размера sizeбайт в куче не окажется непрерывного свободного участка требуемого размера, т.е.MaxAvail < size, в то время как суммарный объем свободной памяти достаточен для выполнения запроса, т.е.MemAvail >= size. Разбиение всей доступной памяти области кучи на большое количество блоков относительно малого размера называетсявнешней фрагментацией.

Внутренняя фрагментациясвязана с появлением неиспользуемых, но и недоступных участков памяти. Внутренняя фрагментация порождается, в частности, механизмом формирования списка свободных блоков. Так, если запрашиваемый размер памяти не кратен восьми байтам, в куче образуется “дырка” размером 1-7 байт, причем этот участок не может использоваться ни при каком другом запросе динамической памяти до того момента, когда связанный с ним объект не будет удален из кучи. Внутренняя фрагментация может возникнуть также вследствие реализации алгоритма резервирования блоков, имеющих размер, больший запрошенного (т.е. за счет отказа от деления блока на части, одна из которых может оказаться совсем маленькой). Внутреннюю фрагментацию могут вызвать сами пользователи, резервируя память“про запас”, заведомо большего размера, чем может понадобиться в текущий момент выполнения программы. Внутренняя фрагментация приводит к ситуации, когда на некоторый запрос будет получен отказ из-за отсутствия блоков требуемого размера, хотя зарезервированной, но не используемой памяти более чем достаточно для удовлетворения запроса, т.е.MaxAvail < size, MemAvail < size, гдеsize – размер запроса.