Что из себя представляет динамическое выделение памяти

Что из себя представляет динамическое выделение памяти?

Какое выражение верно с точки зрения целесообразности использования динамического распределения памяти?

Какое из следующих определений представляет собой правильную запись операции сложения целого числа и объекта:

Что нужно сделать для освобождения памяти после выполнения такого кода ?

char *a; a = new char[20];

Что произойдёт если операция выделения памяти new завершится неудачно?

Отметьте правильный вариант освобождения всей памяти, выделенной для трехмерного массива для следующей программы

long (*lp)[2][4];lp = new long[3][2][4];

Динамическое выделение памяти

хранятся на стеке. Как следует из названия, стек работает с переменными по схеме FILO (first in last out). Управление стеком происходит автоматически. При выходе переменной из области видимости, соответствующая ей в стеке память освобождается. Этот механизм позволяет разработчику не следить за удалением автоматических переменных. Стек работает очень быстро, но имеет ограниченный размер, который обычно не превосходит нескольких мегабайт.

Второй тип памяти — куча — устроен иначе. В куче объекты можно хранить в произвольном месте, создавать и удалять их в произвольном порядке, а размер кучи обычно значительно превосходит размер стека. Платить за эти преимущества приходится скоростью: работа с кучей происходит значительно медленнее, чем со стеком. Кроме того, объекты из кучи не удаляются автоматически.

Кучу имеет смысл использовать в двух случаях:

Необходимо хранить большой объект. Хранение больших объектов на стеке может привести к его переполнению (stack overflow).
Автоматическое управление памятью в стеке не соответствует логике программы. Чаще всего такая ситуация возникает, когда созданный объект должен продолжать свое существование после выхода из блока, в котором он был создан. Ниже мы рассмотрим пример.

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

Ручное управление памятью

Начнем с обзора низкоуровневых инструментов, которые обычно не используются при разработке на современном C++. Знание эти инструментов, однако, может пригодиться при чтении старого кода и при работе со старыми компиляторами.

Создать объект в куче можно с помощью оператора new :

int *intptr = new int(7); auto *vecptr = new std::vectorstd::string>();

Оператор new возвращает указатель на область памяти в куче, в которой был создан объект. Создав объект с помощью оператора new , разработчик становится ответственными за его удаление. Освободить выделенную память и удалить объект можно с помощью оператора delete :

delete intptr; delete vecptr;

Вернемся к примеру из раздела про наследование, в котором мы строили модель символов в графическом текстовом редакторе. Напомним, что мы создали абстрактный базовый класс Character и два его наследника Letter и Digit . Допустим, нам надо реализовать функцию, которая возвращает полиморфный список символов (текст документа). Без динамического выделения нам будет сложно решить эту задачу. Например:

std::listCharacter*> create_document()  // Тут есть проблема Letter l1('a'); Letter l2('b'); Digit d1('1'); Digit d2('2'); return std::listCharacter*>&l1, &l2, &d1, &d2>; >

Объекты l1 , l2 , d1 и d2 в функции create_document созданы на стеке. При выходе из функции create_document для каждого объекта будет вызван деструктор и освобождена память на стеке. В этом виде функция возвращает список указателей на освобожденную память, что приводит к неопределенному поведению. Следующее изменение сделает код корректным:

std::listCharacter*> create_document()  auto* l1 = new Letter('a'); auto* l2 = new Letter('b'); auto* d1 = new Digit('1'); auto* d2 = new Digit('2'); return std::listCharacter*>l1, l2, d1, d2>; >

Теперь память для объектов выделяется в куче, объекты продолжают существовать после выхода из функции. Использовать функцию create_document необходимо с учетом особенностей работы с динамической памятью. Напишем функцию print_document , которая вызывает create_document и выводит символы в стандартный поток вывода:

// здесь есть проблема void print_document()  auto doc = create_document(); for (auto item : doc)  cout  <item; > >

Использование функции print_document приводит к утечке памяти: при каждом ее вызове в куче выделяется память, которая никогда не освобождается. Более аккуратная реализация выглядит так:

void print_document()  auto doc = create_document(); for (auto item : doc)  cout  <item; > // здесь может быть проблема, которую мы обсудим позже for (auto item : doc)  delete item; > >

Эта логика применима в любой ситуации с динамическим выделением памяти. Например, динамическое выделение памяти может происходить в конструкторе класса, а ее освобождение — в деструкторе.

Существуют версии операторов new и delete для создания и удаления массивов объектов:

