原创 设计自己的嵌入式操作系统内核之三 ------ 定长存储块管理

1、概述
?　　这一篇主要讨论eos中作为系统内存管理者的定长存储块管理机制实现。嵌入式的OS通常运行于内存受限的系统上，而不像windows这样的运行于大内存的系统。在Atmega32上，片内仅有2K的RAM,且无外部存储扩展接口，当然也就不可能具备像MMU这样复杂的存储管理硬件了。我们要实现的存储管理机制要足够的简单，能够满足最基本的需要。针对特别的应用，系统运行时所需要的内存空间大小通常是可以预估的。复杂的存储分配方案显然来说是不必要的。当然，使用的机制要能充分提高2K　RAM的空间利用率。

除了编译器所做的存储管理(全局／局部／静态变量等)外，我所了解到的系统存储分配方案有两种：动态存储分配方式和基于定长存储块的管理。前者实现的机制要复杂此，能够根据需要分配存储空间，但可能会产生外部碎片，同时为了实现这些机制，分配的内存块还需要保存存储块的信息以便管理，一个实例为LWIP协议栈的动态存储管理；而后者是在已知应用的存储空间需求的情况下，将大的内存块化分外若干大小相同的块，无论是分配还是回收，总是按块分配，这样不会产生外部碎片，且实现简单，操作快速，典型的代码为UC/OS的存储管理。

在eos中所有的存储管理方案参考了uc/os的实现，同时作出了相应的改动，以适应如下的要求：
1、系统内部所有的控制块都由存储管理者进行分配与回收；
2、存储空间利用率要高，实现要简单、快速；
3、在存储管理者初始化、分配、回收过程中，尽可能的提供必要的检查，以减小应用存储访问越界的可能。

以下，先总体介绍方案的实现，再依次介绍数据结构定义、相应操作及存储检查机制。

2、定长存储管理机制概述


上图所示为某一时刻eos运行时存储管理器的运行状态图。系统中有两大存储分配区：sys_mem, usr_mem。在存储管理器初始化时，对每一分配区，查找分配表，找出要分配的块大小及数量后，依次从存储块中取相应大小、数量的块，组织成单链表，链表的首指针由上图左边的数组进行维护。每一链表中的块大小相同，且块的头部预留出小块空间用于存储链接指针。当进行块分配时，从链表中取出块，并将块除头部以外的区域分配出去，头部保存了指向原链表中维护链表首指针的数组项，用于块的回收.。(见上图已分配块)

系统控制块链由task_struct控制块链，信号量结构控制块链等内核控制块链构成。分配时由mpool_get( type )进行分配，type指明块的类型，同时也是数组的索引，能够直接定位控制块链进行分配。而应用控制块分配时由mpool_malloc( size )决定.这种方式，需要在应用块链中查找大小适合size的链，因为要查找，相对要慢些；但可以用mpool_get()分配，type的值需要由应用自行进行计算。　二者的存储回收都由mpool_free( mem )实现，前面提到，分配出去的块头部保存了链指针，可以使用该指针进行回收。上述的结构实际构成多个“链式栈”，操作的单位为存储块，操作的方式从表头插入与删除结点。

本质上来说，上图所示的结构概括的说为一多级可用空间表结构。这种分配方式与uc/os的一样。这里只是稍微有所改动。

3、定长存储管理机制的具体实现
　　
一)、数据类型定义
首先看内存池类型，对应于上图中左边数组的数据元素类型：




该结构维护每个块链表的信息，链表的首结点指针存储于.blocks域.

对于每个内存块的头部，有如下数据类型定义：
? ?



因为块的头部在存储块未分配出去时要存储下一存储块的首址(即link域)，在存储分配出去后，又要保存所在的 struct _mpool_t 类型的数据项，因而使用了联合体。

另外，还定义了表结构，表中的数据项类型为：
? ?

该类型用于保存每种内存块的大小及数量，在存储管理器初始化时，查找该表，将相应的大的内存区域划组织成多个链表。详见,mpool_init()初始化说明。

