“Writing a memory manager”的版本间差异

2022年4月1日 (五) 14:33的最新版本

难度等级
中等

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

首个够用的内存管理

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

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

malloc()

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

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

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

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

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

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

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

然后逐个分解。

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

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

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

free()

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

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

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

测试

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

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

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

最佳适用的内存管理

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

跟踪空闲块

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

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

合并和拆分块

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

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

@@ 第2行： / 第2行： @@
 {{In_Progress}}
 == 首个够用的内存管理 ==
-实施首个基本够用的内存管理并不难。 我所说的内存管理器并不是指[[Pages|分页管理]]，而是一个简单的库(我们只需要保存一个空闲/已用页面的列表)，您可以在用户空间和内核中使用它(如果您的内存模型是flat的，则可以全局使用)。
+实现首个基本够用的内存管理并不难。 我所说的内存管理器并不是指[[Paging|分页管理]]，而是一个简单的库(我们只需要保存一个空闲/已用页面的列表)，你可以在用户空间和内核中使用它(如果你的内存模型是flat形式的，则可以全局使用)。
 我要说的假设你已知道你可以摆弄的空闲内存块在哪里。 对于flat内存模型，这可以从内核代码的末尾（比如1/2MB标记处）到系统内存的末尾（GRUB可以提供此信息）。 对于分页内核，这可以是分页的开始到分页的结尾。
@@ 第8行： / 第8行： @@
 === malloc() ===
-好的，第一步是拿出笔和纸 - 我指的不是键盘和文本编辑器，因为你没法在那些东西上面画图(或者使用手写笔/平板电脑可以用你的最喜欢的画图工具/OneNote/Windows-Journal).
+好的，第一步是拿出笔和纸 - 我指的不是键盘和文本编辑器，因为你没法在那些东西上面画图(或者使用手写笔/平板电脑可以用你最喜欢的画图工具/OneNote/Windows-Journal).
-不管怎样，我的观点是。 首先明确你了解基本概念吗？ 在纸上勾勒出内存将如何布局。 不要立即开始编写您的分配函数。 这应该是你最不应该做的事情之一。 要实际设计您希望如何管理您的内存，您希望在哪里存储分配信息(在前面的标头中，还是在全局位图中，等等)。 你想在标头/位图中存储什么？ 如果讨论标头，它将保存什么样的数据（比如指向下一个可用空间的指针，或者表达它是空闲的或已使用的）。
+不管怎样，我的观点是。 首先明确你了解基本概念吗？ 在纸上勾勒出内存将如何布局。 不要立即开始编写你的分配函数。 这应该是你最不应该做的事情之一。 要实际设计你希望如何管理你的内存，你希望在哪里存储分配信息(在前面的标头中，还是在全局位图中，等等)。 你想在标头/位图中存储什么？ 如果讨论标头，它将保存什么样的数据（比如指向下一个可用空间的指针，或者表达它是空闲的或已使用的）。
 记住，这是你的操作系统！按照你喜欢的方式来计划它。
@@ 第25行： / 第25行： @@
 然后逐个分解。
-我们怎样才能找到一个空闲的块？ (以下适用于用标头实现的初步方案，对于以后实现基本的Buddy系统，那时您只还需要一些想象力)
+我们怎样才能找到一个空闲的块？ (以下适用于用标头实现的初步方案，对于以后实现基本的Buddy系统，那时你只还需要一些想象力)
 * 从指向空闲内存开始的指针开始
 * 此标头是否具有表达内存状态的完整结尾？
 ** 是的
-* 分配新页面
+*** 分配新页面
 ** 没有
 *** 返回错误（例如指向0的指针）
@@ 第42行： / 第42行： @@
 *** 指向下一个块，然后返回步骤2
-找到后，将其已用位设置为已用。 如果找到的空间明显大于所需的空间，那么将其拆分通常是一个好主意 （将其切成两半，然后再切成两半，或者在使用的空间后添加另一个标头并更新指针。具体怎么做可以完全发挥你的想象力！）  ;] 然后返回地址!
+找到后，将其已用位设置为已用。 如果找到的空间明显大于所需的空间，那么将其拆分通常是一个好主意 （将其切成两半，然后再切成两半，或者在被使用的空间后面添加另一个标头并更新指针。具体怎么做可以完全发挥你的想象力！）  ;] 然后返回地址!
 === free() ===
