Русская Википедия:Куча (память)
Шаблон:Значения Шаблон:Не путать Ку́ча (Шаблон:Lang-en) в информатике и программировании — название структуры данных, с помощью которой реализована динамически распределяемая память приложения.
Размер кучи — размер памяти, выделенный операционной системой (ОС) для хранения кучи (под кучу).
Принцип работы
При запуске процесса ОС выделяет память для размещения кучи. В дальнейшем память для кучи (под кучу) может выделяться динамически.
Программа пользователя, используя функции, подобные Шаблон:Cpp, может получать указатели на области памяти, принадлежащие куче. Программы используют кучу для размещения динамически создаваемых структур данных. Программа может освободить память с помощью функций, подобных Шаблон:Cpp.
Память кучи можно разделить на занятую (выделенную программе с помощью Шаблон:Cpp или подобных функций) и свободную (ещё не занятую или уже освобождённую с помощью Шаблон:Cpp или подобных функций).
Для хранения данных о том, какая область кучи является занятой, а какая — свободной, обычно используется дополнительная область памяти.
Перед началом работы программы выполняется инициализация кучи, в ходе которой память, выделенная под кучу, отмечается как свободная.
Функция, подобная Шаблон:Cpp, выполняет примерно следующие действия:
- просматривает список занятых/свободных областей памяти, размещённых в куче, в поисках свободной области подходящего размера;
- в случае нехватки свободной памяти может запросить дополнительную память у ОС;
- добавляет найденную область в список занятых областей (или помечает область как занятую);
- возвращает указатель на начало области памяти;
- если по тем или иным причинам выделить память не удалось, сообщает об ошибке (например, Шаблон:Cpp возвращает Шаблон:Cpp).
Функция, подобная Шаблон:Cpp, выполняет примерно следующие действия:
- просматривает список занятых/свободных областей памяти, размещённых в куче, в поисках указанной области;
- удаляет из списка занятых областей памяти найденную область;
- добавляет найденную область в список свободных областей (или помечает область как свободную).
Программа может быть уверена в том, что между вызовами функций, подобных Шаблон:Cpp и Шаблон:Cpp, область памяти, помеченная как занятая, не будет выделена повторно. После вызова Шаблон:Cpp или подобной функции, область памяти будет освобождена и в дальнейшем может использоваться повторно или может быть отдана ОС. Использование указателя на освобождённую область памяти будет приводить к сбоям или непредсказуемой работе программы.
Алгоритмы и производительность
Куча представляет собой непрерывную область памяти, поделённую на занятые и свободные области (блоки) различного размера.
Информация о свободных и занятых областях кучи может храниться в списках различных форматов. От выбранного формата списка напрямую зависит производительность функций, подобных Шаблон:Cpp и Шаблон:Cpp, так как большую часть времени эти функции тратят на поиск по списку подходящих областей.
Для увеличения размера кучи Шаблон:Cpp и подобные функции используют системный вызов (вызывают функцию ОС). При этом происходит переключение контекста из пространства пользователя в пространство ядра ОС и обратно. Поиск по списку занятых/свободных областей кучи выполняется быстрее, чем переключение контекстов, поэтому выгоднее один раз использовать системный вызов для выделения большой области памяти под кучу, а в дальнейшем выделять программе области меньшего размера из имеющейся крупной области с ведением списка занятых/свободных областей.
Количество элементов, входящих в список занятых/свободных областей кучи, может быть уменьшено путём слияния элементов, содержащих информацию о следующих друг за другом областях. Это позволит уменьшить время обхода списка.
Каждый элемент списка может хранить адрес области памяти, её размер, информацию о следующей (для поиска в прямом направлении) и/или предыдущей (для поиска в обратном направлении) области.
Пример реализации
Создание нескольких списков для хранения информации об областях одинаковых или близких размеров. Выбор списка в зависимости от размера области.
См. также
- Функции из стандартной библиотеки языка Си
Шаблон:Структуры данных Шаблон:Аспекты операционных систем
