HelloOs总结之内存管理(中)
HelloOs总结之内存管理（中）
4.3 基本内存管理
按照我的理解，一般来说，操作系统关于内存的管理主要有两个大的方面：一个是内存映射和保护（前面章节有论述），另一个就是基本的内存管理，包括内存分配、回收等等。如果说前者大部分是硬件在起作用,后者则几乎全是软件的责任了。
在我一开始学习操作系统时，当时觉得内存分配好神奇，你要多少内存，操作系统就给你多少内存（当然，不超过操作系统分配给进程的内存限制）。就像上大学时，父母给我们的无私的生活费一样。我当时想，这个“给”（分配）的过程是怎么一回事，难道还真是操作系统把进程申请的内存“手把手”交给进程吗？
后来才慢慢了解到，从一个更高的层面上说，这个内存的基本管理（分配和回收）也并不是很复杂。不考虑具体的分配算法的话，整个内存分配过程本质上也就分为两个部分：
（1）、操作系统从管理的、还未分配的内存空间中按照一定的分配算法找到一片合适的区域，然后在管理的元数据中（所谓管理，一般来说并不是针对具体的内存进行管理，而是对一小片元数据进行管理，而这一小片元数据就对应着所需要管理的内存空间）打上已分配的标记（或者以某种方式直接分配出去）。
（2）、将这块物理内存映射到进程的地址空间中去。（如果采取了页表机制的话，一般也就是找一片虚拟地址区域，使其和分配的物理内存地址空间进行对应，然后把这种对应写入到相应的页表项中）。
一般来说，对于内存的分配，或者专业点叫做地址空间的分配，除了物理地址之外，还包括虚拟地址的分配。由于HelloOs中虚拟地址和物理地址基本是相同的，从逻辑上说可以不使用虚拟地址的概念，所以，下面的分配仅针对具体的物理地址空间进行分配。同时，为了简单起见，我们的每个进程中包含了所有的物理内存映射（后文会说到，每个进程的页表其实是一样的），因此上述内存分配的第二个步骤就省略了。
下面我们主要关注的是内存分配的第一个方面，如何分配合适的内存。这里HelloOs采用的是伙伴算法来进行基本的内存管理。
4.3.1 伙伴（Buddy）算法
简单来说，伙伴算法就是将内存分为若干小块，然后尽可能以最合适的方式满足程序内存需求的一种内存管理算法。而这若干小块的分法并不是固定的，但是一般来说，这些内存块的大小必须是2的整数次方。例如，1块1M的内存可以按照64K,128K，256K和512K等数值分成若干块。同时，对于具体的分块原则还要根据其可能产生的内存碎片大小和总的内存容量等条件进行权衡。
在内存划分完成之后，系统就可以对内存进行分配和回收了。在分配时，首先从空闲的内存中搜索比申请的内存大的最小的内存块（为了减小内存碎片）。如果这样的内存块存在，则将这块内存标记为“已用”，同时将改内存分配给应用程序。如果这样的内存不存在，则操作系统将寻找更大块的空闲内存，然后将这块内存平分成两部分（这也是为什么内存块的大小最好是2的次方的原因），一部分返回给程序使用，另一部分最为空闲的内存等待下一次被分配。
当程序释放内存时，操作系统首先将改内存回收，然后检查与该内存相邻的内存是否是同样大小并且同样处于空闲的状态。如果是，则将这两块内存合并，然后程序迭代进行同样的检查。
下面图4.7 和图4.8举了一个栗子，暂且放松一下（以下栗子我是厚着脸皮摘自《一步一步写嵌入式操作系统》）。
图4.7 伙伴算法举例示意图
图 4.8 伙伴算法示例解析
上面说了伙伴算法的理论部分，下面简单谈点实践的部分。（详细的部分，可以参照《一步一步写嵌入式操作系统》）。
谈到实践部分之前，还需要说点其他东西。
上面我们曾说道，对于内存的分配管理，一般来说并不是真正的管理对应的内存，而是划分出一小片元数据区域，让这一小片区域对应具体的内存空间。如下图4.9 所示。以后对内存空间的管理只需要对其元数据进行管理即可。
图4.9 元数据与对应管理的内存区域示意图
在HelloOs中主要有两片元数据区域和对应管理的内存区域，如下图4.10所示。
图4.10 HelloOs中元数据区域和其对应管理的内存区域
这里说的元数据区域，其实就是一片page结构体数组区域，每个page结构体中有一些信息来表明所对应的的内存地址。如下图4.11所示为HelloOs的page结构体。
图4.10 page结构体示意图
在HelloOs中每个page结构体所管理的内存大小为4K,它正好等于伙伴系统中最小的的分块大小。其他的分块都是由最小的4K块组合而成，这些组合的最小块集合，叫做一个buddy，如下图4.11所示。（这大概也是为什么这个算法叫做伙伴算法的原因吧）
图4.11 buddy示意图
整个伙伴系统的实现主要分为三个大部分：
（1）、buddy的初始化
HelloOs总共划分9种类型的buddy（分别拥有1,2,4,8，…,28个最小的page大小）每种类型的buddy的大小是一样的（也就是分块是一样的）。伙伴系统需要把相同大小的分块串在一起，这样方便分配。这样说来，一种类型的buddy需要进行两次组合，一次是一定数量的page组合成一定大小的buddy,然后是所有大小相同的buddy串在一起。如下图4.12所示。
在初始化的时候，系统只分配两种类型的buddy,即最大的和最小的，如4.12所示。
而所谓具体的初始化，其实也就是按照规则填充这里的元数据区域的page结构体，同时把属于相同buddy的page组合在一起。这里就不多说了。
图4.12 buddy初始化示意图
（2）、分配过程
有了上面的初始化过程，分配过程其实也就不是很复杂了。其实在理论部分也有说到，其基本算法流程是：
a) 用户申请一片内存区域，大小为S
b) buddy系统检查是否含有大于S的最小buddy，如果有的话，则取出一个buddy分配给用户。
c) 如果没有的话，则迭代向上寻找一个稍大点的buddy，把其分为较小的buddy块，然后剩下的分配给用户。
（3）、回收过程
回收过程也不是很复杂，只是要进行判断是否其相邻的区域也是空闲的，如果是的话，则需要进行合并操作。不赘述了。
以上就是伙伴系统的大概了，虽然说起来不是很难，但是代码实现起来难度还是不小的，有兴趣吗,可以尝试一下，听说微软曾经出过类似的面试题哦！