Interested Article - Куча (память)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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