Writing a memory manager

难度等级
中等

此页面或部分内容仍在改进中，因此可能还不完整。 其内容可能会在不久的将来更改。

首个够用的内存管理

实现首个基本够用的内存管理并不难。 我所说的内存管理器并不是指分页管理，而是一个简单的库(我们只需要保存一个空闲/已用页面的列表)，你可以在用户空间和内核中使用它(如果你的内存模型是flat形式的，则可以全局使用)。

我要说的假设你已知道你可以摆弄的空闲内存块在哪里。 对于flat内存模型，这可以从内核代码的末尾（比如1/2MB标记处）到系统内存的末尾（GRUB可以提供此信息）。 对于分页内核，这可以是分页的开始到分页的结尾。

malloc()

好的，第一步是拿出笔和纸 - 我指的不是键盘和文本编辑器，因为你没法在那些东西上面画图(或者使用手写笔/平板电脑可以用你最喜欢的画图工具/OneNote/Windows-Journal).

不管怎样，我的观点是。 首先明确你了解基本概念吗？ 在纸上勾勒出内存将如何布局。 不要立即开始编写你的分配函数。 这应该是你最不应该做的事情之一。 要实际设计你希望如何管理你的内存，你希望在哪里存储分配信息(在前面的标头中，还是在全局位图中，等等)。 你想在标头/位图中存储什么？ 如果讨论标头，它将保存什么样的数据（比如指向下一个可用空间的指针，或者表达它是空闲的或已使用的）。

记住，这是你的操作系统！按照你喜欢的方式来计划它。

重要的是从全局出发。 而不是坐在键盘前，对着一个空白的malloc函数期待知道该怎么做。

然后你可以开始编写标头/位图的基本结构。

当你知道内存是如何存储的，那么你可以继续编写你的分配函数。 关掉你的文本编辑器，我们还得继续用笔进行构思 :） 再次，从自上而下的视角开始分析。 内存分配器到底要做什么？

1. 查找空闲块
2. 将其标记为已使用
3. 返回其地址

然后逐个分解。

我们怎样才能找到一个空闲的块？ (以下适用于用标头实现的初步方案，对于以后实现基本的Buddy系统，那时你只还需要一些想象力)

• 从指向空闲内存开始的指针开始
• 此标头是否具有表达内存状态的完整结尾？
  • 是的
    • 分配新页面
  • 没有
    • 返回错误（例如指向0的指针）
• 此标头是否表示此内存可用
  • 是
    • 下一个标头的地址-（此标头的地址-标头的大小）大于所需的大小吗
      • 是的？
        • 我们找到了一个空闲块!
      • 没有？
        • 指向下一块并返回步骤2
  • 否
    • 指向下一个块，然后返回步骤2

找到后，将其已用位设置为已用。 如果找到的空间明显大于所需的空间，那么将其拆分通常是一个好主意 （将其切成两半，然后再切成两半，或者在被使用的空间后面添加另一个标头并更新指针。具体怎么做可以完全发挥你的想象力！）  ;] 然后返回地址!

free()

先别急着编程！ 现在你需要写你的free函数。 你基本上需要经历和malloc同样的过程。 你需要一种方法来找出位图中的位置，或者哪个标头与给出的地址相关联。 如果是带有标头的做法，那么只需要将地址 - 标头大小，就可以找到标头。（译者注：因为用户调用free函数时，给的参数是前面在malloc时返回的用户可用地址。如果你使用的是标头后面跟紧跟可用空间地址的简单做法，把这个地址再减去标头大小，刚刚好是回到标头所在的地址） 将其空闲标志位设置为空闲。

下一步是扫描内存并合并空闲块 (例如，如果下一个指针的头是空闲的，搜索下一个指针的头，再下一个，直到碰到一个用过的块，然后将当前块的下一个指针设置到该用过的块，跳过空闲块 - 如果按你的想法有任何意义的话 :D)。

继续把前面的思路分成越来越小的块。 确保你100%了解每个过程是如何运作的。 关键是在开始编码之前要完全理解它! 把每一个等式过程都写下来。 你必须知道代码是如何工作的，并将其以可读的形式记录在纸上，这样当出现错误时，就很容易调试。

测试

只有经过以上这样，你才能开始编码。 一旦编写完成，你应该在一个简单的沙箱环境中尝试运行它。 比如分配大约5个随机大小，从中间释放几个，重新分配它们，让它们在每一步打印出所有的内存地址，然后花时间在纸上推演它，看看它是否正确。 我遇到的主要是释放问题（要将空闲块组合在一起），我必须将每个步骤打印到屏幕上才能找到错误 (我忘了是什么，可能错写了a=，而不是a==)。

不要复制别人的代码! 你可以复制他们的基本理论，但要在纸上计划如何在你的操作系统中工作，并以你自己的方式实现它。 这样，你就可以确切地知道它是如何工作的，并且可以自己调试和扩展它。

祝你的内存管理开发过程好运。:]

最佳适用的内存管理

最适用的内存管理器的基本想法与前面一个阶段相同。 内存被划分为多个块。 但是，前面一个的问题是，当分割的块比我们需要的大得多时，同时又有不少比合适块更小的块，会出现碎片。

跟踪空闲块

你需要知道每个空闲块在内存中的位置，以及它有多大。 可以将其存储在数组、二叉树或其他任何形式中。 你对这份清单进行排序的方式很重要。 如果我们对列表进行大小排序，从小到大，我们可以从第一个条目开始寻找空闲块，只要当前节点不够大，就可以转到下一个节点。 这样你会找到最合适的块。 如果没有找到块，你需要向虚拟内存管理器请求更多内存。

为了完成这项工作，你可以尝试做一些很棒的函数。 这些函数（例如add）要找到放置节点（空闲块）的最佳位置，然后要稍微移动所有其他节点，为新节点腾出位置。 删除块会更容易。 只需在列表中找到给定的块，将其删除并移动所有其他块以填充该孔。

合并和拆分块

合并和拆分空闲块需要更多一些工作，因为你必须同时保持你的空闲块列表进行更新。

祝你好运，做出一个最适用的内存分配器!