Механизмы работы с кучей

[Aether]

Хочу поинтересоваться, не создавая отдельную тему: malloc(), когда выделяет память делает это кратно страницам или нет. Просто, в первом случае free(), как бы освободит всё чисто, но цена вызова malloc для выделения малых структур данных будет чрезвычайно высока, например, выделяя 1байт 100раз мы уничтожим где-то 409600байт памяти. С другой стороны, если выделение будет идти с созданием какой-то промежуточной структуры, то экономия памяти будет ощутимее, но free() не сможет освободить объём полноценно, и, в итоге, всё превратится в фрагментированную кучу.
Как решается эта задача фактически? Есть ли разные подходы к её решению в разных ОС?

[Dale]

Как решается эта задача фактически? Есть ли разные подходы к её решению в разных ОС?

Управление "кучей" - самая темная сторона языка C (точнее, не самого языка, разумеется, а его стандартной библиотеки). Даже в библиотеках разных компиляторов для одной ОС эти функции могут быть реализованы по-разному. Более того, непредсказуемость скорости их выполнения затрудняет их использование в критичных ко времени отклика приложениях. Например, популярная операционная система реального времени для микроконтроллеров FreeRTOS вовсе отказывается от использования библиотечных malloc() и free() и заменяет собственными аналогами (на самом деле там их целый набор, поскольку ни одна реализация не идеальна).

Хочу поинтересоваться ... : malloc(), когда выделяет память делает это кратно страницам или нет.

В известных мне реализациях - нет. Тем более что логическое адресное пространство зачастую линейно (если не рассматривать аномальные варианты вроде сегментированной памяти 8086 или совсем уж приподвывернутого страничного доступа к памяти 8051 или PIC), и в этом нет реальной необходимости. Поэтому на "обрезки" много памяти не тратится, максимум - на выравнивание блока по границе слова.

free() не сможет освободить объём полноценно, и, в итоге, всё превратится в фрагментированную кучу.

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

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

P.S. Кстати, не вижу никакого криминала, если в подобных случаях создавать новые темы. Тонкости работы с "кучей" IMHO гораздо интереснее первоначального вопроса темы, а найти их в данном случае будет гораздо труднее.

[Dale]

К названию новой темы есть пожелания?

Пожалуй, в данном состоянии "тонкости" - это перебор, пока рассмотрели скорее с высоты птичьего помлета. Название "Механизмы работы с кучей" представляется лично мне более уместным. Может, если будет дальнейший интерес к теме, копнем глубже, тема в общем довольно интересна узкому кругу сишников.

[Aether]

