Как работает malloc?

Возможный дубликат:
Как работают free и malloc в C?

Рассмотрим сценарий, в котором я должен выделить около 20 байт памяти через malloc. Для того чтобы функция call to malloc () была успешной, должны ли 20 байтов быть доступны в памяти или могут быть разбросаны? Например, в приведенном выше случае, если имеется 4 или 5 кусков по 10 байт, будет ли работать malloc? Или это конкретная ОС или специфическая для компилятора?

Вопрос неправильный.

В типичной ОС существуют концепции виртуальной памяти и физической памяти.

Физическая память существует, как правило, в блоках 4kb, виртуальная память аналогична.

Каждый процесс имеет виртуальную память – для каждого процесса ОС представляет то, что представляется полностью адресуемым диапазоном памяти. Таким образом, на 32-битной машине каждый процесс «думает» имеет 4 ГБ свободной памяти.

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

Таким образом, вы все равно можете столкнуться с fragmentацией виртуальной памяти. Здесь процесс запрашивает блок памяти, а в этой конкретной виртуальной карте памяти нет блока условной виртуальной памяти, чтобы запрос мог быть удовлетворен.

Эта проблема – проблема, о которой вы думаете.

При вызове malloc удастся вернуть логически непрерывный блок памяти из памяти вашей памяти HEAP, равный требуемому размеру, или с ошибкой NULL. «Логически смежный» означает, что с помощью malloc этого типа:

 int *ip; /* Nothing yet allocated (other than the size of a pointer... */ int ar[100]; /* 100 ints on the STACK */ ip = (int *)malloc(sizeof ar); /* if that succeeds, 100 ints on the HEAP */ 

выделяет пространство для 100 ints в вашей ОС на HEAP и возвращает либо NULL, либо указатель. Отдельно массив ar выделяется на STACK. Каждый массив будет располагаться со всеми логически рядом друг с другом, по крайней мере, насколько ваша программа знает. Если они не были рядом друг с другом, вы не смогли бы адресовать эти блоки как массивы с помощью обозначения array[offset] или с помощью арифметики указателя.

Затем вы можете получить доступ к блокам памяти STACK или HEAP с доступом к массиву или с помощью указателя так же, как это:

 ip[2]=22; /* the second element of ip[] is '22' */ *(ar+33)=3333; /* the 33 element of ar is '3333' */ i=*(ip+2); /* assign using pointers */ j=ar[33]; /* assign using array offsets */ 

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

За кулисами ваша ОС может перемещать другие блоки памяти, которые могут перемещаться, использовать виртуальную память, обменивать другие элементы в виртуальную память и т. Д., Чтобы увеличить HEAP, выделенный для вашей программы. Malloc может быть очень быстрым или очень дорогостоящим звонком – в зависимости от того, что еще происходит в этой системе, и пространства HEAP, выделенного для вашей программы.

HEAP-память (эта часть, к которой обращаются динамические системные вызовы в C), потенциально подвержена fragmentации. Предположим, вы выделили количество 20-байтовых блоков, где память становится недостаточной. Теперь изображение, которое вы освобождаете каждый блок блоков. У вас будет сильно fragmentированная память, так как блоки, выделенные malloc не могут быть перемещены, если они влияют на указатель, который программа использует для доступа к блоку. (Его можно перемещать прозрачно, но не рассчитывайте на то, что он эффективен.)

Если вы делаете много вызовов для HEAP-памяти, подумайте об изменении своей логики, чтобы использовать realloc для увеличения и сокращения памяти по мере необходимости. Большая ‘gotcha’ с realloc указатель на ваши существующие данные может измениться, поэтому используйте только 1 указатель на него. Realloc позволяет ОС перемещать данные по мере необходимости, чтобы лучше соответствовать тому, что доступно в HEAP. Вы (в основном) избегаете возможности fragmentации памяти таким образом.

Для быстрых блоков по 20 байт рассмотрите использование STACK. Для этого он и есть. Посмотрите на это сообщение SO, чтобы увидеть характеристики STACK vs HEAP.

Прочтите руководство C calloc, malloc, realloc, бесплатно для получения дополнительной информации.

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

На более низком уровне ОС будет делать что-то вроде того, что kotlinski или Blank Xavier описал в своих соответствующих ответах.

Из раздела 7.2.20 стандарта ISO / IEC 9899-1999 C :

Указатель возвращается, если успешно выполняется выделение (по calloc , realloc или malloc ), поэтому его можно назначить указателю на любой тип объекта, а затем использовать для доступа к такому объекту или массиву таких объектов в пространстве (пока пространство явно не освобождено).

Это не так явно, но в параграфе упоминается «доступ к массиву таких объектов», а в стандарте C массивы:

Тип массива описывает смежно выделенный непустой набор объектов с конкретным типом объекта-члена, называемый типом элемента. (из п. 6.2.5 )

Также обратите внимание, что последующие вызовы calloc , realloc и malloc не гарантируют соприкосновения или упорядочения памяти (с уже выделенными другими блоками памяти).

Этот пункт также указан в §7.20.3 .

Порядок и смежность хранилища, выделенные последовательными вызовами функций calloc , malloc и realloc не определены.

Это специфичная платформа. Для ваших глаз, на программном уровне, он всегда будет представлен в виде malloc: ed 20 смежных байтов. Но на некоторых платформах, например, с выгружаемой памятью, эти байты не обязательно должны быть смежными, когда дело доходит до фактического оборудования – оно будет выглядеть так.

Память должна быть непрерывной – то, о чем вы упоминаете, обычно упоминается как fragmentация памяти и представляет собой реальную проблему для приложений, часто приобретающих и освобождающих память.

Специфическая ОС.

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

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

Из стандарта ISO C99 :

7.20.3 Функции управления памятью
Порядок и смежность хранилища, выделенные последовательными вызовами функций calloc, malloc и realloc, не определены. Указатель возвращается, если выделение успешно выполняется соответствующим образом, чтобы его можно было назначить указателю на любой тип объекта, а затем использовать для доступа к такому объекту или массиву таких объектов в выделенном пространстве (пока пространство явно не освобождено) , Время жизни выделенного объекта простирается от выделения до освобождения. Каждое такое распределение должно давать указатель на объект, не связанный с каким-либо другим объектом. Указатель возвращает точки на начало (самый младший адрес байта) выделенного пространства. Если пространство не может быть выделено, возвращается нулевой указатель. Если размер запрошенного пространства равен нулю, поведение определяется реализацией: возвращается нулевой указатель, или поведение такое, как если бы размер был некотором ненулевым значением, за исключением того, что возвращаемый указатель не должен использоваться для доступа к объекту ,

7.20.3.3 Функция malloc
Функция malloc выделяет пространство для объекта, размер которого задается по size и значение которого неопределенно.

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

Скорее всего, это не сработает. malloc не может переупорядочить уже выделенную память, поэтому он не может создать непрерывный свободный блок из 20 байтов. Он может только попросить ОС получить еще одну страницу памяти, из которой она может нарезать 20 байтов + заголовок.