WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии