Куча (память) - История изменений

Patarakin в 09:02, 19 октября 2022

2022-10-19T09:02:51Z

← Предыдущая версия		Версия от 12:02, 19 октября 2022
Строка 5:		Строка 5:
	== Принцип работы ==		== Принцип работы ==
	При запуске [[Процесс (информатика)\|процесса]] ОС выделяет [[Оперативная память\|память]] для размещения кучи. В дальнейшем память для кучи (под кучу) может выделяться динамически.		При запуске [[Процесс (информатика)\|процесса]] ОС выделяет [[Оперативная память\|память]] для размещения кучи. В дальнейшем память для кучи (под кучу) может выделяться динамически.

	Программа пользователя, используя [[Функция (программирование)\|функции]], подобные {{cpp\|1=malloc()}}, может получать [[Указатель (тип данных)\|указатели]] на области памяти, принадлежащие куче. Программы используют кучу для размещения динамически создаваемых структур данных. Программа может освободить память с помощью функций, подобных {{cpp\|1=free()}}.

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

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

Patarakin в 09:02, 19 октября 2022

2022-10-19T09:02:28Z

@@ Строка 1: / Строка 1: @@
-{{Значения|Куча}}
+'''Ку́ча''' — название [[Структура данных|структуры данных]], с помощью которой реализована [[динамически распределяемая память]] приложения.
 '''Размер кучи''' — размер памяти, выделенный [[Операционная система|операционной системой (ОС)]] для хранения кучи (под кучу).
@@ Строка 15: / Строка 13: @@
 Перед началом работы программы выполняется инициализация кучи, в ходе которой память, выделенная под кучу, отмечается как свободная.
 == Алгоритмы и производительность ==
 Куча представляет собой непрерывную область памяти, поделённую на занятые и свободные области (блоки) различного размера.
 == Пример реализации ==
 Создание нескольких списков для хранения информации об областях одинаковых или близких размеров. Выбор списка в зависимости от размера области.
 [[Категория:Структуры данных]]

Patarakin: 1 версия импортирована

2022-10-19T07:30:53Z

1 версия импортирована

← Предыдущая версия		Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>Well very well в 17:22, 29 мая 2022

2022-05-29T17:22:47Z

Новая страница

{{Значения|Куча}}
{{Не путать|Куча (структура данных)}}
'''Ку́ча''' ({{lang-en|heap}}) в [[Информатика|информатике]] и [[Программирование|программировании]] — название [[Структура данных|структуры данных]], с помощью которой реализована [[динамически распределяемая память]] приложения.

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

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

Программа пользователя, используя [[Функция (программирование)|функции]], подобные {{cpp|1=malloc()}}, может получать [[Указатель (тип данных)|указатели]] на области памяти, принадлежащие куче. Программы используют кучу для размещения динамически создаваемых структур данных. Программа может освободить память с помощью функций, подобных {{cpp|1=free()}}.

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

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

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

Функция, подобная {{cpp|1=malloc()}}, выполняет примерно следующие действия:
* просматривает список занятых/свободных областей памяти, размещённых в куче, в поисках свободной области подходящего размера;
* в случае нехватки свободной памяти может запросить дополнительную память у ОС;
* добавляет найденную область в список занятых областей (или помечает область как занятую);
* возвращает указатель на начало области памяти;
* если по тем или иным причинам выделить память не удалось, сообщает об ошибке (например, {{cpp|1=malloc()}} возвращает {{cpp|1=NULL}}).

Функция, подобная {{cpp|1=free()}}, выполняет примерно следующие действия:
* просматривает список занятых/свободных областей памяти, размещённых в куче, в поисках указанной области;
* удаляет из списка занятых областей памяти найденную область;
* добавляет найденную область в список свободных областей (или помечает область как свободную).

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

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

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

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

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

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

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

== См. также ==
* [[Динамически распределяемая память|Динамическая память]]
* [[NULL (Си)|NULL]]

; Функции из [[Стандартная библиотека языка Си|стандартной библиотеки языка Си]]
* [[malloc|malloc()]]
* [[Free (функция языка Си)|free()]]

{{rq|sources|refless|img}}

{{Структуры данных}}
{{Аспекты операционных систем}}

[[Категория:Программирование]]
[[Категория:Управление памятью]]
[[Категория:Структуры данных]]