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

来自osdev
跳到导航 跳到搜索
(创建页面,内容为“{{Rating|2}} {{In_Progress}} == 首个够用的内存管理 == 实施首个基本够用的内存管理并不难。 我所说的内存管理器并不是指分页管理,而是一个简单的库(我们只需要保存一个空闲/已用页面的列表),您可以在用户空间和内核中使用它(如果您的内存模型是flat的,则可以全局使用)。 我要说的假设你已知道你可以摆弄的空闲内存块在哪里。 对于flat内存…”)
 
 
(未显示同一用户的1个中间版本)
第2行: 第2行:
{{In_Progress}}
{{In_Progress}}
== 首个够用的内存管理 ==
== 首个够用的内存管理 ==
实施首个基本够用的内存管理并不难。 我所说的内存管理器并不是指[[Pages|分页管理]],而是一个简单的库(我们只需要保存一个空闲/已用页面的列表),您可以在用户空间和内核中使用它(如果您的内存模型是flat的,则可以全局使用)。
实现首个基本够用的内存管理并不难。 我所说的内存管理器并不是指[[Paging|分页管理]],而是一个简单的库(我们只需要保存一个空闲/已用页面的列表),你可以在用户空间和内核中使用它(如果你的内存模型是flat形式的,则可以全局使用)。


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


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


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


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


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


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


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

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

难度等级
Difficulty 2.png
中等

这个页面正在建设中! 此页面或部分内容仍在改进中,因此可能还不完整。 其内容可能会在不久的将来更改。

首个够用的内存管理

实现首个基本够用的内存管理并不难。 我所说的内存管理器并不是指分页管理,而是一个简单的库(我们只需要保存一个空闲/已用页面的列表),你可以在用户空间和内核中使用它(如果你的内存模型是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)要找到放置节点(空闲块)的最佳位置,然后要稍微移动所有其他节点,为新节点腾出位置。 删除块会更容易。 只需在列表中找到给定的块,将其删除并移动所有其他块以填充该孔。

合并和拆分块

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

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