Алгоритмы динамического управления памятью
Возможны ситуации, когда блоки освобождаются в порядке, обратном тому, в котором они выделялись. Это позволяет свести выделение памяти к стековой структуре, т. е. фактически, вернуться к простому запоминанию границы между занятой и свободной памятью.
Возможны также ситуации, когда некоторые из занятых блоков можно переместить по памяти – тогда есть возможность проводить дефрагментацию памяти, перемещение занятых блоков памяти с целью объединить свободные участки. Например, функцию realloc() в ранних реализациях системы UNIX можно было использовать именно для этой цели.
В стандартных библиотечных функциях языков высокого уровня, таких как malloc/free/realloc в С, new/dispose в Pascal и т. д., как правило, используются алгоритмы, рассчитанные на наиболее общий случай: программа запрашивает блоки случайного размера в случайном порядке и освобождает их также случайным образом.
Впрочем, случайные запросы – далеко не худший вариант. Даже не зная деталей стратегии управления кучей, довольно легко построить программу, которая "испортит жизнь" многим распространенным алгоритмам (пример 4.2).
Пример 4.2. Пример последовательности запросов памяти:
while(TRUE) {
void * bl = malloc(random (10));
/* Случайный размер от 0 до 10 байт */ void * b2 = malloc(random(10)+10);
Л…….. от 10 до 20 байт */
if(b1 == NULL && b2 == NULL) /* Если памяти нет */
break; /* выйти из цикла */
free(b1);
void * bЗ = malloc(150);
/* Скорее всего, память не будет выделена */
В результате исполнения такой программы вся доступная память будет "порезана на лапшу": между любыми двумя свободными блоками будет размещен занятый блок меньшего размера (рис. 4.4)
Рис. 4.4. Результат работы программы примера 4.2
К счастью, пример 4.2 имеет искусственный характер. В реальных программах такая ситуация встречается редко, и часто оказывается проше исправить программу, чем вносить изменения в универсальный алгоритм управления кучей.
Приведенный пример построен на том предположении, что система выделяет нам блоки памяти, размер которых соответствует запрошенному с точностью до байта. Если же минимальная единица выделения равна 32 байтам, никакой внешней фрагментации наш пример не вызовет: на каждый запрос будет выделяться один блок. Но при этом мы столкнемся с обратной проблемой, которая называется внутренней фрагментацией: если система умеет выделять только блоки, кратные 32 байтам, а нам реально нужно 15 или 47 байт, то 17 байт на блок окажутся потеряны (рис. 4.5).
Рис. 4.5. Внутренняя фрагментация