Writing a memory manager - 版本历史

2022年4月1日 (五) 14:33 Zhang3

2022-04-01T14:33:01Z

←上一版本		2022年4月1日 (五) 14:33的版本
第8行：		第8行：
	=== malloc() ===		=== malloc() ===

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

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

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

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

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

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

	===跟踪空闲块===		===跟踪空闲块===
第65行：		第65行：
	你对这份清单进行排序的方式很重要。如果我们对列表进行大小排序，从小到大，我们可以从第一个条目开始寻找空闲块，只要当前节点不够大，就可以转到下一个节点。这样你会找到最合适的块。如果没有找到块，你需要向虚拟内存管理器请求更多内存。		你对这份清单进行排序的方式很重要。如果我们对列表进行大小排序，从小到大，我们可以从第一个条目开始寻找空闲块，只要当前节点不够大，就可以转到下一个节点。这样你会找到最合适的块。如果没有找到块，你需要向虚拟内存管理器请求更多内存。

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

	===合并和拆分块===		===合并和拆分块===

2022年4月1日 (五) 14:16 Zhang3

2022-04-01T14:16:52Z

←上一版本		2022年4月1日 (五) 14:16的版本
第2行：		第2行：
	{{In_Progress}}		{{In_Progress}}
	== 首个够用的内存管理 ==		== 首个够用的内存管理 ==
	~~实施首个基本够用的内存管理并不难。~~ 我所说的内存管理器并不是指[[~~Pages~~\|分页管理]]，而是一个简单的库(我们只需要保存一个空闲/已用页面的列表)~~，您可以在用户空间和内核中使用它~~(~~如果您的内存模型是flat的，则可以全局使用~~)。		实现首个基本够用的内存管理并不难。我所说的内存管理器并不是指[[Paging\|分页管理]]，而是一个简单的库(我们只需要保存一个空闲/已用页面的列表)，你可以在用户空间和内核中使用它(如果你的内存模型是flat形式的，则可以全局使用)。

	我要说的假设你已知道你可以摆弄的空闲内存块在哪里。对于flat内存模型，这可以从内核代码的末尾（比如1/2MB标记处）到系统内存的末尾（GRUB可以提供此信息）。对于分页内核，这可以是分页的开始到分页的结尾。		我要说的假设你已知道你可以摆弄的空闲内存块在哪里。对于flat内存模型，这可以从内核代码的末尾（比如1/2MB标记处）到系统内存的末尾（GRUB可以提供此信息）。对于分页内核，这可以是分页的开始到分页的结尾。
第10行：		第10行：
	好的，第一步是拿出笔和纸 - 我指的不是键盘和文本编辑器，因为你没法在那些东西上面画图(或者使用手写笔/平板电脑可以用你的最喜欢的画图工具/OneNote/Windows-Journal).		好的，第一步是拿出笔和纸 - 我指的不是键盘和文本编辑器，因为你没法在那些东西上面画图(或者使用手写笔/平板电脑可以用你的最喜欢的画图工具/OneNote/Windows-Journal).

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

	记住，这是你的操作系统！按照你喜欢的方式来计划它。		记住，这是你的操作系统！按照你喜欢的方式来计划它。
第25行：		第25行：
	然后逐个分解。		然后逐个分解。

	我们怎样才能找到一个空闲的块？ (~~以下适用于用标头实现的初步方案，对于以后实现基本的Buddy系统，那时您只还需要一些想象力~~)		我们怎样才能找到一个空闲的块？ (以下适用于用标头实现的初步方案，对于以后实现基本的Buddy系统，那时你只还需要一些想象力)
	* 从指向空闲内存开始的指针开始		* 从指向空闲内存开始的指针开始
	* 此标头是否具有表达内存状态的完整结尾？		* 此标头是否具有表达内存状态的完整结尾？
	** 是的		** 是的
	* 分配新页面		*** 分配新页面
	** 没有		** 没有
	*** 返回错误（例如指向0的指针）		*** 返回错误（例如指向0的指针）
