Ку́ча (англ. heap) в информатике и программировании — название структуры данных, с помощью которой реализована динамически распределяемая память приложения.
Размер кучи — размер памяти, выделенной операционной системой (ОС) для хранения кучи (под кучу).
При запуске процесса ОС выделяет память для размещения кучи. В дальнейшем память для кучи (под кучу) может выделяться динамически.
Программа пользователя, используя функции, подобные malloc()
, может получать указатели на области памяти, принадлежащие куче. Программы используют кучу для размещения динамически создаваемых структур данных. Программа может освободить память с помощью функций, подобных free()
.
Память кучи можно разделить на занятую (выделенную программе с помощью функций, подобных malloc()
) и свободную (ещё не занятую или уже освобождённую с помощью функций, подобных free()
).
Для хранения данных о том, какая область кучи является занятой, а какая — свободной, обычно используется дополнительная область памяти.
Перед началом работы программы выполняется инициализация кучи, в ходе которой память, выделенная под кучу, отмечается как свободная.
Функция, подобная malloc()
выполняет примерно следующие действия:
malloc()
возвращает NULL
).Функция, подобная free()
, выполняет примерно следующие действия:
Программа может быть уверена в том, что между вызовами функций, подобных malloc()
и free()
, область памяти, помеченная как занятая, не будет выделена повторно. После вызова функции, подобной free()
, область памяти будет освобождена и в дальнейшем может использоваться повторно или может быть отдана ОС. Использование указателя на освобождённую область памяти будет приводить к сбоям или непредсказуемой работе программы.
Куча представляет собой непрерывную область памяти, поделённую на занятые и свободные области (блоки) различного размера.
Информация о свободных и занятых областях кучи может храниться в списках различных форматов. От выбранного формата списка напрямую зависит производительность функций, подобных malloc()
и free()
, так как большую часть времени эти функции тратят на поиск по списку подходящих областей.
Для увеличения размера кучи функция, подобная malloc()
, использует системный вызов (вызывает функцию ОС). При этом происходит переключение контекста из пространства пользователя в пространство ядра ОС и обратно. Поиск по списку занятых/свободных областей кучи выполняется быстрее, чем переключение контекстов, поэтому выгоднее один раз использовать системный вызов для выделения большой области памяти под кучу, а в дальнейшем выделять программе области меньшего размера из имеющейся крупной области с ведением списка занятых/свободных областей.
Количество элементов, входящих в список занятых/свободных областей кучи, может быть уменьшено путём слияния элементов, содержащих информацию о следующих друг за другом областях. Это позволит уменьшить время обхода списка.
Каждый элемент списка может хранить адрес области памяти, её размер, информацию о следующей (для поиска в прямом направлении) и/или предыдущей (для поиска в обратном направлении) области.
Создание нескольких списков для хранения информации об областях одинаковых или близких размеров. Выбор списка в зависимости от размера области.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .