Каковы альтернативы malloc () в C?

Question

Я пишу C для платы MPC 555 и должен выяснить, как распределить динамическую память без использования malloc.

Answer 1

Обычно malloc() реализуется в Unix с использованием <a href="http://www.manpagez.com/man/2/sbrk/" rel="nofollow noreferrer">sbrk()</a> или <a href="http://www.manpagez.com/man/2/mmap/" rel="nofollow noreferrer">mmap()</a>. (Если вы используете последний, вы хотите использовать флаг MAP_ANON.)

Если вы ориентируетесь на Windows, <a href="http://msdn.microsoft.com/en-us/library/aa366887(VS.85).aspx" rel="nofollow noreferrer">VirtualAlloc</a> может помочь. (Более или менее функционально эквивалентно анонимному mmap().)

Обновление: Не осознавал, что вы не работали под полной ОС, у меня почему-то создалось впечатление, что это может быть домашнее задание, выполняемое поверх системы Unix или что-то в этом роде ...

Если вы выполняете встроенную работу и у вас нет malloc(), я думаю, что вы должны найти некоторый диапазон памяти, в который вы можете писать, и написать свой malloc(). Или возьми чужой.

В значительной степени стандартный, от которого все заимствуют, был написан Дугом Ли в SUNY Oswego . Например, Malloc Malloc основан на этом. См .: malloc.c , malloc.h .

Answer 2

Возможно, вы захотите проверить Менеджер встроенной памяти Ральфа Хемпеля .

Answer 3

Если ваша среда выполнения не поддерживает malloc, вы можете найти malloc с открытым исходным кодом и настроить его для самостоятельного управления частью памяти.

Answer 4

Напишите свой собственный. Поскольку ваш распределитель, вероятно, будет специализирован для нескольких типов объектов, я рекомендую схему Quick Fit , разработанную Биллом Вульфом и Чарльзом Уинстоком. (Мне не удалось найти бесплатную копию этой статьи, но многие люди имеют доступ к цифровой библиотеке ACM.) Бумага короткая, легко читаемая и хорошо подходит для вашей проблемы.

Если вам понадобится более общий распределитель, лучшее руководство, которое я нашел по теме программирования на машинах с фиксированной памятью, - это книга Дональда Кнута Искусство компьютерного программирования , Том 1. Если вам нужны примеры, вы можете найти хорошие примеры в эпической трактовке Дона с исходным кодом TeX, TeX: Программа .

И наконец, учебник для студентов бакалавриата Брайанта и О'Халларона довольно дорогой, но он претерпевает реализацию malloc в мучительных деталях.

Answer 5

Ответ действительно зависит от того, почему вам может потребоваться динамическое выделение памяти. Что делает система, которая должна распределять память, но не может использовать статический буфер? Ответ на этот вопрос поможет вам в управлении памятью. Оттуда вы можете определить, какую структуру данных вы хотите использовать для управления вашей памятью.

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

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

В сборках "отладка" было два буфера сканирования, которые были защищены с помощью защиты виртуальной памяти во время чередующихся строк сканирования. Этот метод обнаруживает устаревшие указатели, используемые с одной строки сканирования на следующую.

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

Вашему приложению может потребоваться другая структура данных для отслеживания вашего свободного хранилища. Какова ваша заявка?

Answer 6

Вы должны объяснить, почему вы не можете использовать malloc(), поскольку могут быть разные решения по разным причинам, и есть несколько причин, по которым оно может быть запрещено или недоступно в небольших / встроенных системах:

• беспокойство по поводу фрагментации памяти. В этом случае набор подпрограмм, выделяющих блоки памяти фиксированного размера для одного или нескольких пулов памяти, может быть решением.
• среда выполнения не обеспечивает malloc() - я думаю, что большинство современных наборов инструментов для встраиваемых систем действительно обеспечивают какой-либо способ связывания в реализации malloc(), но, возможно, вы используете тот, который по каким-то причинам не дает. В этом случае, использование общественного домена Дуга Ли malloc может быть хорошим выбором, но оно может быть слишком большим для вашей системы (я не знаком с MPC 555 в верхней части моей головы). Если это так, может быть в порядке очень простое пользовательское средство malloc(). Это не так сложно написать, но убедитесь, что вы тестируете модуль, потому что также легко получить неправильные детали. Например, у меня есть набор очень маленьких подпрограмм, которые используют стратегию выделения памяти, используя блоки из свободного списка (распределитель может быть настроен во время компиляции для первого, наилучшего или последнего соответствия). Я даю ему массив char при инициализации, и последующие вызовы выделения будут расщеплять свободные блоки по мере необходимости. Это далеко не так сложно, как у Леи malloc(), но она чертовски мала, поэтому для простого использования она подойдет.
• многие встроенные проекты запрещают использование динамического выделения памяти - в этом случае вам придется жить со статически распределенными структурами

Answer 7

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

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

Answer 8

Напишите свой собственный. Предварительно выделите большой кусок статической оперативной памяти, затем напишите некоторые функции, чтобы захватить и освободить ее. Это дух того, что делает malloc(), за исключением того, что он просит ОС динамически выделять и освобождать страницы памяти.

Существует множество способов отслеживания того, что выделено, а что нет (растровые изображения, списки использованных / свободных ссылок, двоичные деревья и т. Д.). Вы сможете найти много ссылок с несколькими вариантами поиска в Google.

Answer 9

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

Answer 10

Если библиотека, поставляемая с вашим компилятором, не предоставляет malloc, то она, вероятно, не имеет понятия кучи.

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

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

K & R, например, включает простую реализацию malloc.