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

2.2.3.2 分配与释放策略

1. 分配策略

为说明分配策略。先做如下三项假定：

· 空间最小值阀值为c，即当空闲块分配后剩下的空间不能小于c；

· 内存大小为m=2ⁿ⁺¹kB；

· 系统初始化工作已经完成，整个内存管理的数据结构已经建立。

系统初始化时，根据实际内存的大小创建空闲块索引，空闲块索引指向相应空闲块链表的表头节点，2ⁱ kB指向大小为S kB（其中2^i－1i）的空闲块链表表头节点。初始化时没有进行内存分配，整个内存块都为空闲。Head总是指向内存的物理起始地址。

现假设应用程序请求内存分配，其中请大小分别是2ⁿkB，2^n-1kB，(2^n-1-2¹）kB。图2.3和图2.4中描述了第一次和第三次分配以后的内存结构，图中阴影部分为为已分配块，空白部分为空闲块。

图2.3 第一次分配后的内存结构

图2.4 第三次分配后的内存结构

2. 分配算法

       通过上面的论述，可以得到内存分配算法的流程图，如图2.5所示。首先根据分配要求检索空闲块索引查找到合适的空闲链表，如果存在这样的空闲链表则说明此空闲链表中的所有空闲内存块都能满足申请要求。然后选择此空闲链表的第一块进行分配，根据此块的大小和申请大小判断是否需要执行分裂。最后根据分配的结果更新空闲链表和空闲块索引。

                                      

图2.5 内存分配算法流程图

3. 回收策略

假设应用程序需要释放已占有的内存，并且当前的内存结构布局如图2.4所示，其释放顺序为2^n-1kB， (2^n-1-2¹)kB，2ⁿkB。在释放大小为2^n-1k的块后，由于该块相邻的两个块都不是空闲块，所以不需要与相邻的块合并，其内存结构布局如图2.6所示。

当释放大小为(2^n-1-2¹)kB的块后，由于相邻的块都为空闲块，所以这三个块会合并，这时的内存结构布局如图2.3所示。释放大小为2ⁿkB块后，由于与其相邻的块都为空闲块，所以这次需要将两个块合并成一个块。三次释放操作以后将会得到初始内存结构布局。

图2.6第一次释放后的内存结构

4. 内存回收算法

       图2.7描述了内存回收算法的流程图，首先释放块检查与其相邻的块是否为空闲，只要相邻块是空闲块则释放块与相邻块合并为一个独立的空闲块，如果相邻块都不是空闲的，则将释放块直接加到相应的空闲链表中。最后更新空闲块链表和空闲块索引。

                         

 

图2.7 内存回收算法流程图

                                     To be continued……

------ anmnmnly     

------ 2008.04.08