6

如果没有 C++ 中其他内存管理器（例如 Malloc/New）的帮助，如何创建自定义 MemoryManager 来管理给定的连续内存块？

这里有一些更多的上下文：

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

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

分配函数应该以字节为单位获取所需的内存量，并返回一个指向该内存块开头的指针。如果没有剩余内存，则返回 NULL 指针。

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

请注意以下约束：

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

- 按照最初的规定，MemManager 不能使用其他内存管理器来执行它的功能，包括 new/malloc 和 delete/free

我已经在几次工作面试中收到过这个问题，但即使是几个小时的在线研究也没有帮助我，而且我每次都失败了。我找到了类似的实现，但它们要么都使用了 malloc/new，要么是通用的，并且向操作系统请求了内存，我不允许这样做。

请注意，我对使用 malloc/new 和 free/delete 感到很自在，并且使用它们也没有什么问题。

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

如果有人对如何实现这样的事情有某种想法，我将不胜感激。提前致谢！

编辑：我忘了在我原来的帖子中直接指定这个，但是用这个 MemManager 分配的对象可以是不同的大小。

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

4

2 回答 2

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)。这是因为您将元数据存储在空闲内存块本身中。您发现自己需要为内部目的存储的元数据越多，您的内存管理器就会越浪费。

于 2014-10-16T04:32:58.147 回答
1

当您管理内存时，您通常希望使用您管理的内存来存储您需要的任何元数据。如果您查看 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，将块标记为已分配并返回它。解除分配只需要计算索引，并标记为未分配。空闲列表是另一种方式（此处描述的内容），但它的内存效率稍低，并且可能无法很好地使用 CPU 缓存。

不过，空闲列表可以作为管理非同质内存块的基础。有了这个，除了内存块中的下一个指针之外，您还需要存储块的大小。该大小使您可以将较大的块拆分为较小的块。但是，这通常会导致碎片化，因为合并块并非易事。这就是为什么大多数数据结构都保留相同大小的块列表，并尝试尽可能接近地映射请求。

于 2014-10-16T19:40:50.923 回答