第42行：		第42行：
	*** 指向下一个块，然后返回步骤2		*** 指向下一个块，然后返回步骤2

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

	=== free() ===		=== free() ===
	先别急着编程！现在你需要写你的free函数。你基本上需要经历和malloc同样的过程。 ~~您需要一种方法来找出位图中的位置，或者哪个标头与给出的地址相关联。~~ 如果是带有标头的做法，所给的地址参数只是标头的地址。将其空闲标志位设置为空闲。		先别急着编程！现在你需要写你的free函数。你基本上需要经历和malloc同样的过程。你需要一种方法来找出位图中的位置，或者哪个标头与给出的地址相关联。如果是带有标头的做法，所给的地址参数只是标头的地址。将其空闲标志位设置为空闲。

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

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

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

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

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

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

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

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

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

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

	[[Category:Memory management]]		[[Category:Memory management]]
	[[Category:Tutorials]]		[[Category:Tutorials]]

Zhang3：创建页面，内容为“{{Rating|2}} {{In_Progress}} == 首个够用的内存管理 == 实施首个基本够用的内存管理并不难。我所说的内存管理器并不是指分页管理，而是一个简单的库(我们只需要保存一个空闲/已用页面的列表)，您可以在用户空间和内核中使用它(如果您的内存模型是flat的，则可以全局使用)。我要说的假设你已知道你可以摆弄的空闲内存块在哪里。对于flat内存…”

2022-04-01T14:10:09Z

创建页面，内容为“{{Rating|2}} {{In_Progress}} == 首个够用的内存管理 == 实施首个基本够用的内存管理并不难。我所说的内存管理器并不是指分页管理，而是一个简单的库(我们只需要保存一个空闲/已用页面的列表)，您可以在用户空间和内核中使用它(如果您的内存模型是flat的，则可以全局使用)。我要说的假设你已知道你可以摆弄的空闲内存块在哪里。对于flat内存…”

新页面

{{Rating|2}}
{{In_Progress}}
== 首个够用的内存管理 ==
实施首个基本够用的内存管理并不难。我所说的内存管理器并不是指[[Pages|分页管理]]，而是一个简单的库(我们只需要保存一个空闲/已用页面的列表)，您可以在用户空间和内核中使用它(如果您的内存模型是flat的，则可以全局使用)。

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

=== malloc() ===

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

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

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

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

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

当你知道内存是如何存储的，那么你可以继续编写你的分配函数。关掉你的文本编辑器，我们还得继续用笔进行构思 :）再次，从自上而下的视角开始分析。内存分配器到底要做什么？
# 查找空闲块
# 将其标记为已使用
# 返回其地址

然后逐个分解。

我们怎样才能找到一个空闲的块？ (以下适用于用标头实现的初步方案，对于以后实现基本的Buddy系统，那时您只还需要一些想象力)
* 从指向空闲内存开始的指针开始
* 此标头是否具有表达内存状态的完整结尾？
** 是的
* 分配新页面
** 没有
*** 返回错误（例如指向0的指针）
* 此标头是否表示此内存可用
** 是
*** 下一个标头的地址-（此标头的地址-标头的大小）大于所需的大小吗
**** 是的？
***** 我们找到了一个空闲块!
**** 没有？
***** 指向下一块并返回步骤2
** 否
*** 指向下一个块，然后返回步骤2

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

=== free() ===
先别急着编程！现在你需要写你的free函数。你基本上需要经历和malloc同样的过程。您需要一种方法来找出位图中的位置，或者哪个标头与给出的地址相关联。如果是带有标头的做法，所给的地址参数只是标头的地址。将其空闲标志位设置为空闲。

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

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

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

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

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

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

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

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

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

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

[[Category:Memory management]]
[[Category:Tutorials]]