-先别急着编程！ 现在你需要写你的free函数。 你基本上需要经历和malloc同样的过程。 您需要一种方法来找出位图中的位置，或者哪个标头与给出的地址相关联。 如果是带有标头的做法，所给的地址参数只是标头的地址。 将其空闲标志位设置为空闲。
+先别急着编程！ 现在你需要写你的free函数。 你基本上需要经历和malloc同样的过程。 你需要一种方法来找出位图中的位置，或者哪个标头与给出的地址相关联。 如果是带有标头的做法，那么只需要将地址 - 标头大小，就可以找到标头。（译者注：因为用户调用free函数时，给的参数是前面在malloc时返回的用户可用地址。如果你使用的是标头后面跟紧跟可用空间地址的简单做法，把这个地址再减去标头大小，刚刚好是回到标头所在的地址） 将其空闲标志位设置为空闲。
-下一步是扫描内存并合并空闲块 (例如，如果下一个指针的头是空闲的，搜索下一个指针的头，再下一个，直到碰到一个用过的块，然后将当前块的下一个指针设置到该用过的块，跳过空闲块 - 如果按你的想法有任何意义的话: D)。
+下一步是扫描内存并合并空闲块 (例如，如果下一个指针的头是空闲的，搜索下一个指针的头，再下一个，直到碰到一个用过的块，然后将当前块的下一个指针设置到该用过的块，跳过空闲块 - 如果按你的想法有任何意义的话 :D)。
-继续把前面的思路分成越来越小的块。 确保你100%了解每个过程是如何运作的。 关键是在开始编码之前要完全理解它! 把每一个等式过程都写下来。 您必须知道代码是如何工作的，并将其以可读的形式记录在纸上，这样当出现错误时，就很容易调试。
+继续把前面的思路分成越来越小的块。 确保你100%了解每个过程是如何运作的。 关键是在开始编码之前要完全理解它! 把每一个等式过程都写下来。 你必须知道代码是如何工作的，并将其以可读的形式记录在纸上，这样当出现错误时，就很容易调试。
 === 测试 ===
-只有经过以上这样，你才能开始编码。 一旦编写完成，您应该在一个简单的沙箱环境中尝试运行它。 比如分配大约5个随机大小，从中间释放几个，重新分配它们，让它们在每一步打印出所有的内存地址，然后花时间在纸上推演它，看看它是否正确。 我遇到的主要是释放问题（要将空闲块组合在一起），我必须将每个步骤打印到屏幕上才能找到错误 (我忘了是什么，可能错写了a=，而不是a==)。
+只有经过以上这样，你才能开始编码。 一旦编写完成，你应该在一个简单的沙箱环境中尝试运行它。 比如分配大约5个随机大小，从中间释放几个，重新分配它们，让它们在每一步打印出所有的内存地址，然后花时间在纸上推演它，看看它是否正确。 我遇到的主要是释放问题（要将空闲块组合在一起），我必须将每个步骤打印到屏幕上才能找到错误 (我忘了是什么，可能错写了a=，而不是a==)。
-不要复制别人的代码! 你可以复制他们的基本理论，但要在纸上计划如何在你的操作系统中工作，并以你自己的方式实现它。 这样，您就可以确切地知道它是如何工作的，并且可以自己调试和扩展它。
+不要复制别人的代码! 你可以复制他们的基本理论，但要在纸上计划如何在你的操作系统中工作，并以你自己的方式实现它。 这样，你就可以确切地知道它是如何工作的，并且可以自己调试和扩展它。
 祝你的内存管理开发过程好运。:]
 ==最佳适用的内存管理==
-最适合的内存管理器的基本概念与前面一个阶段的相同。 内存中有块。 但是，前面一个的问题是，当分割的块比我们需要的大得多时，同时又有比合适块更小的块时，会出现碎片。
+最适用的内存管理器的基本想法与前面一个阶段相同。 内存被划分为多个块。 但是，前面一个的问题是，当分割的块比我们需要的大得多时，同时又有不少比合适块更小的块，会出现碎片。
 ===跟踪空闲块===
 你需要知道每个空闲块在内存中的位置，以及它有多大。 可以将其存储在数组、二叉树或其他任何形式中。
-你对这份清单进行排序的方式很重要。 如果我们对列表进行大小排序，从小到大，我们可以从第一个条目开始寻找空闲块，只要当前节点不够大，就可以转到下一个节点。 这样你会找到最合适的块。 如果没有找到块，您需要向虚拟内存管理器请求更多内存。
+你对这份清单进行排序的方式很重要。 如果我们对列表进行大小排序，从小到大，我们可以从第一个条目开始寻找空闲块，只要当前节点不够大，就可以转到下一个节点。 这样你会找到最合适的块。 如果没有找到块，你需要向虚拟内存管理器请求更多内存。
-为了完成这项工作，你可以做一些很好的功能。 这些函数（例如add）要找到放置节点（空闲块）的最佳位置，然后要稍微移动所有其他节点，为新节点腾出位置。 删除块会更容易。 只需在列表中找到给定的块，将其删除并移动所有其他块以填充该孔。
+为了完成这项工作，你可以尝试做一些很棒的函数。 这些函数（例如add）要找到放置节点（空闲块）的最佳位置，然后要稍微移动所有其他节点，为新节点腾出位置。 删除块会更容易。 只需在列表中找到给定的块，将其删除并移动所有其他块以填充该孔。
 ===合并和拆分块===
-合并和拆分空闲块需要更多一些工作，因为您必须同时保持您的空闲块列表进行更新。
+合并和拆分空闲块需要更多一些工作，因为你必须同时保持你的空闲块列表进行更新。
-祝你好运，做出一个最合适的内存分配器!
+祝你好运，做出一个最适用的内存分配器!
 [[Category:Memory management]]
 [[Category:Tutorials]]