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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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