Куча (память)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Ку́ча (англ. heap) в информатике и программировании — название структуры данных, с помощью которой реализована динамически распределяемая память приложения, а также объём памяти, зарезервированный под эту структуру.

Организация[править | править вики-текст]

Куча использует память, выделяемую динамически или запрошенную статически у операционной системы. Эта память используется для размещения объектов, динамически созданных программой.

В любой момент времени существования кучи вся память, на которой работает куча, разделена на занятую и свободную. Занятая память использована под размещение объектов, уже созданных и ещё не освобождённых к этому моменту времени. Из объёма свободной памяти примитивы работы с кучей могут выделять память под новые объекты.

Для хранения данных о принадлежности памяти к занятой или свободной обычно используется дополнительная область памяти.

Принцип работы[править | править вики-текст]

Для размещения и удаления динамических объектов используются примитивы «создать объект» (например, malloc) и «удалить объект» (например, free). Кроме того, перед началом работы программы выполняется инициализация кучи, в ходе которой вся изначально выделенная под кучу память отмечается как свободная.

При размещении объекта реализация примитива «создать объект» просматривает доступную куче свободную память в поисках возможности разместить в ней объект требуемого размера. Многие реализации примитивов кучи могут в случае нехватки собственной свободной памяти запросить дополнительную память у операционной системы. В случае, если по тем или иным причинам разместить объект невозможно, примитив «создать объект» сообщает об ошибке (например, malloc возвращает NULL). В случае успеха выбранная область памяти отмечается как занятая. Примитив возвращает адрес начала выделенной области.

При удалении объекта реализация примитива «удалить объект» отмечает, что область, ранее использованная удаляемым объектом, теперь свободна.

В промежутках между вызовами примитивов «создать объект» и «удалить объект» выделенная под объект область памяти не может быть отдана ни под какой другой объект. Поэтому приложение может свободно пользоваться выделенной ему областью памяти. В то же время после вызова примитива «удалить объект» освобождённая область может быть использована повторно или отдана операционной системе, поэтому использование указателя, полученного ранее от примитива «создать объект», будет приводить к сбоям или непредсказуемой работе программы.

Алгоритмы кучи и производительность[править | править вики-текст]

Куча — это длинный отрезок адресов памяти, поделенный на идущие подряд блоки различных размеров.

Блоки бывают свободные и занятые. Для возможности выделения памяти путем повторного использования свободного блока (без дорогостоящего увеличения кучи в целом — требует системного вызова) в том или ином виде нужен список свободных блоков.

Для сокращения списка свободных блоков с целью уменьшения времени его обхода всегда имеет смысл сливать 2 или 3 идущих подряд свободных блока в один. Если свободен последующий блок, то его легко найти, отступив вперед на размер освобождаемого блока. С предыдущим блоком все сложнее, и потому имеет смысл хранить размер предыдущего блока (для его поиска) в заголовке любого блока.

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

Очень хорошей реализацией является несколько списков, каждый для своего размера. Это позволяет быстро проигнорировать заведомо слишком маленькие свободные блоки целыми списками, без проверки каждого персонально.

См. также[править | править вики-текст]