C - Создайте свою собственную функцию free ()

Question

Сегодня я появился на собеседовании, и интервьюер спросил меня:

1. Скажите мне шагов как вы будете разрабатывать свою собственную функцию free( ) дляосвободить выделенную память.
2. Как она может быть более эффективной, чем функция C по умолчанию free()?Что вы можете сделать вывод?

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

Как вы думаете, ребята?

---

РЕДАКТИРОВАТЬ: Так как нам нужно знать о том, как работает malloc(), вы можете сказать мне шаги, чтобы написать нашсобственная malloc() функция

Answer 1

Это на самом деле довольно расплывчатый вопрос, и, вероятно, поэтому вы запутались.Имеет ли он ввиду, учитывая существующую реализацию malloc, как бы вы попытались разработать более эффективный способ освобождения базовой памяти?Или он ожидал, что вы начнете обсуждать различные реализации malloc, их преимущества и проблемы?Он ожидал, что вы узнаете, как работает виртуальная память в архитектуре x86?

Кроме того, под более эффективным он подразумевает более эффективное использование пространства или более эффективное время?Должен ли free () быть детерминированным?Нужно ли возвращать ОС столько памяти, сколько возможно, потому что она находится в среде с низким объемом памяти и многозадачностью?Каковы наши критерии здесь?

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

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

Ознакомьтесь с этой статьей IBM DeveloperWorks под названием "Управление внутренней памятью" для начинающих.

Но прежде чем вы сможете написать свой собственныйmalloc / free, сначала нужно выделить память для выделения / освобождения.К сожалению, в защищенном режиме ОС вы не можете напрямую обращаться к памяти на машине.Так как вы это получили?

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

Ядро обычно предоставляет системные вызовы, которые позволяют вам отображать дополнительную память для вашего процесса.В старых ОС UNIX это обычно был brk / sbrk для увеличения кучи памяти на краю вашего процесса или сокращения ее, но многие системы также предоставляют mmap / munmap для простого отображения большого блока кучи памяти. Это только когда выиметь доступ к большому, непрерывно выглядящему блоку памяти, который нужен malloc / free для управления им.

Как только у вашего процесса есть какая-то кучная память, доступная для него, все дело в разбиении его на куски, каждый из которых содержитего собственная мета-информация о его размере и положении и о том, распределяется ли она, а затем управляет этими порциями.Простой список структур, каждое из которых содержит несколько полей для метаинформации и большой массив байтов, может сработать, и в этом случае malloc должен проходить по списку до тех пор, пока не найдет достаточно большой нераспределенный фрагмент (или блоки, которые он может объединить), изатем отобразите в памяти больше, если он не может найти достаточно большой кусок.Найдя чанк, вы просто возвращаете указатель на данные.Затем free () может использовать этот указатель для обратного возврата нескольких байтов к полям-членам, которые существуют в структуре, которые он затем может изменить (т. е. пометить chunk.allocated = false;).Если в конце вашего списка достаточно незанятых блоков, вы даже можете удалить их из списка и удалить из памяти или сжать эту память из кучи вашего процесса.

Это действительно простой способ реализации malloc. Как вы можете себе представить, есть много возможных способов разбить вашу память на куски и затем управлять этими кусками. Есть так много способов, как есть структуры данных и алгоритмы. Все они также предназначены для различных целей, например, для ограничения фрагментации из-за небольших выделенных фрагментов, смешанных с небольшими нераспределенными фрагментами, или для обеспечения того, чтобы malloc и free выполнялись быстро (или иногда даже медленнее, но предсказуемо медленно). Есть dlmalloc , ptmalloc , jemalloc , malloc Hoard и многие другие, и многие из них довольно малы и кратки, так что не бойтесь читать их. Если я правильно помню, «Язык программирования C» Кернигана и Ричи даже использует простую реализацию malloc в качестве одного из своих примеров.

Answer 2

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

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

Answer 3

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

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

Answer 4

Скажите, как вы будете создавать собственную функцию free () для освобождения выделенной памяти.

#include <stdlib.h>
#undef free
#define free(X) my_free(X)

inline void my_free(void *ptr) { }

Как она может быть более эффективной, чем функция free (), используемая по умолчанию в C?

Это очень быстро, требует ноль машинных циклов.Это также устраняет ошибки использования после освобождения.Это очень полезная функция free для использования в программах, которые создаются как краткосрочные пакетные процессы;его можно успешно использовать в некоторых производственных ситуациях.

Что вы можете сделать?

Я действительно хочу эту работу, но в другой компании.

Answer 5

Шаблоны использования памяти могут быть фактором.Реализация по умолчанию free не может предположить ничего о том, как часто вы выделяете / освобождаете и какие размеры вы выделяете при этом.

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

РЕДАКТИРОВАТЬ: как отмечалось DSP, имеет смысл только проектировать free и malloc вместе.Поэтому первым делом нужно выяснить, как реализовано malloc.

Answer 6

Знание работы malloc() необходимо для реализации free(). Вы можете найти реализацию malloc() и free(), используя системный вызов sbrk() в K & R Язык программирования C Глава 8, Раздел 8.7 «Пример - распределитель памяти», с. 185-189. .

Answer 7

Существует архитектура, которой должны придерживаться malloc и free - по сути, классовая архитектура, позволяющая сосуществовать различным стратегиям.Тогда исполняемая версия free соответствует используемой версии malloc.

Однако я не уверен, как часто наблюдается эта архитектура.

Answer 8

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