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

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

Размер кучи — размер памяти, выделенный операционной системой (ОС) для хранения кучи (под кучу).

Принцип работы

При запуске процесса ОС выделяет память для размещения кучи. В дальнейшем память для кучи (под кучу) может выделяться динамически.

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

Память кучи можно разделить на занятую (выделенную программе с помощью malloc() или подобных функций) и свободную (ещё не занятую или уже освобождённую с помощью free() или подобных функций).

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

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

Функция, подобная malloc(), выполняет примерно следующие действия:

просматривает список занятых/свободных областей памяти, размещённых в куче, в поисках свободной области подходящего размера;
в случае нехватки свободной памяти может запросить дополнительную память у ОС;
добавляет найденную область в список занятых областей (или помечает область как занятую);
возвращает указатель на начало области памяти;
если по тем или иным причинам выделить память не удалось, сообщает об ошибке (например, malloc() возвращает NULL).

Функция, подобная free(), выполняет примерно следующие действия:

просматривает список занятых/свободных областей памяти, размещённых в куче, в поисках указанной области;
удаляет из списка занятых областей памяти найденную область;
добавляет найденную область в список свободных областей (или помечает область как свободную).

Программа может быть уверена в том, что между вызовами функций, подобных malloc() и free(), область памяти, помеченная как занятая, не будет выделена повторно. После вызова free() или подобной функции, область памяти будет освобождена и в дальнейшем может использоваться повторно или может быть отдана ОС. Использование указателя на неосвобождённую область памяти будет приводить к сбоям или непредсказуемой работе программы.

Алгоритмы и производительность

Куча представляет собой непрерывную область памяти, поделённую на занятые и свободные области (блоки) различного размера.

Информация о свободных и занятых областях кучи может храниться в списках различных форматов. От выбранного формата списка напрямую зависит производительность функций, подобных malloc() и free(), так как большую часть времени эти функции тратят на поиск по списку подходящих областей.

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

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

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

Пример реализации

Создание нескольких списков для хранения информации об областях одинаковых или близких размеров. Выбор списка в зависимости от размера области.

См. также

Функции из стандартной библиотеки языка Си

malloc()
free()