int* p = new int[10]; // выделяем массив из 10 переменных типа int delete[] p;

При освобождении памяти важно использовать правильную версию оператора delete , что дополнительно усложняет разработку программ с ручным управлением памятью. Хорошей новостью является то, что оператор delete[] сам определяет размер удаляемого массива.

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

Владение ресурсами и идиома RAII

Динамическое выделение памяти тесно связано с концепцией владения ресурсами. Ресурсом может быть не только память, но и, например, файловый дескриптор или сокет-соединение. В хорошо спроектированной программе структура владения ресурсами устроена ясно: каждым ресурсом владеет определенный объект, который отвечает за освобождение ресурса. Владение ресурсом можно передавать другому объекту, который вместе с ресурсом берет на себя ответственность за его освобождение.

Ясно организовать владение ресурсами практически в любой программе можно, следую идиоме RAII (resource acquisition is initialization, получение ресурса есть инициализация), которая (в несколько упрощенном виде) состоит в следующем:

Каждый ресурс следует инкапсулировать в класс, при этом
- Конструктор выполняет выделение ресурса
- Деструктор выполняет освобождение ресурса
Мы уже видели пример RAII-объекта в C++, когда говорили про работу с файлами. Объект fstream владеет ресурсом — файловым дескриптором — и отвечает за его освобождение, а вся работа с файлом происходит через этот объект.

Умные указатели

В рамках идиомы RAII в современном C++ решены сложности работы с динамическим выделением памяти. Логика работы с динамической памятью инкапсулирована в специальных классах std::unique_ptr и std::shared_ptr , которые называют умными указателями. При конструировании такого объекта происходит выделение памяти, а при вызове деструктора — освобождение. Например:
```
#include int main()  auto luptr = std::make_uniqueLetter>('l'); auto dsptr = std::make_sharedDigit>('7'); return 0; > 
```
При выходе из функции main выделенная в куче память корректно будет освобождена. Объекты std::unique_ptr и std::shared_ptr различаются с точки зрения владения объектом. Уникальный указатель std::unique_ptr единолично владеет ресурсом. Это означает, что не может быть два разных объекта std::unique_ptr не могут быть связаны с одним и тем же ресурсом. Это, например, означает, что объект std::unique_ptr не имеет копирующего конструктора и копирующего оператора присваивания. Вместо этого возможно использование перемещающего конструктор и перемещающего оператора присваивания. Например:
```
auto luptr = std::make_uniqueLetter>('l'); // std::unique_ptr luptr2 = luptr; // ошибка, уникальное владение auto luptr3 = std::move(luptr); // перемещение возможно. luptr передал владение и потерял связь с объектом 
```
Объекты std::shared_ptr можно копировать. При этом несколько объектов std::shared_ptr оказываются связанными с одним ресурсом (динамически выделенной памятью). Освобождение памяти происходит в момент, когда последний ссылающийся на эту память объект std::shared_ptr вышел из области видимости. Необходимость подсчета ссылок в объектах std::shared_ptr приводит к определенным накладным расходам. Например объекты std::shared_ptr занимают больше памяти, чем объекты std::unique_ptr . Объекты std::unique_ptr при этом не уступают в производительности простым указателям.

Важно, что умные указатели сохраняют свойство полиморфности. Это позволяет нам модифицировать функцию create_document следующим образом:
```
std::liststd::unique_ptrCharacter>> create_document()  std::liststd::unique_ptrCharacter>> doc; doc.push_back(std::make_uniqueLetter>('a')); doc.push_back(std::make_uniqueLetter>('b')); doc.push_back(std::make_uniqueDigit>('1')); doc.push_back(std::make_uniqueDigit>('2')); return doc; > 
```
и не заботится больше о ручном освобождении ресурсов. Несмотря на некоторую громоздкость синтаксиса умные указатели значительно упрощают разработку на C++. Мы рекомендуем использовать умные указатели вместо низкоуровневых операторов new и delete для работы с динамической памятью.

Сложность обращения с длинными названиями типов в C++ вроде std::list> (и это не самый плохой случай) может быть преодолена с помощью псевдонимов. Например:
```
using CharPtr = std::unique_ptrCharacter>; // определили псевдоним для уникальных указателей на Character using Document = std::listCharPtr>; Document create_document()  Document doc; doc.push_back(std::make_uniqueLetter>('a')); doc.push_back(std::make_uniqueLetter>('b')); doc.push_back(std::make_uniqueDigit>('1')); doc.push_back(std::make_uniqueDigit>('2')); return doc; > 
```
Виртуальный деструктор

