Что происходит, когда есть запрос на блок памяти, который не является степенью 2?

Question

Предположим, мы выполняем запрос malloc для блока памяти размером n, где 2 ^ k! = N для k> 0.Malloc возвращает нам место для этого запрошенного блока памяти, но как обрабатывается оставшийся буфер со страницы.Я читаю Страницы, как правило, блоки памяти, которые имеют степени двух.

Вики заявляет следующее:

 Like any method of memory allocation, the heap will become fragmented; that is,
 there will be sections of used and unused memory in the allocated 
 space on the heap. A good allocator will attempt to find an unused area
 of already allocated memory to use before resorting to expanding the heap.

Так что мой вопрос, как это отслеживается?: Как отслеживается неиспользуемая память при использовании malloc?

Answer 1

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

Это обзор некоторых простых возможностей: http://www.osdcom.info/content/view/31/39/

Эта запись в Википедии имеет несколько интересных ссылок, включая приведенную выше: http://en.wikipedia.org/wiki/Dynamic_memory_allocation#Implementations

В качестве последнего замечания, поиск "реализации malloc" приводит к куче (каламбур) ценных ссылок.

Answer 2

Стандартный распределитель памяти в стиле BSD в основном работает так:

• Хранит связанный список предварительно выделенных блоков памяти для размеров 2 ^ k для k <= 12 (например). </li>
• В действительности каждый список для данного k состоит из блоков памяти из разных областей , см. Ниже.
• Запрос malloc для n байтов обслуживается путем вычисления n ', ближайшего 2 ^ k> = n, затем поиска первой области в списке для k, а затем возврата первого свободного блока в свободном списке для данной области .
• Когда нет заранее выделенного блока памяти для размера 2 ^ k, выделяется область , область, представляющая собой некоторый больший фрагмент непрерывной памяти, скажем, 4 КБ памяти. Этот фрагмент памяти затем разбивается на части размером 2 ^ k байтов. В начале области непрерывной памяти находится информация бухгалтерского учета, например, где найти связанный список свободных блоков в этой области. Также можно использовать растровое изображение, но связанный список обычно имеет лучшее поведение в кэше (вы хотите, чтобы следующий выделенный блок возвращал память, которая уже находится в кэше).
• Причина использования областей заключается в том, что free (ptr) может быть эффективно реализован. В этом примере ptr & 0xfffff000 указывает на начало области , которая содержит структуры учета и позволяет связать блок памяти обратно в область.
• Распределитель BSD будет тратить пространство, всегда возвращая блок памяти размером 2 ^ k, но он может повторно использовать память блока, чтобы сохранить свободный список, что является хорошим свойством. Кроме того, распределение происходит невероятно быстро.

Модификации вышеуказанной общей идеи включают в себя:

• Использование анонимного mmap для больших выделений. Это переносит работу на ядро ​​для обработки больших malloc и в таких случаях не тратит много памяти.
• В версии malloc для GNU есть особые случаи для двухслойных блоков. В распределителе BSD нет ничего, что требовало бы возврата 2 ^ k блоков памяти, только наличие заранее определенных размеров сегментов. Распределитель GNU имеет больше сегментов и, следовательно, тратит меньше места.
• Разделение памяти между потоками - сложная тема. Конфликт блокировок во время выделения является важным фактором, поэтому в распределителе GNU, например, с нетерпением будут созданы дополнительные областей для разных потоков для данного размера сегмента, если он когда-либо столкнется с блокировкой-конфликтом во время выделения.

Answer 3

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

Если это из-за проблем с производительностью, попробуйте сравнить его и посмотреть, что произойдет.