在没有Malloc/New或Free/Delete的情况下管理连续的内存块

Question

如何在没有C++中其他内存管理器(如Malloc/New)的帮助下,如何创建自定义MemoryManager来管理给定的连续内存块？

这里有一些更多的背景:

   MemManager::MemManager(void* memory, unsigned char totalsize)
   {
       Memory = memory;
       MemSize = totalsize;
   }

我需要能够使用MemManager分配和释放这个连续内存的块.构造函数以字节为单位给出块的总大小.

Allocate函数应该以字节为单位占用所需的内存量,并返回指向该内存块开头的指针.如果没有剩余内存,则返回NULL指针.

Deallocate函数应该接收指向必须释放的内存块的指针,并将其返回给MemManager以备将来使用.

请注意以下约束:

- 除了给它的内存块,MemManager不能使用任何动态内存

- 最初指定,MemManager不能使用其他内存管理器来执行其功能,包括new/malloc和delete/free

我已经在几次面试中收到了这个问题,但即使是几个小时的在线研究也没有帮助我,我每次都失败了.我已经找到了类似的实现,但它们都使用了malloc/new,或者是来自操作系统的通用和请求的内存,我不允许这样做.

请注意,我很乐意使用malloc/new和free/delete,并且使用它们时遇到的问题很少.

我尝试过以LinkedList方式利用节点对象的实现,这些实现指向分配的内存块并说明使用了多少字节.然而,在这些实现中,我总是被迫在堆栈中创建新节点并将它们插入到列表中,但是一旦它们超出范围,整个程序就会因地址和内存大小丢失而中断.

如果有人对如何实现这样的事情有某种想法,我将非常感激.提前致谢!

编辑:我忘了在我的原始帖子中直接指定这个,但是用这个MemManager分配的对象可以是不同的大小.

编辑2:我最终使用了同源内存块,由于下面的答案提供的信息,实际上很容易实现.没有指定有关实现本身的确切规则,因此我将每个块分成8个字节.如果用户请求超过8个字节,我将无法提供,但如果用户请求少于8个字节(但> 0),那么我会给予额外的内存.如果传入的内存量不能被8整除,那么最后会浪费内存,我认为这比使用更多内存要好得多.

Answer 1

我尝试过以 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() 和 Deallocate() 的复杂性。您还需要担心内存碎片，因为如果您没有足够内存的空闲块来存储请求的数量，那么除了分配失败之外，您无能为力。几个 Allocate() 算法可能是：

1) 只需返回第一个足够大的可用块来容纳请求，并根据需要更新空闲块。就搜索空闲列表而言，这是 O(n)，但可能不需要搜索大量空闲块，并且可能会导致碎片问题。

2) 在空闲列表中搜索具有最小空闲量的块以容纳内存。就搜索空闲列表而言，这仍然是 O(n)，因为您必须查看每个节点以找到浪费最少的节点，但可以帮助延迟碎片问题。

无论哪种方式，由于大小可变，您还必须在某处存储用于分配的元数据。如果根本无法动态分配，最好的位置是在用户请求的块之前或之后；如果您想添加初始化为已知值的填充并检查填充的差异，您可以添加功能来在 Deallocate() 期间检测缓冲区溢出/下溢。如果您想处理这个问题，您还可以添加另一个答案中提到的紧凑步骤。

最后一点：将元数据添加到 FreeListNode 辅助结构时必须小心，因为允许的最小空闲块大小是 sizeof(FreeListNode)。这是因为您将元数据存储在空闲内存块本身中。您发现自己需要为内部目的存储的元数据越多，您的内存管理器就会越浪费。