Управление непрерывной порцией памяти без Malloc / New или Free / Delete
Как можно было бы создать собственный MemoryManager для управления данным непрерывным портом памяти без помощи других менеджеров памяти (таких как Malloc / New) в C ++?
Вот еще немного контекста:
MemManager::MemManager(void* memory, unsigned char totalsize)
{
Memory = memory;
MemSize = totalsize;
}
Мне нужно иметь возможность выделять и освобождать блоки этой непрерывной памяти, используя MemManager. Конструктор задает общий размер фрагмента в байтах.
Функция Allocate должна занимать объем памяти, требуемый в байтах, и возвращать указатель на начало этого блока памяти. Если памяти не осталось, возвращается нулевой указатель.
Функция Deallocate должна взять указатель на блок памяти, который должен быть освобожден, и вернуть его MemManager для будущего использования.
Обратите внимание на следующие ограничения:
-Помимо части памяти, предоставленной ему, MemManager не может использовать ЛЮБУЮ динамическую память
-Как изначально указано, MemManager НЕ МОЖЕТ использовать другие менеджеры памяти для выполнения своих функций, в том числе new / malloc и delete / free.
Я уже получил этот вопрос на нескольких собеседованиях, но даже часы исследований в Интернете не помогли мне, и я терпел неудачу каждый раз. Я нашел похожие реализации, но все они использовали malloc / new или были общего назначения и запрашивали память у ОС, что мне запрещено делать.
Обратите внимание, что мне удобно использовать malloc / new и free / delete, и у меня мало проблем с ними.
Я пробовал реализации, которые используют объекты узлов способом LinkedList, которые указывают на выделенный блок памяти и указывают, сколько байтов было использовано. Тем не менее, с этими реализациями мне всегда приходилось создавать новые узлы в стеке и вставлять их в список, но как только они выходили из области видимости, вся программа перестала работать, так как адреса и размеры памяти были потеряны.
Если у кого-то есть идея, как реализовать что-то подобное, я был бы очень признателен. Заранее спасибо!
РЕДАКТИРОВАТЬ: я забыл указать это непосредственно в моем исходном сообщении, но объекты, выделенные с помощью этого MemManager, могут быть разных размеров.
РЕДАКТИРОВАТЬ 2: Я закончил с использованием однородных блоков памяти, которые на самом деле было очень просто реализовать благодаря информации, предоставленной ответами ниже. Точные правила, касающиеся самой реализации, не были указаны, поэтому я разделил каждый блок на 8 байтов. Если бы пользователь запросил более 8 байт, я бы не смог его дать, но если бы пользователь запросил менее 8 байт (но> 0), я бы выделил дополнительную память. Если объем передаваемой памяти не делится на 8, то в конце будет потеряна память, что, я полагаю, намного лучше, чем использование большего количества памяти, чем вам дано.
Решение
Я пробовал реализации, которые используют объекты узлов в LinkedList
мода, которая указывает на выделенный блок памяти и указывает, сколько
байты были использованы. Тем не менее, с этими реализациями я всегда был
вынуждены создавать новые узлы в стеке и вставлять их в
список, но как только они вышли из области видимости, вся программа сломалась
так как адреса и размеры памяти были потеряны.
Вы на правильном пути. Вы можете встроить узел LinkedList в блок памяти, который вы получили с помощью reinterpret_cast<>. Поскольку вам разрешено хранить переменные в диспетчере памяти, пока вы не распределяете память динамически, вы можете отслеживать начало списка с помощью переменной-члена. Возможно, вам придется обратить особое внимание на размер объекта (все ли объекты имеют одинаковый размер? Размер объекта больше размера вашего узла связанного списка?)
Предполагая, что ответы на предыдущие вопросы верны, вы можете обработать блок памяти и разделить его на более мелкие куски размером с объект, используя вспомогательный связанный список, который отслеживает свободные узлы. Ваша свободная структура узла будет что-то вроде
struct FreeListNode
{
FreeListNode* Next;
};
При распределении все, что вам нужно сделать, это удалить головной узел из списка свободных и вернуть его. Разблокирование — это просто вставка освобожденного блока памяти в свободный список. Разделение блока памяти — это просто цикл:
// static_cast only needed if constructor takes a void pointer; can't perform pointer arithmetic on void*
char* memoryEnd = static_cast<char*>(memory) + totalSize;
for (char* blockStart = block; blockStart < memoryEnd; blockStart += objectSize)
{
FreeListNode* freeNode = reinterpret_cast<FreeListNode*>(blockStart);
freeNode->Next = freeListHead;
freeListHead = freeNode;
}
Как вы упомянули, функция Allocate принимает размер объекта, приведенное выше необходимо изменить для хранения метаданных. Вы можете сделать это, включив размер свободного блока в данные узла свободного списка. Это устраняет необходимость разделения исходного блока, но создает сложности в Allocate () и Deallocate (). Вам также нужно будет беспокоиться о фрагментации памяти, потому что если у вас нет свободного блока с достаточным объемом памяти для хранения запрошенного объема, вы ничего не можете сделать, кроме как потерпеть неудачу при выделении. Пара алгоритмов Allocate () может быть:
1) Просто верните первый доступный блок, достаточно большой для удержания запроса, обновив свободный блок по мере необходимости. Это O (n) с точки зрения поиска в свободном списке, но может не потребоваться поиск большого количества свободных блоков и может привести к проблемам фрагментации в будущем.
2) Поиск свободного списка для блока, который имеет наименьшее количество свободных для хранения памяти. Это все еще O (n) с точки зрения поиска в свободном списке, потому что вы должны смотреть на каждый узел, чтобы найти наименее расточительный, но это может помочь отсрочить проблемы фрагментации.
В любом случае, с переменным размером, вы также должны где-то хранить метаданные для распределений. Если вы вообще не можете динамически распределять ресурсы, лучшее место — до или после блока, запрошенного пользователем; Вы можете добавить функции для обнаружения переполнения / недополнения буфера во время Deallocate (), если вы хотите добавить заполнение, которое инициализируется к известному значению, и проверить заполнение на разницу. Вы также можете добавить компактный шаг, как упомянуто в другом ответе, если вы хотите справиться с этим.
И последнее замечание: вы должны быть осторожны при добавлении метаданных в вспомогательную структуру FreeListNode, так как наименьший допустимый размер свободного блока — sizeof (FreeListNode). Это потому, что вы храните метаданные в самом блоке свободной памяти. Чем больше метаданных вам понадобится хранить для внутренних целей, тем более бесполезным будет ваш менеджер памяти.
Другие решения
Когда вы управляете памятью, вы обычно хотите использовать память, которой вы управляете, для хранения любых метаданных, которые вам нужны. Если вы посмотрите на любую из реализаций malloc (ptmalloc, phkmalloc, tcmalloc и т. Д.), Вы увидите, что именно так они обычно реализуются (конечно, без учета любых статических данных). Алгоритмы и структуры очень разные, по разным причинам, но я попытаюсь дать небольшое представление о том, что входит в общее управление памятью.
Управление однородными частями памяти отличается от управления неоднородными частями, и это может быть намного проще. Пример…
MemoryManager::MemoryManager() {
this->map = std::bitset<count>();
this->mem = malloc(size * count);
for (int i = 0; i < count; i++)
this->map.set(i);
}
Выделение это вопрос поиска следующего бита в std::bitset (компилятор может оптимизировать), помечая чанк как выделенный и возвращая его. Для перераспределения просто необходимо рассчитать индекс и пометить его как нераспределенное. свободный список это другой способ (что описано Вот), но он немного менее эффективен в отношении памяти и может плохо использовать кэш процессора.
Свободный список может быть основой для управления неоднородными порциями памяти. При этом вам необходимо сохранить размер фрагментов в дополнение к следующему указателю в фрагменте памяти. Размер позволяет разделить большие куски на более мелкие. Это, как правило, приводит к фрагментации, поскольку объединение фрагментов нетривиально. Вот почему большинство структур данных хранят списки порций одинакового размера и стараются отображать запросы как можно точнее.