CN1171152C - 一种实时系统中内存快速分配与释放的方法 - Google Patents

Abstract

本发明的一种实时系统中内存快速分配与释放的方法，申请内存分配时，根据输入的申请内存块大小size，得到内存控制单元序号n＝二进制数(size-1)的有效位数，该单元n对应内存区内的内存块大小bsize＝2ⁿ字节，由此快速定位到所需内存块；释放内存块时，根据内存块指针参数，利用该内存块头部预留指针空间中的内存控制单元的指向，得到该内存块所属内存区，快速释放该内存块。本发明方法用于指令以流水线作业的芯片，效率提高尤其显著。

Description

一种实时系统中内存快速分配与释放的方法

本发明涉及一种计算机内存管理技术，具体涉及一种在实时系统中快速实现内存管理的方法。

实时系统要求在限定的时间内执行完所规定的任务。目前，这种系统有着广泛的应用，如过程控制、数据采集、通信、多媒体信息处理等对时间比较敏感的场合。衡量一个实时系统实时性强弱的指标是该实时系统执行完规定的功能和响应外部异步事件所需时间的长短，所以一些优秀的实时系统都力图在任务上下文切换、系统调用、中断响应、内存管理等系统开销上做到最小。内存管理是实时系统的最重要的组成部分之一，设计实时系统的其中一个重要目标就是提高内存管理的效率，进而提高CPU的利用率。

一种通用的内存分配策略是可变长内存分配策略，但使用这种方法的实时系统在经过较长时间运行后，会产生大量的内存碎片，导致内存的大量浪费，甚至导致系统崩溃；这种方法的还有一个缺点是内存申请与释放的极其不确定性，所以在实际的实时系统中一般较少使用这一方法。

实际上，在实时系统中通常采用一种固定长度的内存分配策略。这一方法是先把内存分成几个区，然后每个区又分成大小相同的内存块，不同的区之间的内存块大小是不相等的，一般内存块的大小为2的幂次方，即16字节、32字节、64字节…1024字节…等等；每次申请大小为size的内存块时，总是先扫描各个区，找到不小于size的最小内存块所在的区，然后从这一区中取出一内存块返回，如果该区内的内存块已经用完，就返回空，而不是从其它区中取更大的内存块返回，每次释放内存时，根据被释放内存块的指针，再次扫描各个区，寻找该内存块属于哪个区，然后再找到了这个区后，就把内存块归还到该区中。这种方法不再导致内存碎片，但因为每次申请与释放内存都需要扫描各个内存区，这种扫描在实现上都由许多比较及跳转指令组成，而内存管理模块是实时系统中使用频度最高的模块之一，内存管理模块的效率将严重影响到整个实时系统的效率，这样就导致了CPU资源的大量浪费；另外，这一方法的内存管理开销还与实时系统中内存区的数量相关，特别是当一个实时系统的内存被分成由4字节到64K字节的内存块所组成的许多不同的内存区时，它将严重影响到内存管理模块以至整个实时系统的效率。

本发明的目的就在于提供了一种解决上述内存管理方法中问题的快速内存管理方法，该方法显著提高了实时系统中内存申请与释放的速度，它可以在每次申请与释放内存块时对该内存块的大小进行快速定位，而不需要每次扫描若干个内存区，进行若干次比较后得出结果，从而极大地提高了实时系统中内存管理的速度和效率。

本发明提供的一种实时系统中内存快速分配与释放的方法，其技术方案是这样实现的：

一种实时系统所应用的内存分配的方法，该实时系统的内存区，均对应一内存控制单元，该单元记录内存块的大小、指针及数量，其中，令该所有的内存控制单元组成一数组，该每一单元的地址以索引号n进行标号；以及设定该单元所对应的该内存块大小为2ⁿ字节，该方法的特征在于，

a)在该内存块的头部预留一个指针空间，指向该内存控制单元的地址；

b)将所需内存块的大小的参数输入实时系统；

c)判断该参数的合法性；

d)如果合法，根据该参数寻找该地址的索引号n，确定所对应的该控制单元。

所述的内存分配方法，其中，所述步骤d)包括

e)将该单元所对应的字节数减去1后转换成二进制数；

f)将该二进制数的位数定义为地址n。

所述的内存分配方法，其中，还包括下列步骤

g)在该所找寻的控制单元中取出一空闲的内存块。

所述的内存分配方法，其中，所述控制单元的地址最大为16。

一种实时系统所应用的内存释放的方法，该实时系统的内存区均对应一内存控制单元，该单元记录其中内存块的大小、指针及数量，其中，该所有的内存控制单元组成一数组，该每一单元的地址以索引号n进行标号；以及设定该单元所对应的该内存块大小为2ⁿ字节，该方法的特征在于，

h)对该内存块进行初始化；

i)在该每一内存块的头部预留一个指针空间。

所述的内存释放方法，其中，在执行步骤i)之后还包括下列处理

j)在该预留的指针空间内，存放指向该内存块所对应的内存控

制单元的指针。

所述的内存释放方法，其中，还包括

k)根据该预留空间内存放的固定偏移值，判断该内存块指针的合法性；

l)如果合法，将该内存块指针所指的内存块归还到依据该预留空间所存放的数值所指向的该内存控制单元中。

由于本发明提供的内存管理方法在内存管理模块上省去了大量的比较及跳转指令，在各种实时系统中，不仅可以减小内存管理的开销、提高系统在内存申请和释放时的效率，而且内存管理开销与内存区的数量配置无关，因此该实时系统不会因为具体应用程序及负荷的变化而降低效率，从而提高了系统高效率工作的稳定性。本发明提供的方法对于指令以流水线作业的CPU来说，其性能的提高尤为明显。

