Для чего нужна динамическая память
Зачем нужна динамическая память
Раньше я думал что динамическая память нужна для того чтобы выделять там память под массивы типов, размер которых не известен во время компиляции. Сейчас я узнал, что в стандарте С++ нет VLA (хотя с настройками компилятора clang, VLA можно осуществить), зато в Си VLA есть. Так зачем вообще тогда нужна динамическая память, если можно включить VLA. Единственное мое предположение, это то что размер стека ограничен много меньшим числом, нежели размер кучи, поэтому большой размер памяти аллоцируем в куче.
1 ответ 1
Динамическая память нужна в первую очередь для того, чтобы дать пользователю ручной контроль над временем жизни/продолжительностью хранения создаваемых объектов. То есть выражаясь попросту для того, чтобы можно было выделить память внутри блока (функции), выйти из этого блока (функции), а память при этом оставалась выделенной.
Именно это свойство динамической памяти позволяет вам, например, создавать списки или деревья с неизвестным на стадии компиляции количеством узлов, т.е. генерировать объекты-узлы в необходимом количестве во время выполнения программы.
Вторым по значимости назначением динамической памяти уже является создание объектов, чей тип известен только во время выполнения: полиморфные объекты или массивы заранее не известного размера.
И, наконец, в качестве третьего, побочного, назначения динамической памяти можно назвать создание объектов, чье время жизни является вполне автоматическим, но которые при этом слишком велики для автоматической памяти (для размещения в стеке).
Динамическая память в системах жёсткого реального времени
Существует класс приложений реального времени, для которых тяжело предсказать потребности в распределении памяти во время выполнения статически. В этот класс входят, например, встраиваемые реализации стеков некоторых коммуникационных протоколов, где поведение и распределение ресурсов определяется отчасти активностью других агентов в сети. Классический подход в таких случаях заключается в использовании блочных менеджеров памяти, выделяющих фрагменты фиксированного размера (как это сделано, например, в LwIP). Этот подход накладывает нежелательные функциональные и качественные ограничения на реализацию. В этой заметке я предлагаю точку зрения, что традиционные (не блочные) аллокаторы незаслуженно обделены вниманием разработчиков систем реального времени, делюсь соображениями по релевантным вопросам, жалуюсь на жизнь, и предлагаю улучшить положение дел.
(КДПВ – см. аннотацию к диаграмме в конце)
Неочевидность свойств алгоритмов динамического распределения памяти породила настораживающую тенденцию к лёгкому искажению действительности в документации некоторых ОСРВ, причём не последнего пошиба. Например, раздел об управлении памятью FreeRTOS обходит стороною класс аллокаторов постоянной вычислительной сложности O(1), заставляя неискушённого коллегу принять, что O(n) есть теоретический потолок. Аналогичные артефакты находятся в документации к ChibiOS (1, 2). Мы, разумеется, не станем подозревать разработчиков столь выдающихся продуктов в незнании матчасти; скорее, спишем это на свойственный людям банальный недосмотр. Приложения реального времени редко полагаются на динамическое распределение во время выполнения, так что множество затронутых здесь невелико.
Знакомому со спецификой систем реального времени читателю не нужно объяснять, что первоочередное значение для них имеют характеристики не среднего, а худшего случая, что радикально отличает их от систем общего назначения (примером последней будет та, при помощи которой вы сейчас читаете этот текст). Для прочих читателей приведу пример: если некий алгоритм имеет асимптотическую сложность O(log n) в подавляющем большинстве случаев, но раз в тысячу лет иногда выпадает случай O(n), то интерес для анализа представляет лишь последний.
Порядком вычислительной сложности дело не ограничивается. Ресурсный потолок по памяти, очевидно, имеет критическое значение для встраиваемых систем, где количество доступных мегабайт можно пересчитать пальцами одной руки. Поставщики же ОСРВ имеют наклонности к заимствованию оптимизированных на средний случай алгоритмов из продуктов, не рассчитанных на реальное время и встраиваемые приложения. Подтверждающим примером будет реализация аллокатора в NuttX, где используется стратегия поиска наилучшего совпадения (best fit), чья пониженная склонность к фрагментации в общем случае даётся ценою крайне пессимистичного её прогноза для худшего случая. Аналогичные замечания можно сделать в адрес упомянутых ранее конкурентов.
Недостаток внимания со стороны вендоров ОСРВ к теоретической стороне вопроса порождает положительную обратную связь, где неточности в документации и технически неоптимальные реализации действительно вынуждают пользователей отказываться от их использования, что снижает интерес, и, как следствие, оставляет осложнения без внимания.
Ваш покорный слуга недаром увяз в этой проблеме. Работая над реализацией встраиваемого сетевого стека для одного протокола реального времени, я обнаружил, что замена используемого на тот момент традиционного блочного менеджера памяти на обычный аллокатор фрагментов произвольного размера не только радикально упрощает API и реализацию, но и улучшает асимптотическую сложность внутренних процедур стека. Последнее обусловлено, среди прочего, заменой фрагментированных буферов из цепочек блоков на непрерывные фрагменты памяти:
На второй день углубления в релевантные материалы, черенок моего сознания наткнулся на анализ алгоритмов 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 кажутся чрезмерными, это неспроста, ведь понятия верхнего предела и худшего случая не эквивалентны. Задача поиска огибающей худшего случая включает в себя минимизацию разрыва между теоретическим пределом и практически достижимым наихудшим состоянием. В нашем случае это конкретизируется в минимизацию разрыва между значением 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». Есть куда стремиться.
Урок №85. Динамическое выделение памяти
Обновл. 13 Сен 2021 |
Язык С++ поддерживает три основных типа выделения (или «распределения») памяти, с двумя из которых, мы уже знакомы:
Статическое выделение памяти выполняется для статических и глобальных переменных. Память выделяется один раз (при запуске программы) и сохраняется на протяжении работы всей программы.
Автоматическое выделение памяти выполняется для параметров функции и локальных переменных. Память выделяется при входе в блок, в котором находятся эти переменные, и удаляется при выходе из него.
Динамическое выделение памяти является темой этого урока.
Динамическое выделение переменных
Как статическое, так и автоматическое распределение памяти имеют два общих свойства:
Размер переменной/массива должен быть известен во время компиляции.
Выделение и освобождение памяти происходит автоматически (когда переменная создается/уничтожается).
В большинстве случаев с этим всё ОК. Однако, когда дело доходит до работы с пользовательским вводом, то эти ограничения могут привести к проблемам.
Если нам нужно объявить размер всех переменных во время компиляции, то самое лучшее, что мы можем сделать — это попытаться угадать их максимальный размер, надеясь, что этого будет достаточно:
Это плохое решение, по крайней мере, по трем причинам:
Во-первых, теряется память, если переменные фактически не используются или используются, но не все. Например, если мы выделим 30 символов для каждого имени, но имена в среднем будут занимать по 15 символов, то потребление памяти получится в два раза больше, чем нам нужно на самом деле. Или рассмотрим массив rendering : если он использует только 20 000 полигонов, то память для других 20 000 полигонов фактически тратится впустую (т.е. не используется)!
Во-вторых, память для большинства обычных переменных (включая фиксированные массивы) выделяется из специального резервуара памяти — стека. Объем памяти стека в программе, как правило, невелик: в Visual Studio он по умолчанию равен 1МБ. Если вы превысите это значение, то произойдет переполнение стека, и операционная система автоматически завершит выполнение вашей программы.
В Visual Studio это можно проверить, запустив следующий фрагмент кода:
Лимит в 1МБ памяти может быть проблематичным для многих программ, особенно где используется графика.
В-третьих, и самое главное, это может привести к искусственным ограничениям и/или переполнению массива. Что произойдет, если пользователь попытается прочесть 500 записей с диска, но мы выделили память максимум для 400? Либо мы выведем пользователю ошибку, что максимальное количество записей — 400, либо (в худшем случае) выполнится переполнение массива и затем что-то очень нехорошее.
К счастью, эти проблемы легко устраняются с помощью динамического выделения памяти. Динамическое выделение памяти — это способ запроса памяти из операционной системы запущенными программами по мере необходимости. Эта память не выделяется из ограниченной памяти стека программы, а выделяется из гораздо большего хранилища, управляемого операционной системой — кучи. На современных компьютерах размер кучи может составлять гигабайты памяти.
Для динамического выделения памяти одной переменной используется оператор new:
В примере, приведенном выше, мы запрашиваем выделение памяти для целочисленной переменной из операционной системы. Оператор new возвращает указатель, содержащий адрес выделенной памяти.
Для доступа к выделенной памяти создается указатель:
Затем мы можем разыменовать указатель для получения значения:
Вот один из случаев, когда указатели полезны. Без указателя с адресом на только что выделенную память у нас не было бы способа получить доступ к ней.
Как работает динамическое выделение памяти?
На вашем компьютере имеется память (возможно, большая её часть), которая доступна для использования программами. При запуске программы ваша операционная система загружает эту программу в некоторую часть этой памяти. И эта память, используемая вашей программой, разделена на несколько частей, каждая из которых выполняет определенную задачу. Одна часть содержит ваш код, другая используется для выполнения обычных операций (отслеживание вызываемых функций, создание и уничтожение глобальных и локальных переменных и т.д.). Мы поговорим об этом чуть позже. Тем не менее, большая часть доступной памяти компьютера просто находится в ожидании запросов на выделение от программ.
Когда вы динамически выделяете память, то вы просите операционную систему зарезервировать часть этой памяти для использования вашей программой. Если ОС может выполнить этот запрос, то возвращается адрес этой памяти обратно в вашу программу. С этого момента и в дальнейшем ваша программа сможет использовать эту память, как только пожелает. Когда вы уже выполнили с этой памятью всё, что было необходимо, то её нужно вернуть обратно в операционную систему, для распределения между другими запросами.
В отличие от статического или автоматического выделения памяти, программа самостоятельно отвечает за запрос и обратный возврат динамически выделенной памяти.
Освобождение памяти
Когда вы динамически выделяете переменную, то вы также можете её инициализировать посредством прямой инициализации или uniform-инициализации (в С++11):
Когда уже всё, что требовалось, выполнено с динамически выделенной переменной — нужно явно указать для С++ освободить эту память. Для переменных это выполняется с помощью оператора delete:
Оператор delete на самом деле ничего не удаляет. Он просто возвращает память, которая была выделена ранее, обратно в операционную систему. Затем операционная система может переназначить эту память другому приложению (или этому же снова).
Хотя может показаться, что мы удаляем переменную, но это не так! Переменная-указатель по-прежнему имеет ту же область видимости, что и раньше, и ей можно присвоить новое значение, как и любой другой переменной.
Обратите внимание, удаление указателя, не указывающего на динамически выделенную память, может привести к проблемам.
Висячие указатели
Язык C++ не предоставляет никаких гарантий относительно того, что произойдет с содержимым освобожденной памяти или со значением удаляемого указателя. В большинстве случаев, память, возвращаемая операционной системе, будет содержать те же значения, которые были у нее до освобождения, а указатель так и останется указывать на только что освобожденную (удаленную) память.
Указатель, указывающий на освобожденную память, называется висячим указателем. Разыменование или удаление висячего указателя приведет к неожиданным результатам. Рассмотрим следующую программу:
Процесс освобождения памяти может также привести и к созданию нескольких висячих указателей. Рассмотрим следующий пример:
Есть несколько рекомендаций, которые могут здесь помочь:
Во-первых, старайтесь избегать ситуаций, когда несколько указателей указывают на одну и ту же часть выделенной памяти. Если это невозможно, то выясните, какой указатель из всех «владеет» памятью (и отвечает за её удаление), а какие указатели просто получают доступ к ней.
Во-вторых, когда вы удаляете указатель, и, если он не выходит из области видимости сразу же после удаления, то его нужно сделать нулевым, т.е. присвоить значение 0 (или nullptr в С++11). Под «выходом из области видимости сразу же после удаления» имеется в виду, что вы удаляете указатель в самом конце блока, в котором он объявлен.
Правило: Присваивайте удаленным указателям значение 0 (или nullptr в C++11), если они не выходят из области видимости сразу же после удаления.
Оператор new
При запросе памяти из операционной системы в редких случаях она может быть не выделена (т.е. её может и не быть в наличии).
Во многих случаях процесс генерации исключения оператором new (как и сбой программы) нежелателен, поэтому есть альтернативная форма оператора new, которая возвращает нулевой указатель, если память не может быть выделена. Нужно просто добавить константу std::nothrow между ключевым словом new и типом данных:
В примере, приведенном выше, если оператор new не возвратит указатель с динамически выделенной памятью, то возвратится нулевой указатель.
Разыменовывать его также не рекомендуется, так как это приведет к неожиданным результатам (скорее всего, к сбою в программе). Поэтому наилучшей практикой является проверка всех запросов на выделение памяти для обеспечения того, что эти запросы будут выполнены успешно и память выделится:
Поскольку не выделение памяти оператором new происходит крайне редко, то обычно программисты забывают выполнять эту проверку!
Нулевые указатели и динамическое выделение памяти
Нулевые указатели (указатели со значением 0 или nullptr ) особенно полезны в процессе динамического выделения памяти. Их наличие как бы сообщаем нам: «Этому указателю не выделено никакой памяти». А это, в свою очередь, можно использовать для выполнения условного выделения памяти:
Удаление нулевого указателя ни на что не влияет. Таким образом, в следующем нет необходимости:
Вместо этого вы можете просто написать:
Если ptr не является нулевым, то динамически выделенная переменная будет удалена. Если значением указателя является нуль, то ничего не произойдет.
Утечка памяти
Динамически выделенная память не имеет области видимости, т.е. она остается выделенной до тех пор, пока не будет явно освобождена или пока ваша программа не завершит свое выполнение (и операционная система очистит все буфера памяти самостоятельно). Однако указатели, используемые для хранения динамически выделенных адресов памяти, следуют правилам области видимости обычных переменных. Это несоответствие может вызвать интересное поведение, например:
Здесь мы динамически выделяем целочисленную переменную, но никогда не освобождаем память через использование оператора delete. Поскольку указатели следуют всем тем же правилам, что и обычные переменные, то, когда функция завершит свое выполнение, ptr выйдет из области видимости. Поскольку ptr — это единственная переменная, хранящая адрес динамически выделенной целочисленной переменной, то, когда ptr уничтожится, больше не останется указателей на динамически выделенную память. Это означает, что программа «потеряет» адрес динамически выделенной памяти. И в результате эту динамически выделенную целочисленную переменную нельзя будет удалить.
Это называется утечкой памяти. Утечка памяти происходит, когда ваша программа теряет адрес некоторой динамически выделенной части памяти (например, переменной или массива), прежде чем вернуть её обратно в операционную систему. Когда это происходит, то программа уже не может удалить эту динамически выделенную память, поскольку больше не знает, где выделенная память находится. Операционная система также не может использовать эту память, поскольку считается, что она по-прежнему используется вашей программой.
Утечки памяти «съедают» свободную память во время выполнения программы, уменьшая количество доступной памяти не только для этой программы, но и для других программ также. Программы с серьезными проблемами с утечкой памяти могут «съесть» всю доступную память, в результате чего ваш компьютер будет медленнее работать или даже произойдет сбой. Только после того, как выполнение вашей программы завершится, операционная система сможет очистить и вернуть всю память, которая «утекла».
Хотя утечка памяти может возникнуть и из-за того, что указатель выходит из области видимости, возможны и другие способы, которые могут привести к утечкам памяти. Например, если указателю, хранящему адрес динамически выделенной памяти, присвоить другое значение:
Динамическое распределение памяти C: как работает динамическая память
В язык е программирования С можно реализовать три основных способа выделения памяти:
Динамическое выделение памяти в С
Об автоматическом и статическом распределении памяти мы обязательно поговорим в наших следующих статьях, а пока давайте разберемся, что такое динамическое выделение памяти в Си и как оно функционирует.
Статическое и автоматическое выделение памяти имеет 2 общих свойства:
В основной массе компонентов программы этих свойств достаточно, чтобы управлять памятью. Однако проблемы начинаются, когда в программе нужно реализовать пользовательский ввод каких-либо сведений. В этом случае никогда точно не известно, какое количество памяти может понадобиться, пока пользователь не введет какое-либо значение.
Динамическое выделение памяти в С как раз решает подобные проблемы с памятью. Потому что динамическое выделение памяти в Си дает возможность работающим программам давать представление на необходимое количество памяти непосредственно в операционную систему. Такая память не ограничивается количеством стековой памяти, которая сама по себе очень часто сильно ограничена несколькими мегабайтами. Динамическая память «черпается» из памяти, которой управляет операционная, а там уже счет идет на гигабайты.
Как работает динамическое выделение памяти
Когда происходит динамическое выделение памяти, мы фактически «просим» операционную систему воспользоваться свободной областью памяти для нужд нашего программного продукта. Когда «операционка» соглашается с нашей «просьбой», то в ответ выдает адрес выделенной памяти для нужд нашего программного обеспечения. С этого момента наша программа сможет пользоваться выделенной памятью по своему усмотрению. Когда программа завершает свою работу, она «передает» эту память обратно под управление операционной системе.
Как реализовать динамическое выделение памяти в С
Динамическое выделение памяти в С может быть реализовано следующими функциями:
1. malloc(). Общая формула реализации:
#include /* или #include */
void *malloc(size_t size);
2. calloc(). Общая формула реализации:
#include /* или #include */
void *calloc(size_t count, size_t elem_size);
3. realloc(). Общая формула реализации:
#include /* или #include */
void *realloc(void *memory, size_t newSize);
4. free(). Общая формула реализации:
#include /* или #include */
void free(void *memory).
Также динамическое выделение памяти в С можно реализовать при помощи оператора «new»:
int *p = new int; // Здесь не задается начальное значение памяти
int *p = new int(10); // Здесь задается начальное значение памяти
Заключение
Мы будем очень благодарны
если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.