В заключение этого раздела обсудим один тонкий момент, связанный с полиморфизмом и освобождением ресурсов в C++. Функция create_document корректно работает с динамической памятью. Однако, если использовать классы Character , Letter и Digit в том виде, в каком мы их оставили в разделе про наследование, то освобождение памяти при удалении объекта Document будет выполнено неверно. Контейнер std::list работает с (умными) указателями на объекты абстрактного класса Character . При удалении объекта std::list происходит удаление всех объектов типа std::unique_ptr , которые в свою очередь вызывают деструкторы объектов Character . Вместо этого мы хотим, чтобы для каждого объекта вызывался деструктор нужного класса-наследника. Вызов только деструктора базового класса снова может привести к утечке памяти.

Как для любого другого метода полиморфизм вызова деструктора реализуется через механизм виртуальных методов, в данном случае нам нужен виртуальный деструктор:
```
class Character  // . virtual ~Character() = default; >; 
```
Поскольку ничего особенного, кроме собственно виртуальности, нам не нужно, мы доверили генерирование деструктора компилятору. Теперь наша программа, динамически выделяющая память для полиморфных объектов с помощью умных указателей, будет работать так, как нам нужно.

В любой иерархии классов деструктор базового класса рекомендуется объявлять виртуальным, чтобы избегать проблем с освобождением ресурсов объектами классов-наследников.

Резюме

В этом разделе мы обсудили основы работы с динамической памятью в C++. Рекомендуемыми инструментами работы с динамической памятью являются умные указатели std::unique_ptr и std::shared_ptr . Не забывайте объявлять деструктор базового класса виртуальным, если возможна работа с объектами классов-потомков через указатель на объект базового класса (а такая возможность есть всегда).

Документация и ссылки
- https://en.cppreference.com/w/cpp/memory/new/operator_new
- https://en.cppreference.com/w/cpp/memory/new/operator_delete
- https://en.cppreference.com/w/cpp/language/raii
- Идиома RAII (wikipedia)
- https://en.cppreference.com/w/cpp/keyword/using
- https://en.cppreference.com/w/cpp/language/destructor
Что из себя представляет динамическое выделение памяти

Для работы с динамической памятью в языке С используются следующие функции: malloc, calloc, free, realloc.
Рассмотрим их подробнее.

void *malloc(size_t size);

В качестве входного параметра функция принимает размер памяти, которую требуется выделить. Возвращаемым значением является указатель на выделенный в куче участок памяти.
Для выделения памяти под 1 000 000 int`ов необходимо выполнить следующий код:

int * p = malloc(1000000*sizeof(int));

В языке С++ потребуется небольшая модификация данной кода (из-за того, что в С++ нет неявного приведения указателей):

int * p = (int *) malloc(1000000*sizeof(int));

Если ОС не смогла выделить память (например, памяти не хватило), то malloc возвращает 0.

После окончания работы с выделенной динамически памятью нужно освободить ее. Для этой цели используется функция free, которая возвращает память под управление ОС.

void free(void *ptr);

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

void *calloc(size_t nmemb, size_t size);

Функция работает аналогично malloc, но отличается синтаксисом (вместо размера выделяемой памяти нужно задать количество элементов и размер одного элемента) и тем, что выделенная память будет обнулена. Например, после выполнения

int * q = (int *) calloc(1000000, sizeof(int))

q будет указывать на начало массива из миллиона int`ов инициализированных нулями.

void *realloc(void *ptr, size_t size);

Функция изменяет размер выделенной памяти (на которую указывает ptr, полученный из вызова malloc, calloc или realloc). Если размер указанный в параметре size больше, чем тот, который был выделен под указатель ptr, то проверяется, есть ли возможность выделить недостающие ячейки памяти подряд с уже выделенными. Если места недостаточно, то выделяется новый участок памяти размером size и данные по указателю ptr копируются в начало нового участка.

Какие бывают ошибки:

1. Потеря памяти

int * p = (int *) malloc(100);
p = (int *) malloc(200); // потерян указатель на первые 100 int`ов, которые теперь нельзя отдать обратно ОС

2.Повторное освобождение выделенной памяти

free(p); … free(p); // неопределенное поведение

free(p);
p = 0;
…
free(p); // отработает без ошибок

Работа с динамической памятью в С++

В С++ есть свой механизм выделения и освобождения памяти — это функции new и delete.

Пример использования new:

int * p = new int[1000000]; // выделение памяти под 1000000 int`ов

Т.е. при использовании функции new не нужно приводить указатель и не нужно использовать sizeof().
Освобождение выделенной при помощи new памяти осуществляется посредством следующего вызова:

Если требуется выделить память под один элемент, то можно использовать

int * q = new int;

int * q = new int(10); // выделенный int проинциализируется значением 10

в этом случае удаление будет выглядеть следующим образом:
1. При динамическом выделении памяти в ней помимо значения указанного типа будет храниться служебная информация ОС и С/С++. Таким образом потребуется гораздо больше памяти, чем при хранении необходимых данных на стеке.
2. Если в памяти хранить большое количество маленьких кусочков, то она будет сильно фрагментирована и большой массив данных может не поместиться.
Многомерные массивы.

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

1ый способ

На первом шаге выделяется указатель на массив указателей, а на втором шаге, в цикле каждому указателю из массива выделяется массив чисел в памяти:

int ** a = new int*[n];
for (int i = 0; i != n; ++i)
a[i] = new int[m];

Однако, этот способ плох тем, что в нём требуется n+1 выделение памяти, а это достаточно дорогая по времени операция.

2ой способ

На первом шаге выделение массива указателей и массива чисел размером n на m. На втором шаге каждому указателю из массива ставится в соответствие строка в массиве чисел.

int ** a = new int*[n];
a[0] = new int[n*m];
for (int i = 1; i != n; ++i)
a[i] = a[0] + i*m;

В данном случае требуется всего 2 выделения памяти.

Для освобождения памяти требуется выполнить:

for (int i = 0; i != n; ++i)
delete [] a[i];
delete [] a;

delete [] a[0];
delete [] a;

Таким образом, второй способ опять же требует гораздо меньше вызовов функции delete [], чем первый.

Динамическая память в системах жёсткого реального времени

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

(КДПВ – см. аннотацию к диаграмме в конце)

Неочевидность свойств алгоритмов динамического распределения памяти породила настораживающую тенденцию к лёгкому искажению действительности в документации некоторых ОСРВ, причём не последнего пошиба. Например, раздел об управлении памятью FreeRTOS обходит стороною класс аллокаторов постоянной вычислительной сложности O(1), заставляя неискушённого коллегу принять, что O(n) есть теоретический потолок. Аналогичные артефакты находятся в документации к ChibiOS (1, 2). Мы, разумеется, не станем подозревать разработчиков столь выдающихся продуктов в незнании матчасти; скорее, спишем это на свойственный людям банальный недосмотр. Приложения реального времени редко полагаются на динамическое распределение во время выполнения, так что множество затронутых здесь невелико.

Знакомому со спецификой систем реального времени читателю не нужно объяснять, что первоочередное значение для них имеют характеристики не среднего, а худшего случая, что радикально отличает их от систем общего назначения (примером последней будет та, при помощи которой вы сейчас читаете этот текст). Для прочих читателей приведу пример: если некий алгоритм имеет асимптотическую сложность O(log n) в подавляющем большинстве случаев, но раз в тысячу лет иногда выпадает случай O(n), то интерес для анализа представляет лишь последний.

Порядком вычислительной сложности дело не ограничивается. Ресурсный потолок по памяти, очевидно, имеет критическое значение для встраиваемых систем, где количество доступных мегабайт можно пересчитать пальцами одной руки. Поставщики же ОСРВ имеют наклонности к заимствованию оптимизированных на средний случай алгоритмов из продуктов, не рассчитанных на реальное время и встраиваемые приложения. Подтверждающим примером будет реализация аллокатора в NuttX, где используется стратегия поиска наилучшего совпадения (best fit), чья пониженная склонность к фрагментации в общем случае даётся ценою крайне пессимистичного её прогноза для худшего случая. Аналогичные замечания можно сделать в адрес упомянутых ранее конкурентов.

Недостаток внимания со стороны вендоров ОСРВ к теоретической стороне вопроса порождает положительную обратную связь, где неточности в документации и технически неоптимальные реализации действительно вынуждают пользователей отказываться от их использования, что снижает интерес, и, как следствие, оставляет осложнения без внимания.

