Память кучи и распределение плиты

Question

Я смущен относительно heap и free list. У меня есть несколько вопросов, и у меня есть собственное понимание того, как работает malloc на C. Пожалуйста, исправьте меня, если я ошибаюсь.

• Является ли память кучи организована как связанный список (свободный список) данных блоков?
• Есть ли разница между памятью кучи и свободным списком?

Мое понимание распределения памяти (открыто для улучшения): - Когда мы называем таНос, он выделяет память в куче, и он делает это, выбирая блок данных подходящего размера из free list, верно?

Когда определенный блок памяти возвращается malloc, он удаляется из бесплатного списка, а физический адрес этого блока памяти обновляется в таблице страниц.

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

Таким образом, вся куча является свободным списком (связанным списком свободных блоков) + выделенными блоками данных.

Это всеобъемлющая картина распределения хранилища?

EDIT: С Linux Kernel Development (Robert Love) Глава по управлению памятью, распределения Slab

«Свободный список содержит блок доступен, уже выделены, данные, структуры Когда код требует. новый экземпляр структуры данных, он может захватить одну из структур из бесплатного списка, а не выделять достаточный объем памяти и настроить его для структуры данных. Позже, когда структура данных больше не нужна, возвращается в бесплатный список вместо dealloca Тед. В этом смысле, в свободный список действует как объект кэша, кэширование часто используемый тип объекта «.

Free-лист упоминается как„блок доступной, выделенной структуры данных.“

• Как это выделяется, когда он находится в свободном списке?
• И как возвращается блок памяти в свободный список _ не _ то же самое, что и освобождение этого блока?
• Как распределение горбыль отличается от распределения памяти

Answer 1

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

malloc() взаимодействует с ядром через системный вызов brk(), который просит ядро ​​выделить больше страниц для процесса или выслать страницы обратно в ядро. Таким образом, существуют два уровня распределения памяти:

• Ядро выделяет страницы для процесса, что делает эти страницы недоступными для использования другими процессами. С точки зрения ядра страницы могут быть расположены где угодно, а их местоположения отслеживаются таблицей страниц, но с точки зрения процесса это непрерывное виртуальное адресное пространство. «Программный разрыв», который обрабатывает brk(), является границей между адресами, которые ядро ​​позволит вам получить доступ (поскольку они соответствуют выделенным страницам) и адресам, которые вызовут ошибку сегментации, если вы попытаетесь получить к ним доступ.
• malloc() выделяет часть переменного размера сегмента данных программы для использования программой. Когда в текущем размере сегмента данных недостаточно свободного места, он использует brk() для получения большего количества страниц из ядра, что делает сегмент данных более крупным. Когда он обнаруживает, что какое-то место в конце сегмента данных не используется, он использует brk(), чтобы вернуть неиспользуемые страницы в ядро, делая сегмент данных меньше.

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

Ваше описание того, как работает бесплатный список, звучит правильно для меня, хотя я не знаю, как реализованы распределители памяти. Но цитируемая вами цитата из Robert Love звучит так, будто речь идет о распределении памяти в ядре Linux, которая не связана с распределением памяти malloc() в рамках процесса пользовательского пространства. Такой бесплатный список, вероятно, работает по-другому.

Answer 2

Первое, что вы хотите сделать, - это различие между ядром и распределением программ. Как и @Wyzard, malloc использует brk (sbrk, а иногда и mmap), чтобы получить больше страниц из ядра. Мое понимание malloc не очень хорошее, но оно отслеживает то, что вы можете назвать ареной. Он обеспечивает доступ к памяти и делает правильные системные вызовы для распределения памяти по мере необходимости.

Бесплатный список - это один из способов управления памятью. Вызов mmap или brk каждый раз, когда вам требуется больше памяти из ядра, работает медленно и неэффективно. Оба из них потребуют переключения контекста в режим ядра и будут выделять структуры данных для отслеживания того, какой процесс владеет памятью. Свободный список на уровне пользователя - это оптимизация, которая не требует постоянного возврата и возврата памяти в ядро. Цель пользовательской программы - выполнять свою работу, а не ждать, пока ядро ​​выполнит свою работу.

Теперь, чтобы ответить на ваши другие вопросы:

• Как она выделяется, когда она находится в свободном списке?

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

• И как возвращается блок памяти в свободный список не такой же, как deallocating этот блок?

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

• Как распределение плиты отличается от распределения хранилища?

Это начало получить другую область (которую я не очень хорошо знаком). Распределитель slab - это один из способов, которым ядро ​​управляет распределением памяти. Из того, что я видел, плита пытается группировать распределения в разные размеры и имеет пул страниц для удовлетворения этих запросов. Я полагаю, что общие архитектуры x86 позволят распределять непрерывную физическую память в два раза с 16 до 4 МБ (хотя я на 64-битной машине). Я считаю, что существует определенная концепция бесплатного списка на этом уровне, а также способы эффективного обновления или сокращения размера распределения, чтобы обеспечить различные системные потребности.

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

Answer 3

Здесь вы имеете в виду двух разных распределителей,

1. Buddy система Распределитель, используется для выделения страниц зоны, использует free_list для хранения свободных страниц, выделить их, после освобождения, если это возможно объединить их обратно один большой смежный размер страницы более высокого порядка.
2. Slab allocator, который работает с уже выделенными структурами данных, такими как keme_cache, вызовы kmalloc.

см. Heap Memory in C Programming для кучи.

Для программы c в пользовательском пространстве у нас есть куча памяти в call_stack, где происходит malloc. Это отмечено _break, которое продвигается sbrk(), когда требуется больше памяти.

В ядре Linux каждый процесс имеет task_struct, который имеет свой собственный стек и указатель на список используемых им страниц.