|
|
| (не показана 1 промежуточная версия этого же участника) |
| Строка 1: |
Строка 1: |
| {{Значения|Куча}}
| | '''Ку́ча''' — название [[Структура данных|структуры данных]], с помощью которой реализована [[динамически распределяемая память]] приложения. |
| {{Не путать|Куча (структура данных)}}
| |
| '''Ку́ча''' ({{lang-en|heap}}) в [[Информатика|информатике]] и [[Программирование|программировании]] — название [[Структура данных|структуры данных]], с помощью которой реализована [[динамически распределяемая память]] приложения. | |
|
| |
|
| '''Размер кучи''' — размер памяти, выделенный [[Операционная система|операционной системой (ОС)]] для хранения кучи (под кучу). | | '''Размер кучи''' — размер памяти, выделенный [[Операционная система|операционной системой (ОС)]] для хранения кучи (под кучу). |
| Строка 7: |
Строка 5: |
| == Принцип работы == | | == Принцип работы == |
| При запуске [[Процесс (информатика)|процесса]] ОС выделяет [[Оперативная память|память]] для размещения кучи. В дальнейшем память для кучи (под кучу) может выделяться динамически. | | При запуске [[Процесс (информатика)|процесса]] ОС выделяет [[Оперативная память|память]] для размещения кучи. В дальнейшем память для кучи (под кучу) может выделяться динамически. |
|
| |
| Программа пользователя, используя [[Функция (программирование)|функции]], подобные {{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}}
| |
|
| |
| {{Структуры данных}}
| |
| {{Аспекты операционных систем}}
| |
|
| |
| [[Категория:Программирование]]
| |
| [[Категория:Управление памятью]]
| |
| [[Категория:Структуры данных]] | | [[Категория:Структуры данных]] |
Ку́ча — название структуры данных, с помощью которой реализована динамически распределяемая память приложения.
Размер кучи — размер памяти, выделенный операционной системой (ОС) для хранения кучи (под кучу).
Принцип работы
При запуске процесса ОС выделяет память для размещения кучи. В дальнейшем память для кучи (под кучу) может выделяться динамически.
Для хранения данных о том, какая область кучи является занятой, а какая — свободной, обычно используется дополнительная область памяти.
Перед началом работы программы выполняется инициализация кучи, в ходе которой память, выделенная под кучу, отмечается как свободная.
Алгоритмы и производительность
Куча представляет собой непрерывную область памяти, поделённую на занятые и свободные области (блоки) различного размера.
Пример реализации
Создание нескольких списков для хранения информации об областях одинаковых или близких размеров. Выбор списка в зависимости от размера области.