Если я понял правильно, реализация конкретного вида механизма выделения памяти лежит на самой программе, а не на ОС? И можно воздействовать на этот механизм.
Я как-то размышлял на эту тему, и, в голове рисуется вот что: если производить выделение блоками разной размерности, то организовать таблицу размещения этих блоков не совсем рационально, поскольку она будет также динамической и рано или поздно столкнётся с проблемой собственного роста и постоянного перемещения. Более целесообразно снабдить каждый блок небольшой шапкой, состоящей из трёх чисел:
1. Указателя на начало предыдущего блока. (BP_Prev)
2. Указателя на начало следующего блока. (BP_Next)
3. Размер текущего блока. (BP_Size)
Плюс сам блок данных, и указатель, возвращаемый программе, должен указывать именно сюда - точнее на начало этой зоны. (BP_Data)
Помимо этого в программе должна быть определены две статические переменные:
1. Счётчик того, сколько памяти было взято у ОС.
2. Счётчик свободной памяти.
В момент, когда программа загружается в оперативную память необходимо вычислить адрес начала динамической памяти (DM_Start) и заполнить наши две переменные и сразу же выделить "нулевой блок". Этот блок формирует стартовую запись:
Start.BP_Prev = 0 - нету предыдущего блока,
Start.BP_Next = 0 - нету выделенных блоков,
Start.BP_Size = 12 (для 32 бит системы, каждое число по 4 байта, их три) - текущий размер.
Указатель на эту структуру (Start.p) будет равен (DM_Start+12).
Теперь, предположим, нам нужно выделить место под структуру А, для этого к вычисленному размеру А (пусть будет 50) прибавляем 12. Проверяем на наличие свободного пространства и начинаем последовательно идти по шапкам BP - пока шапка одна идти придётся не долго.
Итак, образуется структура:
A.BP_Prev = Start.p;
A.BP_Next = 0; - этот блок стал последним;
A.BP_Size = 62;
A.p = Start.p + sizeof (A) = Start.p + 50;
В предыдущем блоке изменяем параметр Start.Next = A.p;
Выделяя последовательно структуры B, С, D... поступаем похожим образом. И программист получает свой законный указатель (p) на начало области данных любой из структур не вникая во внутреннее устройство. В свою очередь значения p-4, p-8 и p-12 указывающие на служебные конструкции могут быть легко вычислены.
Если необходимо освободить структуру B, то, согласно алгоритму, переписываются служебные записи смежных с ним блоков и образуется окно, координаты и размер которого легко можно вычислить. Во время выделения новых блоков процедура должна сканировать весь ряд служебных записей блоков. При таких ошибках программиста, как вызов free() с указанием неправильного указателя или запись в служебную зону следующего блока при превышении текущего приведёт к полному краху.
Кстати, стратегии видится в основном две: выделять с расширением вглубь адресного пространства, пока не дойдём до финиша, а только затем будем либо дефрагментировать, либо пытаться вести запись в окна. Это даст прирост к скорости ценою памяти, но, когда адресное пространство будет исчерпано произойдёт резкое снижение скорости. Второе: сразу вести поиск окон - на деле данная стратегия приведёт к увеличению количества этих самых окон с одновременным их уменьшением. Момент падения скорости можно оттянуть, но не получится избежать фундаментально.
Выводы:
1) если есть возможность вместо выделения группы блоков выделить необходимый объём одним разом, то это лучше при любом раскладе.
2) перезапуск приложения при достижении определённой степени фрагментации может ускорить выполнение задачи, нежели продолжать работать за один приём.
3) часто требуется выделение динамической области для использования в роли статической (экономия размера исполняемого файла - вынос переменных не требующих инициализации в кучу). Так вот, лучше это сделать вначале программы сразу всем объёмом, чтобы эта область не участвовала в процессе дробления. Заодно, возможно организовать процесс перезагрузки истинно динамических данных для дефрагментации.

[Dale]

Если я понял правильно, реализация конкретного вида механизма выделения памяти лежит на самой программе, а не на ОС? И можно воздействовать на этот механизм.

И то, и другое вместе.

Если 32-разрядная программа может теоретически адресовать 4Gb оперативной памяти, это не значит, что она реально обладает таким ресурсом. Чтобы задействовать какую-то область памяти, процесс сначала должен успешно запросить ее у ОС (если она вообще есть на данной системе).

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

Что касается структур данных конкретных реализаций кучи - мне совсем недавно попадалась весьма толковая документация по ее организации в стандартной библиотеке С. Вот только не могу вспомнить, где именно, поскольку читать приходится очень много, а пометок я для себя не оставил за практической ненадобностью - все равно рытье кучи в обход библиотечных функций ни к чему хорошему не приведет, а тратить время на изучение подобных вещей только ради чистого любопытства в данный момент позволить себе не могу.

В одной из статей Андрея Курница, посвященных работе с FreeRTOS, есть глава о механизмах распределения памяти в этой ОС с учетом ее специфики. Если интересно, посмотрите http://www.kit-e.ru/assets/files/pdf/2011_05_97.pdf , раздел "Схемы выделения памяти". Не слишком подробно, но самое общее представление о проблеме дает.