下面结合附图，通过对本发明较佳实施例详细描述，将使本发明的上述目的和其他优点显而易见，其中，

图1是实时系统中内存管理模块的数据结构示意图；

图2是本发明的内存快速分配方法的流程图；

图3是本发明的内存快速释放方法的流程图。

图1描述了实时系统中内存管理模块的数据结构示意图。101是内存控制单元组成的数组，每一单元记录了它所对应的内存区内的内存块的大小、数量、空闲内存块的指针等信息。控制单元索引号n(即控制单元数组的单元序号)与该单元对应的内在区内的内存块大小bsize存在以下关系：bsize＝2ⁿ字节；每一内存块在其头部还预留一个指针空间，如102、103等所示；该指针指向了其所对应的内存控制单元的地址，如内存块102预留空间中的指针指向了控制单元0，而内存块103预留空间中的指针指向了控制单元1，依次类推，如图1所示。

图2描述了利用本发明方法设计的内存快速分配流程图。从步骤201中开始，内存申请服务程序被调用。在步骤202中把传入的参数，即需申请的内存大小，赋值给size。在步骤203中判断size的合法性，如果size是一个非法值就返回空，到步骤206结束；如果size是一个合法的值就转到步骤204中，在步骤204中根据size的值算出内存控制单元的索引号n，依照关系n＝二进制数(size-1)的有效位数，该对应关系可由现有CPU指令系统中的一条相应指令来完成。在步骤205中可以根据上一步得到的单元号n定位到控制单元，如果该控制单元所对应的内存块不为空，则取出一空闲内存块返回，否则就返回空，进入到步骤206结束，从而能快速定位到实际取得的内存块的位置。

图3描述了利用本发明方法设计的内存快速释放流程图。从步骤301中开始，内存释放服务程序被调用。在步骤302中把传入的参数，即将被释放的内存块指针赋值给p1。在步骤303中根据内存块中预留空间的固定偏移值得到反向指向内存控制单元的指针p2。在步骤304中可根据内存控制单元的信息判断内存块指针p1的合法性，如果p1是一个非法值就跳转到步骤306结束；如果p1是一个合法的值就转到步骤305中，在步骤305中把p1所指向的内存块归还到p2所指向的内存控制单元中后，到步骤306中结束。

值得说明的是，利用本发明的方法，可以在各种平台上很容易地开发出内存管理模块，而使用本发明方法设计的内存管理模块流程基本一致，只是在具体实现上，可能用到的指令形式不同；如果高级语言的编译器无法生成该指令，就需要在高级语言中嵌入汇编语言实现。

例如，用本发明的方法在Motorola PowerPC860(以下简称MPC860)这种RISC芯片上实现的内存管理模块，其效率的提高就比较明显。因为RISC芯片的指令以流水线作业，而本发明方法中大大减少了比较及跳转指令。在MPC860上，需要计算一个数的二进制位数时，要用到指令cntlzw rA rS，该指令首先取出寄存器rS中的前导0的个数，并赋值给寄存器rA，然后再用32减去rA的值就得到了寄存器rS中原数的二进制位数。在50MHz的MPC860上的试验表明，现有技术中对内存申请与释放的平均操作时间为12us，而使用本方法的时间为2us。与以往的内存分配方法相比，本发明的内存分配与释放的速度有显著提高，这种效率的提高能最终导致整个实时系统的性能的提高。

应当理解的是，本领域内的普通技术人员在不脱离本发明的前提下，可以做出各种适当的改变或替换，但这些改变或替换都应属于本发明的保护范围。

Claims (7)

1、一种实时系统所应用的内存分配的方法，该实时系统的内存区，均对应一内存控制单元，该单元记录内存块的大小、指针及数量，其中，令该所有的内存控制单元组成一数组，该每一单元的地址以索引号n进行标号；以及设定该单元所对应的该内存块大小为2ⁿ字节，该方法的特征在于：

a)在该内存块的头部预留一个指针空间，指向该内存控制单元的地址；

b)将所需内存块的大小的参数输入实时系统；

c)判断该参数的合法性；

d)如果合法，根据该参数寻找该地址的索引号n，确定所对应的该控制单元。

2、根据权利要求1所述的方法，其特征在于：所述步骤d)包括

e)将该单元所对应的字节数减去1后转换成二进制数；

f)将该二进制数的位数定义为地址n。

3、根据权利要求1所述的方法，其特征在于：还包括下列步骤

g)在该所找寻的控制单元中取出一空闲的内存块。

4、根据权利要求1所述的方法，其特征在于：所述控制单元的地址最大为16。

5、一种实时系统所应用的内存释放的方法，该实时系统的内存区均对应一内存控制单元，该单元记录其中内存块的大小、指针及数量，其中，该所有的内存控制单元组成一数组，该每一单元的地址以索引号n进行标号；以及设定该单元所对应的该内存块大小为2ⁿ字节，该方法的特征在于：

h)对该内存块进行初始化；

i)在该每一内存块的头部预留一个指针空间。

6、根据权利要求5所述的方法，其特征在于：在执行步骤i)之后还包括下列处理

j)在该预留的指针空间内，存放指向该内存块所对应的内存控制单元的指针。

7、根据权利要求5或6所述的方法，其特征在于：还包括

k)根据该预留空间内存放的固定偏移值，判断该内存块指针的合法性；

l)如果合法，将该内存块指针所指的内存块归还到依据该预留空间所存放的数值所指向的该内存控制单元中。

Images