Ваш покорный слуга недаром увяз в этой проблеме. Работая над реализацией встраиваемого сетевого стека для одного протокола реального времени, я обнаружил, что замена используемого на тот момент традиционного блочного менеджера памяти на обычный аллокатор фрагментов произвольного размера не только радикально упрощает API и реализацию, но и улучшает асимптотическую сложность внутренних процедур стека. Последнее обусловлено, среди прочего, заменой фрагментированных буферов из цепочек блоков на непрерывные фрагменты памяти:
```
// Список фрагментов на блочном аллокаторе: struct FragmentedBuffer < struct FragmentedBuffer* next; uint8_t data[]; >; // . превращается в: uint8_t* data;
```
На второй день углубления в релевантные материалы, черенок моего сознания наткнулся на анализ алгоритмов Buddy Allocator, Half-Fit, и Two-Level Segregated Fit (TLSF). Все они представляют собою детерминированные аллокаторы постоянной вычислительной сложности O(1) (для Buddy Allocator мы делаем допущение, что объём памяти постоянен, в противном случае оценка будет иной). Почтенные господа J. Herter и J. Robson подвергают оба ресурсных вопроса – как времени, так и памяти – детальному рассмотрению в диссертации “Timing-Predictable Memory Allocation In Hard Real-Time Systems” и статье “Worst case fragmentation of first fit and best fit storage allocation strategies”, соответственно.

Даже малознакомый с теорией динамического распределения памяти читатель найдёт обоснование постоянства вычислительной сложности приведённых алгоритмов тривиальным. Гораздо больший интерес здесь представляет фрагментация. Насколько я могу видеть, многие мои коллеги ошибочно подозревают, что динамические аллокаторы неизбежно приходят в состояние катастрофической фрагментации (где выделение памяти невозможно из-за высокого дробления свободных участков) за конечное время. Подробный разбор вопроса с доказательством обратного можно найти на страницах 26–33 диссертации многоуважаемого Хертера, здесь же я лишь оставлю финальный вывод, что предел размера кучи H, при котором катастрофическая фрагментация недостижима, для лучших из приведённых алгоритмов определён как:

Где M – пиковая потребность приложения в динамической памяти, n – размер наибольшей аллокации.

Здесь уместно вернуться к началу и бросить ещё камней в огород поставщиков ОСРВ. Как я упомянул, в некоторых продуктах встречаются реализации алгоритмов управления памятью, чья стратегия размещения предусматривает выбор свободного фрагмента минимально возможного размера. Эта стратегия хорошо показывает себя в среднем случае, но в особых условиях деградирует до теоретического предела H = M (n — 2), уничтожая надежду на её уместность во встраиваемых системах.

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

Приведённая выше модель худшего случая фрагментации потребовала дополнения, потому что её общая форма не уделяет внимания собственной потребности аллокатора в памяти для хранения метаданных. Уточнённая модель, построенная с учётом специфики моей реализации, доступна в документации, здесь её не привожу по причине малой теоретической ценности. Вместо этого призываю осмотреть иллюстрацию в начале текста; её содержимое учитывает конкретику моей реализации, и оно таково:
- Левая диаграмма: размер кучи H [KiB] от пиковой потребности приложения в памяти M [KiB] и наибольшей аллокации n [KiB] при минимальном размере аллокации 16 байт.
- Правая диаграмма: аналогично, но единицы измерения MiB.
Если величины H кажутся чрезмерными, это неспроста, ведь понятия верхнего предела и худшего случая не эквивалентны. Задача поиска огибающей худшего случая включает в себя минимизацию разрыва между теоретическим пределом и практически достижимым наихудшим состоянием. В нашем случае это конкретизируется в минимизацию разрыва между значением H, предсказанным нашей моделью, и реальным пиковым случаем фрагментации, который система может встретить на практике. Я надеялся подобраться к проблеме уменьшения H при сохранении гарантированных свойств алгоритма при помощи симуляций с систематическим перебором возможных состояний, но был вынужден отложить эту затею по причине отсутствия времени. Однако, вовлечённый в тему человек понимает высокую практическую значимость этой доработки. Если среди читателей найдутся достаточно мотивированные коллеги (Embox?), я бы с готовностью ввязался в коллаборацию по этому вопросу.

Другой важный вопрос заключается в исправлении текущего положения дел в открытых системах. Я вяло потыкал метафорической палочкой одного из разработчиков NuttX по этому поводу, и почерпнул, что вопрос имеет низкий приоритет: «I considered porting TLSF at one point, but overall it’s low on my list of NuttX improvements I’d explore if I actually had time». Есть куда стремиться.
- Open source
- Системное программирование
- Алгоритмы
- C
- Программирование микроконтроллеров
Похожие публикации:

Что из себя представляет динамическое выделение памяти