嵌入式操作系统内核实现（三）（转载）

第二章 内存管理

2.1 什么是内存管理

       要回答这个问题的确是件比较难的事，为了回答这个问题，先看看c语言的标准库函数malloc，它的原型是void *malloc(unsigned int num_bytes)，它的功能是分配长度为num_bytes字节的内存块，它的返回值是一个void型的指针。一说到指针就会联想到内存地址，实际上malloc函数返回的只是一个内存地址，从这个地址开始的num_bytes字节的空间就是分配给程序使用的空间，而操作系统内核不会在释放这块空间之前再分配给其他程序。那么内核是怎样知道这块空间已经分配出去了呢？很容易想的是，内核应该为这块空间做些记录，这些记录应该保存一些关于该块大小、使用状态等的信息。到这里可以回答什么是内存管理这个问题了，内存管理可以等价于内核用什么样的记录、怎么样使用这个记录的问题。

       想一想似乎内存管理很简单，不外乎就是一块空地怎么样分给农民的问题嘛。村干部拿上一个小本子，记下一些东西就搞定了。宏观上就是这么一回事，但是如果什么事情都从宏观上去考虑，那世界上就没什么难事了，原子弹不外乎就是金属片包着一些核物质，外加一根导火线，要引爆的时候用打火机一点就OK。可是这里关心的是什么呢？关心的是村干部的小本子上到底记录了什么？他的本子上可能这样记录着一些东西：

户主：    张三

田地位置：村头

田地大小：2亩

田的土质：优良

租用年限：3年

田地周围的情况：……

       有了这些记录，村头那块2亩大小的田地就分给张三了，其他人不可以在这块地上种庄稼了。万一村长隔壁家那条狗的妈妈的主人李大（毕竟和村长有点关系）要在这块地上种点菜之类的怎么办？张三很生气，后果很严重！可能张三要杀人也说不定。这时候村长就要出来处理这种情况，他会怎么处理呢？这个就不知道了，一般情况下会大事化小，小事化无嘛。好啦，不要在那里东拉西扯的了，这些和计算机有关系吗？我的anmnmnly！这里anmnmnly可以做个类比了，土地就是内存，张三就是应用程序，村长就是操作系统内核，李大与张三的矛盾就是内存泄漏。OK，相信现在应该知道什么叫内存管理了吧，如果还不清楚，就拿着本子去做点类似的事情，如果还不清楚，那说明基础不够或者不适合学计算机，呵呵，当然开玩笑啦，只要努力学习就没有学不懂的事。

       现在做一个假设，您的硬件上有一块8M大小的内存空间，现在要求您来实现malloc和free函数，您会怎么做呢？为了不和标准C库中的malloc和free混淆，从这里开始就用kmalloc和kfree，ByCore中的名字也是这样的。为了做出这道题，我会去读数据结构、操作系统，甚至一些内存管理的论文。这些书上我们会发现很多术语，什么分区、分块、分配策略，动态（静态）分配……，好多啊，就像苍蝇一样。不过没关系，不懂就多看几遍，总有一遍过后就懂了。好了，废话就不多说了，书上那些知识anmnmnly就不多说了，相信聪明的您应该完全理解他们了。下面看看怎样来解答上面那到习题，这道习题解决了，ByCore的内存管理方法就说完了。

2.2 解答习题

       这道习题的实现方法太多了，anmnmnly就不一一叙述了。我就直奔主题，看看ByCore是怎样解答这道习题的。ByCore借用了伙伴系统的原理，只是对伙伴系统做了修改，这里用了修改这个词，实在不敢用改进这个词，因为改是改了，有没有进就不知道了^_^。

2.2.1 伙伴系统是什么？

在伙伴系统中，内存块的大小为2^k，L≤K≤U，其中

2^L＝分配的最小块尺寸

2^U＝分配的最大块尺寸

开始时，可用于分配的整个空间被看作是大小为2^U的块。如果请求的大小S（2^U－1＜S≤2^U）则分配整个空间。如果有请求S（2^U－2＜S≤2^U－1)， 这个块被分成两个大小相等的伙伴，大小为2^U－1，并分配两个伙伴中的任何一个；否则，该块又被分成两个伙伴，这个过程一直继续到产生的最小块大于或等于S的块。例如，最初的内存块为1MB，第一个请求A为100KB，需要分配一个128KB的块。分配过程如下：块被划分成两个512KB的伙伴，第一个又被划分成两个256KB的伙伴，并且第一个又被划分成两个128KB的伙伴，第一个分配给A。下一个请求B需要256KB的块，由于已有这样的块，随即分配给它。当两个伙伴块为空闲时又可以合并成一个大块，可以根据块的起始地址和大小确定伙伴块的起始地址如图2.1：

                     图2.1

2.2.2 伙伴系统的优缺点

说到优缺点的时候，一定要知道这是个相对的概念。要不然蔡依林也不会唱优点变成缺点了。这篇连载的题目叫嵌入式操作系统内核实现，也就是说本连载的基调已经限定在嵌入式领域内了，当然这些优缺点也是在这个范围以内。好了，看看伙伴系统的优劣吧。

优点：分配和回收速度快、算法简单，当一个大小为2^K字节的块释放后，存储管理只需要搜索2^K字节大小的块以判定是否需要合并。而那些允许以任意形式分割内存的策略的算法需要搜索整个空闲块表。

缺点：伴系统的内存利用率比较低效，这主要是所有的内存请求都必须以2的幂次方大小的空间来满足。比如应用程序申请20kB的空间，系统必须分配32kB的空间。

2.2.3 ByCore的策略

2.2.3.1 基本思想

根据伙伴系统的优缺点可以对伙伴系统改进，从而提高内存的利用率。从伙伴系统原理可知，内存利用率低下的主要原因是内存按照2^K字节为单位进行分配，如果能按照申请需求进行内存分配，那么内存的利用率就会得到显著提高。基于这种思想可以对伙伴系统加以修改，图2.1描述了ByCore内存管理方法在某个时刻的状态。

  

图2.2 ByCore内存管理某时刻

其基本思想是将系统中所有独立块(空闲块和使用块)按照物理地址的先后顺序组织成一个双链表，每个块存放块本身的信息。分配时，查找整个链表找到最优适配的空闲块，并将此空闲块分裂成二块，一块用来满足请求，另一块作为空闲块插入空闲块链表。空间释放时，查找相邻的空闲块，如果相邻的块为空闲则合并成一个独立块。

为了提高内存分配的效率，将系统中所有的空闲块按照空间大小组成不同的空闲块链表。为了在分配过程中更快速的查找最优适配块，为每个空闲块链表创建索引。为防止产生小的不能继续使用的空闲块，在空间分配时，如果m-n其中m：空闲块的大小，n：申请大小，c：给定的阀值)时，不需将此空闲块分裂，直接将整个空闲块分配出去。

综上所述，可以将内存块组织成两种双链表，即空闲块链表和物理块链表。

1. 空闲块链表：将所有的空闲块按大小组织成多个独立的空闲链表，并建立相应的索引；

2. 物理块链表：将所有独立块(空闲块和使用块)组织成一个双链表，链表中各节点之间是按照物理地址顺序链接的。空间释放时直接根据这一链表找到与释放块相邻的块，再根据相邻块中的相关信息判断是否需要执行合并操作。

       说了好多，感觉有点抽象，不过也没关系，可能再看一遍就能明白是怎么回事了，读不懂也没有关系，看看下面对源代码的解释就应该清楚了。

                                    To be continued……

------ anmnmnly     

------ 2008.04.07