2）、相关的操作
定长存储块管理器初始化：
初始化操作由mpool_init()完成，完成包括系统存储块和应用存储块的初始化。初始化流程如下伪代码：

初始化系统存储块块链:
blocks 指向sys_mem起始地址
i = 0

循环：直至 i < 系统块类型数( MPOOL_SYS_TBL_SIZE )
size = sys_tbl.size ( 取系统块类型大小)
nr = sys_tbl.nr (取系统块类型数量 )

取 j = 1
循环：直至 j < nr ( 第i种类型系统块的数量 )
检查blocks 是否越界
越界，跳出当前循环

从blocks指向的存储块首址取size大小存储块链接至
存储块链 mem_pool.blocks链表中
调整blocks指向下一块内存块

检查blocks 是否越界
越界，跳出当前循环

循环退出：
保存存储块链信息。
mem_pool.nr / avail (链表内块的数量及可用数) = j - 1

初始化应用存储块链：
流程结构同上
依据存储块类型进行存储块分配：
分配操作由mpool_get( type )完成。由于type等同于相应的块链类在mem_pool[]数组中的索引。

操作的伪代码：
检查mem_pool[ type ].blocks链表是否为空
是，退出
否，从单链表中取出存储块block
向存储块blocks头部存储mem_pool + type
更新mem_pool[type]信息

简单的说，上述操作仅是完成从链表中删除头结点的操作。

依据存储块大小进行分配：
分配操作由mem_malloc( size )完成。并且只被应用调用。分配的操作实际是在前图中的应用块链中，逐次查找块大小大于等待size的块链，再从块链中进行分配。其实际比较简单，和mpool_get()类似，这里不作介绍。

存储块的回收：
对于任意分配出的存储块，都由mpool_free( mem )进行回收。
在分配出的存储块头部保存了原所在链表的mem_pool中某项的指针，回收时，将块插入原链表。

4、关于存储管理机制一些问题的思考
１、在实际系统运行时，出现过因为存储管理机制实现中的一些BUG导致应用存储访问越界的情况。有时会因为越界的访问而修改ＯＳ的关键数据导致整个系统的崩溃。另外，当为系统分配的堆栈不足时，也会因为堆栈溢出导致同样的情况。所以，系统初始化，分配与回收块中均加入一定的检查机制是有必要的。

2、从效果上来看，这种采用定长存储块分配的方式存储空间利用率是比较有效的。特别是在分配系统控制块(如task_struct块)时，操作简单、快速。对于仅有2K RAM的单片机而言，还是比较合适。但mpool_malloc( size )需要进行一定的查找，事实上，可以对存储块链进行一定的修改，使得分配操作需要的时间是可预知的。如下例：
　　　
设定应用存储块大小由 min_size开始，增量为inc_size, 最大的类型块大小为max_size，这样当要分配size的大小块时，可由以下式子直接定位所在的链表：
index = ( size - min_size ) / size + 系统存储块类型数量
当然，实际分配的块大小总是会比要求的要大，产生一定的内部碎片，有些浪费。

3、实现的检查机制比较简单，除了入口参数的检查，还包括越界的检查。这里的越界只检查分配的块是否超过内存分配边界，而不能检查是否重复释放块、应用使用块时是否访问越界。提供的接口要传递的参数很少，这样就减小了出现错误的可能。　Atmega32内部的结构决定了无法再实现更复杂的检查机制。
4、在我看来，存储管理非常有意思。初始OS面对的只是一大块的内存区域。除了编译器进行一定的存储管理外，操作系统需要将内存进行有效的组织，通过附加一定的结构进行管理。有非常多的算法，看起来也比较复杂、灵活，便可为应用提供一定的接口，简单化编程的难度。存储管理，是对内存及内存操作的一种抽像。

6、源码与资料
　<<数据结构与算法>>　严蔚敏、吴伟民　其中有存储管理的章节，写的比较经典，推荐！

涉及源码文件：
mpool.c / mm.h ------------ 定长存储块管理实现