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

При динамическом выделении памяти запросы на выделение памяти формируются во время исполнения задачи. Динамическое выделение, таким образом, противопоставляется статическому, когда запросы формируются на этапе компиляции программы. В конечном итоге, и те, и другие запросы нередко обрабатываются одним и тем же алгоритмом выделения памяти в ядре ОС. Но во многих случаях статическое выделение можно реализовать намного более простыми способами, чем динамическое. Главная сложность здесь в том, что при статическом выделении кажется неестественной – и поэтому редко требуется – возможность отказаться от ранее выделенной памяти. При динамическом же распределении часто требуется предоставить возможность отказываться от запрошенных блоков так, чтобы освобожденная память могла использоваться для удовлетворения последующих запросов. Таким образом, динамический распределитель вместо простой границы между занятой и свободной памятью (которой достаточно в простых случаях статического распределения) вынужден хранить список возможно несвязных областей свободной памяти, называемый пулом или кучей. Многие последовательности запросов памяти и отказов от нее могут привести к тому, что вся доступная память будет разбита на блоки маленького размера, и попытка выделения большого блока завершится неудачей, даже если сумма длин доступных маленьких блоков намного больше требуемой. Это явление называется фрагментацией памяти. Иногда используют более точный термин – внешняя фрагментация. Кроме того, большое количество блоков требует длительного поиска. В зависимости от решаемой задачи используются различные стратегии поиска свободных блоков памяти. Например, программа может выделять блоки одинакового размера или нескольких фиксированных размеров. Это сильно облегчает решение задач дефрагментации и поиска свободных участков ОЗУ. Возможны ситуации, когда блоки освобождаются в порядке, обратном тому, в котором они выделялись. Это позволяет свести выделение памяти к стековой структуре, т. е. фактически, вернуться к простому запоминанию границы между занятой и свободной памятью. Возможны также ситуации, когда некоторые из занятых блоков можно переместить по памяти – тогда есть возможность проводить дефрагментацию памяти, перемещение занятых блоков памяти с целью объединить свободные участки. В стандартных библиотечных функциях языков высокого уровня, как правило, используются алгоритмы, рассчитанные на наиболее общий случай: программа запрашивает блоки случайного размера в случайном порядке и освобождает их также случайным образом.

Варианты алгоритмов распределения памяти исследовались еще в 50-е годы. Обычно все свободные блоки памяти объединяются в двунаправленный связанный список. Список должен быть двунаправленным для того, чтобы из него в любой момент можно было извлечь любой блок. Впрочем, если все действия по извлечению блока производятся после поиска, то можно слегка усложнить процедуру поиска и всегда сохранять указатель на предыдущий блок. Это решает проблему извлечения и можно ограничиться однонаправленным списком. Беда только в том, что многие алгоритмы при объединении свободных блоков извлекают их из списка в соответствии с адресом, поэтому для таких алгоритмов двунаправленный список остро необходим.

Поиск в списке может вестись тремя способами: до нахождения первого подходящего (first fit) блока, до блока, размер которого ближе всего к заданному – наиболее подходящего (best fit), и, наконец, до нахождения самого большого блока, наименее подходящего (worst fit).

Использование стратегии worst fit имеет смысл разве что в сочетании с сортировкой списка по убыванию размера. Это может ускорить выделение памяти (всегда берется первый блок, а если он недостаточно велик, мы с чистой совестью можем сообщить, что свободной памяти нет), но создает проблемы при освобождении блоков: время вставки в отсортированный список пропорционально размеру списка. Помещать блоки в отсортированный массив еще хуже – время вставки становится еще больше и появляется ограничение на количество блоков. Использование хэш-таблиц или двоичных деревьев требует накладных расходов и усложнений программы, которые себя в итоге не оправдывают. На практике стратегия worst fit используется при размещении пространства в файловых системах, например в HPFS. Чаще всего применяют несортированный список. Для нахождения наиболее подходящего мы обязаны просматривать весь список, в то время как первый подходящий может оказаться в любом месте, и среднее время поиска будет меньше.

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

Библиотеки распределения памяти обычно рассчитывают на общий случай и используют алгоритмы first fit.

Сборка мусора

Явное освобождение динамически выделенной памяти применяется во многих системах программирования и потому привычно для большинства программистов, но оно имеет серьезный недостаток: если программист по какой-то причине не освобождает выделенные блоки, память будет теряться. Эта ошибка, называемая утечкой памяти (memory leak), особенно неприятна в программах, которые длительное время работают без перезапуска – подсистемах ядра ОС, постоянно запущенных сервисах или серверных приложениях. Дополнительная неприятность состоит в том, что медленные утечки могут привести к заметным потерям памяти лишь при многодневной или даже многомесячной непрерывной эксплуатации системы, поэтому их сложно обнаружить при тестировании. Некоторые системы программирования используют специальный метод освобождения динамической памяти, называемый сборкой мусора (garbage collection). Этот метод состоит в том, что ненужные блоки памяти не освобождаются явным образом. Вместо этого используется некоторый более или менее изощренный алгоритм, следящий за тем, какие блоки еще нужны, а какие – уже нет. Самый простой метод отличать используемые блоки от ненужных – считать, что блок, на который есть ссылка, нужен, а блок, на который ни одной ссылки не осталось, – не нужен. Для этого к каждому блоку присоединяют дескриптор, в котором подсчитывают количество ссылок на него. Каждая передача указателя на этот блок приводит к увеличению счетчика ссылок на 1, а каждое уничтожение объекта, содержавшего указатель, – к уменьшению. Впрочем, при наивной реализации такого подхода возникает специфическая проблема. Если у нас есть циклический список, на который нет ни одной ссылки извне, то все объекты в нем будут считаться используемыми, хотя они и являются мусором. Если мы по тем или иным причинам уверены, что кольца не возникают, метод подсчета ссылок вполне приемлем; если же мы используем графы произвольного вида, необходим более умный алгоритм. Наиболее распространенной альтернативой подсчету ссылок является периодический просмотр всех ссылок, которые мы считаем “существующими”. Если некоторые из указуемых объектов сами по себе могут содержать ссылки, мы вынуждены осуществлять просмотр рекурсивно. Проведя эту рекурсию до конца, мы можем быть уверены, что, то и только то, что мы просмотрели, является нужными данными, и с чистой совестью можем объявить все остальное мусором. Эта стратегия решает проблему кольцевых списков, но требует остановки всей остальной деятельности, которая может сопровождаться созданием или уничтожением ссылок. Все методы сборки мусора, так или иначе, сводятся к поддержанию базы данных о том, какие объекты на кого ссылаются.