Русская Википедия:Куча (память)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Значения Шаблон:Не путать Ку́ча (Шаблон:Lang-en) в информатике и программировании — название структуры данных, с помощью которой реализована динамически распределяемая память приложения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Шаблон:Rq

Шаблон:Структуры данных Шаблон:Аспекты операционных систем